Merging r58475 through r58700 from trunk into soc-2013-depsgraph_mt
[blender.git] / source / blender / blenlib / BLI_array.h
index 65c01d72fb3eccbbd67ad101c0366584c1ef467c..ef5cb8bde04f7660cba0d7374836feee1956eaf2 100644 (file)
@@ -1,6 +1,4 @@
-/**
- * Array Library
- *
+/*
  * ***** BEGIN GPL LICENSE BLOCK *****
  *
  * This program is free software; you can redistribute it and/or
  * ***** END GPL LICENSE BLOCK *****
  */
 
-/*
-this library needs to be changed to not use macros quite so heavily,
-and to be more of a complete array API.  The way arrays are
-exposed to client code as normal C arrays is very useful though, imho.
-it does require some use of macros, however.  
-
-anyway, it's used a bit too heavily to simply rewrite as a 
-more "correct" solution without macros entirely.  I originally wrote this
-to be very easy to use, without the normal pain of most array libraries.
-This was especially helpful when it came to the massive refactors necessary for
-bmesh, and really helped to speed the process up. - joeedh
-  
-little array macro library.  example of usage:
-
-int *arr = NULL;
-BLI_array_declare(arr);
-int i;
-
-for (i=0; i<10; i++) {
-       BLI_array_growone(arr);
-       arr[i] = something;
-}
-BLI_array_free(arr);
-
-arrays are buffered, using double-buffering (so on each reallocation,
-the array size is doubled).  supposedly this should give good Big Oh
-behaviour, though it may not be the best in practice.
-*/
-
-#define BLI_array_declare(arr)                                                \
-       int _##arr##_count=0;                                                     \
-       void *_##arr##_tmp;                                                       \
-       void *_##arr##_static = NULL
+#ifndef __BLI_ARRAY_H__
+#define __BLI_ARRAY_H__
 
-/* this will use stack space, up to maxstatic array elements, before
- * switching to dynamic heap allocation */
-#define BLI_array_staticdeclare(arr, maxstatic)                               \
-       int _##arr##_count=0;                                                     \
-       void *_##arr##_tmp;                                                       \
-       char _##arr##_static[maxstatic*sizeof(arr)]
+/** \file BLI_array.h
+ *  \ingroup bli
+ *  \brief A (mainly) macro array library.
+ */
 
+/* -------------------------------------------------------------------- */
+/* internal defines */
 
 /* this returns the entire size of the array, including any buffering. */
-#define BLI_array_totalsize_dyn(arr)  (                                       \
-       ((arr)==NULL) ?                                                           \
-               0 :                                                                   \
-               MEM_allocN_len(arr) / sizeof(*arr)                                    \
+#define _bli_array_totalsize_dynamic(arr)  (                                  \
+       ((arr) == NULL) ?                                                         \
+           0 :                                                                   \
+           MEM_allocN_len(arr) / sizeof(*(arr))                                  \
 )
 
+#define _bli_array_totalsize_static(arr)  \
+       (sizeof(_##arr##_static) / sizeof(*(arr)))
 
-#define BLI_array_totalsize(arr)  (                                           \
-       (signed int)                                                              \
+#define _bli_array_totalsize(arr)  (                                          \
+       (size_t)                                                                  \
        (((void *)(arr) == (void *)_##arr##_static && (void *)(arr) != NULL) ?    \
-               (sizeof(_##arr##_static) / sizeof(*arr)) :                            \
-               BLI_array_totalsize_dyn(arr))                                         \
+           _bli_array_totalsize_static(arr) :                                    \
+           _bli_array_totalsize_dynamic(arr))                                    \
 )
 
+/* BLI_array.c
+ *
+ * Doing the realloc in a macro isn't so simple,
+ * so use a function the macros can use.
+ */
+void _bli_array_grow_func(void **arr_p, const void *arr_static,
+                          const int sizeof_arr_p, const int arr_count, const int num,
+                          const char *alloc_str);
+
+
+/* -------------------------------------------------------------------- */
+/* public defines */
+
+/* use sizeof(*(arr)) to ensure the array exists and is an array */
+#define BLI_array_declare(arr)                                                \
+       int   _##arr##_count = ((void)(sizeof(*(arr))), 0);                       \
+       void *_##arr##_static = NULL
+
+/* this will use stack space, up to maxstatic array elements, before
+ * switching to dynamic heap allocation */
+#define BLI_array_staticdeclare(arr, maxstatic)                               \
+       int   _##arr##_count = 0;                                                 \
+       char  _##arr##_static[maxstatic * sizeof(arr)]
 
 /* this returns the logical size of the array, not including buffering. */
 #define BLI_array_count(arr) _##arr##_count
 
-/* grow the array by one.  zeroes the new elements. */
-#define _bli_array_growone(arr)  (                                            \
-       (BLI_array_totalsize(arr) > _##arr##_count) ?                             \
-           ++_##arr##_count :                                                    \
-           (                                                                     \
-               (void) (_##arr##_tmp = MEM_callocN(                               \
-                       sizeof(*arr)*(_##arr##_count*2+2),                        \
-                       #arr " " __FILE__ ":" STRINGIFY(__LINE__)                 \
-                       )                                                         \
-                       ),                                                        \
-               (void) (arr && memcpy(_##arr##_tmp,                               \
-                                     arr,                                        \
-                                     sizeof(*arr) * _##arr##_count)              \
-                       ),                                                        \
-               (void) (arr && ((void *)(arr) != (void*)_##arr##_static ?         \
-                       (MEM_freeN(arr), arr) :                                   \
-                       arr)                                                      \
-                       ),                                                        \
-               (void) (arr = _##arr##_tmp                                        \
-                       ),                                                        \
-               _##arr##_count++                                                  \
-           )                                                                     \
-)
-
+/* Grow the array by a fixed number of items.
+ *
+ * Allow for a large 'num' value when the new size is more than double
+ * to allocate the exact sized array. */
+#define BLI_array_grow_items(arr, num)  ((                                    \
+       (((void *)(arr) == NULL) &&                                               \
+        ((void *)(_##arr##_static) != NULL) &&                                   \
+       /* don't add _##arr##_count below because it must be zero */              \
+        (_bli_array_totalsize_static(arr) >= _##arr##_count + num)) ?            \
+       /* we have an empty array and a static var big enough */                  \
+       (void)(arr = (void *)_##arr##_static)                                     \
+           :                                                                     \
+       /* use existing static array or allocate */                               \
+       (LIKELY(_bli_array_totalsize(arr) >= _##arr##_count + num) ?              \
+        (void)0 /* do nothing */ :                                               \
+        _bli_array_grow_func((void **)&(arr), _##arr##_static,                   \
+                              sizeof(*(arr)), _##arr##_count, num,               \
+                              "BLI_array." #arr),                                \
+        (void)0)  /* msvc2008 needs this */                                      \
+       ),                                                                        \
+       /* increment the array count, all conditions above are accounted for. */  \
+       (_##arr##_count += num))
 
 /* returns length of array */
-#define BLI_array_growone(arr)  (                                             \
-       ((void *)(arr)==NULL && (void *)(_##arr##_static) != NULL) ?              \
-               ((arr=(void*)_##arr##_static), ++_##arr##_count) :                    \
-               _bli_array_growone(arr)                                               \
-)
+#define BLI_array_grow_one(arr)  BLI_array_grow_items(arr, 1)
 
 
 /* appends an item to the array. */
 #define BLI_array_append(arr, item)  (                                        \
-       (void) BLI_array_growone(arr),                                            \
-       (void) (arr[_##arr##_count-1] = item)                                     \
+       (void) BLI_array_grow_one(arr),                                           \
+       (void) (arr[_##arr##_count - 1] = item)                                   \
 )
 
 /* appends an item to the array and returns a pointer to the item in the array.
  * item is not a pointer, but actual data value.*/
 #define BLI_array_append_r(arr, item)  (                                      \
-       (void) BLI_array_growone(arr),                                            \
-       (void) (arr[_##arr##_count-1] = item),                                    \
-       (&arr[_##arr##_count-1])                                                  \
+       (void) BLI_array_grow_one(arr),                                           \
+       (void) (arr[_##arr##_count - 1] = item),                                  \
+       (&arr[_##arr##_count - 1])                                                \
 )
 
-/* grow an array by a specified number of items. */
-/* TODO, this could be done in a less crappy way by not looping - campbell */
-#define BLI_array_growitems(arr, num)                                         \
-       if ((BLI_array_totalsize(arr) - _##arr##_count) >= num) {                 \
-           _##arr##_count += num;                                                \
-       }                                                                         \
-       else {                                                                    \
-               int _i;                                                               \
-               for (_i = 0; _i < (num); _i++) {                                      \
-                       BLI_array_growone(arr);                                           \
-               }                                                                     \
-       }
+#define BLI_array_reserve(arr, num)                                           \
+       BLI_array_grow_items(arr, num), (void)(_##arr##_count -= (num))
+
 
 #define BLI_array_free(arr)                                                   \
        if (arr && (char *)arr != _##arr##_static) {                              \
-               BLI_array_fake_user(arr);                                             \
-               MEM_freeN(arr);                                                       \
-       }
+           BLI_array_fake_user(arr);                                             \
+           MEM_freeN(arr);                                                       \
+       } (void)0
 
 #define BLI_array_pop(arr)  (                                                 \
-       (arr&&_##arr##_count) ?                                                   \
-               arr[--_##arr##_count] :                                               \
-               0                                                                     \
+       (arr && _##arr##_count) ?                                                 \
+           arr[--_##arr##_count] :                                               \
+           NULL                                                                  \
 )
 
 /* resets the logical size of an array to zero, but doesn't
  * free the memory. */
 #define BLI_array_empty(arr)                                                  \
-       _##arr##_count=0
+       { _##arr##_count = 0; } (void)0
 
 /* set the count of the array, doesn't actually increase the allocated array
  * size.  don't use this unless you know what you're doing. */
-#define BLI_array_set_length(arr, count)                                      \
-       _##arr##_count = (count)
+#define BLI_array_length_set(arr, count)                                      \
+       { _##arr##_count = (count); }(void)0
 
 /* only to prevent unused warnings */
 #define BLI_array_fake_user(arr)                                              \
-       (void)_##arr##_count,                                                     \
-       (void)_##arr##_tmp,                                                       \
-       (void)_##arr##_static
+       ((void)_##arr##_count,                                                    \
+        (void)_##arr##_static)
+
 
+/* -------------------------------------------------------------------- */
+/* other useful defines
+ * (unrelated to the main array macros) */
 
 /* not part of the 'API' but handy funcs,
  * same purpose as BLI_array_staticdeclare()
  * but use when the max size is known ahead of time */
 #define BLI_array_fixedstack_declare(arr, maxstatic, realsize, allocstr)      \
-       char _##arr##_static[maxstatic*sizeof(*arr)];                             \
-       const int _##arr##_is_static= ((void *)_##arr##_static) != (              \
-           arr= (realsize <= maxstatic) ?                                        \
+       char _##arr##_static[maxstatic * sizeof(*(arr))];                         \
+       const bool _##arr##_is_static = ((void *)_##arr##_static) != (            \
+           arr = ((realsize) <= maxstatic) ?                                     \
                (void *)_##arr##_static :                                         \
-               MEM_mallocN(sizeof(*arr)*realsize, allocstr)                      \
+               MEM_mallocN(sizeof(*(arr)) * (realsize), allocstr)                \
            )                                                                     \
 
 #define BLI_array_fixedstack_free(arr)                                        \
-       if (_##arr##_is_static) MEM_freeN(arr)                                    \
+       if (_##arr##_is_static) {                                                 \
+               MEM_freeN(arr);                                                       \
+       } (void)0
 
+#endif  /* __BLI_ARRAY_H__ */