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

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

Parent Directory Parent Directory | Revision Log Revision Log


Revision 1171 - (hide 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 michael 1171 /* 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