vendor/ircservices-5.1.24/list-array.h

/* Macros to handle insertion, deletion, iteration, and searching for
 * linked lists and arrays.
 *
 * IRC Services is copyright (c) 1996-2009 Andrew Church.
 *     E-mail: <achurch@achurch.org>
 * Parts written by Andrew Kempe and others.
 * This program is free but copyrighted software; see the file GPL.txt for
 * details.
 */

#ifndef LIST_ARRAY_H
#define LIST_ARRAY_H

/*************************************************************************/

/* Comments on the efficiency of lists vs. arrays:
 *
 * Lists are simple to insert into and remove from, but searching can be
 * inefficient, as the list must be walked through each time.  Arrays can
 * be searched quickly, particularly if the list is sorted (note that the
 * macros below do not support sorted arrays), but insertion and removal
 * are expensive, requiring data to be moved around in memory if the
 * element to be inserted or removed is not last in the array or if
 * reallocation of the array results in a different array pointer.  Lists
 * also have the advantage that the list can be easily modified (items
 * inserted or deleted) within a FOREACH loop, while arrays require extra
 * logic to modify the counter variable after an insert or delete.
 *
 * As far as searching goes, arrays do not show a significant improvement
 * until the data set size reaches around 15 elements, at which point the
 * reduced number of memory accesses (and reduced cache pressure,
 * particularly with large data sets) gives arrays a clear advantage.  The
 * following results were obtained from running the test program below on a
 * Celeron 1.7GHz system (compiled with gcc-4.1 -O3):
 *
 *      | Time/search (ns)
 * Size |   List  |  Array
 * -----+-------------------
 *    3 |     4.1 |    3.7
 *    5 |     7.3 |    6.7
 *    7 |     9.7 |    9.3
 *   10 |    14.5 |   12.3
 *   15 |    23.6 |   18.2
 *   20 |    53.5 |   21.7
 *   30 |    73.2 |   44.8
 *   50 |   109   |   56.7
 *  100 |   200   |  101
 *  300 |   564   |  267
 * 1000 |  4530   |  864
 * 3000 | 13740   | 4440
 *
 * Test program (outputs average time per trial):
 *
#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#include <sys/resource.h>

int main(int ac, char **av)
{
    int size = atoi(av[1]), runs = atoi(av[2]), trials = ac>3?atoi(av[3]):1;
    struct p_s {struct p_s *next; int a,b; } *p, *p2;
    struct { int a,b; } *q;
    int i, j, t;
    struct rusage ru1, ru2, ru3, ru4;
    int list = 0, array = 0;

    p = p2 = malloc(sizeof(*p));
    q = malloc(sizeof(*q) * size);
    for (i = 0; i < size; i++) {
        p2->b = q[i].b = i;
        p2 = (p2->next = malloc(sizeof(*p2)));
    }
    for (t = 0; t < trials+1; t++) {
        for (p2 = p; p2->b != size-1; p2 = p2->next)
            ;
        getrusage(RUSAGE_SELF, &ru1);
        for (i = 0; i < runs; i++)
            for (p2 = p; p2->b != size-1; p2 = p2->next)
                ;
        getrusage(RUSAGE_SELF, &ru2);
        for (j = 0; q[j].b != size-1; j++)
            ;
        getrusage(RUSAGE_SELF, &ru3);
        for (i = 0; i < runs; i++)
            for (j = 0; q[j].b != size-1; j++)
                ;
        getrusage(RUSAGE_SELF, &ru4);
#define TIME(ru) ((ru).ru_utime.tv_sec*1000 + (ru).ru_utime.tv_usec/1000)
        if (t > 0) {  // skip first trial for cache loading
            list += TIME(ru2) - TIME(ru1);
            array += TIME(ru4) - TIME(ru3);
        }
    }
    printf("List : %d ms\nArray: %d ms\n",
           (list*2+trials)/(trials*2), (array*2+trials)/(trials*2));
    return 0;
}
 */

/*************************************************************************/
/*************************************************************************/

/* Remove anything defined by system headers. */

#undef LIST_INSERT
#undef LIST_INSERT_ORDERED
#undef LIST_REMOVE
#undef LIST_FOREACH
#undef LIST_FOREACH_SAFE
#undef LIST_SEARCH
#undef LIST_SEARCH_SCALAR
#undef LIST_SEARCH_ORDERED
#undef LIST_SEARCH_ORDERED_SCALAR
#undef ARRAY2_EXTEND
#undef ARRAY2_INSERT
#undef ARRAY2_REMOVE
#undef ARRAY2_FOREACH
#undef ARRAY2_SEARCH
#undef ARRAY2_SEARCH_SCALAR
#undef ARRAY2_SEARCH_PLAIN_SCALAR
#undef ARRAY_EXTEND
#undef ARRAY_INSERT
#undef ARRAY_REMOVE
#undef ARRAY_FOREACH
#undef ARRAY_SEARCH
#undef ARRAY_SEARCH_SCALAR
#undef ARRAY_SEARCH_PLAIN_SCALAR

/*************************************************************************/
/*************************************************************************/

/* List macros.  In these macros, `list' must be an lvalue (with no side
 * effects) of the same type as the nodes in the list. */

/*************************************************************************/

/* Insert `node' into the beginning of `list'.  Insertion is performed in
 * constant time. */

#define LIST_INSERT(node_,list)         \
    do {                                \
        typeof(list) _node = (node_);   \
        _node->next = (list);           \
        _node->prev = NULL;             \
        if (list)                       \
            (list)->prev = _node;       \
        (list) = _node;                 \
    } while (0)

/*************************************************************************/

/* Append `node' to the end of `list'.  Insertion is performed in linear
 * time with the length of the list. */

#define LIST_APPEND(node_,list)                 \
    do {                                        \
        typeof(list) _node = (node_);           \
        typeof(_node) *_nextptr = &(list);      \
        typeof(_node) _prev = NULL;             \
        while (*_nextptr) {                     \
            _prev = *_nextptr;                  \
            _nextptr = &((*_nextptr)->next);    \
        }                                       \
        *_nextptr = _node;                      \
        _node->prev = _prev;                    \
        _node->next = NULL;                     \
    } while (0)

/*************************************************************************/

/* Insert `node' into `list' so that `list' maintains its order as
 * determined by the function `compare' called on the field `field' of each
 * node.  `field' must be a field of `node', and `compare' must be a
 * function that takes two `field' values and returns -1, 0, or 1
 * indicating whether the first argument is ordered before, equal to, or
 * after the second (strcmp(), for example).  If an equal node is found,
 * `node' is inserted after it.  Insertion is performed in linear time
 * with the length of the list. */

#define LIST_INSERT_ORDERED(node_,list,compare,field)   \
    do {                                                \
        typeof(list) _node = (node_);                   \
        typeof(_node) _ptr, _prev;                      \
        for (_ptr = (list), _prev = NULL; _ptr;         \
             _prev = _ptr, _ptr = _ptr->next            \
        ) {                                             \
            if (compare(_node->field, _ptr->field) < 0) \
                break;                                  \
        }                                               \
        _node->next = _ptr;                             \
        _node->prev = _prev;                            \
        if (_ptr)                                       \
            _ptr->prev = _node;                         \
        if (_prev)                                      \
            _prev->next = _node;                        \
        else                                            \
            (list) = _node;                             \
    } while (0)

/*************************************************************************/

/* Remove `node' from `list'.  Removal is performed in constant time. */

#define LIST_REMOVE(node_,list)                 \
    do {                                        \
        typeof(list) _node = (node_);           \
        if (_node->next)                        \
            _node->next->prev = _node->prev;    \
        if (_node->prev)                        \
            _node->prev->next = _node->next;    \
        else                                    \
            (list) = _node->next;               \
    } while (0)

/*************************************************************************/

/* Iterate over every element in `list', using `iter' as the iterator.  The
 * macro has the same properties as a for() loop.  `iter' must be an
 * lvalue. */

#define LIST_FOREACH(iter,list) \
    for ((iter) = (list); (iter); (iter) = (iter)->next)

/*************************************************************************/

/* Iterate over `list' using an extra variable (`temp') to hold the next
 * element, ensuring proper operation even when the current element is
 * deleted.  `iter' and `temp' must be lvalues. */

#define LIST_FOREACH_SAFE(iter,list,temp) \
    for ((iter) = (list); (iter) && (temp = (iter)->next, 1); (iter) = temp)

/*************************************************************************/

/* Search `list' for a node with `field' equal to `target' (as evaluated by
 * `compare') and place a pointer to the node found, or NULL if no node is
 * found, in `result'.  `field' must be a field of the nodes in `list';
 * `target' must be an expression of the type of `field' with no side
 * effects; `result' must be an lvalue; and `compare' must be a
 * strcmp()-like function (see LIST_INSERT_ORDERED).  The search is
 * performed in linear time, disregarding the comparison function. */

#define LIST_SEARCH(list,field,target,compare,result)   \
    do {                                                \
        LIST_FOREACH ((result), (list)) {               \
            if (compare((result)->field, (target)) == 0)\
                break;                                  \
        }                                               \
    } while (0)

/*************************************************************************/

/* Search `list' as LIST_SEARCH does, but for a scalar value.  The search
 * is performed in linear time. */

#define LIST_SEARCH_SCALAR(list,field,target,result)    \
    do {                                                \
        LIST_FOREACH ((result), (list)) {               \
            if ((result)->field == (target))            \
                break;                                  \
        }                                               \
    } while (0)

/*************************************************************************/

/* Search `list' as LIST_SEARCH does, but for a list known to be ordered.
 * The search is performed in linear time, disregarding the comparison
 * function. */

#define LIST_SEARCH_ORDERED(list,field,target,compare,result)   \
    do {                                                        \
        LIST_FOREACH ((result), (list)) {                       \
            int i = compare((result)->field, (target));         \
            if (i > 0)                                          \
                (result) = NULL;                                \
            if (i >= 0)                                         \
                break;                                          \
        }                                                       \
    } while (0)

/*************************************************************************/

/* Search `list' as LIST_SEARCH_ORDERED does, but for a scalar value.  The
 * search is performed in linear time. */

#define LIST_SEARCH_ORDERED_SCALAR(list,field,target,result)    \
    do {                                                        \
        LIST_FOREACH ((result), (list)) {                       \
            int i = (result)->field - (target);                 \
            if (i > 0)                                          \
                (result) = NULL;                                \
            if (i >= 0)                                         \
                break;                                          \
        }                                                       \
    } while (0)

/*************************************************************************/
/*************************************************************************/

/* Array macros.  In these macros, `array' and `size' must be lvalues with
 * no side effects; `array' is a pointer to the elements of the array, and
 * `size' is the current size (length) of the array. */

/*************************************************************************/

/* Extend a variable-length array by one entry.  Execution time is no
 * greater than linear with the length of the array. */

#define ARRAY2_EXTEND(array,size)                               \
    do {                                                        \
        (size)++;                                               \
        (array) = srealloc((array), sizeof(*(array)) * (size)); \
    } while (0)

/*************************************************************************/

/* Insert a slot at position `index' in a variable-length array.
 * Execution time is linear with the length of the array. */

#define ARRAY2_INSERT(array,size,index_)                        \
    do {                                                        \
        unsigned int _index = (index_);                         \
        (size)++;                                               \
        (array) = srealloc((array), sizeof(*(array)) * (size)); \
        if (_index < (size)-1)                                  \
            memmove(&(array)[_index+1], &(array)[_index],       \
                    sizeof(*(array)) * (((size)-1)-_index));    \
    } while (0)

/*************************************************************************/

/* Delete entry number `index' from a variable-length array.  Execution
 * time is linear with the length of the array. */

#define ARRAY2_REMOVE(array,size,index_)                        \
    do {                                                        \
        unsigned int _index = (index_);                         \
        (size)--;                                               \
        if (_index < (size))                                    \
            memmove(&(array)[_index], &(array)[_index]+1,       \
                    sizeof(*(array)) * ((size)-_index));        \
        (array) = srealloc((array), sizeof(*(array)) * (size)); \
    } while (0)

/*************************************************************************/

/* Iterate over every element in a variable-length array. */

#define ARRAY2_FOREACH(iter,array,size) \
    for ((iter) = 0; (iter) < (size); (iter)++)

/*************************************************************************/

/* Search a variable-length array for a value.  Operates like LIST_SEARCH.
 * `result' must be an integer lvalue.  If nothing is found, `result' will
 * be set equal to `size'.  The search is performed in linear time,
 * disregarding the comparison function. */

#define ARRAY2_SEARCH(array,size,field,target,compare,result)   \
    do {                                                        \
        ARRAY2_FOREACH ((result), (array), (size)) {            \
            if (compare((array)[(result)].field, (target)) == 0)\
                break;                                          \
        }                                                       \
    } while (0)

/*************************************************************************/

/* Search a variable-length array for a value, when the array elements do
 * not have fields.  The search is performed in linear time, disregarding
 * the comparison function. */

#define ARRAY2_SEARCH_PLAIN(array,size,target,compare,result)   \
    do {                                                        \
        ARRAY2_FOREACH ((result), (array), (size)) {            \
            if (compare((array)[(result)], (target)) == 0)      \
                break;                                          \
        }                                                       \
    } while (0)

/*************************************************************************/

/* Search a variable-length array for a scalar value.  The search is
 * performed in linear time. */

#define ARRAY2_SEARCH_SCALAR(array,size,field,target,result)    \
    do {                                                        \
        ARRAY2_FOREACH ((result), (array), (size)) {            \
            if ((array)[(result)].field == (target))            \
                break;                                          \
        }                                                       \
    } while (0)

/*************************************************************************/

/* Search a variable-length array for a scalar value, when the array
 * elements do not have fields.  The search is performed in linear time. */

#define ARRAY2_SEARCH_PLAIN_SCALAR(array,size,target,result)    \
    do {                                                        \
        ARRAY2_FOREACH ((result), (array), (size)) {            \
            if ((array)[(result)] == (target))                  \
                break;                                          \
        }                                                       \
    } while (0)

/*************************************************************************/
/*************************************************************************/

/* Perform the ARRAY2_* actions on an array `array' whose size is stored in
 * `array_count'. */

#define ARRAY_EXTEND(array)       ARRAY2_EXTEND(array,array##_count)
#define ARRAY_INSERT(array,index) ARRAY2_INSERT(array,array##_count,index)
#define ARRAY_REMOVE(array,index) ARRAY2_REMOVE(array,array##_count,index)
#define ARRAY_FOREACH(iter,array) ARRAY2_FOREACH(iter,array,array##_count)
#define ARRAY_SEARCH(array,field,target,compare,result) \
    ARRAY2_SEARCH(array,array##_count,field,target,compare,result)
#define ARRAY_SEARCH_PLAIN(array,target,compare,result) \
    ARRAY2_SEARCH_PLAIN(array,array##_count,target,compare,result)
#define ARRAY_SEARCH_SCALAR(array,field,target,result) \
    ARRAY2_SEARCH_SCALAR(array,array##_count,field,target,result)
#define ARRAY_SEARCH_PLAIN_SCALAR(array,target,result) \
    ARRAY2_SEARCH_PLAIN_SCALAR(array,array##_count,target,result)

/*************************************************************************/
/*************************************************************************/

#endif  /* LIST_ARRAY_H */

/*
 * Local variables:
 *   c-file-style: "stroustrup"
 *   c-file-offsets: ((case-label . *) (statement-case-intro . *))
 *   indent-tabs-mode: nil
 * End:
 *
 * vim: expandtab shiftwidth=4:
 */
Revision:	3389
Committed:	Fri Apr 25 14:12:15 2014 UTC (12 years, 2 months ago) by michael
Content type:	text/x-chdr
File size:	18706 byte(s)
Log Message:	- Imported ircservices-5.1.24
#	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	(list2+trials)/(trials2), (array2+trials)/(trials2));
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	*/