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

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