/[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 592 - (show annotations) (download) (as text)
Fri May 12 09:50:57 2006 UTC (14 years, 8 months ago) by johnpye
File MIME type: text/x-chdr
File size: 34573 byte(s)
Working on adding some more export symbols, for purpose of getting Jerry's test suite to work with SCons build.
1 /* ASCEND modelling environment
2 Copyright (C) 1990, 1993, 1994 Thomas Guthrie Epperly
3 Copyright (C) 2006 Carnegie Mellon University
4
5 This program is free software; you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published by
7 the Free Software Foundation; either version 2, or (at your option)
8 any later version.
9
10 This program is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 GNU General Public License for more details.
14
15 You should have received a copy of the GNU General Public License
16 along with this program; if not, write to the Free Software
17 Foundation, Inc., 59 Temple Place - Suite 330,
18 Boston, MA 02111-1307, USA.
19 *//**
20 @file
21 List Module.
22
23 The purpose of this module is to provide a kind of flexible array.
24 The flexible array has two interesting characteristics. It allows
25 contant time(O(1)) retrieval of list items and it is almost infinitely
26 extendable (i.e. has no preset limit on the number of items in the list).
27 It does not use much extra memory while providing these services.<br><br>
28
29 The list only stores pointers to items as VOIDPTR (void *). This is
30 an advantage, in that the user has the flexibility to store pointers to
31 any data type in the list. It is also a disadvanatage, since the data
32 structure is not type safe and the user must carefully keep track of
33 what is stored in the list.<br><br>
34
35 This module provides a standard set of list type operations. Each includes
36 some predictions about the efficiency of that operation. Any modification
37 of these procedures should live up to those claims.
38
39 Requires:
40 #include <stdio.h>
41 #include "utilities/ascConfig.h"
42 #include "compiler/compiler.h"
43 *//*
44 by Tom Epperly
45 Version: $Revision: 1.3 $
46 Version control file: $RCSfile: list.h,v $
47 Date last modified: $Date: 1998/02/19 13:03:22 $
48 Last modified by: $Author: ballan $
49
50 Any bugs or suggestions can be sent to:
51
52 te07@edrc.cmu.edu or te07@andrew.cmu.edu or epperly@osnome.che.wisc.edu
53 Tom Epperly
54 314 South Orchard Street
55 Madison, WI 53715-1542
56
57 Also please copy any bugs or suggestions to ascend+developers@cs.cmu.edu
58
59 This utility depends on ascmalloc.[ch] and (optionally) pool.[ch]
60
61 Change Log
62 2/26/88 added gl_copy, gl_concat
63 3/31/88 added additional commenting
64 2/18/96 added defines when -DNDEBUG is active. We can't
65 afford the calls in a production compiler. (Ben Allan)
66 2/23/96 Added recycling feature to reuse gl_lists. (TGWE)
67 3/25/96 Improved recycling feature. (Ben Allan)
68 3/30/96 Took dispose flag off gl_destroy and added a mirror
69 function gl_free_and_destroy to take its place.
70 Added pooled list heads (optional) which depends on
71 pool.[ch] and improves performance substantially.
72 Tuned to large applications. (Ben Allan)
73 9/9/96 Changed flags from struct to int. (Ben Allan)
74 10/2/96 Added switch over -DMOD_REALLOC to use ascreallocPURE.
75 If this file is compiled -DMOD_REALLOC, purify leaks of
76 list->data are real, OTHERWISE it may be noise.
77 Skipping the call to gl_init may also help dianosis.
78 9/20/97 Added gl_compare_ptrs.
79 */
80
81 #ifndef ASC_LIST_H
82 #define ASC_LIST_H
83
84 #include <utilities/ascConfig.h>
85
86 #ifndef TRUE
87 #define TRUE 1
88 #endif
89 #ifndef FALSE
90 #define FALSE 0
91 #endif
92 #define LISTIMPLEMENTED 0 /**< BAA_DEBUG changes that need work */
93
94 /*
95 * The following bit fields are defined for the gl_list flags
96 */
97 #define gsf_SORTED 0x1 /**< gl_list_t flag: list is sorted. */
98 #define gsf_EXPANDABLE 0x2 /**< gl_list_t flag: list is expandable. */
99
100 /** List data structure. */
101 struct gl_list_t {
102 VOIDPTR *data; /**< The data. */
103 unsigned long length; /**< Number of items used. */
104 unsigned long capacity; /**< Capacity of list. */
105 unsigned int flags; /**< Status flags. */
106 };
107
108 /** Generic comparator for sorts and searches. */
109 typedef int (*CmpFunc)(CONST VOIDPTR, CONST VOIDPTR);
110
111 /** Generic destroyer for iterations. */
112 typedef void (*DestroyFunc)(VOIDPTR);
113
114 /** Generic function called during iterations. */
115 typedef void (*IterateFunc)(VOIDPTR);
116
117 ASC_DLLSPEC(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 ASC_DLLSPEC(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 ASC_DLLSPEC(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 ASC_DLLSPEC(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 ASC_DLLSPEC(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 ASC_DLLSPEC(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 ASC_DLLSPEC(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 ASC_DLLSPEC(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 ASC_DLLSPEC(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 ASC_DLLSPEC(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 ASC_DLLSPEC(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 ASC_DLLSPEC(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 ASC_DLLSPEC(void) gl_iterate(struct gl_list_t *list, IterateFunc func);
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 ASC_DLLSPEC(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 ASC_DLLSPEC(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 ASC_DLLSPEC(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 ASC_DLLSPEC(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