/[ascend]/trunk/base/generic/general/list.h
ViewVC logotype

Contents of /trunk/base/generic/general/list.h

Parent Directory Parent Directory | Revision Log Revision Log


Revision 67 - (show annotations) (download) (as text)
Wed Nov 30 16:31:29 2005 UTC (18 years, 6 months ago) by johnpye
File MIME type: text/x-chdr
File size: 34811 byte(s)
Standardised the "if seen" #defines to [ASC|ASCTK|ASCPY|ASCXX]_FILENAME_H
Fixed compile on FC3
1 /*
2 * List Module
3 * by Tom Epperly
4 * Version: $Revision: 1.3 $
5 * Version control file: $RCSfile: list.h,v $
6 * Date last modified: $Date: 1998/02/19 13:03:22 $
7 * Last modified by: $Author: ballan $
8 *
9 * This file is part of the Ascend Language Interpreter.
10 *
11 * Copyright (C) 1990, 1993, 1994 Thomas Guthrie Epperly
12 *
13 * The Ascend Language Interpreter is free software; you can redistribute it
14 * and/or modify it under the terms of the GNU General Public License as
15 * published by the Free Software Foundation; either version 2 of the
16 * License, or (at your option) any later version.
17 *
18 * The Ascend Language Interpreter is distributed in hope that it will be
19 * useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
20 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General
21 * Public License for more details.
22 *
23 * You should have received a copy of the GNU General Public License along
24 * with the program; if not, write to the Free Software Foundation, Inc.,
25 * 675 Mass Ave, Cambridge, MA 02139 USA. Check the file named COPYING.
26 */
27
28 /** @file
29 * List Module.
30 *
31 * The purpose of this module is to provide a kind of flexible array.
32 * The flexible array has two interesting characteristics. It allows
33 * contant time(O(1)) retrieval of list items and it is almost infinitely
34 * extendable (i.e. has no preset limit on the number of items in the list).
35 * It does not use much extra memory while providing these services.<br><br>
36 *
37 * The list only stores pointers to items as VOIDPTR (void *). This is
38 * an advantage, in that the user has the flexibility to store pointers to
39 * any data type in the list. It is also a disadvanatage, since the data
40 * structure is not type safe and the user must carefully keep track of
41 * what is stored in the list.<br><br>
42 *
43 * This module provides a standard set of list type operations. Each includes
44 * some predictions about the efficiency of that operation. Any modification
45 * of these procedures should live up to those claims.
46 * <pre>
47 * When #including list.h, make sure these files are #included first:
48 * #include <stdio.h>
49 * #include "utilities/ascConfig.h"
50 * #include "compiler/compiler.h"
51 * </pre>
52 */
53
54 /*
55 * Any bugs or suggestions can be sent to:
56 *
57 * te07@edrc.cmu.edu or te07@andrew.cmu.edu or epperly@osnome.che.wisc.edu
58 * Tom Epperly
59 * 314 South Orchard Street
60 * Madison, WI 53715-1542
61 *
62 * Also please copy any bugs or suggestions to ascend+developers@cs.cmu.edu
63 *
64 * This utility depends on ascmalloc.[ch] and (optionally) pool.[ch]
65 *
66 * Change Log
67 * 2/26/88 added gl_copy, gl_concat
68 * 3/31/88 added additional commenting
69 * 2/18/96 added defines when -DNDEBUG is active. We can't
70 * afford the calls in a production compiler. (Ben Allan)
71 * 2/23/96 Added recycling feature to reuse gl_lists. (TGWE)
72 * 3/25/96 Improved recycling feature. (Ben Allan)
73 * 3/30/96 Took dispose flag off gl_destroy and added a mirror
74 * function gl_free_and_destroy to take its place.
75 * Added pooled list heads (optional) which depends on
76 * pool.[ch] and improves performance substantially.
77 * Tuned to large applications. (Ben Allan)
78 * 9/9/96 Changed flags from struct to int. (Ben Allan)
79 * 10/2/96 Added switch over -DMOD_REALLOC to use ascreallocPURE.
80 * If this file is compiled -DMOD_REALLOC, purify leaks of
81 * list->data are real, OTHERWISE it may be noise.
82 * Skipping the call to gl_init may also help dianosis.
83 * 9/20/97 Added gl_compare_ptrs.
84 */
85
86 #ifndef ASC_LIST_H
87 #define ASC_LIST_H
88
89 #ifndef TRUE
90 #define TRUE 1
91 #endif
92 #ifndef FALSE
93 #define FALSE 0
94 #endif
95 #define LISTIMPLEMENTED 0 /**< BAA_DEBUG changes that need work */
96
97 /*
98 * The following bit fields are defined for the gl_list flags
99 */
100 #define gsf_SORTED 0x1 /**< gl_list_t flag: list is sorted. */
101 #define gsf_EXPANDABLE 0x2 /**< gl_list_t flag: list is expandable. */
102
103 /** List data structure. */
104 struct gl_list_t {
105 VOIDPTR *data; /**< The data. */
106 unsigned long length; /**< Number of items used. */
107 unsigned long capacity; /**< Capacity of list. */
108 unsigned int flags; /**< Status flags. */
109 };
110
111 /** Generic comparator for sorts and searches. */
112 typedef int (*CmpFunc)(CONST VOIDPTR, CONST VOIDPTR);
113
114 /** Generic destroyer for iterations. */
115 typedef void (*DestroyFunc)(VOIDPTR);
116
117 extern void gl_init(void);
118 /**<
119 * Initializes the list recycler control table.
120 * Until this function is called, no recycling will take place.
121 * This recycler control table should be tuned to your application.
122 * The list recycler is independent of the pool implementation.
123 * This function may be called more than once, although in general
124 * there is no reason to do so.
125 */
126
127 #ifdef ASC_NO_POOL
128 #define LISTUSESPOOL FALSE
129 #else
130 #define LISTUSESPOOL TRUE
131 #endif
132 /**<
133 * Flag to select list management strategy.
134 * LISTUSESPOOL == TRUE allows the list module to use pool.[ch] to
135 * manage list memory overhead. Performance is enhanced this way.<br><br>
136 *
137 * LISTUSESPOOL == FALSE removes the pool dependency completely, at
138 * a performance penalty.<br><br>
139 *
140 * The following 3 functions work for either value of LISTUSESPOOL
141 * in some appropriate fashion: gl_init_pool(), gl_destroy_pool(),
142 * gl_report_pool().
143 */
144
145 extern void gl_init_pool(void);
146 /**<
147 * Sets up list overhead structure data management.
148 * This function should be called before anything can be built,
149 * ideally at startup time. Do not call it again unless
150 * gl_destroy_pool() is called first. If there is insufficient
151 * memory to compile anything at all, it does exit(2). Do not
152 * call gl_create() before this is called if LISTUSESPOOL == TRUE.
153 */
154
155 extern void gl_destroy_pool(void);
156 /**<
157 * Destroys list overhead structure data management. This must be
158 * called to clean up before shutting down your application if
159 * gl_init_pool() was called. Do not call this function while
160 * there are ANY lists in existence. Do not attempt to create
161 * any lists after you call this unless you have recalled
162 * gl_init_pool(). Do not call this if gl_init_pool() has not
163 * been called.
164 */
165
166 extern int gl_pool_initialized(void);
167 /**<
168 * Query whether the list pool has been initialized.
169 * Always returns TRUE if the list does not use pooling.
170 *
171 * @return Returns TRUE if the pool has already been initialized,
172 * FALSE otherwise.
173 */
174
175 extern void gl_report_pool(FILE *f);
176 /**<
177 * Prints a report on the recycle pool to f.
178 *
179 * @param f Open file stream to which to print report.
180 */
181
182 extern struct gl_list_t *gl_create(unsigned long capacity);
183 /**<
184 * Creates a new empty list having the specified initial capacity.
185 * If the number of list items later exceeds this size, the
186 * capacity will be expanded. It is not crucial, but a good
187 * guess will increase the performance of this module. There
188 * is an implementation-defined minimum list size, so the actual
189 * initial capacity can be larger than the requested capacity.<br><br>
190 *
191 * Note that newly-created lists are both sorted and expandable.
192 * Destruction of the returned list is the responsibility of the
193 * caller. Use gl_free_and_destroy() or gl_destroy() to do this.<br><br>
194 *
195 * Do not call this function unless gl_init_pool() has been called
196 * if LISTUSESPOOL == TRUE.
197 *
198 * Complexity: worst case O(capacity) <br>
199 * Because memory proportional to capacity is allocated, depending on
200 * your memory management system, this could be proportional to the
201 * initial capacity.
202 *
203 * @param capacity The desired initial list capacity.
204 * @return Returns a pointer to the new empty gl_list_t.
205 */
206
207 extern void gl_free_and_destroy(struct gl_list_t *list);
208 /**<
209 * Destroys a list and deallocates all list items.
210 * The specified list will be destroyed (its memory is to be
211 * returned to free memory or the list pool). Unlike with
212 * gl_destroy(), the items in the list WILL BE DEALLOCATED.
213 * This is appropriate when the list is considered the owner
214 * of the list items. The specified list can be NULL.<br><br>
215 *
216 * DO NOT CALL gl_free_and_destroy() ON BOTH A LIST AND IT'S
217 * gl_copy(). Since the copy is shallow, this would result in
218 * double deletion of the pointers and a likely crash.<br><br>
219 *
220 * Complexity: worst case O(n) <br>
221 * where n is the size of the list. This is because memory proportional
222 * to n must be deallocated. If that time is not proportional to the
223 * size then it should be O(1)
224 *
225 * @param list A pointer to the gl_list_t to destroy.
226 */
227
228 extern void gl_destroy(struct gl_list_t *list);
229 /**<
230 * Destroys a list without deallocating the list items.
231 * The specified list will be destroyed (its memory is to be
232 * returned to free memory or the list pool). Unlike with
233 * gl_free_and_destroy(), the items in the list WILL NOT be
234 * deallocated. This is appropriate when the list is considered
235 * to be storing pointers to data owned by someone else. Note that
236 * the stored pointers are no longer available after calling this
237 * function, so copies of the pointers must exist somewhere to
238 * allow deallocation of the data. The specified list can be NULL.<br><br>
239 *
240 * If you want the items to be freed (a la the old gl_destroy(list,1))
241 * call gl_free_and_destroy() instead.<br><br>
242 *
243 * Complexity: worst case O(n) <br>
244 * where n is the size of the list. I say this because memory proportional
245 * to n must be deallocated. If that time is not proportional to the
246 * size then it should be O(1)
247 *
248 * @param list A pointer to the gl_list_t to destroy.
249 */
250
251 #ifndef NDEBUG
252 #define gl_fetch(list,pos) gl_fetchF((list),(pos))
253 #else
254 #define gl_fetch(list,pos) ((list)->data[((pos)-1)])
255 #endif
256 /**<
257 * Retrieves the data item stored at position pos in the list.
258 * This function is used to access the list elements. It returns the
259 * pointer indexed by pos, which must be in the range [1..gl_length(list)]
260 * (checked by assertion). The specified list may not be NULL
261 * (checked by assertion).<br><br>
262 *
263 * The returned pointer is of type VOIDPTR (void *). It will usually be
264 * necessary to cast the pointer to the correct type before use. This is
265 * similar to what needs to be done with the pointer returned be malloc().<br><br>
266 *
267 * Example: <pre>
268 * struct data_t *item;
269 * item = (struct data_t *)gl_fetch(datalist,4); </pre>
270 *
271 * Complexity: O(1)
272 *
273 * @param list CONST struct gl_list_t*, the list to query (non-NULL).
274 * @param pos unsigned long, index to fetch [1..gl_length(list)].
275 * @return The list element at index pos as a VOIDPTR.
276 * @see gl_fetchF()
277 */
278
279 extern VOIDPTR gl_fetchF(CONST struct gl_list_t *list, unsigned long pos);
280 /**<
281 * Implementation function for gl_fetch() (debug mode).
282 * Do not call this function directly - use gl_fetch() instead.
283 */
284
285 extern void gl_store(struct gl_list_t *list, unsigned long pos, VOIDPTR ptr);
286 /**<
287 * Stores an item in the list in position pos. This procedure can only
288 * modify existing list items (i.e. 1 <= pos <= gl_length(list)). It cannot
289 * expand the list length or capacity. You must use gl_append_ptr() to
290 * do that. The specified list may not be NULL (checked by assertion).<br><br>
291 *
292 * Because any pointer type is convertible to a void pointer, you
293 * pass in a pointer to your data structure. It stores whatever pointer
294 * you give it.<br><br>
295 *
296 * Example: <pre>
297 * struct data_t *item;
298 * item = (struct data_t *)malloc(sizeof(struct data_t));
299 * various assignments to item->
300 * gl_store(list,4,item); * This stores item </pre>
301 *
302 * COMPLEXITY: O(1)
303 *
304 * @param list The list to modify (non-NULL).
305 * @param pos Index of position to modify, [1..gl_length(list)].
306 * @param ptr Pointer to data to store at index pos.
307 */
308
309 extern void gl_append_ptr(struct gl_list_t *list, VOIDPTR ptr);
310 /**<
311 * <!-- PROCEDURE gl_append_ptr(list,ptr); -->
312 * <!-- struct gl_list_t *list; -->
313 * <!-- VOIDPTR ptr; -->
314 *
315 * Appends ptr to the end of the list. If the addition of ptr exceeds
316 * the list capacity, the list capacity is increased. This and
317 * gl_append_list() are the only procedures that will expand the
318 * length and/or the capacity of a list. ptr is always stored in
319 * position gl_length(list)+1. The specified list may not be
320 * NULL, and the list must be expandable (checked by assertion).<br><br>
321 *
322 * Because any pointer type is convertible to a void pointer, you
323 * pass in a pointer to your data structure. It stores whatever pointer
324 * you give it.<br><br>
325 *
326 * Example: <pre>
327 * struct data_t *item;
328 * item = (struct data_t *)malloc(sizeof(struct data_t));
329 * various assignments to item->
330 * gl_append_ptr(list,item); * This stores item </pre>
331 *
332 * Complexity: worst case O(n) <br>
333 * where n is the capacity of the list. Normally it is O(1). It is
334 * only when the list capacity is increased that it takes O(n). This
335 * may also be an over estimate.
336 *
337 * @param list The list to modify (non-NULL).
338 * @param ptr Pointer to data to append to the list.
339 */
340
341 extern void gl_fast_append_ptr(struct gl_list_t *list, VOIDPTR ptr);
342 /**<
343 * Appends ptr to the end of the list without checking for adequate
344 * capacity. If the addition of ptr exceeds the list capacity, the
345 * memory adjacent will be corrupted. This function does not expand
346 * the list length or check it. ptr is always stored in position
347 * gl_length(list)+1. Only use this function in situations where
348 * you are absolutely sure the gl_length(list) < list->capacity.
349 * The specified list may not be NULL (checked by assertion).<br><br>
350 *
351 * Because any pointer type is convertible to a void pointer, you
352 * pass in a pointer to your data structure. It stores whatever pointer
353 * you give it.<br><br>
354 *
355 * Example: See gl_append_ptr.<br>
356 * Intended use is that you create a list of the size you know you
357 * need (but may want to expand at a later time) and then call this.
358 * This is faster than gl_store().<br><br>
359 *
360 * Complexity: O(1)
361 *
362 * @param list The list to modify (non-NULL).
363 * @param ptr Pointer to data to append to the list.
364 */
365
366 extern void gl_append_list(struct gl_list_t *extendlist,
367 struct gl_list_t *list);
368 /**<
369 * Appends the pointers stored in list to the end of extendlist.
370 * If the addition exceeds the capacity of extendlist, the extendlist
371 * capacity is increased. This function and gl_append_ptr() are the
372 * only procedures that will expand the length and/or the capacity of
373 * a list. Neither extendlist nor list may be NULL, and expandlist
374 * must be expandable (checked by assertion).<br><br>
375 *
376 * No new list is created. extendlist is changed if there is data in list.
377 * list is never changed in any case.<br><br>
378 *
379 * Example: <pre>
380 * gl_append_list(oldlist,addlist);
381 * This stores contents of addlist at the end of oldlist </pre>
382 *
383 * Complexity: worst case O(gl_length(list)+gl_length(extendlist)) <br>
384 * Normally it is O(gl_length(list)). It is
385 * only when the extendlist capacity is increased that it is worst. This
386 * may also be an over estimate depending on your allocator.
387 *
388 * @param extendlist The list to modify (non-NULL).
389 * @param list The list to append to extendlist (non-NULL).
390 */
391
392 #ifndef NDEBUG
393 #define gl_length(list) gl_lengthF(list)
394 #else
395 #define gl_length(list) ((list)->length)
396 #endif
397 /**<
398 * Returns the length of list. This is the number of items it
399 * is currently holding. There is no checking for whether list
400 * is a valid pointer. The specified list may not be NULL
401 * (checked by assertion). Use gl_safe_length() if the
402 * list pointer might be NULL.<br><br>
403 *
404 * Complexity: O(1)
405 *
406 * @param list CONST struct gl_list_t*. the list to query (non-NULL).
407 * @return The length as an unsigned long.
408 * @see gl_lengthF()
409 */
410 extern unsigned long gl_lengthF(CONST struct gl_list_t *list);
411 /**<
412 * Implementation function for gl_length() (debug mode).
413 * Do not call this function directly - use gl_length() instead.
414 *
415 * @param list CONST struct gl_list_t*. the list to query (non-NULL).
416 */
417
418 extern unsigned long gl_safe_length(CONST struct gl_list_t *list);
419 /**<
420 * Returns the length of list. This is the number of items it
421 * is currently holding. Unlike gl_length() this function
422 * tolerates NULL input, for which the return value is 0.<br><br>
423 *
424 * Complexity: O(1)
425 *
426 * @param list The list to query.
427 * @return The number of items stored in list.
428 */
429
430 extern unsigned long gl_capacity(CONST struct gl_list_t *list);
431 /**<
432 * Returns the *potential* capacity of the list at the current time.
433 * This is the number of items the list can store without having to
434 * expand its capacity. To find out the number of items in the list
435 * use gl_length(). The specified list may be NULL, in which case
436 * 0 is returned.<br><br>
437 *
438 * Complexity: O(1)
439 *
440 * @param list The list to query.
441 * @return The number of items that can be stored in list without expanding.
442 */
443
444 extern int gl_sorted(CONST struct gl_list_t *list);
445 /**<
446 * Query whether the specified list is sorted. A list having 0 or 1
447 * element is always sorted. The specified list may not be NULL
448 * (checked by assertion).
449 *
450 * Complexity: O(1)
451 *
452 * @param list The list to query (non-NULL).
453 * @return Non-zero if the list is sorted and 0 otherwise.
454 */
455
456 #if LISTIMPLEMENTED
457 extern void gl_ptr_sort(struct gl_list_t *list, int inc);
458 /**<
459 * <!-- PROCEDURE gl_ptr_sort(list,inc); -->
460 * <!-- struct gl_list_t *list; -->
461 * <!-- int inc; -->
462 *
463 * This will sort the list data using Quick Sort. It
464 * uses a somewhat intelligent pivot choice, so it is unlikely that the
465 * worst case of O(n^2) will arise. I however will not guarantee that.
466 * We will sort the list into order of decreasing order of address if
467 * inc == 0 and increasing order if increasing !=0.
468 * Which value of inc you use can drastically affect performance of
469 * other functions; consider your application carefully.<br><br>
470 *
471 * Complexity: worst case O(n^2) average case O(n*log(n)) <br><br>
472 * The multiplier is considerably smaller than for gl_sort, however.
473 */
474 #endif
475
476 extern void gl_sort(struct gl_list_t *list, CmpFunc func);
477 /**<
478 * Sorts the list in increasing order using Quick Sort. It
479 * uses a somewhat intelligent pivot choice, so it is unlikely that the
480 * worst case of O(n^2) will arise. This is not, however, guaranteed.
481 * The caller must furnish a procedure "func" that compares two list items
482 * and returns an integer > 0 if item1 > item2 and otherwise <= 0.
483 * NOTE: THE COMPARISON PROCEDURE SHOULD BE ABLE TO HANDLE NULL POINTERS
484 * GRACEFULLY. Neither the specified list nor func may not be NULL
485 * (checked by assertion).<br><br>
486 *
487 * Example: <pre>
488 * const struct itemtype *item1, *item2; // whatever type being stored in the list.
489 * int func(item1,item2);
490 * gl_sort(my_list, func); </pre>
491 *
492 * Complexity: worst case O(n^2) average case O(n*log(n))
493 *
494 * @param list The list to sort (non-NULL).
495 * @param func The comparison function to call during the sort.
496 */
497
498 #if LISTIMPLEMENTED
499 extern void gl_insert_ptr_sorted(struct gl_list_t *list, VOIDPTR ptr, int inc);
500 /**<
501 * <!-- PROCEDURE gl_insert_ptr_sorted(list,ptr,inc); -->
502 * <!-- struct gl_list_t *list; -->
503 * <!-- VOIDPTR ptr; -->
504 * <!-- int inc; -->
505 *
506 * This procedure will insert an item into the list in the position
507 * where it belongs to keep the list sorted. If inc != 0,
508 * sort will be in increasing order of address, else it will be
509 * in decreasing order of address.
510 * Which value of inc you use can drastically affect performance of
511 * other functions; consider your application carefully.<br><br>
512 *
513 * Example: <pre>
514 * struct data_t *item;
515 * item = (struct data_t *)malloc(sizeof(struct data_t));
516 * various assignments to item->
517 * gl_insert_ptr_sorted(list,item,0); * This stores item </pre>
518 *
519 * Complexity: O(length)
520 */
521 #endif
522
523 extern void gl_insert_sorted(struct gl_list_t *list, VOIDPTR ptr, CmpFunc func);
524 /**<
525 * Inserts an item into a sorted list in the position where it belongs to
526 * keep the list sorted. The specified func is used to compare to list items
527 * in the following way:
528 * - item1 > item2 returns > 0
529 * - item1 = item2 returns = 0
530 * - item1 < item2 returns < 0
531 * This function should be the same as used to gl_sort() the list
532 * If the list is not sorted, it will be sorted and the item added
533 * in the appropriate location. Neither the specified list nor
534 * func may be NULL, and the list must be expandable (checked
535 * by assertion).<br><br>
536 *
537 * Because any pointer type is convertible to a void pointer, you
538 * pass in a pointer to your data structure. It stores whatever pointer
539 * you give it.<br><br>
540 *
541 * Example: <pre>
542 * struct data_t *item;
543 * item = (struct data_t *)malloc(sizeof(struct data_t));
544 * various assignments to item->
545 * gl_insert_sorted(list,item,sortfunc); * This stores item </pre>
546 *
547 * Complexity: O(length)
548 *
549 * @param list The list to modify (non-NULL).
550 * @param ptr Pointer to data to append to the list.
551 * @param func The comparison function to call during the sort.
552 */
553
554 extern void gl_iterate(struct gl_list_t *list, void (*func)(VOIDPTR) );
555 /**<
556 * Executes the function func on all the members of the list.
557 * It will always execute the function on the items in the order
558 * they appear in the list, 1,2,3..gl_length(list). The function
559 * should handle NULL pointers as input gracefully. Neither the
560 * specified list nor the func may be NULL (checked by
561 * assertion).<br><br>
562 *
563 * Complexity: O(n*O(func))
564 *
565 * @param list The list to iterate through (non-NULL).
566 * @param func The function to execute for each list item.
567 */
568
569 extern unsigned long gl_ptr_search(CONST struct gl_list_t *list,
570 CONST VOIDPTR match,
571 int increasing);
572 /**<
573 * Searches the list for a specific item and returns the position
574 * where it is stored. If match is not found, the function returns 0.
575 * The definition of match is as follows:
576 * It will return item i iff (gl_fetch(list,i) == match).
577 * The specified list may not be NULL (checked by assertion).<br><br>
578 *
579 * If the list is sorted this function will use a binary search,
580 * otherwise it will search linearly. The binary search will proceed
581 * based on increasing. If you have the list sorted in increasing ptr
582 * order, give this increasing=1, else increasing=0.<br><br>
583 *
584 * CAUTION!! If the list is sorted by some other criteria than
585 * pointer address order, this function may erroneously return 0.
586 * If you give us an incorrect increasing, we may erroneously
587 * return 0. <br><br>
588 *
589 * Complexity: if gl_sorted(list) O(log gl_length(list))
590 * else O(gl_length(list))<br>
591 * Multiplier is better than for gl_search().
592 *
593 * @param list The list to search (non-NULL).
594 * @param match The pointer to search for in list.
595 * @param increasing TRUE if the list is sorted in increasing
596 * pointer order, FALSE otherwise.
597 * @return The position of match in the list [1..gl_length(list)],
598 * 0 if match not found.
599 */
600
601 extern unsigned long gl_search(CONST struct gl_list_t *list,
602 CONST VOIDPTR match,
603 CmpFunc func);
604 /**<
605 * Searches a list for a specified item and returns the position where
606 * it is stored. If match is not found, the function returns 0.
607 * The definition of match is as follows:
608 * It will return item i iff (*func)(gl_fetch(list,i),match) = 0.
609 * Neither the specified list nor func may be NULL (checked by
610 * assertion).<br><br>
611 *
612 * If the list is sorted this function will use a binary search, otherwise
613 * it will search linearly. The user must provide func, a comparison
614 * function returning:
615 * - item1 > item2 ==> 1 (actually it need only be > 0)
616 * - item1 = item2 ==> 0
617 * - item1 < item2 ==> -1 (actually it need only be < 0)
618 *
619 * Complexity: if gl_sorted(list) O(log gl_length(list))
620 * else O(gl_length(list))
621 *
622 * @param list The list to search (non-NULL).
623 * @param match The pointer to search for in list.
624 * @param func The comparison function to call during the search.
625 * @return The position of match in the list[1..gl_length(list)],
626 * 0 if match not found.
627 */
628
629 extern unsigned long gl_search_reverse(CONST struct gl_list_t *list,
630 CONST VOIDPTR match,
631 CmpFunc func);
632 /**<
633 * Searches a list for a specified item and returns the position where
634 * it is stored. This is similar to gl_search(), except that if the list
635 * is NOT sorted, it does a linear search starting from the last element in
636 * the list and working toward the first element. For sorted lists,
637 * this function calls gl_search() to do a binary search. Neither the
638 * specified list nor func may be NULL (checked by assertion).
639 *
640 * @param list The list to search (non-NULL).
641 * @param match The pointer to search for in list.
642 * @param func The comparison function to call during the search.
643 * @return The position of match in the list[1..gl_length(list)],
644 * 0 if match not found.
645 */
646
647 extern int gl_empty(CONST struct gl_list_t *list);
648 /**<
649 * Query whether the list is empty. An empty list has no items stored.
650 * The specified list may not be NULL (checked by assertion).
651 *
652 * Complexity: O(1)
653 *
654 * @param list The list to query (non-NULL).
655 * @return TRUE if the list is empty, FALSE otherwise.
656 */
657
658 extern int gl_unique_list(CONST struct gl_list_t *list);
659 /**<
660 * Query whether the pointers stored in the list are all unique.
661 * The specified list may be NULL, in which case TRUE is returned.
662 *
663 * Complexity: O(nlogn)
664 *
665 * @param list The list to query.
666 * @return TRUE if the pointers in the list are unique, FALSE otherwise.
667 */
668
669 extern void gl_delete(struct gl_list_t *list,
670 unsigned long pos,
671 int dispose);
672 /**<
673 * Deletes the item in position pos from the list.
674 * pos must be in the range [1..gl_length(list)], although pos = 0 is
675 * tolerated (and has no effect). The upper bound is checked by assertion.
676 * If dispose is true then the memory associated with the item will also
677 * be deallocated. The specified list may not be NULL (checked by
678 * assertion).<br><br>
679 *
680 * Complexity: O(gl_length(list)) <br>
681 * This is because all the list items to the right of the deleted
682 * item must be shuffled left one space.
683 *
684 * @param list The list to modify (non-NULL).
685 * @param pos The position of the item to remove [1..gl_length(list)].
686 * @param dispose If non-zero the item will be free'd;
687 * if 0 the item will not be deallocated.
688 * @todo Why does general/list:gl_delete() check for pos == 0? Should
689 * it be an ASSERTRANGE like other functions, or is there some
690 * reason to expect this lone function to be called with pos == 0?
691 */
692
693 extern void gl_reverse(struct gl_list_t *list);
694 /**<
695 * Reverses the ordering of the list.
696 * If the list given is marked as sorted, this function will
697 * leave it marked as sorted, though an inverse CmpFunc is now
698 * required for search/insertion. The specified list may be
699 * NULL, in which case no action is taken.<br><br>
700 *
701 * Complexity: O(gl_length(list))
702 *
703 * @param list The list to modify.
704 */
705
706 extern void gl_reset(struct gl_list_t *list);
707 /**<
708 * Resets the list to a *clean* state as if it had just been created.
709 * As such, the list will be considered as expandle and sorted but
710 * with a length of zero. The items in the list are NOT deallocated.
711 * The specified list may not be NULL (checked by assertion).<br><br>
712 *
713 * Complexity 1. <br>
714 * This is useful for a list that is being used as a scratch list,
715 * and needs to be *reset* between operations.
716 *
717 * @param list The list to reset (non-NULL).
718 */
719
720 extern struct gl_list_t *gl_copy(CONST struct gl_list_t *list);
721 /**<
722 * Copies a list. The copy of the list will have its own memory
723 * associated with it, but the items themselves are shared between the
724 * lists. That is, the copy of the items is shallow and the 2 lists will
725 * share pointers to the same memory locations. The starting list is not
726 * changed in any way. The specified list may not be NULL (checked by
727 * assertion). Destruction of the returned list is the responsibility
728 * of the caller, but be careful not to call gl_free_and_destroy() on both
729 * the original and copy. This will result in double deletion of the
730 * pointers and likely a crash.<br><br>
731 *
732 * Complexity O(gl_length(list))
733 *
734 * @param list The list to copy (non-NULL).
735 * @return A shallow copy of the list.
736 */
737
738 extern struct gl_list_t *gl_concat(CONST struct gl_list_t *list1,
739 CONST struct gl_list_t *list2);
740 /**<
741 * Concatenates two lists into a new list. Neither of the original
742 * lists is changed in any way. The list that is returned will contain
743 * the items in list1 followed by the items in list2. Neither list1
744 * list 2 may be NULL (checked by assertion). Destruction of the
745 * returned list is the responsibility of the caller.<br><br>
746 *
747 * Complexity O(gl_length(list1)+gl_length(list2))
748 *
749 * @param list1 The 1st list to append to the new list (non-NULL).
750 * @param list2 The 2nd list to append to the new list (non-NULL).
751 * @return A new list containing the items of list1 and list2 appended.
752 */
753
754 extern int gl_compare_ptrs(CONST struct gl_list_t *list1,
755 CONST struct gl_list_t *list2);
756 /**<
757 * Compares the data (ptrs or whatever) in two lists. Returns a code
758 * as follows:
759 * - -1 list1 < list2
760 * - 0 list1 == list2
761 * - 1 list1 > list2
762 * The comparison is performed on an item-by-item basis, with the relative
763 * values of the first different items found determining the "greater" list.
764 * If all items up to the length of the shorter list have equal values,
765 * the longer list is considered "greater". For pointers this is a weird
766 * function. But, we sometimes store ints in lists and want to sort lists
767 * of lists. This function does NOT tolerate NULL inputs. Calling it with
768 * a NULL pointer will abort the program.<br><br>
769 *
770 * Complexity O(SHORTER_OF(list1,list2))
771 *
772 * @param list1 The 1st list to compare (non-NULL).
773 * @param list2 The 2st list to compare (non-NULL).
774 * @return Returns -1 if list1 < list2, 1 if list1 > list 2, and 0 if the
775 * lists are equal.
776 * @todo Why does general/list:gl_compare_ptrs() use Asc_Panic()
777 * on a NULL pointer? Assertions used in rest of module.
778 */
779
780 extern void gl_set_sorted(struct gl_list_t *list, int TRUE_or_FALSE);
781 /**<
782 * Sets the sorted flag for the list based on TRUE_or_FALSE.
783 * Setting a list to sorted should be done only if you are sure
784 * that the list is sorted. The list may not be NULL (checked
785 * by assertion).
786 *
787 * @param list The list to modify (non-NULL).
788 */
789
790 extern int gl_expandable(struct gl_list_t *list);
791 /**<
792 * Query whether the specified list is expandable. The specified list
793 * may not be NULL (checked by assertion).
794 *
795 * Complexity: O(1)
796 *
797 * @param list The list to query (non-NULL).
798 * @return Non-zero if the list is expandable and 0 otherwise.
799 */
800
801 extern void gl_set_expandable(struct gl_list_t *list, int TRUE_or_FALSE);
802 /**<
803 * Sets the expandable flag for the list based on TRUE_or_FALSE.
804 * All lists are expandable until this flag is explicitly cleared.
805 * Setting a list to non-expandable should be done only when you are
806 * quite sure that you want this. It is sometimes useful to have a
807 * list not be expandable, as in the case when someone is depending
808 * on the address of a list member. However, list append and insert
809 * functions will fail if the list is not expandable. The list may
810 * not be NULL (checked by assertion).
811 *
812 * @param list The list to modify (non-NULL).
813 */
814
815 extern VOIDPTR *gl_fetchaddr(CONST struct gl_list_t *list,
816 unsigned long pos);
817 /**<
818 * Returns the address of the pointer stored at position pos. This
819 * is sometimes useful for ptr to ptr manipulation. pos must be in
820 * the range [1..gl_length(list). The specified list may not be NULL.
821 * Both of these conditions are checked by assertion.
822 *
823 * @param list The list to query (non-NULL).
824 * @param pos The position of the data to fetch, [1..gl_length(list).
825 * @return The address of the pointer as position pos.
826 */
827
828 extern void gl_emptyrecycler(void);
829 /**<
830 * Empties the list recycler.
831 * To improve runtime performance, this list module trys to reuse destroyed
832 * lists. However, it may be beneficial to empty recycling bin from time
833 * to time. The most appropriate time for this is before shutdown and
834 * perhaps after an instantiation. If LISTRECYCLERDEBUG is defined, a
835 * summary of the recycler status is also reported on stdout.
836 */
837
838 extern void gl_reportrecycler(FILE *fp);
839 /**<
840 * Prints a report of the recycler status to fp.
841 * To improve runtime performance, this list module trys to reuse destroyed
842 * lists. This function reports the recycler status. Note that the report is
843 * only printed if LISTRECYCLERDEBUG is defined. The specified fp may not be
844 * NULL (checked by assertion).
845 *
846 * @param fp Pointer to file stream to receive report.
847 */
848
849 #endif /* ASC_LIST_H */
850

john.pye@anu.edu.au
ViewVC Help
Powered by ViewVC 1.1.22