/
nodelist.c
96 lines (74 loc) · 2.6 KB
/
nodelist.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <stdlib.h>
#include "common.h"
#include "netconv.h"
/*****************************************************************************/
/* Allocate a nodelist element. To reduce memory fragmentation, nodelist_t */
/* elements are allocated in large contingents, and freed cells are kept in */
/* li_freelist. New allocation requests are served from li_freelist first. */
#define LI_ALLOC_STEP 1024 /* how many nodelist elements to grab at a time */
typedef struct contingent_t
{
nodelist_t *nodes;
struct contingent_t *next;
} contingent_t;
nodelist_t *li_freelist = NULL; /* pointer to freed nodelist elements */
contingent_t *li_contlist = NULL; /* pointer to allocated contingents */
int li_counter = 0; /* num of free elements in the latest contingent */
nodelist_t* nodelist_alloc ()
{
nodelist_t *tmp_nl;
contingent_t *tmp_co;
if ((tmp_nl = li_freelist))
{
li_freelist = tmp_nl->next;
return tmp_nl;
}
if (li_counter--) return li_contlist->nodes + li_counter;
tmp_co = MYmalloc(sizeof(contingent_t));
tmp_co->nodes = MYmalloc(LI_ALLOC_STEP * sizeof(nodelist_t));
tmp_co->next = li_contlist;
li_contlist = tmp_co;
li_counter = LI_ALLOC_STEP-1;
return li_contlist->nodes + li_counter;
}
/*****************************************************************************/
/* add a node to the front of a list */
nodelist_t* nodelist_push (nodelist_t **list, void *node)
{
nodelist_t *newlist = nodelist_alloc();
newlist->node = node;
newlist->next = *list;
return *list = newlist;
}
/*****************************************************************************/
/* add a place to a list; sort by pointer in ascending order */
nodelist_t* nodelist_insert (nodelist_t **list, void *node)
{
while (*list && node < (*list)->node)
list = &((*list)->next);
if (*list && (*list)->node == node) return *list;
return nodelist_push(list,node);
}
/*****************************************************************************/
/* release a nodelist; move its cells to the "free" list */
void nodelist_delete (nodelist_t *list)
{
nodelist_t *tmp;
while (list)
{
tmp = list;
list = list->next;
tmp->next = li_freelist;
li_freelist = tmp;
}
}
/*****************************************************************************/
/* compare two lists; return 0 if equal, -1 if list1 < list2, 1 otherwise */
char nodelist_compare (nodelist_t *list1, nodelist_t *list2)
{
while (list1 && list2 && list1->node == list2->node)
list1 = list1->next, list2 = list2->next;
if (!list1 && !list2) return 0;
if (!list1 || (list2 && list1->node < list2->node)) return -1;
return 1;
}