Line data    Source code

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