diff options
Diffstat (limited to 'src')
-rw-r--r-- | src/list.c | 84 | ||||
-rw-r--r-- | src/symtab.c | 113 |
2 files changed, 150 insertions, 47 deletions
@@ -86,6 +86,46 @@ grecs_list_remove_entry(struct grecs_list *lp, struct grecs_list_entry *ent) | |||
86 | lp->count--; | 86 | lp->count--; |
87 | } | 87 | } |
88 | 88 | ||
89 | void * | ||
90 | grecs_list_remove_tail(struct grecs_list *lp) | ||
91 | { | ||
92 | void *data; | ||
93 | struct grecs_list_entry *ep; | ||
94 | |||
95 | if (!lp || !lp->tail) | ||
96 | return NULL; | ||
97 | ep = lp->tail; | ||
98 | data = lp->tail->data; | ||
99 | grecs_list_remove_entry(lp, ep); | ||
100 | return data; | ||
101 | } | ||
102 | |||
103 | static int | ||
104 | _ptrcmp(const void *a, const void *b) | ||
105 | { | ||
106 | return a != b; | ||
107 | } | ||
108 | |||
109 | int | ||
110 | grecs_list_remove(struct grecs_list *lp, void *data) | ||
111 | { | ||
112 | struct grecs_list_entry *ep; | ||
113 | int (*cmp)(const void *, const void *); | ||
114 | |||
115 | |||
116 | if (!lp) | ||
117 | return 1; | ||
118 | |||
119 | cmp = lp->cmp ? lp->cmp : _ptrcmp; | ||
120 | for (ep = lp->head; ep; ep = ep->next) { | ||
121 | if (cmp(ep->data, data) == 0) { | ||
122 | grecs_list_remove_entry(lp, ep); | ||
123 | return 0; | ||
124 | } | ||
125 | } | ||
126 | return 1; | ||
127 | } | ||
128 | |||
89 | void | 129 | void |
90 | grecs_list_append(struct grecs_list *lp, void *val) | 130 | grecs_list_append(struct grecs_list *lp, void *val) |
91 | { | 131 | { |
@@ -123,7 +163,11 @@ void * | |||
123 | grecs_list_pop(struct grecs_list *lp) | 163 | grecs_list_pop(struct grecs_list *lp) |
124 | { | 164 | { |
125 | void *data; | 165 | void *data; |
126 | struct grecs_list_entry *ep = lp->head; | 166 | struct grecs_list_entry *ep; |
167 | |||
168 | if (!lp) | ||
169 | return NULL; | ||
170 | ep = lp->head; | ||
127 | if (ep) { | 171 | if (ep) { |
128 | data = ep->data; | 172 | data = ep->data; |
129 | grecs_list_remove_entry(lp, ep); | 173 | grecs_list_remove_entry(lp, ep); |
@@ -132,25 +176,14 @@ grecs_list_pop(struct grecs_list *lp) | |||
132 | return data; | 176 | return data; |
133 | } | 177 | } |
134 | 178 | ||
135 | void * | ||
136 | grecs_list_remove_tail(struct grecs_list *lp) | ||
137 | { | ||
138 | void *data; | ||
139 | struct grecs_list_entry *ep; | ||
140 | |||
141 | if (!lp->tail) | ||
142 | return NULL; | ||
143 | ep = lp->tail; | ||
144 | data = lp->tail->data; | ||
145 | grecs_list_remove_entry(lp, ep); | ||
146 | return data; | ||
147 | } | ||
148 | |||
149 | void | 179 | void |
150 | grecs_list_clear(struct grecs_list *lp) | 180 | grecs_list_clear(struct grecs_list *lp) |
151 | { | 181 | { |
152 | struct grecs_list_entry *ep = lp->head; | 182 | struct grecs_list_entry *ep; |
153 | 183 | ||
184 | if (!lp) | ||
185 | return; | ||
186 | ep = lp->head; | ||
154 | while (ep) { | 187 | while (ep) { |
155 | struct grecs_list_entry *next = ep->next; | 188 | struct grecs_list_entry *next = ep->next; |
156 | if (lp->free_entry) | 189 | if (lp->free_entry) |
@@ -171,17 +204,16 @@ grecs_list_free(struct grecs_list *lp) | |||
171 | } | 204 | } |
172 | } | 205 | } |
173 | 206 | ||
174 | static int | ||
175 | _ptrcmp(const void *a, const void *b) | ||
176 | { | ||
177 | return a != b; | ||
178 | } | ||
179 | |||
180 | void * | 207 | void * |
181 | grecs_list_locate(struct grecs_list *lp, void *data) | 208 | grecs_list_locate(struct grecs_list *lp, void *data) |
182 | { | 209 | { |
183 | struct grecs_list_entry *ep; | 210 | struct grecs_list_entry *ep; |
184 | int (*cmp)(const void *, const void *) = lp->cmp ? lp->cmp : _ptrcmp; | 211 | int (*cmp)(const void *, const void *); |
212 | |||
213 | if (!lp) | ||
214 | return NULL; | ||
215 | |||
216 | cmp = lp->cmp ? lp->cmp : _ptrcmp; | ||
185 | 217 | ||
186 | for (ep = lp->head; ep; ep = ep->next) { | 218 | for (ep = lp->head; ep; ep = ep->next) { |
187 | if (cmp(ep->data, data) == 0) | 219 | if (cmp(ep->data, data) == 0) |
@@ -194,7 +226,9 @@ void * | |||
194 | grecs_list_index(struct grecs_list *lp, size_t idx) | 226 | grecs_list_index(struct grecs_list *lp, size_t idx) |
195 | { | 227 | { |
196 | struct grecs_list_entry *ep; | 228 | struct grecs_list_entry *ep; |
197 | 229 | ||
230 | if (!lp) | ||
231 | return NULL; | ||
198 | for (ep = lp->head; ep && idx; ep = ep->next, idx--) | 232 | for (ep = lp->head; ep && idx; ep = ep->next, idx--) |
199 | ; | 233 | ; |
200 | return ep ? ep->data : NULL; | 234 | return ep ? ep->data : NULL; |
@@ -219,7 +253,7 @@ grecs_list_compare(struct grecs_list *a, struct grecs_list *b) | |||
219 | cmp = a->cmp ? a->cmp : _ptrcmp; | 253 | cmp = a->cmp ? a->cmp : _ptrcmp; |
220 | 254 | ||
221 | for (ap = a->head, bp = b->head; ap; ap = ap->next, bp = bp->next) | 255 | for (ap = a->head, bp = b->head; ap; ap = ap->next, bp = bp->next) |
222 | if (cmp (ap->data, bp->data)) | 256 | if (cmp(ap->data, bp->data)) |
223 | return 1; | 257 | return 1; |
224 | 258 | ||
225 | return 0; | 259 | return 0; |
diff --git a/src/symtab.c b/src/symtab.c index 540ea0f..3647a81 100644 --- a/src/symtab.c +++ b/src/symtab.c | |||
@@ -33,16 +33,36 @@ static unsigned int hash_size[] = { | |||
33 | /* |max_rehash| keeps the number of entries in |hash_size| table. */ | 33 | /* |max_rehash| keeps the number of entries in |hash_size| table. */ |
34 | static unsigned int max_rehash = sizeof(hash_size) / sizeof(hash_size[0]); | 34 | static unsigned int max_rehash = sizeof(hash_size) / sizeof(hash_size[0]); |
35 | 35 | ||
36 | enum symtab_defer_type { | ||
37 | defer_add, | ||
38 | defer_del | ||
39 | }; | ||
40 | |||
36 | struct grecs_symtab { | 41 | struct grecs_symtab { |
37 | int flags; | 42 | int flags; |
38 | unsigned int hash_num; /* Index to hash_size table */ | 43 | unsigned int hash_num; /* Index to hash_size table */ |
39 | size_t elsize; /* Size of an element */ | 44 | size_t elsize; /* Size of an element */ |
40 | struct grecs_syment **tab; | 45 | size_t elcount; /* Number of elements in use */ |
41 | unsigned (*hash_fun)(void *, unsigned long hash_num); | 46 | struct grecs_syment **tab; /* Table of element pointers */ |
47 | |||
48 | /* Functions that can be overridden when creating the symtab: */ | ||
49 | unsigned (*hash_fun)(void *, unsigned long); | ||
42 | int (*cmp_fun)(const void *, const void *); | 50 | int (*cmp_fun)(const void *, const void *); |
43 | int (*copy_fun)(void *, void *); | 51 | int (*copy_fun)(void *, void *); |
44 | void *(*syment_alloc_fun)(size_t size); | 52 | void *(*syment_alloc_fun)(size_t); |
45 | void (*syment_free_fun) (void *); | 53 | void (*syment_free_fun) (void *); |
54 | |||
55 | /* Support for deferred operations. When an insertion or deletion | ||
56 | is requested while the symtab is being iterated over, this operation | ||
57 | is deferred until the iteration is finished. */ | ||
58 | |||
59 | /* Iteration level. Gets increased upon entry to grecs_symtab_foreach, | ||
60 | and decreased right before leaving it. */ | ||
61 | unsigned int itr_level; | ||
62 | /* Two deferment lists keep track of the deferred additions and | ||
63 | removals: | ||
64 | */ | ||
65 | grecs_list_ptr_t defer_list[2]; | ||
46 | }; | 66 | }; |
47 | 67 | ||
48 | static void | 68 | static void |
@@ -72,7 +92,17 @@ syment_alloc(struct grecs_symtab *st, void *key) | |||
72 | } | 92 | } |
73 | return ent; | 93 | return ent; |
74 | } | 94 | } |
75 | 95 | ||
96 | static void | ||
97 | symtab_defer_op(struct grecs_symtab *st, enum symtab_defer_type type, | ||
98 | struct grecs_syment *ent) | ||
99 | { | ||
100 | if (!st->defer_list[type]) { | ||
101 | st->defer_list[type] = grecs_list_create(); | ||
102 | st->defer_list[type]->cmp = st->cmp_fun; | ||
103 | } | ||
104 | grecs_list_append(st->defer_list[type], ent); | ||
105 | } | ||
76 | 106 | ||
77 | unsigned | 107 | unsigned |
78 | grecs_hash_string(const char *name, unsigned long hashsize) | 108 | grecs_hash_string(const char *name, unsigned long hashsize) |
@@ -101,8 +131,8 @@ grecs_hash_string_ci(const char *name, unsigned long hashsize) | |||
101 | static unsigned | 131 | static unsigned |
102 | def_hash(void *data, unsigned long hashsize) | 132 | def_hash(void *data, unsigned long hashsize) |
103 | { | 133 | { |
104 | struct grecs_syment *sym = data; | 134 | struct grecs_syment *sym = data; |
105 | return grecs_hash_string(sym->name, hashsize); | 135 | return grecs_hash_string(sym->name, hashsize); |
106 | } | 136 | } |
107 | 137 | ||
108 | static int | 138 | static int |
@@ -218,6 +248,11 @@ grecs_symtab_remove(struct grecs_symtab *st, void *elt) | |||
218 | unsigned int pos, i, j, r; | 248 | unsigned int pos, i, j, r; |
219 | struct grecs_syment *entry; | 249 | struct grecs_syment *entry; |
220 | 250 | ||
251 | if (st->itr_level) { | ||
252 | if (grecs_list_remove(st->defer_list[defer_add], elt) == 0) | ||
253 | return 0; | ||
254 | } | ||
255 | |||
221 | pos = st->hash_fun(elt, hash_size[st->hash_num]); | 256 | pos = st->hash_fun(elt, hash_size[st->hash_num]); |
222 | for (i = pos; (entry = st->tab[i]);) { | 257 | for (i = pos; (entry = st->tab[i]);) { |
223 | if (st->cmp_fun(entry, elt) == 0) | 258 | if (st->cmp_fun(entry, elt) == 0) |
@@ -231,7 +266,14 @@ grecs_symtab_remove(struct grecs_symtab *st, void *elt) | |||
231 | if (!entry) | 266 | if (!entry) |
232 | return ENOENT; | 267 | return ENOENT; |
233 | 268 | ||
269 | if (st->itr_leve |