ViewVC Help
View File | Revision Log | Show Annotations | View Changeset | Root Listing
root/svn/vendor/ircservices-5.1.24/list-array.h
Revision: 3389
Committed: Fri Apr 25 14:12:15 2014 UTC (9 years, 10 months ago) by michael
Content type: text/x-chdr
File size: 18706 byte(s)
Log Message:
- Imported ircservices-5.1.24

File Contents

# Content
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 */