moved the Judy implementation to osrf_big_list and made osrf_list a
authorerickson <erickson@dcc99617-32d9-48b4-a31d-7c20da2025e4>
Wed, 1 Mar 2006 17:14:51 +0000 (17:14 +0000)
committererickson <erickson@dcc99617-32d9-48b4-a31d-7c20da2025e4>
Wed, 1 Mar 2006 17:14:51 +0000 (17:14 +0000)
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 [new file with mode: 0644]
OpenSRF/src/libstack/osrf_big_list.h [new file with mode: 0644]
OpenSRF/src/libstack/osrf_list.c
OpenSRF/src/libstack/osrf_list.h

diff --git a/OpenSRF/src/libstack/osrf_big_list.c b/OpenSRF/src/libstack/osrf_big_list.c
new file mode 100644 (file)
index 0000000..5d7e3dc
--- /dev/null
@@ -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 (file)
index 0000000..523f28d
--- /dev/null
@@ -0,0 +1,142 @@
+#ifndef OSRF_BIG_LIST_H
+#define OSRF_BIG_LIST_H
+
+
+#include <stdio.h>
+#include "opensrf/utils.h"
+#include <Judy.h>
+
+/**
+  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
index 2a60317..f04c6ec 100644 (file)
 #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;
index dc1dc15..69ced17 100644 (file)
@@ -1,10 +1,11 @@
 #ifndef OSRF_LIST_H
 #define OSRF_LIST_H
 
-
-#include <stdio.h>
 #include "opensrf/utils.h"
-#include <Judy.h>
+
+#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
   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