3 @brief Implementation of osrfList, sort of like a vector class.
6 #include <opensrf/osrf_list.h>
7 /** @brief The initial size of the array when none is specified */
8 #define OSRF_LIST_DEFAULT_SIZE 48 /* most opensrf lists are small... */
9 /** @brief How many slots to add at a time when the array grows */
10 #define OSRF_LIST_INC_SIZE 256
11 //#define OSRF_LIST_MAX_SIZE 10240
14 @brief Create a new osrfList with OSRF_LIST_DEFAULT_SIZE slots.
15 @return A pointer to the new osrfList.
17 The calling code is responsible for freeing the osrfList by calling osrfListFree().
19 osrfList* osrfNewList() {
20 return osrfNewListSize( OSRF_LIST_DEFAULT_SIZE );
24 @brief Create a new osrfList with a specified number of slots.
25 @param size How many pointers to store initially.
26 @return A pointer to the new osrfList.
28 The calling code is responsible for freeing the osrfList by calling osrfListFree().
30 osrfList* osrfNewListSize( unsigned int size ) {
32 OSRF_MALLOC(list, sizeof(osrfList));
34 list->freeItem = NULL;
35 if( size <= 0 ) size = 16;
37 OSRF_MALLOC( list->arrlist, list->arrsize * sizeof(void*) );
39 // Nullify all pointers in the array
42 for( i = 0; i < list->arrsize; ++i )
43 list->arrlist[ i ] = NULL;
50 @brief Add a pointer to the end of the array.
51 @param list A pointer to the osrfList
52 @param item A pointer to be added to the list.
53 @return Zero if successful, or -1 if the list parameter is NULL.
55 The item pointer is stored one position past the last slot that might be in use. The calling
56 code should, in general, make no assumptions about where that position is. See the discussion
57 of osrfListGetCount() for the dirty details.
59 int osrfListPush( osrfList* list, void* item ) {
60 if(!(list)) return -1;
61 osrfListSet( list, item, list->size );
66 @brief Store a pointer in the first unoccupied slot.
67 @param list A pointer to the osrfList.
68 @param item The pointer to be stored.
69 @return If successful, the number of slots currently in use, or -1 if either of the
72 Find the lowest-numbered position holding a NULL and overwrite it with the specified
75 The meaning of the return value (other than -1) is fuzzy and probably not useful,
76 because some of the slots counted as "in use" may in fact hold NULLs.
78 int osrfListPushFirst( osrfList* list, void* item ) {
79 if(!(list && item)) return -1;
81 for( i = 0; i < list->size; i++ )
82 if(!list->arrlist[i]) break;
83 osrfListSet( list, item, i );
88 @brief Store a pointer at a specified position in an osrfList.
89 @param list A pointer to the osrfList.
90 @param item The pointer to be stored.
91 @param position Where to store it (a zero-based subscript).
92 @return A pointer to the previous occupant of the specified slot, if any, or NULL if
93 it was unoccupied, or if we have freed the occupant.
95 If the pointer previously stored in the specified slot is not NULL, then the behavior
96 depends on whether the calling code has provided a callback function for freeing stored
97 items. If there is such a callback function, we call it for the previously stored
98 pointer, and return NULL. Otherwise we return the previously stored pointer, so that
99 the calling code can free it if it needs to.
101 If the specified position is beyond the physical bounds of the array, we replace the
102 existing array with one that's big enough. This replacement is transparent to the
105 void* osrfListSet( osrfList* list, void* item, unsigned int position ) {
106 if(!list) return NULL;
108 int newsize = list->arrsize;
110 while( position >= newsize )
111 newsize += OSRF_LIST_INC_SIZE;
113 if( newsize > list->arrsize ) { /* expand the list if necessary */
115 OSRF_MALLOC(newarr, newsize * sizeof(void*));
117 // Copy the old pointers, and nullify the new ones
120 for( i = 0; i < list->arrsize; i++ )
121 newarr[i] = list->arrlist[i];
122 for( ; i < newsize; i++ )
125 list->arrlist = newarr;
126 list->arrsize = newsize;
129 void* olditem = osrfListRemove( list, position );
130 list->arrlist[position] = item;
131 if( list->size <= position ) list->size = position + 1;
137 @brief Fetch the pointer stored at a specified position.
138 @param list A pointer to an osrfList.
139 @param position A zero-based index specifying which item to fetch.
140 @return The pointer stored at the specified position, if any, or NULL.
142 The contents of the osrfList are unchanged.
144 If either parameter is invalid, the return value is NULL.
146 void* osrfListGetIndex( const osrfList* list, unsigned int position ) {
147 if(!list || position >= list->size) return NULL;
148 return list->arrlist[position];
152 @brief Free an osrfList, and, optionally, everything in it.
153 @param list A pointer to the osrfList to be freed.
155 If the calling code has specified a function for freeing items, it is called for every
156 non-NULL pointer in the array.
158 void osrfListFree( osrfList* list ) {
161 if( list->freeItem ) {
163 for( i = 0; i < list->size; i++ ) {
164 if( (val = list->arrlist[i]) )
174 @brief Make an osrfList empty.
175 @param list Pointer to the osrfList to be cleared.
177 Delete every item in the list. If a callback function is defined for freeing the items,
178 call it for every item.
180 void osrfListClear( osrfList* list ) {
184 for( i = 0; i < list->size; ++i ) {
185 if( list->freeItem && list->arrlist[ i ] )
186 list->freeItem( list->arrlist[ i ] );
187 list->arrlist[ i ] = NULL;
194 @brief Exchange the contents of two osrfLists.
195 @param one Pointer to the first osrfList.
196 @param two Pointer to the second osrfList.
198 After the call, the first list contains what had been the contents of the second,
199 and vice versa. This swap also works if the two parameters point to the same
200 list; i.e. there is no net effect.
202 If either parameter is NULL, nothing happens.
204 void osrfListSwap( osrfList* one, osrfList* two ) {
206 osrfList temp = *one;
213 @brief Remove the pointer from a specified position.
214 @param list A pointer to the osrfList.
215 @param position A zero-based index identifying the pointer to be removed.
216 @return A copy of the pointer removed, or NULL if the item was freed.
218 Returns NULL if either parameter is invalid. Otherwise:
220 If a callback function has been installed for freeing the item to which the pointer
221 points, it is called, and osrfListRemove returns NULL. Otherwise it returns the pointer
222 at the specified position in the array. In either case it overwrites the pointer in
225 Note that other positions in the array are not affected; i.e. osrfListRemove does NOT
226 shift other pointers down to fill in the hole left by the removal.
228 void* osrfListRemove( osrfList* list, unsigned int position ) {
229 if(!list || position >= list->size) return NULL;
231 void* olditem = list->arrlist[position];
232 list->arrlist[position] = NULL;
233 if( list->freeItem ) {
234 list->freeItem(olditem);
238 if( position == list->size - 1 ) list->size--;
243 @brief Remove a pointer from a specified position and return it.
244 @param list A pointer to the osrfList.
245 @param position A zero-based subscript identifying the pointer to be extracted.
246 @return The pointer at the specified position.
248 This function is identical to osrfListRemove(), except that it never frees the item
249 to which the pointer points, even if an item-freeing function has been designated.
251 void* osrfListExtract( osrfList* list, unsigned int position ) {
252 if(!list || position >= list->size) return NULL;
254 void* olditem = list->arrlist[position];
255 list->arrlist[position] = NULL;
257 if( position == list->size - 1 ) list->size--;
263 @brief Find the position where a given pointer is stored.
264 @param list A pointer to the osrfList.
265 @param addr A void pointer possibly stored in the osrfList.
266 @return A zero-based index indicating where the specified pointer resides in the array,
267 or -1 if no such pointer is found.
269 If either parameter is NULL, osrfListFind returns -1.
271 If the pointer in question is stored in more than one slot, osrfListFind returns the
272 lowest applicable index.
274 int osrfListFind( const osrfList* list, void* addr ) {
275 if(!(list && addr)) return -1;
277 for( index = 0; index < list->size; index++ ) {
278 if( list->arrlist[index] == addr )
286 @brief Return the number of slots in use.
287 @param list A pointer to an osrfList.
288 @return The number of slots in use.
290 The concept of "in use" is highly counter-intuitive and not, in general, very useful for the
291 calling code. It is an internal optimization trick: it keeps track of how many slots *might*
292 contain non-NULL pointers, not how many slots *do* contain non_NULL pointers. It
293 represents how many slots certain operations need to look at before they can safely stop.
295 Extreme example: starting with an empty osrfList, call osrfListSet()
296 to add a pointer at slot 15. If you then call osrfListGetCount(),
297 it returns 16, because you installed the pointer in the sixteenth slot (counting from 1),
298 even though the array contains only one non-NULL pointer.
300 Now call osrfListRemove() to remove the pointer you just added. If you then call
301 osrfListGetCount(), it returns 15, even though all the pointers in the array are NULL,
302 because osrfListRemove() simply decremented the counter from its previous value of 16.
304 Conclusion: osrfListGetCount() tells you next to nothing about the contents of the array.
305 The value returned reflects not only the current state of the array but also the history
306 and sequence of previous operations.
308 If you have changed the contents of the array only by calls to osrfListPush() and/or
309 osrfListPushFirst(), thereby leaving no holes in the array at any time, then
310 osrfListGetCount() will return the answer you expect. Otherwise all bets are off.
312 unsigned int osrfListGetCount( const osrfList* list ) {
319 @brief Remove the last pointer from the array.
320 @param list A pointer to an osrfList.
321 @return The pointer so removed, or NULL.
323 As with osrfListRemove(), if a callback function has been defined, osrfListPop() calls it
324 for the pointer it removes, and returns NULL. Otherwise it returns the removed pointer.
326 The concept of "last pointer" is non-intuitive. It reflects, in part, the history and
327 sequence of previous operations on the osrfList. The pointer removed is the one with
328 subscript n - 1, where n is the value returned by osrfListGetCount(). See the discussion
329 of the latter function for the dirty details.
331 In brief, osrfListPop() will behave in the obvious and expected way as long as you never
332 create holes in the array via calls to osrfListSet(), osrfListRemove(), or osrfListExtract().
334 void* osrfListPop( osrfList* list ) {
335 if(!list) return NULL;
336 return osrfListRemove( list, list->size - 1 );
341 @brief Create and initialize an osrfListIterator for a given osrfList.
342 @param list A pointer to an osrfList.
343 @return A pointer to the newly constructed osrfListIterator.
345 The calling code is responsible for freeing the osrfListIterator by calling
346 osrfListIteratorFree().
348 osrfListIterator* osrfNewListIterator( const osrfList* list ) {
349 if(!list) return NULL;
350 osrfListIterator* itr;
351 OSRF_MALLOC(itr, sizeof(osrfListIterator));
358 @brief Advance an osrfListIterator to the next position in the array.
359 @param itr A pointer to the osrfListIterator to be advanced.
360 @return The pointer at the next position in the array; or NULL, if the osrfIterator
361 is already past the end.
363 The first call to osrfListIteratorNext() for a given osrfListIterator returns the first
364 pointer in the array (i.e slot zero, counting from zero). Subsequent calls return successive
365 pointers from the array. Once it has returned the last pointer, the iterator responds to
366 subsequent calls by returning NULL, unless it is restored to an initial state by a call to
367 osrfListIteratorReset().
369 A return value of NULL does not necessarily indicate that the iterator has reached the end
370 of the array. Depending on the history and sequence of previous operations, the array may
371 include NULLs that are regarded as part of the array. See the discussions of osrfListPop()
372 and osrfListGetCount().
374 void* osrfListIteratorNext( osrfListIterator* itr ) {
375 if(!(itr && itr->list)) return NULL;
376 if(itr->current >= itr->list->size) return NULL;
377 return itr->list->arrlist[itr->current++];
381 @brief Free an osrfListIterator.
382 @param itr A pointer to the osrfListIterator to be freed.
384 void osrfListIteratorFree( osrfListIterator* itr ) {
391 @brief Reset an osrfListIterator to the beginning of the associated osrfList.
392 @param itr A pointer to the osrfListIterator to be reset.
394 void osrfListIteratorReset( osrfListIterator* itr ) {
401 @brief Install a default item-freeing callback function (the ANSI standard free() function).
402 @param list A pointer to the osrfList where the callback function will be installed.
404 void osrfListSetDefaultFree( osrfList* list ) {
406 list->freeItem = free;