merge with/from trunk at r35190
[blender.git] / source / blender / blenlib / intern / BLI_mempool.c
1 /*
2  *
3  * ***** BEGIN GPL LICENSE BLOCK *****
4  *
5  * This program is free software; you can redistribute it and/or
6  * modify it under the terms of the GNU General Public License
7  * as published by the Free Software Foundation; either version 2
8  * of the License, or (at your option) any later version.
9  *
10  * This program is distributed in the hope that it will be useful,
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13  * GNU General Public License for more details.
14  *
15  * You should have received a copy of the GNU General Public License
16  * along with this program; if not, write to the Free Software Foundation,
17  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
18  *
19  * The Original Code is Copyright (C) 2008 by Blender Foundation.
20  * All rights reserved.
21  *
22  * The Original Code is: all of this file.
23  *
24  * Contributor(s): Geoffery Bantle
25  *
26  * ***** END GPL LICENSE BLOCK *****
27  */
28
29 /*
30         Simple, fast memory allocator for allocating many elements of the same size.
31 */
32
33 #include "MEM_guardedalloc.h"
34
35 #include "BKE_utildefines.h"
36
37 #include "BLI_blenlib.h"
38 #include "BLI_linklist.h"
39 #include "BLI_mempool.h"
40 #include "BLI_utildefines.h"
41
42 #include "DNA_listBase.h"
43 #include "DNA_ID.h"
44
45 #include <string.h> 
46
47 #define BLI_MEMPOOL_INTERN
48 #include "BLI_mempool.h"
49
50 BLI_mempool *BLI_mempool_create(int esize, int tote, int pchunk,
51                                                                 int use_sysmalloc, int allow_iter)
52 {       BLI_mempool  *pool = NULL;
53         BLI_freenode *lasttail = NULL, *curnode = NULL;
54         int i,j, maxchunks;
55         char *addr;
56         
57         if (esize < sizeof(void*)*2)
58                 esize = sizeof(void*)*2;
59         
60         if (esize < sizeof(void*)*2)
61                 esize = sizeof(void*)*2;
62
63         /*allocate the pool structure*/
64         pool = use_sysmalloc ? malloc(sizeof(BLI_mempool)) : MEM_mallocN(sizeof(BLI_mempool), "memory pool");
65         pool->esize = allow_iter ? MAX2(esize, sizeof(BLI_freenode)) : esize;
66         pool->use_sysmalloc = use_sysmalloc;
67         pool->pchunk = pchunk;  
68         pool->csize = esize * pchunk;
69         pool->chunks.first = pool->chunks.last = NULL;
70         pool->totused= 0;
71         pool->allow_iter= allow_iter;
72         
73         maxchunks = tote / pchunk + 1;
74         if (maxchunks==0) maxchunks = 1;
75
76         /*allocate the actual chunks*/
77         for(i=0; i < maxchunks; i++){
78                 BLI_mempool_chunk *mpchunk = use_sysmalloc ? malloc(sizeof(BLI_mempool_chunk)) : MEM_mallocN(sizeof(BLI_mempool_chunk), "BLI_Mempool Chunk");
79                 mpchunk->next = mpchunk->prev = NULL;
80                 mpchunk->data = use_sysmalloc ? malloc(pool->csize) : MEM_mallocN(pool->csize, "BLI Mempool Chunk Data");
81                 BLI_addtail(&(pool->chunks), mpchunk);
82                 
83                 if(i==0) {
84                         pool->free = mpchunk->data; /*start of the list*/
85                         if (pool->allow_iter)
86                                 pool->free->freeword = FREEWORD;
87                 }
88
89                 /*loop through the allocated data, building the pointer structures*/
90                 for(addr = mpchunk->data, j=0; j < pool->pchunk; j++){
91                         curnode = ((BLI_freenode*)addr);
92                         addr += pool->esize;
93                         curnode->next = (BLI_freenode*)addr;
94                         if (pool->allow_iter) {
95                                 if (j != pool->pchunk-1)
96                                         curnode->next->freeword = FREEWORD;
97                                 curnode->freeword = FREEWORD;
98                         }
99                 }
100                 /*final pointer in the previously allocated chunk is wrong.*/
101                 if(lasttail) {
102                         lasttail->next = mpchunk->data;
103                         if (pool->allow_iter)
104                                 lasttail->freeword = FREEWORD;
105                 }
106
107                 /*set the end of this chunks memoryy to the new tail for next iteration*/
108                 lasttail = curnode;
109
110                 pool->totalloc += pool->pchunk;
111         }
112         
113         /*terminate the list*/
114         curnode->next = NULL;
115         return pool;
116 }
117 #if 0
118 void *BLI_mempool_alloc(BLI_mempool *pool){
119         void *retval=NULL;
120         BLI_freenode *curnode=NULL;
121         char *addr=NULL;
122         int j;
123         
124         if (!pool) return NULL;
125         
126         pool->totused++;
127
128         if(!(pool->free)){
129                 /*need to allocate a new chunk*/
130                 BLI_mempool_chunk *mpchunk = pool->use_sysmalloc ? malloc(sizeof(BLI_mempool_chunk)) :  MEM_mallocN(sizeof(BLI_mempool_chunk), "BLI_Mempool Chunk");
131                 mpchunk->next = mpchunk->prev = NULL;
132                 mpchunk->data = pool->use_sysmalloc ? malloc(pool->csize) : MEM_mallocN(pool->csize, "BLI_Mempool Chunk Data");
133                 BLI_addtail(&(pool->chunks), mpchunk);
134
135                 pool->free = mpchunk->data; /*start of the list*/
136                 if (pool->allow_iter)
137                         pool->free->freeword = FREEWORD;
138                 for(addr = mpchunk->data, j=0; j < pool->pchunk; j++){
139                         curnode = ((BLI_freenode*)addr);
140                         addr += pool->esize;
141                         curnode->next = (BLI_freenode*)addr;
142
143                         if (pool->allow_iter) {
144                                 curnode->freeword = FREEWORD;
145                                 if (j != pool->pchunk-1)
146                                         curnode->next->freeword = FREEWORD;
147                         }
148                 }
149                 curnode->next = NULL; /*terminate the list*/
150
151                 pool->totalloc += pool->pchunk;
152         }
153
154         retval = pool->free;
155         if (pool->allow_iter)
156                 pool->free->freeword = 0x7FFFFFFF;
157
158         pool->free = pool->free->next;
159         //memset(retval, 0, pool->esize);
160         return retval;
161 }
162 #endif
163
164 void *BLI_mempool_calloc(BLI_mempool *pool){
165         void *retval=NULL;
166         retval = BLI_mempool_alloc(pool);
167         BMEMSET(retval, 0, pool->esize);
168         return retval;
169 }
170
171
172 void BLI_mempool_free(BLI_mempool *pool, void *addr){ //doesnt protect against double frees, dont be stupid!
173         BLI_freenode *newhead = addr;
174         BLI_freenode *curnode=NULL;
175         char *tmpaddr=NULL;
176         int i;
177         
178         if (pool->allow_iter)
179                 newhead->freeword = FREEWORD;
180         newhead->next = pool->free;
181         pool->free = newhead;
182
183         pool->totused--;
184
185         /*nothing is in use; free all the chunks except the first*/
186         if (pool->totused == 0) {
187                 BLI_mempool_chunk *mpchunk=NULL, *first;
188
189                 first = pool->chunks.first;
190                 BLI_remlink(&pool->chunks, first);
191
192                 for(mpchunk = pool->chunks.first; mpchunk; mpchunk = mpchunk->next) {
193                         if(pool->use_sysmalloc) free(mpchunk->data);
194                         else                                    MEM_freeN(mpchunk->data);
195                 }
196
197                 pool->use_sysmalloc ? BLI_freelist(&(pool->chunks)) : BLI_freelistN(&(pool->chunks));
198                 
199                 BLI_addtail(&pool->chunks, first);
200                 pool->totalloc = pool->pchunk;
201
202                 pool->free = first->data; /*start of the list*/
203                 for(tmpaddr = first->data, i=0; i < pool->pchunk; i++){
204                         curnode = ((BLI_freenode*)tmpaddr);
205                         tmpaddr += pool->esize;
206                         curnode->next = (BLI_freenode*)tmpaddr;
207                 }
208                 curnode->next = NULL; /*terminate the list*/
209         }
210 }
211
212 void BLI_mempool_iternew(BLI_mempool *pool, BLI_mempool_iter *iter)
213 {
214         if (!pool->allow_iter) {
215                 fprintf(stderr, "evil! you can't iterate over this mempool!\n");
216                 iter->curchunk = NULL;
217                 iter->curindex = 0;
218                 
219                 return;
220         }
221         
222         iter->pool = pool;
223         iter->curchunk = pool->chunks.first;
224         iter->curindex = 0;
225 }
226
227 static void *bli_mempool_iternext(BLI_mempool_iter *iter)
228 {
229         void *ret = NULL;
230         
231         if (!iter->curchunk || !iter->pool->totused) return NULL;
232         
233         ret = ((char*)iter->curchunk->data) + iter->pool->esize*iter->curindex;
234         
235         iter->curindex++;
236         
237         if (iter->curindex >= iter->pool->pchunk) {
238                 iter->curchunk = iter->curchunk->next;
239                 iter->curindex = 0;
240         }
241         
242         return ret;
243 }
244
245 void *BLI_mempool_iterstep(BLI_mempool_iter *iter)
246 {
247         BLI_freenode *ret;
248         
249         do {
250                 ret = bli_mempool_iternext(iter);
251         } while (ret && ret->freeword == FREEWORD);
252         
253         return ret;
254 }
255
256 void BLI_mempool_destroy(BLI_mempool *pool)
257 {
258         BLI_mempool_chunk *mpchunk=NULL;
259         if(pool->use_sysmalloc) {
260                 for(mpchunk = pool->chunks.first; mpchunk; mpchunk = mpchunk->next) {
261                         free(mpchunk->data);
262                 }
263                 BLI_freelist(&(pool->chunks));
264                 free(pool);
265         }
266         else {
267                 for(mpchunk = pool->chunks.first; mpchunk; mpchunk = mpchunk->next) {
268                         MEM_freeN(mpchunk->data);
269                 }
270                 BLI_freelistN(&(pool->chunks));
271                 MEM_freeN(pool);
272         }
273 }