1 files changed, 265 insertions, 0 deletions
diff --git a/source/blender/blenlib/intern/dynamiclist.c b/source/blender/blenlib/intern/dynamiclist.c
new file mode 100644
index 00000000000..fbb87124bba
--- /dev/null
+++ b/source/blender/blenlib/intern/dynamiclist.c
@@ -0,0 +1,265 @@
+/* util.c
+ *
+ * various string, file, list operations.
+ *
+ *
+ * $Id: util.c 17433 2008-11-12 21:16:53Z blendix $
+ *
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
+ *
+ * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
+ * All rights reserved.
+ *
+ * The Original Code is: all of this file.
+ *
+ * Contributor(s): none yet.
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ * 
+ */
+
+#include "MEM_guardedalloc.h"
+
+#include "DNA_listBase.h"
+
+#include "BLI_listbase.h"
+#include "BLI_dynamiclist.h"
+
+#define PAGE_SIZE 4
+
+/*=====================================================================================*/
+/* Methods for access array (realloc) */
+/*=====================================================================================*/
+
+/* remove item with index */
+static void rem_array_item(struct DynamicArray *da, unsigned int index)
+{
+	da->items[index]=NULL;
+	da->count--;
+	if(index==da->last_item_index){
+		while((!da->items[da->last_item_index]) && (da->last_item_index>0)){
+			da->last_item_index--;
+		}
+	}
+}
+
+/* add array (if needed, then realloc) */
+static void add_array_item(struct DynamicArray *da, void *item, unsigned int index)
+{
+	/* realloc of access array */
+	if(da->max_item_index < index){
+		unsigned int i, max = da->max_item_index;
+		void **nitems;
+
+		do {
+			da->max_item_index += PAGE_SIZE;	/* OS can allocate only PAGE_SIZE Bytes */
+		} while(da->max_item_index<=index);
+
+		nitems = (void**)MEM_mallocN(sizeof(void*)*(da->max_item_index+1), "dlist access array");
+		for(i=0;i<=max;i++)
+			nitems[i] = da->items[i];
+
+		/* set rest pointers to the NULL */
+		for(i=max+1; i<=da->max_item_index; i++)
+			nitems[i]=NULL;
+
+		MEM_freeN(da->items);		/* free old access array */
+		da->items = nitems;
+	}
+
+	da->items[index] = item;
+	da->count++;
+	if(index > da->last_item_index) da->last_item_index = index;
+}
+
+/* free access array */
+static void destroy_array(DynamicArray *da)
+{
+	da->count=0;
+	da->last_item_index=0;
+	da->max_item_index=0;
+	MEM_freeN(da->items);
+	da->items = NULL;
+}
+
+/* initialize dynamic array */
+static void init_array(DynamicArray *da)
+{
+	unsigned int i;
+
+	da->count=0;
+	da->last_item_index=0;
+	da->max_item_index = PAGE_SIZE-1;
+	da->items = (void*)MEM_mallocN(sizeof(void*)*(da->max_item_index+1), "dlist access array");
+	for(i=0; i<=da->max_item_index; i++) da->items[i]=NULL;
+}
+
+/* reinitialize dynamic array */
+static void reinit_array(DynamicArray *da)
+{
+	destroy_array(da);
+	init_array(da);
+}
+
+/*=====================================================================================*/
+/* Methods for two way dynamic list with access array */
+/*=====================================================================================*/
+
+/* create new two way dynamic list with access array from two way dynamic list
+ * it doesn't copy any items to new array or something like this It is strongly
+ * recomended to use BLI_dlist_ methods for adding/removing items from dynamic list
+ * unless you can end with inconsistence system !!! */
+DynamicList *BLI_dlist_from_listbase(ListBase *lb)
+{
+	DynamicList *dlist;
+	Link *item;
+	int i=0, count;
+	
+	if(!lb) return NULL;
+	
+	count = BLI_countlist(lb);
+
+	dlist = MEM_mallocN(sizeof(DynamicList), "temp dynamic list");
+	/* ListBase stuff */
+	dlist->lb.first = lb->first;
+	dlist->lb.last = lb->last;
+	/* access array stuff */
+	dlist->da.count=count;
+	dlist->da.max_item_index = count-1;
+	dlist->da.last_item_index = count -1;
+	dlist->da.items = (void*)MEM_mallocN(sizeof(void*)*count, "temp dlist access array");
+
+	item = (Link*)lb->first;
+	while(item){
+		dlist->da.items[i] = (void*)item;
+		item = item->next;
+		i++;
+	}
+
+	/* to prevent you of using original ListBase :-) */
+	lb->first = lb->last = NULL;
+
+	return dlist;
+}
+
+/* take out ListBase from DynamicList and destroy all temporary structures of DynamicList */
+ListBase *BLI_listbase_from_dlist(DynamicList *dlist, ListBase *lb)
+{
+	if(!dlist) return NULL;
+
+	if(!lb) lb = (ListBase*)MEM_mallocN(sizeof(ListBase), "ListBase");
+	
+	lb->first = dlist->lb.first;
+	lb->last = dlist->lb.last;
+
+	/* free all items of access array */
+	MEM_freeN(dlist->da.items);
+	/* free DynamicList*/
+	MEM_freeN(dlist);
+
+	return lb;
+}
+
+/* return pointer at item from th dynamic list with access array */
+void *BLI_dlist_find_link(DynamicList *dlist, unsigned int index)
+{
+	if(!dlist || !dlist->da.items) return NULL;
+
+	if((index <= dlist->da.last_item_index) && (index >= 0) && (dlist->da.count>0)){
+      		return dlist->da.items[index];
+	}
+	else {
+		return NULL;
+	}
+}
+
+/* return count of items in the dynamic list with access array */
+unsigned int BLI_count_items(DynamicList *dlist)
+{
+	if(!dlist) return 0;
+
+	return dlist->da.count;
+}
+
+/* free item from the dynamic list with access array */
+void BLI_dlist_free_item(DynamicList *dlist, unsigned int index)
+{
+	if(!dlist || !dlist->da.items) return;
+	
+	if((index <= dlist->da.last_item_index) && (dlist->da.items[index])){
+		BLI_freelinkN(&(dlist->lb), dlist->da.items[index]);
+		rem_array_item(&(dlist->da), index);
+	}
+}
+
+/* remove item from the dynamic list with access array */
+void BLI_dlist_rem_item(DynamicList *dlist, unsigned int index)
+{
+	if(!dlist || !dlist->da.items) return;
+	
+	if((index <= dlist->da.last_item_index) && (dlist->da.items[index])){
+		BLI_remlink(&(dlist->lb), dlist->da.items[index]);
+		rem_array_item(&(dlist->da), index);
+	}
+}
+
+/* add item to the dynamic list with access array (index) */
+void* BLI_dlist_add_item_index(DynamicList *dlist, void *item, unsigned int index)
+{
+	if(!dlist || !dlist->da.items) return NULL;
+
+	if((index <= dlist->da.max_item_index) && (dlist->da.items[index])) {
+		/* you can't place item at used index */
+		return NULL;
+	}
+	else {
+		add_array_item(&(dlist->da), item, index);
+		BLI_addtail(&(dlist->lb), item);
+		return item;
+	}
+}
+
+/* destroy dynamic list with access array */
+void BLI_dlist_destroy(DynamicList *dlist)
+{
+	if(!dlist) return;
+
+	BLI_freelistN(&(dlist->lb));
+	destroy_array(&(dlist->da));
+}
+
+/* initialize dynamic list with access array */
+void BLI_dlist_init(DynamicList *dlist)
+{
+	if(!dlist) return;
+
+	dlist->lb.first = NULL;
+	dlist->lb.last = NULL;
+
+	init_array(&(dlist->da));
+}
+
+/* reinitialize dynamic list with acces array */
+void BLI_dlist_reinit(DynamicList *dlist)
+{
+	if(!dlist) return;
+	
+	BLI_freelistN(&(dlist->lb));
+	reinit_array(&(dlist->da));
+}
+
+/*=====================================================================================*/