svn merge ^/trunk/blender -r42722:42742
[blender.git] / source / blender / blenlib / BLI_array.h
1 /**
2  * Array Library
3  *
4  * ***** BEGIN GPL LICENSE BLOCK *****
5  *
6  * This program is free software; you can redistribute it and/or
7  * modify it under the terms of the GNU General Public License
8  * as published by the Free Software Foundation; either version 2
9  * of the License, or (at your option) any later version.
10  *
11  * This program is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14  * GNU General Public License for more details.
15  *
16  * You should have received a copy of the GNU General Public License
17  * along with this program; if not, write to the Free Software Foundation,
18  * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
19  *
20  * The Original Code is Copyright (C) 2008 Blender Foundation.
21  * All rights reserved.
22  *
23  * The Original Code is: all of this file.
24  *
25  * Contributor(s): Joseph Eagar.
26  *
27  * ***** END GPL LICENSE BLOCK *****
28  */
29
30 /*
31 this library needs to be changed to not use macros quite so heavily,
32 and to be more of a complete array API.  The way arrays are
33 exposed to client code as normal C arrays is very useful though, imho.
34 it does require some use of macros, however.  
35
36 anyway, it's used a bit too heavily to simply rewrite as a 
37 more "correct" solution without macros entirely.  I originally wrote this
38 to be very easy to use, without the normal pain of most array libraries.
39 This was especially helpful when it came to the massive refactors necessary for
40 bmesh, and really helped to speed the process up. - joeedh
41   
42 little array macro library.  example of usage:
43
44 int *arr = NULL;
45 BLI_array_declare(arr);
46 int i;
47
48 for (i=0; i<10; i++) {
49         BLI_array_growone(arr);
50         arr[i] = something;
51 }
52 BLI_array_free(arr);
53
54 arrays are buffered, using double-buffering (so on each reallocation,
55 the array size is doubled).  supposedly this should give good Big Oh
56 behaviour, though it may not be the best in practice.
57 */
58
59 #define BLI_array_declare(arr)                                                \
60         int _##arr##_count=0;                                                     \
61         void *_##arr##_tmp;                                                       \
62         void *_##arr##_static = NULL
63
64 /* this will use stack space, up to maxstatic array elements, before
65  * switching to dynamic heap allocation */
66 #define BLI_array_staticdeclare(arr, maxstatic)                               \
67         int _##arr##_count=0;                                                     \
68         void *_##arr##_tmp;                                                       \
69         char _##arr##_static[maxstatic*sizeof(arr)]
70
71
72 /* this returns the entire size of the array, including any buffering. */
73 #define BLI_array_totalsize_dyn(arr)  (                                       \
74         ((arr)==NULL) ?                                                           \
75                 0 :                                                                   \
76                 MEM_allocN_len(arr) / sizeof(*arr)                                    \
77 )
78
79
80 #define BLI_array_totalsize(arr)  (                                           \
81         (signed int)                                                              \
82         (((void *)(arr) == (void *)_##arr##_static && (void *)(arr) != NULL) ?    \
83                 (sizeof(_##arr##_static) / sizeof(*arr)) :                            \
84                 BLI_array_totalsize_dyn(arr))                                         \
85 )
86
87
88 /* this returns the logical size of the array, not including buffering. */
89 #define BLI_array_count(arr) _##arr##_count
90
91 /* grow the array by one.  zeroes the new elements. */
92 #define _bli_array_growone(arr)  (                                            \
93         (BLI_array_totalsize(arr) > _##arr##_count) ?                             \
94             ++_##arr##_count :                                                    \
95             (                                                                     \
96                 (void) (_##arr##_tmp = MEM_callocN(                               \
97                         sizeof(*arr)*(_##arr##_count*2+2),                        \
98                         #arr " " __FILE__ ":" STRINGIFY(__LINE__)                 \
99                         )                                                         \
100                         ),                                                        \
101                 (void) (arr && memcpy(_##arr##_tmp,                               \
102                                       arr,                                        \
103                                       sizeof(*arr) * _##arr##_count)              \
104                         ),                                                        \
105                 (void) (arr && ((void *)(arr) != (void*)_##arr##_static ?         \
106                         (MEM_freeN(arr), arr) :                                   \
107                         arr)                                                      \
108                         ),                                                        \
109                 (void) (arr = _##arr##_tmp                                        \
110                         ),                                                        \
111                 _##arr##_count++                                                  \
112             )                                                                     \
113 )
114
115
116 /* returns length of array */
117 #define BLI_array_growone(arr)  (                                             \
118         ((void *)(arr)==NULL && (void *)(_##arr##_static) != NULL) ?              \
119                 ((arr=(void*)_##arr##_static), ++_##arr##_count) :                    \
120                 _bli_array_growone(arr)                                               \
121 )
122
123
124 /* appends an item to the array. */
125 #define BLI_array_append(arr, item)  (                                        \
126         (void) BLI_array_growone(arr),                                            \
127         (void) (arr[_##arr##_count-1] = item)                                     \
128 )
129
130 /* appends an item to the array and returns a pointer to the item in the array.
131  * item is not a pointer, but actual data value.*/
132 #define BLI_array_append_r(arr, item)  (                                      \
133         (void) BLI_array_growone(arr),                                            \
134         (void) (arr[_##arr##_count-1] = item),                                    \
135         (&arr[_##arr##_count-1])                                                  \
136 )
137
138 /* grow an array by a specified number of items. */
139 /* TODO, this could be done in a less crappy way by not looping - campbell */
140 #define BLI_array_growitems(arr, num)                                         \
141         if ((BLI_array_totalsize(arr) - _##arr##_count) >= num) {                 \
142             _##arr##_count += num;                                                \
143         }                                                                         \
144         else {                                                                    \
145                 int _i;                                                               \
146                 for (_i = 0; _i < (num); _i++) {                                      \
147                         BLI_array_growone(arr);                                           \
148                 }                                                                     \
149         }
150
151 #define BLI_array_free(arr)                                                   \
152         if (arr && (char *)arr != _##arr##_static) {                              \
153                 BLI_array_fake_user(arr);                                             \
154                 MEM_freeN(arr);                                                       \
155         }
156
157 #define BLI_array_pop(arr)  (                                                 \
158         (arr&&_##arr##_count) ?                                                   \
159                 arr[--_##arr##_count] :                                               \
160                 0                                                                     \
161 )
162
163 /* resets the logical size of an array to zero, but doesn't
164  * free the memory. */
165 #define BLI_array_empty(arr)                                                  \
166         _##arr##_count=0
167
168 /* set the count of the array, doesn't actually increase the allocated array
169  * size.  don't use this unless you know what you're doing. */
170 #define BLI_array_set_length(arr, count)                                      \
171         _##arr##_count = (count)
172
173 /* only to prevent unused warnings */
174 #define BLI_array_fake_user(arr)                                              \
175         (void)_##arr##_count,                                                     \
176         (void)_##arr##_tmp,                                                       \
177         (void)_##arr##_static
178
179
180 /* not part of the 'API' but handy funcs,
181  * same purpose as BLI_array_staticdeclare()
182  * but use when the max size is known ahead of time */
183 #define BLI_array_fixedstack_declare(arr, maxstatic, realsize, allocstr)      \
184         char _##arr##_static[maxstatic*sizeof(*arr)];                             \
185         const int _##arr##_is_static= ((void *)_##arr##_static) != (              \
186             arr= (realsize <= maxstatic) ?                                        \
187                 (void *)_##arr##_static :                                         \
188                 MEM_mallocN(sizeof(*arr)*realsize, allocstr)                      \
189             )                                                                     \
190
191 #define BLI_array_fixedstack_free(arr)                                        \
192         if (_##arr##_is_static) MEM_freeN(arr)                                    \
193