/[svn]/vendor/ircservices-5.1.24/list-array.h
ViewVC logotype

Contents of /vendor/ircservices-5.1.24/list-array.h

Parent Directory Parent Directory | Revision Log Revision Log


Revision 1171 - (show annotations)
Fri Aug 12 20:00:46 2011 UTC (10 years, 5 months ago) by michael
File MIME type: text/x-csrc
File size: 18706 byte(s)
- Import ircservices-5.1.24. Don't ever think about modifying anything in this
  folder!
  Since Andrew Church has discontinued his services project in April 2011, the
  ircd-hybrid team has been given permissions to officially continue and
  maintain the already mentioned project.
  The name of this project will be changed for the reason being that the current
  name "IRC Services" is way too generic these days.

  Remember: Don't ever modify anything in here. This folder is kept for reference.

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

svnadmin@ircd-hybrid.org
ViewVC Help
Powered by ViewVC 1.1.28