svn merge -r 23207:23528 https://svn.blender.org/svnroot/bf-blender/trunk/blender
[blender.git] / source / blender / blenlib / intern / dynamiclist.c
1 /* util.c
2  *
3  * various string, file, list operations.
4  *
5  *
6  * $Id$
7  *
8  * ***** BEGIN GPL LICENSE BLOCK *****
9  *
10  * This program is free software; you can redistribute it and/or
11  * modify it under the terms of the GNU General Public License
12  * as published by the Free Software Foundation; either version 2
13  * of the License, or (at your option) any later version.
14  *
15  * This program is distributed in the hope that it will be useful,
16  * but WITHOUT ANY WARRANTY; without even the implied warranty of
17  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
18  * GNU General Public License for more details.
19  *
20  * You should have received a copy of the GNU General Public License
21  * along with this program; if not, write to the Free Software Foundation,
22  * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
23  *
24  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
25  * All rights reserved.
26  *
27  * The Original Code is: all of this file.
28  *
29  * Contributor(s): none yet.
30  *
31  * ***** END GPL LICENSE BLOCK *****
32  * 
33  */
34
35 #include "MEM_guardedalloc.h"
36
37 #include "DNA_listBase.h"
38
39 #include "BLI_listbase.h"
40 #include "BLI_dynamiclist.h"
41
42 #define PAGE_SIZE 4
43
44 /*=====================================================================================*/
45 /* Methods for access array (realloc) */
46 /*=====================================================================================*/
47
48 /* remove item with index */
49 static void rem_array_item(struct DynamicArray *da, unsigned int index)
50 {
51         da->items[index]=NULL;
52         da->count--;
53         if(index==da->last_item_index){
54                 while((!da->items[da->last_item_index]) && (da->last_item_index>0)){
55                         da->last_item_index--;
56                 }
57         }
58 }
59
60 /* add array (if needed, then realloc) */
61 static void add_array_item(struct DynamicArray *da, void *item, unsigned int index)
62 {
63         /* realloc of access array */
64         if(da->max_item_index < index){
65                 unsigned int i, max = da->max_item_index;
66                 void **nitems;
67
68                 do {
69                         da->max_item_index += PAGE_SIZE;        /* OS can allocate only PAGE_SIZE Bytes */
70                 } while(da->max_item_index<=index);
71
72                 nitems = (void**)MEM_mallocN(sizeof(void*)*(da->max_item_index+1), "dlist access array");
73                 for(i=0;i<=max;i++)
74                         nitems[i] = da->items[i];
75
76                 /* set rest pointers to the NULL */
77                 for(i=max+1; i<=da->max_item_index; i++)
78                         nitems[i]=NULL;
79
80                 MEM_freeN(da->items);           /* free old access array */
81                 da->items = nitems;
82         }
83
84         da->items[index] = item;
85         da->count++;
86         if(index > da->last_item_index) da->last_item_index = index;
87 }
88
89 /* free access array */
90 static void destroy_array(DynamicArray *da)
91 {
92         da->count=0;
93         da->last_item_index=0;
94         da->max_item_index=0;
95         MEM_freeN(da->items);
96         da->items = NULL;
97 }
98
99 /* initialize dynamic array */
100 static void init_array(DynamicArray *da)
101 {
102         unsigned int i;
103
104         da->count=0;
105         da->last_item_index=0;
106         da->max_item_index = PAGE_SIZE-1;
107         da->items = (void*)MEM_mallocN(sizeof(void*)*(da->max_item_index+1), "dlist access array");
108         for(i=0; i<=da->max_item_index; i++) da->items[i]=NULL;
109 }
110
111 /* reinitialize dynamic array */
112 static void reinit_array(DynamicArray *da)
113 {
114         destroy_array(da);
115         init_array(da);
116 }
117
118 /*=====================================================================================*/
119 /* Methods for two way dynamic list with access array */
120 /*=====================================================================================*/
121
122 /* create new two way dynamic list with access array from two way dynamic list
123  * it doesn't copy any items to new array or something like this It is strongly
124  * recomended to use BLI_dlist_ methods for adding/removing items from dynamic list
125  * unless you can end with inconsistence system !!! */
126 DynamicList *BLI_dlist_from_listbase(ListBase *lb)
127 {
128         DynamicList *dlist;
129         Link *item;
130         int i=0, count;
131         
132         if(!lb) return NULL;
133         
134         count = BLI_countlist(lb);
135
136         dlist = MEM_mallocN(sizeof(DynamicList), "temp dynamic list");
137         /* ListBase stuff */
138         dlist->lb.first = lb->first;
139         dlist->lb.last = lb->last;
140         /* access array stuff */
141         dlist->da.count=count;
142         dlist->da.max_item_index = count-1;
143         dlist->da.last_item_index = count -1;
144         dlist->da.items = (void*)MEM_mallocN(sizeof(void*)*count, "temp dlist access array");
145
146         item = (Link*)lb->first;
147         while(item){
148                 dlist->da.items[i] = (void*)item;
149                 item = item->next;
150                 i++;
151         }
152
153         /* to prevent you of using original ListBase :-) */
154         lb->first = lb->last = NULL;
155
156         return dlist;
157 }
158
159 /* take out ListBase from DynamicList and destroy all temporary structures of DynamicList */
160 ListBase *BLI_listbase_from_dlist(DynamicList *dlist, ListBase *lb)
161 {
162         if(!dlist) return NULL;
163
164         if(!lb) lb = (ListBase*)MEM_mallocN(sizeof(ListBase), "ListBase");
165         
166         lb->first = dlist->lb.first;
167         lb->last = dlist->lb.last;
168
169         /* free all items of access array */
170         MEM_freeN(dlist->da.items);
171         /* free DynamicList*/
172         MEM_freeN(dlist);
173
174         return lb;
175 }
176
177 /* return pointer at item from th dynamic list with access array */
178 void *BLI_dlist_find_link(DynamicList *dlist, unsigned int index)
179 {
180         if(!dlist || !dlist->da.items) return NULL;
181
182         if((index <= dlist->da.last_item_index) && (index >= 0) && (dlist->da.count>0)){
183                 return dlist->da.items[index];
184         }
185         else {
186                 return NULL;
187         }
188 }
189
190 /* return count of items in the dynamic list with access array */
191 unsigned int BLI_count_items(DynamicList *dlist)
192 {
193         if(!dlist) return 0;
194
195         return dlist->da.count;
196 }
197
198 /* free item from the dynamic list with access array */
199 void BLI_dlist_free_item(DynamicList *dlist, unsigned int index)
200 {
201         if(!dlist || !dlist->da.items) return;
202         
203         if((index <= dlist->da.last_item_index) && (dlist->da.items[index])){
204                 BLI_freelinkN(&(dlist->lb), dlist->da.items[index]);
205                 rem_array_item(&(dlist->da), index);
206         }
207 }
208
209 /* remove item from the dynamic list with access array */
210 void BLI_dlist_rem_item(DynamicList *dlist, unsigned int index)
211 {
212         if(!dlist || !dlist->da.items) return;
213         
214         if((index <= dlist->da.last_item_index) && (dlist->da.items[index])){
215                 BLI_remlink(&(dlist->lb), dlist->da.items[index]);
216                 rem_array_item(&(dlist->da), index);
217         }
218 }
219
220 /* add item to the dynamic list with access array (index) */
221 void* BLI_dlist_add_item_index(DynamicList *dlist, void *item, unsigned int index)
222 {
223         if(!dlist || !dlist->da.items) return NULL;
224
225         if((index <= dlist->da.max_item_index) && (dlist->da.items[index])) {
226                 /* you can't place item at used index */
227                 return NULL;
228         }
229         else {
230                 add_array_item(&(dlist->da), item, index);
231                 BLI_addtail(&(dlist->lb), item);
232                 return item;
233         }
234 }
235
236 /* destroy dynamic list with access array */
237 void BLI_dlist_destroy(DynamicList *dlist)
238 {
239         if(!dlist) return;
240
241         BLI_freelistN(&(dlist->lb));
242         destroy_array(&(dlist->da));
243 }
244
245 /* initialize dynamic list with access array */
246 void BLI_dlist_init(DynamicList *dlist)
247 {
248         if(!dlist) return;
249
250         dlist->lb.first = NULL;
251         dlist->lb.last = NULL;
252
253         init_array(&(dlist->da));
254 }
255
256 /* reinitialize dynamic list with acces array */
257 void BLI_dlist_reinit(DynamicList *dlist)
258 {
259         if(!dlist) return;
260         
261         BLI_freelistN(&(dlist->lb));
262         reinit_array(&(dlist->da));
263 }
264
265 /*=====================================================================================*/