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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
|
/* loptr.c
* Simple list-of-pointers handling library; this library is intended to
* be directly included in the source file that would use it, without prior
* or separated compilation. We use a hash table not just because we expect
* to be likely to have many records in the list, but also hoping that in
* many cases this will make it faster to find out whether or not a pointer
* is already present.
*
* Even though this library is useless, it's however released under the LGPL.
*
* $Id: loptr.c 340 2008-02-21 00:39:34Z Franz $
* (c) 2008 - Francesco Garosi/JKS
*/
/* the kind of integers we will be dealing with */
#define LOPTR_INT unsigned long
#define LOPTR_BOOL int
#define LOPTR_TRUE 1
#define LOPTR_FALSE 0
/* the following can be helpful when allocating objects */
#ifdef USE_PYTHON_MEMMGR
#define LOPTR_NEW(x) PyMem_New(x, 1)
#define LOPTR_DELETE(x) PyMem_Del(x)
#else
#define LOPTR_NEW(x) ((x *)malloc(sizeof(x)))
#define LOPTR_DELETE(x) free(x)
#endif
/* these functions are intended to be very fast and inlined */
#ifdef F_INLINE
#define LOPTR_INLINE F_INLINE
#else
#define LOPTR_INLINE
#endif /* F_INLINE */
/* size of hash table for sublists of pointers, should be a prime */
#ifndef STRAY_FACTS_TABLE_SIZE
#define STRAY_FACTS_TABLE_SIZE 211
#endif
#define LOPTR_HASH_TABLE_SIZE ((LOPTR_INT)STRAY_FACTS_TABLE_SIZE)
#define LOPTR_HASH(_x) (((LOPTR_INT)_x) % LOPTR_HASH_TABLE_SIZE)
/* decide whether or not to use register variables and pointers */
#ifdef USE_REGISTER_VARIABLES
#define LOPTR_REGISTER register
#else
#define LOPTR_REGISTER
#endif
/* will constitute the sublists of pointers */
typedef struct __struct_LOPTR_ITEM {
void *elem;
struct __struct_LOPTR_ITEM *next;
} LOPTR_ITEM;
/* type of function accepted by LOPTR_apply */
typedef LOPTR_BOOL(*LOPTR_FUNC)(void *);
/* give a standardized way to create a hash table */
#define LOPTR_HASH_TABLE(name) LOPTR_ITEM *name[LOPTR_HASH_TABLE_SIZE]
#define INIT_LOPTR_HASH_TABLE(name) \
memset(name, 0, sizeof(LOPTR_ITEM *) * (LOPTR_HASH_TABLE_SIZE))
#define COPY_LOPTR_HASH_TABLE(dst, src) \
memcpy((dst), (src), sizeof(LOPTR_ITEM *) * (LOPTR_HASH_TABLE_SIZE))
/* functions to transparently manage the list */
/* find an element */
static LOPTR_INLINE LOPTR_ITEM *LOPTR_find(LOPTR_ITEM **t, void *elem) {
LOPTR_REGISTER LOPTR_ITEM *p = t[LOPTR_HASH(elem)];
while(p) {
if(p->elem == elem)
return p;
else
p = p->next;
}
return NULL;
}
/* find the last item in the hash table for element */
static LOPTR_INLINE LOPTR_ITEM *LOPTR_lastitem(LOPTR_ITEM **t, void *elem) {
LOPTR_REGISTER LOPTR_ITEM *p = t[LOPTR_HASH(elem)];
if(p) {
while(p->next != NULL)
p = p->next;
return p;
} else
return NULL;
}
/* append an element in the hash table */
static LOPTR_INLINE LOPTR_BOOL LOPTR_append(LOPTR_ITEM **t, void *elem) {
LOPTR_ITEM *p = NULL, *q = NULL;
if(LOPTR_find(t, elem))
return LOPTR_FALSE;
else {
p = LOPTR_NEW(LOPTR_ITEM);
p->elem = elem;
p->next = NULL;
q = LOPTR_lastitem(t, elem);
if(q)
q->next = p;
else
t[LOPTR_HASH(elem)] = p;
return LOPTR_TRUE;
}
}
/* remove an element from the hash table */
static LOPTR_INLINE LOPTR_BOOL LOPTR_remove(LOPTR_ITEM **t, void *elem) {
int h = LOPTR_HASH(elem);
LOPTR_REGISTER LOPTR_ITEM *p = t[h];
LOPTR_ITEM *q = NULL;
if(p) {
if(p->elem == elem) {
t[h] = p->next; /* could be NULL */
LOPTR_DELETE(p);
return LOPTR_TRUE;
} else {
while(p) {
q = p;
p = p->next;
if(p->elem == elem) {
q->next = p->next; /* could be NULL either */
LOPTR_DELETE(p);
return LOPTR_TRUE;
}
}
}
}
return LOPTR_FALSE;
}
/* apply a bool-returning function to list elements ignoring result */
static LOPTR_INLINE void LOPTR_apply(LOPTR_ITEM **t, LOPTR_FUNC f) {
int i = 0;
LOPTR_REGISTER LOPTR_ITEM *p = NULL;
for(i = 0; i < LOPTR_HASH_TABLE_SIZE; i++) {
p = t[i];
while(p) {
f(p->elem);
p = p->next;
}
}
}
/* apply a bool-returning function to list elements returning failing result */
static LOPTR_INLINE void *LOPTR_test_apply(LOPTR_ITEM **t, LOPTR_FUNC f) {
LOPTR_REGISTER int i = 0;
LOPTR_REGISTER LOPTR_ITEM *p = NULL;
for(i = 0; i < LOPTR_HASH_TABLE_SIZE; i++) {
p = t[i];
while(p) {
if(!f(p->elem))
return p->elem;
p = p->next;
}
}
return NULL;
}
/* reset a hash table (only leave the array) removing all possible lists */
static LOPTR_INLINE void LOPTR_reset_hash_table(LOPTR_ITEM **t) {
LOPTR_REGISTER int i = 0;
LOPTR_REGISTER LOPTR_ITEM *p = NULL;
LOPTR_ITEM *q = NULL;
for(i = 0; i < LOPTR_HASH_TABLE_SIZE; i++) {
p = t[i];
while(p) {
q = p;
p = p->next;
LOPTR_DELETE(q);
}
t[i] = NULL;
}
}
/* end. */
|
