From e5dbdab134a9baf7a71bd8f10bcc98fa1de8e35a Mon Sep 17 00:00:00 2001
From: erickson <erickson@9efc2488-bf62-4759-914b-345cdb29e865>
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/OpenSRF/trunk@652 9efc2488-bf62-4759-914b-345cdb29e865
---
 src/libstack/osrf_big_list.c | 174 +++++++++++++++++++++++++++++++++++++++++++
 src/libstack/osrf_big_list.h | 142 +++++++++++++++++++++++++++++++++++
 src/libstack/osrf_list.c     | 133 ++++++++++++---------------------
 src/libstack/osrf_list.h     |  20 ++---
 4 files changed, 375 insertions(+), 94 deletions(-)
 create mode 100644 src/libstack/osrf_big_list.c
 create mode 100644 src/libstack/osrf_big_list.h

diff --git a/src/libstack/osrf_big_list.c b/src/libstack/osrf_big_list.c
new file mode 100644
index 0000000..5d7e3dc
--- /dev/null
+++ b/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/src/libstack/osrf_big_list.h b/src/libstack/osrf_big_list.h
new file mode 100644
index 0000000..523f28d
--- /dev/null
+++ b/src/libstack/osrf_big_list.h
@@ -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
diff --git a/src/libstack/osrf_list.c b/src/libstack/osrf_list.c
index 2a60317..f04c6ec 100644
--- a/src/libstack/osrf_list.c
+++ b/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/src/libstack/osrf_list.h b/src/libstack/osrf_list.h
index dc1dc15..69ced17 100644
--- a/src/libstack/osrf_list.h
+++ b/src/libstack/osrf_list.h
@@ -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
@@ -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.11.0