BLI_stack: various small additions

- add BLI_stack_count
- add BLI_stack_pop_n to pop into an array
- add BLI_stack_push_r, which returns a pointer that can be filled in

Also remove sanity check in BLI_stack_pop, assert if the stack is empty.

diff --git a/source/blender/blenlib/BLI_stack.h b/source/blender/blenlib/BLI_stack.h
index d65c8f024626f79e037f0546593d06b335485264..1e0b29bc7e8fe6488f1341dcff8e20111ad32787 100644 (file)
--- a/source/blender/blenlib/BLI_stack.h
+++ b/source/blender/blenlib/BLI_stack.h
@@ -34,16 +34,20 @@ typedef struct BLI_Stack BLI_Stack;
 
 BLI_Stack *BLI_stack_new_ex(
         const size_t elem_size, const char *description,
 
 BLI_Stack *BLI_stack_new_ex(
         const size_t elem_size, const char *description,

-        const size_t chunk_size) ATTR_NONNULL();
+        const size_t chunk_size) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL();

 BLI_Stack *BLI_stack_new(
 BLI_Stack *BLI_stack_new(

-        const size_t elem_size, const char *description) ATTR_NONNULL();
+        const size_t elem_size, const char *description) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL();

 
 void BLI_stack_free(BLI_Stack *stack) ATTR_NONNULL();
 
 
 void BLI_stack_free(BLI_Stack *stack) ATTR_NONNULL();
 

-void BLI_stack_push(BLI_Stack *stack, const void *src) ATTR_NONNULL();
+void *BLI_stack_push_r(BLI_Stack *stack) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL();
+void  BLI_stack_push(BLI_Stack *stack, const void *src) ATTR_NONNULL();

 
 

+void BLI_stack_pop_n(BLI_Stack *stack, void *dst, unsigned int n) ATTR_NONNULL();

 void BLI_stack_pop(BLI_Stack *stack, void *dst) ATTR_NONNULL();
 
 void BLI_stack_pop(BLI_Stack *stack, void *dst) ATTR_NONNULL();
 

-bool BLI_stack_is_empty(const BLI_Stack *stack) ATTR_NONNULL();
+size_t BLI_stack_count(const BLI_Stack *stack) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL();

 
 

-#endif
+bool BLI_stack_is_empty(const BLI_Stack *stack) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL();
+
+#endif  /* __BLI_STACK_H__ */

diff --git a/source/blender/blenlib/intern/stack.c b/source/blender/blenlib/intern/stack.c
index c2ee73d96932b1dc3452011bf610080558826f8a..9d6eecdba558751401d421ca0d2b05a6fc7aa665 100644 (file)
--- a/source/blender/blenlib/intern/stack.c
+++ b/source/blender/blenlib/intern/stack.c
@@ -35,7 +35,7 @@
 
 #include "BLI_strict_flags.h"
 
 
 #include "BLI_strict_flags.h"
 

-// #define USE_TOTELEM
+#define USE_TOTELEM

 
 #define CHUNK_EMPTY ((size_t)-1)
 /* target chunks size: 64kb */
 
 #define CHUNK_EMPTY ((size_t)-1)
 /* target chunks size: 64kb */


@@ -135,7 +135,7 @@ void BLI_stack_free(BLI_Stack *stack)
  * Copies the source value onto the stack (note that it copies
  * elem_size bytes from 'src', the pointer itself is not stored)
  */
  * Copies the source value onto the stack (note that it copies
  * elem_size bytes from 'src', the pointer itself is not stored)
  */

-void BLI_stack_push(BLI_Stack *stack, const void *src)
+void *BLI_stack_push_r(BLI_Stack *stack)

 {
        stack->chunk_index++;
 
 {
        stack->chunk_index++;
 


@@ -161,8 +161,14 @@ void BLI_stack_push(BLI_Stack *stack, const void *src)
        stack->totelem++;
 #endif
 
        stack->totelem++;
 #endif
 

-       /* Copy source to end of stack */
-       memcpy(CHUNK_LAST_ELEM(stack), src, stack->elem_size);
+       /* Return end of stack */
+       return CHUNK_LAST_ELEM(stack);
+}
+
+void BLI_stack_push(BLI_Stack *stack, const void *src)
+{
+       void *dst = BLI_stack_push_r(stack);
+       memcpy(dst, src, stack->elem_size);

 }
 
 /**
 }
 
 /**


@@ -175,29 +181,62 @@ void BLI_stack_pop(BLI_Stack *stack, void *dst)
 {
        BLI_assert(BLI_stack_is_empty(stack) == false);
 
 {
        BLI_assert(BLI_stack_is_empty(stack) == false);
 

-       if (!BLI_stack_is_empty(stack)) {
-               memcpy(dst, CHUNK_LAST_ELEM(stack), stack->elem_size);
+       memcpy(dst, CHUNK_LAST_ELEM(stack), stack->elem_size);

 #ifdef USE_TOTELEM
 #ifdef USE_TOTELEM

-               stack->totelem--;
+       stack->totelem--;

 #endif
 #endif

-               if (--stack->chunk_index == CHUNK_EMPTY) {
-                       struct StackChunk *chunk_free;
+       if (--stack->chunk_index == CHUNK_EMPTY) {
+               struct StackChunk *chunk_free;

 
 

-                       chunk_free        = stack->chunk_curr;
-                       stack->chunk_curr = stack->chunk_curr->next;
+               chunk_free        = stack->chunk_curr;
+               stack->chunk_curr = stack->chunk_curr->next;

 
 

-                       chunk_free->next  = stack->chunk_free;
-                       stack->chunk_free = chunk_free;
+               chunk_free->next  = stack->chunk_free;
+               stack->chunk_free = chunk_free;

 
 

-                       stack->chunk_index = stack->chunk_elem_max - 1;
-               }
+               stack->chunk_index = stack->chunk_elem_max - 1;
+       }
+}
+
+void BLI_stack_pop_n(BLI_Stack *stack, void *dst, unsigned int n)
+{
+       BLI_assert(n <= BLI_stack_count(stack));
+
+       while (n--) {
+               BLI_stack_pop(stack, dst);
+               dst = (void *)((char *)dst + stack->elem_size);

        }
 }
 
        }
 }
 

+size_t BLI_stack_count(const BLI_Stack *stack)
+{
+#ifdef USE_TOTELEM
+       return stack->totelem;
+#else
+       struct StackChunk *data = stack->chunk_curr;
+       size_t totelem = stack->chunk_index + 1;
+       size_t i;
+       if (totelem != stack->chunk_elem_max) {
+               data = data->next;
+       }
+       else {
+               totelem = 0;
+       }
+       for (i = 0; data; data = data->next) {
+               i++;
+       }
+       totelem += stack->chunk_elem_max * i;
+       return totelem;
+#endif
+}
+

 /**
  * Returns true if the stack is empty, false otherwise
  */
 bool BLI_stack_is_empty(const BLI_Stack *stack)
 {
 /**
  * Returns true if the stack is empty, false otherwise
  */
 bool BLI_stack_is_empty(const BLI_Stack *stack)
 {

+#ifdef USE_TOTELEM
+       BLI_assert((stack->chunk_curr == NULL) == (stack->totelem == 0));
+#endif

        return (stack->chunk_curr == NULL);
 }
        return (stack->chunk_curr == NULL);
 }

diff --git a/tests/gtests/blenlib/BLI_stack_test.cc b/tests/gtests/blenlib/BLI_stack_test.cc
index 8ad4d95781343df3f16655bef7db956caebd522f..c4884cb894056807a79155c113ffae37477bafee 100644 (file)
--- a/tests/gtests/blenlib/BLI_stack_test.cc
+++ b/tests/gtests/blenlib/BLI_stack_test.cc
@@ -17,6 +17,7 @@ TEST(stack, Empty)
 
        stack = BLI_stack_new(sizeof(int), __func__);
        EXPECT_EQ(BLI_stack_is_empty(stack), true);
 
        stack = BLI_stack_new(sizeof(int), __func__);
        EXPECT_EQ(BLI_stack_is_empty(stack), true);

+       EXPECT_EQ(BLI_stack_count(stack), 0);

        BLI_stack_free(stack);
 }
 
        BLI_stack_free(stack);
 }
 


@@ -29,9 +30,11 @@ TEST(stack, One)
 
        BLI_stack_push(stack, (void *)&in);
        EXPECT_EQ(BLI_stack_is_empty(stack), false);
 
        BLI_stack_push(stack, (void *)&in);
        EXPECT_EQ(BLI_stack_is_empty(stack), false);

+       EXPECT_EQ(BLI_stack_count(stack), 1);

        BLI_stack_pop(stack, (void *)&out);
        EXPECT_EQ(in, out);
        EXPECT_EQ(BLI_stack_is_empty(stack), true);
        BLI_stack_pop(stack, (void *)&out);
        EXPECT_EQ(in, out);
        EXPECT_EQ(BLI_stack_is_empty(stack), true);

+       EXPECT_EQ(BLI_stack_count(stack), 0);

        BLI_stack_free(stack);
 }
 
        BLI_stack_free(stack);
 }
 


@@ -79,7 +82,6 @@ TEST(stack, String)
                *((int *)in) = i;
                BLI_stack_pop(stack, (void *)&out);
                EXPECT_STREQ(in, out);
                *((int *)in) = i;
                BLI_stack_pop(stack, (void *)&out);
                EXPECT_STREQ(in, out);

-

        }
        EXPECT_EQ(BLI_stack_is_empty(stack), true);
 
        }
        EXPECT_EQ(BLI_stack_is_empty(stack), true);
 


@@ -133,5 +135,14 @@ TEST(stack, Reuse)
        EXPECT_EQ(i, 0);
        EXPECT_EQ(memcmp(sizes, sizes_test, sizeof(sizes) - sizeof(int)), 0);
 
        EXPECT_EQ(i, 0);
        EXPECT_EQ(memcmp(sizes, sizes_test, sizeof(sizes) - sizeof(int)), 0);
 

+
+       /* finally test BLI_stack_pop_n */
+       for (i = ARRAY_SIZE(sizes); i--; ) {
+               BLI_stack_push(stack, (void *)&sizes[i]);
+       }
+       EXPECT_EQ(BLI_stack_count(stack), ARRAY_SIZE(sizes));
+       BLI_stack_pop_n(stack, (void *)sizes_test, ARRAY_SIZE(sizes));
+       EXPECT_EQ(memcmp(sizes, sizes_test, sizeof(sizes) - sizeof(int)), 0);
+

        BLI_stack_free(stack);
 }
        BLI_stack_free(stack);
 }