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 | }
|
---|