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

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

Parent Directory Parent Directory | Revision Log Revision Log


Revision 592 - (hide annotations) (download) (as text)
Fri May 12 09:50:57 2006 UTC (14 years, 10 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 johnpye 485 /* ASCEND modelling environment
2     Copyright (C) 1990, 1993, 1994 Thomas Guthrie Epperly
3     Copyright (C) 2006 Carnegie Mellon University
4 aw0a 1
5 johnpye 485 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 jds 59
10 johnpye 485 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 aw0a 1
15 johnpye 485 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 johnpye 67 #ifndef ASC_LIST_H
82     #define ASC_LIST_H
83 aw0a 1
84 johnpye 485 #include <utilities/ascConfig.h>
85    
86 aw0a 1 #ifndef TRUE
87     #define TRUE 1
88     #endif
89     #ifndef FALSE
90     #define FALSE 0
91     #endif
92 jds 54 #define LISTIMPLEMENTED 0 /**< BAA_DEBUG changes that need work */
93 aw0a 1
94 jds 54 /*
95     * The following bit fields are defined for the gl_list flags
96 aw0a 1 */
97 jds 54 #define gsf_SORTED 0x1 /**< gl_list_t flag: list is sorted. */
98     #define gsf_EXPANDABLE 0x2 /**< gl_list_t flag: list is expandable. */
99 aw0a 1
100 jds 54 /** List data structure. */
101 aw0a 1 struct gl_list_t {
102 jds 54 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 aw0a 1 };
107    
108 jds 54 /** Generic comparator for sorts and searches. */
109 aw0a 1 typedef int (*CmpFunc)(CONST VOIDPTR, CONST VOIDPTR);
110    
111 jds 54 /** Generic destroyer for iterations. */
112 aw0a 1 typedef void (*DestroyFunc)(VOIDPTR);
113    
114 jds 216 /** Generic function called during iterations. */
115     typedef void (*IterateFunc)(VOIDPTR);
116    
117 johnpye 592 ASC_DLLSPEC(void) gl_init(void);
118 jds 54 /**<
119 jds 59 * Initializes the list recycler control table.
120 aw0a 1 * 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 jds 59 * This function may be called more than once, although in general
124     * there is no reason to do so.
125 aw0a 1 */
126    
127 ben.allan 14 #ifdef ASC_NO_POOL
128     #define LISTUSESPOOL FALSE
129     #else
130 aw0a 1 #define LISTUSESPOOL TRUE
131 ben.allan 14 #endif
132 jds 54 /**<
133     * Flag to select list management strategy.
134 aw0a 1 * LISTUSESPOOL == TRUE allows the list module to use pool.[ch] to
135 jds 54 * manage list memory overhead. Performance is enhanced this way.<br><br>
136 aw0a 1 *
137     * LISTUSESPOOL == FALSE removes the pool dependency completely, at
138 jds 54 * a performance penalty.<br><br>
139 aw0a 1 *
140     * The following 3 functions work for either value of LISTUSESPOOL
141 jds 54 * in some appropriate fashion: gl_init_pool(), gl_destroy_pool(),
142     * gl_report_pool().
143 aw0a 1 */
144 johnpye 480
145 aw0a 1 extern void gl_init_pool(void);
146 jds 59 /**<
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 aw0a 1 */
154    
155 johnpye 592 ASC_DLLSPEC(void) gl_destroy_pool(void);
156 jds 59 /**<
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 aw0a 1 */
165    
166 jds 59 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 jds 54 extern void gl_report_pool(FILE *f);
176 jds 59 /**<
177     * Prints a report on the recycle pool to f.
178     *
179     * @param f Open file stream to which to print report.
180 aw0a 1 */
181    
182 johnpye 522 ASC_DLLSPEC(struct gl_list_t *) gl_create(unsigned long capacity);
183 jds 54 /**<
184 jds 59 * 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 aw0a 1 *
191 jds 59 * 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 aw0a 1 *
195 jds 59 * 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 aw0a 1 * Because memory proportional to capacity is allocated, depending on
200     * your memory management system, this could be proportional to the
201     * initial capacity.
202 jds 59 *
203     * @param capacity The desired initial list capacity.
204     * @return Returns a pointer to the new empty gl_list_t.
205 aw0a 1 */
206    
207 johnpye 522 ASC_DLLSPEC(void ) gl_free_and_destroy(struct gl_list_t *list);
208 jds 54 /**<
209 jds 59 * 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 aw0a 1 *
216 jds 59 * 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 aw0a 1 *
220 jds 59 * Complexity: worst case O(n) <br>
221     * where n is the size of the list. This is because memory proportional
222 aw0a 1 * to n must be deallocated. If that time is not proportional to the
223     * size then it should be O(1)
224 jds 59 *
225     * @param list A pointer to the gl_list_t to destroy.
226 aw0a 1 */
227    
228 johnpye 522 ASC_DLLSPEC(void ) gl_destroy(struct gl_list_t *list);
229 jds 59 /**<
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 aw0a 1 *
240     * If you want the items to be freed (a la the old gl_destroy(list,1))
241 jds 59 * call gl_free_and_destroy() instead.<br><br>
242 aw0a 1 *
243 jds 59 * Complexity: worst case O(n) <br>
244 aw0a 1 * 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 jds 59 *
248     * @param list A pointer to the gl_list_t to destroy.
249 aw0a 1 */
250    
251     #ifndef NDEBUG
252 jds 54 #define gl_fetch(list,pos) gl_fetchF((list),(pos))
253 aw0a 1 #else
254 jds 54 #define gl_fetch(list,pos) ((list)->data[((pos)-1)])
255 aw0a 1 #endif
256 jds 54 /**<
257 jds 59 * Retrieves the data item stored at position pos in the list.
258 aw0a 1 * This function is used to access the list elements. It returns the
259 jds 59 * 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 aw0a 1 *
263 jds 59 * 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 aw0a 1 *
267 jds 54 * Example: <pre>
268     * struct data_t *item;
269     * item = (struct data_t *)gl_fetch(datalist,4); </pre>
270 aw0a 1 *
271     * Complexity: O(1)
272 jds 54 *
273 jds 59 * @param list CONST struct gl_list_t*, the list to query (non-NULL).
274 jds 54 * @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 aw0a 1 */
278 jds 59
279 johnpye 490 ASC_DLLSPEC(VOIDPTR) gl_fetchF(CONST struct gl_list_t *list, unsigned long pos);
280 jds 54 /**<
281     * Implementation function for gl_fetch() (debug mode).
282     * Do not call this function directly - use gl_fetch() instead.
283     */
284 aw0a 1
285 johnpye 522 ASC_DLLSPEC(void ) gl_store(struct gl_list_t *list, unsigned long pos, VOIDPTR ptr);
286 jds 59 /**<
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 aw0a 1 *
292 jds 59 * Because any pointer type is convertible to a void pointer, you
293 jds 54 * pass in a pointer to your data structure. It stores whatever pointer
294     * you give it.<br><br>
295 aw0a 1 *
296 jds 54 * 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 aw0a 1 *
302 jds 54 * COMPLEXITY: O(1)
303 aw0a 1 *
304 jds 59 * @param list The list to modify (non-NULL).
305     * @param pos Index of position to modify, [1..gl_length(list)].
306 jds 54 * @param ptr Pointer to data to store at index pos.
307 aw0a 1 */
308    
309 johnpye 522 ASC_DLLSPEC(void ) gl_append_ptr(struct gl_list_t *list, VOIDPTR ptr);
310 jds 59 /**<
311 jds 54 * <!-- PROCEDURE gl_append_ptr(list,ptr); -->
312     * <!-- struct gl_list_t *list; -->
313     * <!-- VOIDPTR ptr; -->
314 aw0a 1 *
315 jds 59 * 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 aw0a 1 *
322 jds 59 * 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 jds 54 * you give it.<br><br>
325 aw0a 1 *
326 jds 54 * 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 aw0a 1 *
332 jds 59 * Complexity: worst case O(n) <br>
333 aw0a 1 * 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 jds 59 *
337     * @param list The list to modify (non-NULL).
338     * @param ptr Pointer to data to append to the list.
339 aw0a 1 */
340    
341 jds 54 extern void gl_fast_append_ptr(struct gl_list_t *list, VOIDPTR ptr);
342     /**<
343 jds 59 * 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 aw0a 1 *
351 jds 59 * 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 jds 54 * you give it.<br><br>
354 aw0a 1 *
355 jds 59 * Example: See gl_append_ptr.<br>
356 aw0a 1 * 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 jds 59 * This is faster than gl_store().<br><br>
359 aw0a 1 *
360     * Complexity: O(1)
361 jds 59 *
362     * @param list The list to modify (non-NULL).
363     * @param ptr Pointer to data to append to the list.
364 aw0a 1 */
365    
366 jds 59 extern void gl_append_list(struct gl_list_t *extendlist,
367 jds 54 struct gl_list_t *list);
368     /**<
369 jds 59 * 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 aw0a 1 *
376 jds 59 * No new list is created. extendlist is changed if there is data in list.
377 jds 54 * list is never changed in any case.<br><br>
378 aw0a 1 *
379 jds 54 * Example: <pre>
380     * gl_append_list(oldlist,addlist);
381     * This stores contents of addlist at the end of oldlist </pre>
382 aw0a 1 *
383 jds 59 * Complexity: worst case O(gl_length(list)+gl_length(extendlist)) <br>
384 aw0a 1 * 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 jds 59 *
388     * @param extendlist The list to modify (non-NULL).
389     * @param list The list to append to extendlist (non-NULL).
390 aw0a 1 */
391    
392     #ifndef NDEBUG
393 jds 54 #define gl_length(list) gl_lengthF(list)
394 aw0a 1 #else
395 jds 54 #define gl_length(list) ((list)->length)
396 aw0a 1 #endif
397 jds 54 /**<
398 jds 59 * 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 aw0a 1 *
404     * Complexity: O(1)
405 jds 54 *
406 jds 59 * @param list CONST struct gl_list_t*. the list to query (non-NULL).
407 jds 54 * @return The length as an unsigned long.
408     * @see gl_lengthF()
409 aw0a 1 */
410 johnpye 490 ASC_DLLSPEC(unsigned long) gl_lengthF(CONST struct gl_list_t *list);
411 jds 54 /**<
412     * Implementation function for gl_length() (debug mode).
413     * Do not call this function directly - use gl_length() instead.
414 jds 59 *
415     * @param list CONST struct gl_list_t*. the list to query (non-NULL).
416 jds 54 */
417 aw0a 1
418     extern unsigned long gl_safe_length(CONST struct gl_list_t *list);
419 jds 54 /**<
420 jds 59 * 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 aw0a 1 *
424 jds 59 * Complexity: O(1)
425 aw0a 1 *
426 jds 59 * @param list The list to query.
427     * @return The number of items stored in list.
428 aw0a 1 */
429    
430 jds 54 extern unsigned long gl_capacity(CONST struct gl_list_t *list);
431     /**<
432 jds 59 * 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 aw0a 1 *
438 jds 59 * Complexity: O(1)
439 aw0a 1 *
440 jds 59 * @param list The list to query.
441     * @return The number of items that can be stored in list without expanding.
442 aw0a 1 */
443    
444 johnpye 592 ASC_DLLSPEC(int) gl_sorted(CONST struct gl_list_t *list);
445 jds 54 /**<
446 jds 59 * Query whether the specified list is sorted. A list having 0 or 1
447 johnpye 480 * element is always sorted. The specified list may not be NULL
448 jds 59 * (checked by assertion).
449 aw0a 1 *
450     * Complexity: O(1)
451 jds 59 *
452     * @param list The list to query (non-NULL).
453     * @return Non-zero if the list is sorted and 0 otherwise.
454 aw0a 1 */
455    
456     #if LISTIMPLEMENTED
457 jds 54 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 aw0a 1 *
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 jds 54 * other functions; consider your application carefully.<br><br>
470 aw0a 1 *
471 jds 54 * Complexity: worst case O(n^2) average case O(n*log(n)) <br><br>
472 aw0a 1 * The multiplier is considerably smaller than for gl_sort, however.
473     */
474     #endif
475    
476 johnpye 522 ASC_DLLSPEC(void ) gl_sort(struct gl_list_t *list, CmpFunc func);
477 jds 54 /**<
478 jds 59 * 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 johnpye 480 * GRACEFULLY. Neither the specified list nor func may not be NULL
485 jds 59 * (checked by assertion).<br><br>
486 aw0a 1 *
487 jds 59 * 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 aw0a 1 *
492 jds 59 * Complexity: worst case O(n^2) average case O(n*log(n))
493 aw0a 1 *
494 jds 59 * @param list The list to sort (non-NULL).
495     * @param func The comparison function to call during the sort.
496 aw0a 1 */
497    
498     #if LISTIMPLEMENTED
499 jds 54 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 aw0a 1 *
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 jds 54 * other functions; consider your application carefully.<br><br>
512 aw0a 1 *
513 jds 54 * 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 aw0a 1 * Complexity: O(length)
520     */
521     #endif
522    
523 johnpye 522 ASC_DLLSPEC(void ) gl_insert_sorted(struct gl_list_t *list, VOIDPTR ptr, CmpFunc func);
524 jds 54 /**<
525 jds 59 * 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 jds 54 * - item1 > item2 returns > 0
529     * - item1 = item2 returns = 0
530     * - item1 < item2 returns < 0
531 jds 59 * This function should be the same as used to gl_sort() the list
532 johnpye 480 * 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 jds 59 * by assertion).<br><br>
536 aw0a 1 *
537 jds 59 * 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 jds 54 * you give it.<br><br>
540 aw0a 1 *
541 jds 54 * 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 aw0a 1 * Complexity: O(length)
548 jds 59 *
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 aw0a 1 */
553    
554 johnpye 490 ASC_DLLSPEC(void) gl_iterate(struct gl_list_t *list, IterateFunc func);
555 jds 54 /**<
556 jds 59 * 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 johnpye 480 * specified list nor the func may be NULL (checked by
561 jds 59 * assertion).<br><br>
562 aw0a 1 *
563     * Complexity: O(n*O(func))
564 jds 59 *
565     * @param list The list to iterate through (non-NULL).
566     * @param func The function to execute for each list item.
567 aw0a 1 */
568 johnpye 480
569 jds 54 extern unsigned long gl_ptr_search(CONST struct gl_list_t *list,
570     CONST VOIDPTR match,
571 jds 59 int increasing);
572 jds 54 /**<
573 jds 59 * 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 aw0a 1 * The definition of match is as follows:
576 jds 59 * 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 aw0a 1 *
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 johnpye 480 * based on increasing. If you have the list sorted in increasing ptr
582 jds 59 * order, give this increasing=1, else increasing=0.<br><br>
583 aw0a 1 *
584 johnpye 480 * CAUTION!! If the list is sorted by some other criteria than
585 jds 59 * pointer address order, this function may erroneously return 0.
586 johnpye 480 * If you give us an incorrect increasing, we may erroneously
587 jds 59 * return 0. <br><br>
588     *
589 aw0a 1 * Complexity: if gl_sorted(list) O(log gl_length(list))
590 jds 59 * 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 aw0a 1 */
600    
601 johnpye 522 ASC_DLLSPEC(unsigned long ) gl_search(CONST struct gl_list_t *list,
602 jds 54 CONST VOIDPTR match,
603     CmpFunc func);
604     /**<
605 jds 59 * 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 aw0a 1 * The definition of match is as follows:
608 jds 59 * 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 aw0a 1 *
612     * If the list is sorted this function will use a binary search, otherwise
613 jds 59 * it will search linearly. The user must provide func, a comparison
614     * function returning:
615 jds 54 * - item1 > item2 ==> 1 (actually it need only be > 0)
616     * - item1 = item2 ==> 0
617     * - item1 < item2 ==> -1 (actually it need only be < 0)
618 aw0a 1 *
619     * Complexity: if gl_sorted(list) O(log gl_length(list))
620     * else O(gl_length(list))
621 jds 59 *
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 aw0a 1 */
628    
629 jds 54 extern unsigned long gl_search_reverse(CONST struct gl_list_t *list,
630     CONST VOIDPTR match,
631     CmpFunc func);
632     /**<
633 jds 59 * 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 aw0a 1 * the list and working toward the first element. For sorted lists,
637 johnpye 480 * this function calls gl_search() to do a binary search. Neither the
638 jds 59 * specified list nor func may be NULL (checked by assertion).
639 aw0a 1 *
640 jds 59 * @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 aw0a 1 */
646    
647 jds 54 extern int gl_empty(CONST struct gl_list_t *list);
648     /**<
649 jds 59 * 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 aw0a 1 *
652     * Complexity: O(1)
653 jds 59 *
654     * @param list The list to query (non-NULL).
655     * @return TRUE if the list is empty, FALSE otherwise.
656 aw0a 1 */
657    
658 jds 54 extern int gl_unique_list(CONST struct gl_list_t *list);
659     /**<
660 jds 59 * 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 aw0a 1 *
663     * Complexity: O(nlogn)
664 jds 59 *
665     * @param list The list to query.
666     * @return TRUE if the pointers in the list are unique, FALSE otherwise.
667 aw0a 1 */
668    
669 johnpye 522 ASC_DLLSPEC(void ) gl_delete(struct gl_list_t *list,
670 jds 54 unsigned long pos,
671     int dispose);
672     /**<
673 jds 59 * 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 jds 61 * assertion).<br><br>
679 aw0a 1 *
680 jds 59 * Complexity: O(gl_length(list)) <br>
681 aw0a 1 * This is because all the list items to the right of the deleted
682     * item must be shuffled left one space.
683 jds 59 *
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 aw0a 1 */
692    
693 jds 54 extern void gl_reverse(struct gl_list_t *list);
694 jds 59 /**<
695     * Reverses the ordering of the list.
696 aw0a 1 * If the list given is marked as sorted, this function will
697     * leave it marked as sorted, though an inverse CmpFunc is now
698 jds 59 * required for search/insertion. The specified list may be
699     * NULL, in which case no action is taken.<br><br>
700     *
701 aw0a 1 * Complexity: O(gl_length(list))
702 jds 59 *
703     * @param list The list to modify.
704 aw0a 1 */
705    
706 johnpye 592 ASC_DLLSPEC(void) gl_reset(struct gl_list_t *list);
707 jds 54 /**<
708 jds 59 * 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 aw0a 1 *
713 jds 59 * Complexity 1. <br>
714 aw0a 1 * This is useful for a list that is being used as a scratch list,
715     * and needs to be *reset* between operations.
716 jds 59 *
717     * @param list The list to reset (non-NULL).
718 aw0a 1 */
719    
720 jds 54 extern struct gl_list_t *gl_copy(CONST struct gl_list_t *list);
721 jds 59 /**<
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 johnpye 480 * assertion). Destruction of the returned list is the responsibility
728 jds 59 * of the caller, but be careful not to call gl_free_and_destroy() on both
729 johnpye 480 * the original and copy. This will result in double deletion of the
730 jds 59 * pointers and likely a crash.<br><br>
731 aw0a 1 *
732 jds 59 * Complexity O(gl_length(list))
733 aw0a 1 *
734 jds 59 * @param list The list to copy (non-NULL).
735     * @return A shallow copy of the list.
736 aw0a 1 */
737    
738 jds 54 extern struct gl_list_t *gl_concat(CONST struct gl_list_t *list1,
739     CONST struct gl_list_t *list2);
740     /**<
741 jds 59 * 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 aw0a 1 *
747 jds 59 * Complexity O(gl_length(list1)+gl_length(list2))
748 aw0a 1 *
749 jds 59 * @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 aw0a 1 */
753    
754 jds 59 extern int gl_compare_ptrs(CONST struct gl_list_t *list1,
755 jds 54 CONST struct gl_list_t *list2);
756     /**<
757 jds 59 * 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 aw0a 1 *
770     * Complexity O(SHORTER_OF(list1,list2))
771 jds 59 *
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 aw0a 1 */
779    
780 jds 59 extern void gl_set_sorted(struct gl_list_t *list, int TRUE_or_FALSE);
781 jds 54 /**<
782 johnpye 480 * 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 jds 59 * 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 aw0a 1 */
789    
790 jds 59 extern int gl_expandable(struct gl_list_t *list);
791 jds 54 /**<
792 jds 59 * 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 aw0a 1 */
800    
801 jds 59 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 johnpye 480 * 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 jds 59 * not be NULL (checked by assertion).
811     *
812     * @param list The list to modify (non-NULL).
813     */
814    
815 jds 54 extern VOIDPTR *gl_fetchaddr(CONST struct gl_list_t *list,
816     unsigned long pos);
817     /**<
818 jds 59 * 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 aw0a 1 */
827    
828 johnpye 592 ASC_DLLSPEC(void) gl_emptyrecycler(void);
829 jds 54 /**<
830 jds 59 * Empties the list recycler.
831 aw0a 1 * 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 jds 59 * perhaps after an instantiation. If LISTRECYCLERDEBUG is defined, a
835     * summary of the recycler status is also reported on stdout.
836 aw0a 1 */
837    
838 jds 54 extern void gl_reportrecycler(FILE *fp);
839     /**<
840 jds 59 * Prints a report of the recycler status to fp.
841 aw0a 1 * To improve runtime performance, this list module trys to reuse destroyed
842 jds 59 * 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 aw0a 1 */
848    
849 johnpye 67 #endif /* ASC_LIST_H */
850 aw0a 1

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