From 81c409c489730d608bbddbee56fea097c0e891be Mon Sep 17 00:00:00 2001 From: erickson Date: Wed, 1 Mar 2006 17:14:51 +0000 Subject: [PATCH] moved the Judy implementation to osrf_big_list and made osrf_list a standard array based list git-svn-id: svn://svn.open-ils.org/ILS/trunk@3227 dcc99617-32d9-48b4-a31d-7c20da2025e4 --- OpenSRF/src/libstack/osrf_big_list.c | 174 +++++++++++++++++++++++++++ OpenSRF/src/libstack/osrf_big_list.h | 142 ++++++++++++++++++++++ OpenSRF/src/libstack/osrf_list.c | 133 ++++++++------------ OpenSRF/src/libstack/osrf_list.h | 20 +-- 4 files changed, 375 insertions(+), 94 deletions(-) create mode 100644 OpenSRF/src/libstack/osrf_big_list.c create mode 100644 OpenSRF/src/libstack/osrf_big_list.h diff --git a/OpenSRF/src/libstack/osrf_big_list.c b/OpenSRF/src/libstack/osrf_big_list.c new file mode 100644 index 0000000000..5d7e3dc957 --- /dev/null +++ b/OpenSRF/src/libstack/osrf_big_list.c @@ -0,0 +1,174 @@ +#include "osrf_big_list.h" + + +osrfBigList* osrfNewBigList() { + osrfBigList* list = safe_malloc(sizeof(osrfBigList)); + list->list = (Pvoid_t) NULL; + list->size = 0; + list->freeItem = NULL; + return list; +} + + +int osrfBigListPush( osrfBigList* list, void* item ) { + if(!(list && item)) return -1; + Word_t* value; + unsigned long index = -1; + JLL(value, list->list, index ); + osrfBigListSet( list, item, index+1 ); + return 0; +} + + +void* osrfBigListSet( osrfBigList* list, void* item, unsigned long position ) { + if(!list || position < 0) return NULL; + + Word_t* value; + void* olditem = osrfBigListRemove( list, position ); + + JLI( value, list->list, position ); + *value = (Word_t) item; + __osrfBigListSetSize( list ); + + return olditem; +} + + +void* osrfBigListGetIndex( osrfBigList* list, unsigned long position ) { + if(!list) return NULL; + + Word_t* value; + JLG( value, list->list, position ); + if(value) return (void*) *value; + return NULL; +} + +void osrfBigListFree( osrfBigList* list ) { + if(!list) return; + + Word_t* value; + unsigned long index = -1; + JLL(value, list->list, index ); + int retcode; + + while (value != NULL) { + if(list->freeItem) + list->freeItem( (void*) *value ); + JLD(retcode, list->list, index); + JLP(value, list->list, index); + } + + free(list); +} + +void* osrfBigListRemove( osrfBigList* list, int position ) { + if(!list) return NULL; + + int retcode; + Word_t* value; + JLG( value, list->list, position ); + void* olditem = NULL; + + if( value ) { + + olditem = (void*) *value; + if( olditem ) { + JLD(retcode, list->list, position ); + if(retcode == 1) { + if(list->freeItem) { + list->freeItem( olditem ); + olditem = NULL; + } + __osrfBigListSetSize( list ); + } + } + } + + return olditem; +} + + +int osrfBigListFind( osrfBigList* list, void* addr ) { + if(!(list && addr)) return -1; + + Word_t* value; + unsigned long index = -1; + JLL(value, list->list, index ); + + while (value != NULL) { + if( (void*) *value == addr ) + return index; + JLP(value, list->list, index); + } + + return -1; +} + + + +void __osrfBigListSetSize( osrfBigList* list ) { + if(!list) return; + + Word_t* value; + unsigned long index = -1; + JLL(value, list->list, index ); + list->size = index + 1; +} + + +unsigned long osrfBigListGetCount( osrfBigList* list ) { + if(!list) return -1; + unsigned long retcode = -1; + JLC( retcode, list->list, 0, -1 ); + return retcode; +} + + +void* osrfBigListPop( osrfBigList* list ) { + if(!list) return NULL; + return osrfBigListRemove( list, list->size - 1 ); +} + + +osrfBigBigListIterator* osrfNewBigListIterator( osrfBigList* list ) { + if(!list) return NULL; + osrfBigBigListIterator* itr = safe_malloc(sizeof(osrfBigBigListIterator)); + itr->list = list; + itr->current = 0; + return itr; +} + +void* osrfBigBigListIteratorNext( osrfBigBigListIterator* itr ) { + if(!(itr && itr->list)) return NULL; + + Word_t* value; + if(itr->current >= itr->list->size) return NULL; + JLF( value, itr->list->list, itr->current ); + if(value) { + itr->current++; + return (void*) *value; + } + return NULL; +} + +void osrfBigBigListIteratorFree( osrfBigBigListIterator* itr ) { + if(!itr) return; + free(itr); +} + + + +void osrfBigBigListIteratorReset( osrfBigBigListIterator* itr ) { + if(!itr) return; + itr->current = 0; +} + + +void osrfBigListVanillaFree( void* item ) { + free(item); +} + +void osrfBigListSetDefaultFree( osrfBigList* list ) { + if(!list) return; + list->freeItem = osrfBigListVanillaFree; +} diff --git a/OpenSRF/src/libstack/osrf_big_list.h b/OpenSRF/src/libstack/osrf_big_list.h new file mode 100644 index 0000000000..523f28d695 --- /dev/null +++ b/OpenSRF/src/libstack/osrf_big_list.h @@ -0,0 +1,142 @@ +#ifndef OSRF_BIG_LIST_H +#define OSRF_BIG_LIST_H + + +#include +#include "opensrf/utils.h" +#include + +/** + Items are stored as void*'s so it's up to the user to + manage the data wisely. Also, if the 'freeItem' callback is defined for the list, + then, it will be used on any item that needs to be freed, so don't mix data + types in the list if you want magic freeing */ + +struct __osrfBigListStruct { + Pvoid_t list; /* the list */ + int size; /* how many items in the list including NULL items between non-NULL items */ + void (*freeItem) (void* item); /* callback for freeing stored items */ +}; +typedef struct __osrfBigListStruct osrfBigList; + + +struct __osrfBigBigListIteratorStruct { + osrfBigList* list; + unsigned long current; +}; +typedef struct __osrfBigBigListIteratorStruct osrfBigBigListIterator; + + +/** + Creates a new list iterator with the given list + */ +osrfBigBigListIterator* osrfNewBigListIterator( osrfBigList* list ); + +/** + Returns the next non-NULL item in the list, return NULL when + the end of the list has been reached + */ +void* osrfBigBigListIteratorNext( osrfBigBigListIterator* itr ); + +/** + Deallocates the given list + */ +void osrfBigBigListIteratorFree( osrfBigBigListIterator* itr ); + +void osrfBigBigListIteratorReset( osrfBigBigListIterator* itr ); + + +/** + Allocates a new list + @param compress If true, the list will compress empty slots on delete. If item positionality + is not important, then using this feature is reccomended to keep the list from growing indefinitely. + if item positionality is not important. + @return The allocated list + */ +osrfBigList* osrfNewBigList(); + +/** + Pushes an item onto the end of the list. This always finds the highest index + in the list and pushes the new item into the list after it. + @param list The list + @param item The item to push + @return 0 on success, -1 on failure + */ +int osrfBigListPush( osrfBigList* list, void* item ); + + +/** + * Removes the last item in the list + * See osrfBigListRemove for details on how the removed item is handled + * @return The item, unless 'freeItem' exists, then returns NULL + */ +void* osrfBigListPop( osrfBigList* list ); + +/** + Puts the given item into the list at the specified position. If there + is already an item at the given position and the list has it's + "freeItem" function defined, then it will be used to free said item. + If no 'freeItem' callback is defined, then the displaced item will + be returned; + @param list The list + @param item The item to put into the list + @param position The position to place the item in + @return NULL in successfully inserting the new item and freeing + any displaced items. Returns the displaced item if no "freeItem" + callback is defined. + */ +void* osrfBigListSet( osrfBigList* list, void* item, unsigned long position ); + +/** + Returns the item at the given position + @param list The list + @param postiont the position + */ +void* osrfBigListGetIndex( osrfBigList* list, unsigned long position ); + +/** + Frees the list and all list items (if the list has a "freeItem" function defined ) + @param list The list + */ +void osrfBigListFree( osrfBigList* list ); + +/** + Removes the list item at the given index + @param list The list + @param position The position of the item to remove + @return A pointer to the item removed if "freeItem" is not defined + for this list, returns NULL if it is. + */ +void* osrfBigListRemove( osrfBigList* list, int position ); + +/** + Finds the list item whose void* is the same as the one passed in + @param list The list + @param addr The pointer connected to the list item we're to find + @return the index of the item, or -1 if the item was not found + */ +int osrfBigListFind( osrfBigList* list, void* addr ); + + +void __osrfBigListSetSize( osrfBigList* list ); + + +/** + @return The number of non-null items in the list + */ +unsigned long osrfBigListGetCount( osrfBigList* list ); + +/** + * May be used as a default memory freeing call + * Just calls free() on list items + */ +void osrfBigListVanillaFree( void* item ); + +/** + * Tells the list to just call 'free()' on each item when + * an item or the whole list is destroyed + */ +void osrfBigListSetDefaultFree( osrfBigList* list ); + + +#endif diff --git a/OpenSRF/src/libstack/osrf_list.c b/OpenSRF/src/libstack/osrf_list.c index 2a6031774f..f04c6ec629 100644 --- a/OpenSRF/src/libstack/osrf_list.c +++ b/OpenSRF/src/libstack/osrf_list.c @@ -1,126 +1,97 @@ #include "osrf_list.h" - osrfList* osrfNewList() { osrfList* list = safe_malloc(sizeof(osrfList)); - list->list = (Pvoid_t) NULL; - list->size = 0; + list->size = 0; list->freeItem = NULL; + list->arrsize = OSRF_LIST_DEFAULT_SIZE; + list->arrlist = safe_malloc( list->arrsize * sizeof(void*) ); return list; } int osrfListPush( osrfList* list, void* item ) { - if(!(list && item)) return -1; - Word_t* value; - unsigned long index = -1; - JLL(value, list->list, index ); - osrfListSet( list, item, index+1 ); + if(!(list)) return -1; + osrfListSet( list, item, list->size ); return 0; } - -void* osrfListSet( osrfList* list, void* item, unsigned long position ) { +void* osrfListSet( osrfList* list, void* item, unsigned int position ) { if(!list || position < 0) return NULL; - Word_t* value; - void* olditem = osrfListRemove( list, position ); + int i; + int newsize = list->arrsize; + void** newarr; - JLI( value, list->list, position ); - *value = (Word_t) item; - __osrfListSetSize( list ); + while( position >= newsize ) + newsize += OSRF_LIST_INC_SIZE; + if( newsize > list->arrsize ) { /* expand the list if necessary */ + newarr = safe_malloc( newsize * sizeof(void*) ); + for( i = 0; i < list->arrsize; i++ ) + newarr[i] = list->arrlist[i]; + free(list->arrlist); + list->arrlist = newarr; + list->arrsize = newsize; + } + + void* olditem = osrfListRemove( list, position ); + list->arrlist[position] = item; + if( list->size == 0 || list->size <= position ) + list->size = position + 1; return olditem; } -void* osrfListGetIndex( osrfList* list, unsigned long position ) { - if(!list) return NULL; - - Word_t* value; - JLG( value, list->list, position ); - if(value) return (void*) *value; - return NULL; +void* osrfListGetIndex( osrfList* list, unsigned int position ) { + if(!list || position >= list->size) return NULL; + return list->arrlist[position]; } void osrfListFree( osrfList* list ) { if(!list) return; - Word_t* value; - unsigned long index = -1; - JLL(value, list->list, index ); - int retcode; - - while (value != NULL) { - if(list->freeItem) - list->freeItem( (void*) *value ); - JLD(retcode, list->list, index); - JLP(value, list->list, index); - } + if( list->freeItem ) { + int i; void* val; + for( i = 0; i < list->size; i++ ) { + if( (val = list->arrlist[i]) ) + list->freeItem(val); + } + } + free(list->arrlist); free(list); } void* osrfListRemove( osrfList* list, int position ) { - if(!list) return NULL; + if(!list || position >= list->size) return NULL; - int retcode; - Word_t* value; - JLG( value, list->list, position ); - void* olditem = NULL; - - if( value ) { - - olditem = (void*) *value; - if( olditem ) { - JLD(retcode, list->list, position ); - if(retcode == 1) { - if(list->freeItem) { - list->freeItem( olditem ); - olditem = NULL; - } - __osrfListSetSize( list ); - } - } + void* olditem = list->arrlist[position]; + list->arrlist[position] = NULL; + if( list->freeItem ) { + list->freeItem(olditem); + olditem = NULL; } + if( position == list->size - 1 ) list->size--; return olditem; } int osrfListFind( osrfList* list, void* addr ) { if(!(list && addr)) return -1; - - Word_t* value; - unsigned long index = -1; - JLL(value, list->list, index ); - - while (value != NULL) { - if( (void*) *value == addr ) + int index; + for( index = 0; index < list->size; index++ ) { + if( list->arrlist[index] == addr ) return index; - JLP(value, list->list, index); } - return -1; } - -void __osrfListSetSize( osrfList* list ) { - if(!list) return; - - Word_t* value; - unsigned long index = -1; - JLL(value, list->list, index ); - list->size = index + 1; -} - - -unsigned long osrfListGetCount( osrfList* list ) { +unsigned int osrfListGetCount( osrfList* list ) { if(!list) return -1; - unsigned long retcode = -1; - JLC( retcode, list->list, 0, -1 ); - return retcode; + return list->size; } @@ -140,15 +111,8 @@ osrfListIterator* osrfNewListIterator( osrfList* list ) { void* osrfListIteratorNext( osrfListIterator* itr ) { if(!(itr && itr->list)) return NULL; - - Word_t* value; if(itr->current >= itr->list->size) return NULL; - JLF( value, itr->list->list, itr->current ); - if(value) { - itr->current++; - return (void*) *value; - } - return NULL; + return itr->list->arrlist[itr->current++]; } void osrfListIteratorFree( osrfListIterator* itr ) { @@ -157,7 +121,6 @@ void osrfListIteratorFree( osrfListIterator* itr ) { } - void osrfListIteratorReset( osrfListIterator* itr ) { if(!itr) return; itr->current = 0; diff --git a/OpenSRF/src/libstack/osrf_list.h b/OpenSRF/src/libstack/osrf_list.h index dc1dc150c1..69ced17e22 100644 --- a/OpenSRF/src/libstack/osrf_list.h +++ b/OpenSRF/src/libstack/osrf_list.h @@ -1,10 +1,11 @@ #ifndef OSRF_LIST_H #define OSRF_LIST_H - -#include #include "opensrf/utils.h" -#include + +#define OSRF_LIST_DEFAULT_SIZE 48 /* most opensrf lists are small... */ +#define OSRF_LIST_INC_SIZE 256 +#define OSRF_LIST_MAX_SIZE 10240 /** Items are stored as void*'s so it's up to the user to @@ -13,16 +14,17 @@ types in the list if you want magic freeing */ struct __osrfListStruct { - Pvoid_t list; /* the list */ - int size; /* how many items in the list including NULL items between non-NULL items */ + unsigned int size; /* how many items in the list including NULL items between non-NULL items */ void (*freeItem) (void* item); /* callback for freeing stored items */ + void** arrlist; + int arrsize; /* how big is the currently allocated array */ }; typedef struct __osrfListStruct osrfList; struct __osrfListIteratorStruct { osrfList* list; - unsigned long current; + unsigned int current; }; typedef struct __osrfListIteratorStruct osrfListIterator; @@ -85,14 +87,14 @@ void* osrfListPop( osrfList* list ); any displaced items. Returns the displaced item if no "freeItem" callback is defined. */ -void* osrfListSet( osrfList* list, void* item, unsigned long position ); +void* osrfListSet( osrfList* list, void* item, unsigned int position ); /** Returns the item at the given position @param list The list @param postiont the position */ -void* osrfListGetIndex( osrfList* list, unsigned long position ); +void* osrfListGetIndex( osrfList* list, unsigned int position ); /** Frees the list and all list items (if the list has a "freeItem" function defined ) @@ -124,7 +126,7 @@ void __osrfListSetSize( osrfList* list ); /** @return The number of non-null items in the list */ -unsigned long osrfListGetCount( osrfList* list ); +unsigned int osrfListGetCount( osrfList* list ); /** * May be used as a default memory freeing call -- 2.43.2