1 |
/* Macros to handle insertion, deletion, iteration, and searching for |
2 |
* linked lists and arrays. |
3 |
* |
4 |
* IRC Services is copyright (c) 1996-2009 Andrew Church. |
5 |
* E-mail: <achurch@achurch.org> |
6 |
* Parts written by Andrew Kempe and others. |
7 |
* This program is free but copyrighted software; see the file GPL.txt for |
8 |
* details. |
9 |
*/ |
10 |
|
11 |
#ifndef LIST_ARRAY_H |
12 |
#define LIST_ARRAY_H |
13 |
|
14 |
/*************************************************************************/ |
15 |
|
16 |
/* Comments on the efficiency of lists vs. arrays: |
17 |
* |
18 |
* Lists are simple to insert into and remove from, but searching can be |
19 |
* inefficient, as the list must be walked through each time. Arrays can |
20 |
* be searched quickly, particularly if the list is sorted (note that the |
21 |
* macros below do not support sorted arrays), but insertion and removal |
22 |
* are expensive, requiring data to be moved around in memory if the |
23 |
* element to be inserted or removed is not last in the array or if |
24 |
* reallocation of the array results in a different array pointer. Lists |
25 |
* also have the advantage that the list can be easily modified (items |
26 |
* inserted or deleted) within a FOREACH loop, while arrays require extra |
27 |
* logic to modify the counter variable after an insert or delete. |
28 |
* |
29 |
* As far as searching goes, arrays do not show a significant improvement |
30 |
* until the data set size reaches around 15 elements, at which point the |
31 |
* reduced number of memory accesses (and reduced cache pressure, |
32 |
* particularly with large data sets) gives arrays a clear advantage. The |
33 |
* following results were obtained from running the test program below on a |
34 |
* Celeron 1.7GHz system (compiled with gcc-4.1 -O3): |
35 |
* |
36 |
* | Time/search (ns) |
37 |
* Size | List | Array |
38 |
* -----+------------------- |
39 |
* 3 | 4.1 | 3.7 |
40 |
* 5 | 7.3 | 6.7 |
41 |
* 7 | 9.7 | 9.3 |
42 |
* 10 | 14.5 | 12.3 |
43 |
* 15 | 23.6 | 18.2 |
44 |
* 20 | 53.5 | 21.7 |
45 |
* 30 | 73.2 | 44.8 |
46 |
* 50 | 109 | 56.7 |
47 |
* 100 | 200 | 101 |
48 |
* 300 | 564 | 267 |
49 |
* 1000 | 4530 | 864 |
50 |
* 3000 | 13740 | 4440 |
51 |
* |
52 |
* Test program (outputs average time per trial): |
53 |
* |
54 |
#include <stdio.h> |
55 |
#include <stdlib.h> |
56 |
#include <sys/time.h> |
57 |
#include <sys/resource.h> |
58 |
|
59 |
int main(int ac, char **av) |
60 |
{ |
61 |
int size = atoi(av[1]), runs = atoi(av[2]), trials = ac>3?atoi(av[3]):1; |
62 |
struct p_s {struct p_s *next; int a,b; } *p, *p2; |
63 |
struct { int a,b; } *q; |
64 |
int i, j, t; |
65 |
struct rusage ru1, ru2, ru3, ru4; |
66 |
int list = 0, array = 0; |
67 |
|
68 |
p = p2 = malloc(sizeof(*p)); |
69 |
q = malloc(sizeof(*q) * size); |
70 |
for (i = 0; i < size; i++) { |
71 |
p2->b = q[i].b = i; |
72 |
p2 = (p2->next = malloc(sizeof(*p2))); |
73 |
} |
74 |
for (t = 0; t < trials+1; t++) { |
75 |
for (p2 = p; p2->b != size-1; p2 = p2->next) |
76 |
; |
77 |
getrusage(RUSAGE_SELF, &ru1); |
78 |
for (i = 0; i < runs; i++) |
79 |
for (p2 = p; p2->b != size-1; p2 = p2->next) |
80 |
; |
81 |
getrusage(RUSAGE_SELF, &ru2); |
82 |
for (j = 0; q[j].b != size-1; j++) |
83 |
; |
84 |
getrusage(RUSAGE_SELF, &ru3); |
85 |
for (i = 0; i < runs; i++) |
86 |
for (j = 0; q[j].b != size-1; j++) |
87 |
; |
88 |
getrusage(RUSAGE_SELF, &ru4); |
89 |
#define TIME(ru) ((ru).ru_utime.tv_sec*1000 + (ru).ru_utime.tv_usec/1000) |
90 |
if (t > 0) { // skip first trial for cache loading |
91 |
list += TIME(ru2) - TIME(ru1); |
92 |
array += TIME(ru4) - TIME(ru3); |
93 |
} |
94 |
} |
95 |
printf("List : %d ms\nArray: %d ms\n", |
96 |
(list*2+trials)/(trials*2), (array*2+trials)/(trials*2)); |
97 |
return 0; |
98 |
} |
99 |
*/ |
100 |
|
101 |
/*************************************************************************/ |
102 |
/*************************************************************************/ |
103 |
|
104 |
/* Remove anything defined by system headers. */ |
105 |
|
106 |
#undef LIST_INSERT |
107 |
#undef LIST_INSERT_ORDERED |
108 |
#undef LIST_REMOVE |
109 |
#undef LIST_FOREACH |
110 |
#undef LIST_FOREACH_SAFE |
111 |
#undef LIST_SEARCH |
112 |
#undef LIST_SEARCH_SCALAR |
113 |
#undef LIST_SEARCH_ORDERED |
114 |
#undef LIST_SEARCH_ORDERED_SCALAR |
115 |
#undef ARRAY2_EXTEND |
116 |
#undef ARRAY2_INSERT |
117 |
#undef ARRAY2_REMOVE |
118 |
#undef ARRAY2_FOREACH |
119 |
#undef ARRAY2_SEARCH |
120 |
#undef ARRAY2_SEARCH_SCALAR |
121 |
#undef ARRAY2_SEARCH_PLAIN_SCALAR |
122 |
#undef ARRAY_EXTEND |
123 |
#undef ARRAY_INSERT |
124 |
#undef ARRAY_REMOVE |
125 |
#undef ARRAY_FOREACH |
126 |
#undef ARRAY_SEARCH |
127 |
#undef ARRAY_SEARCH_SCALAR |
128 |
#undef ARRAY_SEARCH_PLAIN_SCALAR |
129 |
|
130 |
/*************************************************************************/ |
131 |
/*************************************************************************/ |
132 |
|
133 |
/* List macros. In these macros, `list' must be an lvalue (with no side |
134 |
* effects) of the same type as the nodes in the list. */ |
135 |
|
136 |
/*************************************************************************/ |
137 |
|
138 |
/* Insert `node' into the beginning of `list'. Insertion is performed in |
139 |
* constant time. */ |
140 |
|
141 |
#define LIST_INSERT(node_,list) \ |
142 |
do { \ |
143 |
typeof(list) _node = (node_); \ |
144 |
_node->next = (list); \ |
145 |
_node->prev = NULL; \ |
146 |
if (list) \ |
147 |
(list)->prev = _node; \ |
148 |
(list) = _node; \ |
149 |
} while (0) |
150 |
|
151 |
/*************************************************************************/ |
152 |
|
153 |
/* Append `node' to the end of `list'. Insertion is performed in linear |
154 |
* time with the length of the list. */ |
155 |
|
156 |
#define LIST_APPEND(node_,list) \ |
157 |
do { \ |
158 |
typeof(list) _node = (node_); \ |
159 |
typeof(_node) *_nextptr = &(list); \ |
160 |
typeof(_node) _prev = NULL; \ |
161 |
while (*_nextptr) { \ |
162 |
_prev = *_nextptr; \ |
163 |
_nextptr = &((*_nextptr)->next); \ |
164 |
} \ |
165 |
*_nextptr = _node; \ |
166 |
_node->prev = _prev; \ |
167 |
_node->next = NULL; \ |
168 |
} while (0) |
169 |
|
170 |
/*************************************************************************/ |
171 |
|
172 |
/* Insert `node' into `list' so that `list' maintains its order as |
173 |
* determined by the function `compare' called on the field `field' of each |
174 |
* node. `field' must be a field of `node', and `compare' must be a |
175 |
* function that takes two `field' values and returns -1, 0, or 1 |
176 |
* indicating whether the first argument is ordered before, equal to, or |
177 |
* after the second (strcmp(), for example). If an equal node is found, |
178 |
* `node' is inserted after it. Insertion is performed in linear time |
179 |
* with the length of the list. */ |
180 |
|
181 |
#define LIST_INSERT_ORDERED(node_,list,compare,field) \ |
182 |
do { \ |
183 |
typeof(list) _node = (node_); \ |
184 |
typeof(_node) _ptr, _prev; \ |
185 |
for (_ptr = (list), _prev = NULL; _ptr; \ |
186 |
_prev = _ptr, _ptr = _ptr->next \ |
187 |
) { \ |
188 |
if (compare(_node->field, _ptr->field) < 0) \ |
189 |
break; \ |
190 |
} \ |
191 |
_node->next = _ptr; \ |
192 |
_node->prev = _prev; \ |
193 |
if (_ptr) \ |
194 |
_ptr->prev = _node; \ |
195 |
if (_prev) \ |
196 |
_prev->next = _node; \ |
197 |
else \ |
198 |
(list) = _node; \ |
199 |
} while (0) |
200 |
|
201 |
/*************************************************************************/ |
202 |
|
203 |
/* Remove `node' from `list'. Removal is performed in constant time. */ |
204 |
|
205 |
#define LIST_REMOVE(node_,list) \ |
206 |
do { \ |
207 |
typeof(list) _node = (node_); \ |
208 |
if (_node->next) \ |
209 |
_node->next->prev = _node->prev; \ |
210 |
if (_node->prev) \ |
211 |
_node->prev->next = _node->next; \ |
212 |
else \ |
213 |
(list) = _node->next; \ |
214 |
} while (0) |
215 |
|
216 |
/*************************************************************************/ |
217 |
|
218 |
/* Iterate over every element in `list', using `iter' as the iterator. The |
219 |
* macro has the same properties as a for() loop. `iter' must be an |
220 |
* lvalue. */ |
221 |
|
222 |
#define LIST_FOREACH(iter,list) \ |
223 |
for ((iter) = (list); (iter); (iter) = (iter)->next) |
224 |
|
225 |
/*************************************************************************/ |
226 |
|
227 |
/* Iterate over `list' using an extra variable (`temp') to hold the next |
228 |
* element, ensuring proper operation even when the current element is |
229 |
* deleted. `iter' and `temp' must be lvalues. */ |
230 |
|
231 |
#define LIST_FOREACH_SAFE(iter,list,temp) \ |
232 |
for ((iter) = (list); (iter) && (temp = (iter)->next, 1); (iter) = temp) |
233 |
|
234 |
/*************************************************************************/ |
235 |
|
236 |
/* Search `list' for a node with `field' equal to `target' (as evaluated by |
237 |
* `compare') and place a pointer to the node found, or NULL if no node is |
238 |
* found, in `result'. `field' must be a field of the nodes in `list'; |
239 |
* `target' must be an expression of the type of `field' with no side |
240 |
* effects; `result' must be an lvalue; and `compare' must be a |
241 |
* strcmp()-like function (see LIST_INSERT_ORDERED). The search is |
242 |
* performed in linear time, disregarding the comparison function. */ |
243 |
|
244 |
#define LIST_SEARCH(list,field,target,compare,result) \ |
245 |
do { \ |
246 |
LIST_FOREACH ((result), (list)) { \ |
247 |
if (compare((result)->field, (target)) == 0)\ |
248 |
break; \ |
249 |
} \ |
250 |
} while (0) |
251 |
|
252 |
/*************************************************************************/ |
253 |
|
254 |
/* Search `list' as LIST_SEARCH does, but for a scalar value. The search |
255 |
* is performed in linear time. */ |
256 |
|
257 |
#define LIST_SEARCH_SCALAR(list,field,target,result) \ |
258 |
do { \ |
259 |
LIST_FOREACH ((result), (list)) { \ |
260 |
if ((result)->field == (target)) \ |
261 |
break; \ |
262 |
} \ |
263 |
} while (0) |
264 |
|
265 |
/*************************************************************************/ |
266 |
|
267 |
/* Search `list' as LIST_SEARCH does, but for a list known to be ordered. |
268 |
* The search is performed in linear time, disregarding the comparison |
269 |
* function. */ |
270 |
|
271 |
#define LIST_SEARCH_ORDERED(list,field,target,compare,result) \ |
272 |
do { \ |
273 |
LIST_FOREACH ((result), (list)) { \ |
274 |
int i = compare((result)->field, (target)); \ |
275 |
if (i > 0) \ |
276 |
(result) = NULL; \ |
277 |
if (i >= 0) \ |
278 |
break; \ |
279 |
} \ |
280 |
} while (0) |
281 |
|
282 |
/*************************************************************************/ |
283 |
|
284 |
/* Search `list' as LIST_SEARCH_ORDERED does, but for a scalar value. The |
285 |
* search is performed in linear time. */ |
286 |
|
287 |
#define LIST_SEARCH_ORDERED_SCALAR(list,field,target,result) \ |
288 |
do { \ |
289 |
LIST_FOREACH ((result), (list)) { \ |
290 |
int i = (result)->field - (target); \ |
291 |
if (i > 0) \ |
292 |
(result) = NULL; \ |
293 |
if (i >= 0) \ |
294 |
break; \ |
295 |
} \ |
296 |
} while (0) |
297 |
|
298 |
/*************************************************************************/ |
299 |
/*************************************************************************/ |
300 |
|
301 |
/* Array macros. In these macros, `array' and `size' must be lvalues with |
302 |
* no side effects; `array' is a pointer to the elements of the array, and |
303 |
* `size' is the current size (length) of the array. */ |
304 |
|
305 |
/*************************************************************************/ |
306 |
|
307 |
/* Extend a variable-length array by one entry. Execution time is no |
308 |
* greater than linear with the length of the array. */ |
309 |
|
310 |
#define ARRAY2_EXTEND(array,size) \ |
311 |
do { \ |
312 |
(size)++; \ |
313 |
(array) = srealloc((array), sizeof(*(array)) * (size)); \ |
314 |
} while (0) |
315 |
|
316 |
/*************************************************************************/ |
317 |
|
318 |
/* Insert a slot at position `index' in a variable-length array. |
319 |
* Execution time is linear with the length of the array. */ |
320 |
|
321 |
#define ARRAY2_INSERT(array,size,index_) \ |
322 |
do { \ |
323 |
unsigned int _index = (index_); \ |
324 |
(size)++; \ |
325 |
(array) = srealloc((array), sizeof(*(array)) * (size)); \ |
326 |
if (_index < (size)-1) \ |
327 |
memmove(&(array)[_index+1], &(array)[_index], \ |
328 |
sizeof(*(array)) * (((size)-1)-_index)); \ |
329 |
} while (0) |
330 |
|
331 |
/*************************************************************************/ |
332 |
|
333 |
/* Delete entry number `index' from a variable-length array. Execution |
334 |
* time is linear with the length of the array. */ |
335 |
|
336 |
#define ARRAY2_REMOVE(array,size,index_) \ |
337 |
do { \ |
338 |
unsigned int _index = (index_); \ |
339 |
(size)--; \ |
340 |
if (_index < (size)) \ |
341 |
memmove(&(array)[_index], &(array)[_index]+1, \ |
342 |
sizeof(*(array)) * ((size)-_index)); \ |
343 |
(array) = srealloc((array), sizeof(*(array)) * (size)); \ |
344 |
} while (0) |
345 |
|
346 |
/*************************************************************************/ |
347 |
|
348 |
/* Iterate over every element in a variable-length array. */ |
349 |
|
350 |
#define ARRAY2_FOREACH(iter,array,size) \ |
351 |
for ((iter) = 0; (iter) < (size); (iter)++) |
352 |
|
353 |
/*************************************************************************/ |
354 |
|
355 |
/* Search a variable-length array for a value. Operates like LIST_SEARCH. |
356 |
* `result' must be an integer lvalue. If nothing is found, `result' will |
357 |
* be set equal to `size'. The search is performed in linear time, |
358 |
* disregarding the comparison function. */ |
359 |
|
360 |
#define ARRAY2_SEARCH(array,size,field,target,compare,result) \ |
361 |
do { \ |
362 |
ARRAY2_FOREACH ((result), (array), (size)) { \ |
363 |
if (compare((array)[(result)].field, (target)) == 0)\ |
364 |
break; \ |
365 |
} \ |
366 |
} while (0) |
367 |
|
368 |
/*************************************************************************/ |
369 |
|
370 |
/* Search a variable-length array for a value, when the array elements do |
371 |
* not have fields. The search is performed in linear time, disregarding |
372 |
* the comparison function. */ |
373 |
|
374 |
#define ARRAY2_SEARCH_PLAIN(array,size,target,compare,result) \ |
375 |
do { \ |
376 |
ARRAY2_FOREACH ((result), (array), (size)) { \ |
377 |
if (compare((array)[(result)], (target)) == 0) \ |
378 |
break; \ |
379 |
} \ |
380 |
} while (0) |
381 |
|
382 |
/*************************************************************************/ |
383 |
|
384 |
/* Search a variable-length array for a scalar value. The search is |
385 |
* performed in linear time. */ |
386 |
|
387 |
#define ARRAY2_SEARCH_SCALAR(array,size,field,target,result) \ |
388 |
do { \ |
389 |
ARRAY2_FOREACH ((result), (array), (size)) { \ |
390 |
if ((array)[(result)].field == (target)) \ |
391 |
break; \ |
392 |
} \ |
393 |
} while (0) |
394 |
|
395 |
/*************************************************************************/ |
396 |
|
397 |
/* Search a variable-length array for a scalar value, when the array |
398 |
* elements do not have fields. The search is performed in linear time. */ |
399 |
|
400 |
#define ARRAY2_SEARCH_PLAIN_SCALAR(array,size,target,result) \ |
401 |
do { \ |
402 |
ARRAY2_FOREACH ((result), (array), (size)) { \ |
403 |
if ((array)[(result)] == (target)) \ |
404 |
break; \ |
405 |
} \ |
406 |
} while (0) |
407 |
|
408 |
/*************************************************************************/ |
409 |
/*************************************************************************/ |
410 |
|
411 |
/* Perform the ARRAY2_* actions on an array `array' whose size is stored in |
412 |
* `array_count'. */ |
413 |
|
414 |
#define ARRAY_EXTEND(array) ARRAY2_EXTEND(array,array##_count) |
415 |
#define ARRAY_INSERT(array,index) ARRAY2_INSERT(array,array##_count,index) |
416 |
#define ARRAY_REMOVE(array,index) ARRAY2_REMOVE(array,array##_count,index) |
417 |
#define ARRAY_FOREACH(iter,array) ARRAY2_FOREACH(iter,array,array##_count) |
418 |
#define ARRAY_SEARCH(array,field,target,compare,result) \ |
419 |
ARRAY2_SEARCH(array,array##_count,field,target,compare,result) |
420 |
#define ARRAY_SEARCH_PLAIN(array,target,compare,result) \ |
421 |
ARRAY2_SEARCH_PLAIN(array,array##_count,target,compare,result) |
422 |
#define ARRAY_SEARCH_SCALAR(array,field,target,result) \ |
423 |
ARRAY2_SEARCH_SCALAR(array,array##_count,field,target,result) |
424 |
#define ARRAY_SEARCH_PLAIN_SCALAR(array,target,result) \ |
425 |
ARRAY2_SEARCH_PLAIN_SCALAR(array,array##_count,target,result) |
426 |
|
427 |
/*************************************************************************/ |
428 |
/*************************************************************************/ |
429 |
|
430 |
#endif /* LIST_ARRAY_H */ |
431 |
|
432 |
/* |
433 |
* Local variables: |
434 |
* c-file-style: "stroustrup" |
435 |
* c-file-offsets: ((case-label . *) (statement-case-intro . *)) |
436 |
* indent-tabs-mode: nil |
437 |
* End: |
438 |
* |
439 |
* vim: expandtab shiftwidth=4: |
440 |
*/ |