[418] | 1 | /*
|
---|
| 2 | * $Source: /tmp_mnt/n/fs/grad1/jsp/src/jgraph/RCS/list.c,v $
|
---|
| 3 | * $Revision: 8.3 $
|
---|
| 4 | * $Date: 92/11/30 11:42:25 $
|
---|
| 5 | * $Author: jsp $
|
---|
| 6 | */
|
---|
| 7 |
|
---|
| 8 | #include <stdio.h> /* Basic includes and definitions */
|
---|
| 9 | #include "list.h"
|
---|
| 10 |
|
---|
| 11 | #define boolean int
|
---|
| 12 | #define TRUE 1
|
---|
| 13 | #define FALSE 0
|
---|
| 14 |
|
---|
| 15 |
|
---|
| 16 | /*---------------------------------------------------------------------*
|
---|
| 17 | * PROCEDURES FOR MANIPULATING DOUBLY LINKED LISTS
|
---|
| 18 | * Each list contains a sentinal node, so that
|
---|
| 19 | * the first item in list l is l->flink. If l is
|
---|
| 20 | * empty, then l->flink = l->blink = l.
|
---|
| 21 | * The sentinal contains extra information so that these operations
|
---|
| 22 | * can work on lists of any size and type.
|
---|
| 23 | * Memory management is done explicitly to avoid the slowness of
|
---|
| 24 | * malloc and free. The node size and the free list are contained
|
---|
| 25 | * in the sentinal node.
|
---|
| 26 | *---------------------------------------------------------------------*/
|
---|
| 27 |
|
---|
| 28 | typedef struct int_list { /* Information held in the sentinal node */
|
---|
| 29 | struct int_list *flink;
|
---|
| 30 | struct int_list *blink;
|
---|
| 31 | int size;
|
---|
| 32 | List free_list;
|
---|
| 33 | } *Int_list;
|
---|
| 34 |
|
---|
| 35 | insert(item, list) /* Inserts to the end of a list */
|
---|
| 36 | List item;
|
---|
| 37 | List list;
|
---|
| 38 | {
|
---|
| 39 | List last_node;
|
---|
| 40 |
|
---|
| 41 | last_node = list->blink;
|
---|
| 42 |
|
---|
| 43 | list->blink = item;
|
---|
| 44 | last_node->flink = item;
|
---|
| 45 | item->blink = last_node;
|
---|
| 46 | item->flink = list;
|
---|
| 47 | }
|
---|
| 48 |
|
---|
| 49 | delete_item(item) /* Deletes an arbitrary iterm */
|
---|
| 50 | List item;
|
---|
| 51 | {
|
---|
| 52 | item->flink->blink = item->blink;
|
---|
| 53 | item->blink->flink = item->flink;
|
---|
| 54 | }
|
---|
| 55 |
|
---|
| 56 | List make_list(size) /* Creates a new list */
|
---|
| 57 | int size;
|
---|
| 58 | {
|
---|
| 59 | Int_list l;
|
---|
| 60 |
|
---|
| 61 | l = (Int_list) malloc(sizeof(struct int_list));
|
---|
| 62 | l->flink = l;
|
---|
| 63 | l->blink = l;
|
---|
| 64 | l->size = size;
|
---|
| 65 | l->free_list = (List) malloc (sizeof(struct list));
|
---|
| 66 | l->free_list->flink = l->free_list;
|
---|
| 67 | return (List) l;
|
---|
| 68 | }
|
---|
| 69 |
|
---|
| 70 | List get_node(list) /* Allocates a node to be inserted into the list */
|
---|
| 71 | List list;
|
---|
| 72 | {
|
---|
| 73 | Int_list l;
|
---|
| 74 | List to_return;
|
---|
| 75 |
|
---|
| 76 | l = (Int_list) list;
|
---|
| 77 | if (l->free_list->flink == l->free_list) {
|
---|
| 78 | return (List) malloc(l->size);
|
---|
| 79 | } else {
|
---|
| 80 | to_return = l->free_list;
|
---|
| 81 | l->free_list = to_return->flink;
|
---|
| 82 | return to_return;
|
---|
| 83 | }
|
---|
| 84 | }
|
---|
| 85 |
|
---|
| 86 | free_node(node, list) /* Deallocates a node from the list */
|
---|
| 87 | List node;
|
---|
| 88 | List list;
|
---|
| 89 | {
|
---|
| 90 | Int_list l;
|
---|
| 91 |
|
---|
| 92 | l = (Int_list) list;
|
---|
| 93 | node->flink = l->free_list;
|
---|
| 94 | l->free_list = node;
|
---|
| 95 | }
|
---|