Line data    Source code

       1             : #include "passgen/container/stack.h"
       2             : #include "passgen/assert.h"
       3             : #include <stdlib.h>
       4             : #include <string.h>
       5             : 
       6             : static const size_t passgen_stack_bin_size = 32;
       7             : static const size_t passgen_stack_cap_init = 4;
       8             : 
       9      103154 : static size_t passgen_stack_bins(const passgen_stack *stack) {
      10      103154 :     return (stack->len + stack->bin_size - 1) / stack->bin_size;
      11             : }
      12             : 
      13      170760 : static size_t passgen_stack_bin(const passgen_stack *stack, size_t pos) {
      14      170760 :     return pos / stack->bin_size;
      15             : }
      16             : 
      17      227645 : static size_t passgen_stack_bin_count(const passgen_stack *stack, size_t len) {
      18             :     (void) stack;
      19      227645 :     size_t power = 1;
      20      368364 :     while(power < len) {
      21      140719 :         power *= 2;
      22             :     }
      23      227645 :     return power;
      24             : }
      25             : 
      26             : // Initialize this stack.
      27      103154 : void passgen_stack_init(passgen_stack *stack, size_t element_size) {
      28      103154 :     memset(stack, 0, sizeof(*stack));
      29      103154 :     stack->element_size = element_size;
      30      103154 :     stack->bin_size = passgen_stack_bin_size;
      31      103154 : }
      32             : 
      33             : // Delete the memory for this stack.
      34      103154 : void passgen_stack_free(passgen_stack *stack) {
      35      103154 :     size_t bins = passgen_stack_bins(stack);
      36      203030 :     for(size_t i = 0; i < bins; i++) {
      37       99876 :         free(stack->data[i]);
      38             :     }
      39             : 
      40      103154 :     if(stack->len) {
      41       99849 :         free(stack->data);
      42             :     }
      43             : 
      44      103154 :     memset(stack, 0, sizeof(*stack));
      45      103154 : }
      46             : 
      47             : // Execute a function for every item on the stack.
      48           3 : void passgen_stack_foreach(
      49             :     const passgen_stack *stack,
      50             :     void (*func)(void *element)) {
      51           3 :     size_t full_bins = stack->len / stack->bin_size;
      52          10 :     for(size_t i = 0; i < full_bins; i++) {
      53           7 :         void *bin = stack->data[i];
      54         231 :         for(size_t j = 0; j < stack->bin_size; j++) {
      55         224 :             func(bin + j * stack->element_size);
      56             :         }
      57             :     }
      58           3 :     size_t last_bin_items = stack->len % stack->bin_size;
      59          33 :     for(size_t i = 0; i < last_bin_items; i++) {
      60          30 :         void *bin = stack->data[full_bins];
      61          30 :         func(bin + i * stack->element_size);
      62             :     }
      63           3 : }
      64             : 
      65             : // Push a new value onto this stack. If a non-NULL pointer is passed, it is
      66             : // copied to the new value. A pointer to the value on the stack is returned.
      67      169360 : void *passgen_stack_push(passgen_stack *stack, void *value) {
      68      169360 :     size_t new_bin = passgen_stack_bin(stack, stack->len);
      69             : 
      70             :     // initially allocate data
      71      169360 :     if(!new_bin) {
      72      168338 :         if(!stack->len) {
      73       99963 :             stack->data = calloc(1, sizeof(void *));
      74       99963 :             stack->data[0] =
      75       99963 :                 calloc(passgen_stack_cap_init, stack->element_size);
      76             :         }
      77      168338 :         if(passgen_stack_bin_count(stack, stack->len) == stack->len) {
      78       57467 :             size_t new_size = passgen_stack_bin_count(stack, stack->len + 1);
      79       57467 :             stack->data[0] =
      80       57467 :                 realloc(stack->data[0], new_size * stack->element_size);
      81             :         }
      82             :     } else {
      83        1022 :         size_t max_bin = passgen_stack_bin(stack, stack->len - 1);
      84             : 
      85             :         // do we need to increase the bins?
      86        1022 :         if(new_bin != max_bin) {
      87          33 :             size_t current_bins = passgen_stack_bin_count(stack, new_bin);
      88          33 :             size_t needed_bins = passgen_stack_bin_count(stack, new_bin + 1);
      89          33 :             if(current_bins != needed_bins) {
      90             :                 void **new_data =
      91          16 :                     realloc(stack->data, needed_bins * sizeof(void *));
      92          16 :                 passgen_assert(new_data);
      93          16 :                 stack->data = new_data;
      94             :             }
      95          33 :             stack->data[new_bin] = calloc(stack->bin_size, stack->element_size);
      96             :         }
      97             :     }
      98             : 
      99      169360 :     size_t offset = stack->len % stack->bin_size;
     100      169360 :     void *data = stack->data[new_bin] + offset * stack->element_size;
     101             : 
     102      169360 :     stack->len += 1;
     103      169360 :     if(value) {
     104        1245 :         memcpy(data, value, stack->element_size);
     105             :     }
     106             : 
     107      169360 :     return data;
     108             : }
     109             : 
     110             : // Get the nth element on the stack. If the position is invalid, returns NULL.
     111     1024885 : void *passgen_stack_get(const passgen_stack *stack, size_t pos) {
     112     1024885 :     if(stack->len <= pos) {
     113         714 :         return NULL;
     114             :     }
     115             : 
     116     1024171 :     size_t bin = pos / stack->bin_size;
     117     1024171 :     size_t offset = pos % stack->bin_size;
     118     1024171 :     return stack->data[bin] + offset * stack->element_size;
     119             : }
     120             : 
     121             : // Pop the largest element off the stack. If a non-NULL pointer is passed,
     122             : // the element's memory is copied into that value, and the passed pointer
     123             : // is returned. If the stack is empty, a NULL pointer is returned.
     124        1191 : void *passgen_stack_pop(passgen_stack *stack, void *element) {
     125        1191 :     if(!stack->len) {
     126           1 :         return NULL;
     127             :     }
     128             : 
     129        1190 :     if(element) {
     130         254 :         void *item = passgen_stack_top(stack);
     131         254 :         memcpy(element, item, stack->element_size);
     132             :     }
     133             : 
     134        1190 :     if(stack->len == 1) {
     135         114 :         free(stack->data[0]);
     136         114 :         stack->data[0] = NULL;
     137         114 :         free(stack->data);
     138         114 :         stack->data = NULL;
     139        1076 :     } else if(stack->len <= stack->bin_size) {
     140         887 :         size_t entry_size = passgen_stack_bin_count(stack, stack->len);
     141         887 :         size_t new_size = passgen_stack_bin_count(stack, stack->len - 1);
     142         887 :         if(entry_size != new_size) {
     143         833 :             stack->data[0] =
     144         833 :                 realloc(stack->data[0], new_size * stack->element_size);
     145             :         }
     146             :     } else {
     147         189 :         size_t max_bin = passgen_stack_bin(stack, stack->len - 1);
     148         189 :         size_t new_bin = passgen_stack_bin(stack, stack->len - 2);
     149         189 :         if(max_bin != new_bin) {
     150           6 :             free(stack->data[max_bin]);
     151           6 :             stack->data[max_bin] = NULL;
     152             :         }
     153             :     }
     154             : 
     155        1190 :     stack->len -= 1;
     156             : 
     157        1190 :     return element;
     158             : }
     159             : 
     160             : // Returns the topmost element of the stack, or NULL if the stack is empty.
     161      914710 : void *passgen_stack_top(const passgen_stack *stack) {
     162      914710 :     return passgen_stack_get(stack, stack->len > 0 ? stack->len - 1 : 0);
     163             : }