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 103196 : static size_t passgen_stack_bins(const passgen_stack *stack) { 11 103196 : return (stack->len + stack->bin_size - 1) / stack->bin_size; 12 : } 13 : 14 169823 : static size_t passgen_stack_bin(const passgen_stack *stack, size_t pos) { 15 169823 : return pos / stack->bin_size; 16 : } 17 : 18 226433 : static size_t passgen_stack_bin_count(const passgen_stack *stack, size_t len) { 19 : (void) stack; 20 226433 : size_t power = 1; 21 363455 : while(power < len) { 22 137022 : power *= 2; 23 : } 24 226433 : return power; 25 : } 26 : 27 : // Initialize this stack. 28 103196 : void passgen_stack_init(passgen_stack *stack, size_t element_size) { 29 103196 : memset(stack, 0, sizeof(*stack)); 30 103196 : stack->element_size = element_size; 31 103196 : stack->bin_size = passgen_stack_bin_size; 32 103196 : } 33 : 34 : // Delete the memory for this stack. 35 103196 : void passgen_stack_free(passgen_stack *stack) { 36 103196 : size_t bins = passgen_stack_bins(stack); 37 203056 : for(size_t i = 0; i < bins; i++) { 38 99860 : free(stack->data[i]); 39 : } 40 : 41 103196 : if(stack->len) { 42 99833 : free(stack->data); 43 : } 44 : 45 103196 : PASSGEN_CLEAR(stack); 46 103196 : } 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 168423 : void *passgen_stack_push(passgen_stack *stack, void *value) { 69 168423 : size_t new_bin = passgen_stack_bin(stack, stack->len); 70 : 71 : // initially allocate data 72 168423 : if(!new_bin) { 73 167401 : if(!stack->len) { 74 99952 : stack->data = calloc(1, sizeof(void *)); 75 99952 : stack->data[0] = 76 99952 : calloc(passgen_stack_cap_init, stack->element_size); 77 : } 78 167401 : if(passgen_stack_bin_count(stack, stack->len) == stack->len) { 79 57202 : size_t new_size = passgen_stack_bin_count(stack, stack->len + 1); 80 57202 : stack->data[0] = 81 57202 : 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 168423 : size_t offset = stack->len % stack->bin_size; 101 168423 : void *data = stack->data[new_bin] + offset * stack->element_size; 102 : 103 168423 : stack->len += 1; 104 168423 : if(value) { 105 1245 : memcpy(data, value, stack->element_size); 106 : } 107 : 108 168423 : return data; 109 : } 110 : 111 : // Get the nth element on the stack. If the position is invalid, returns NULL. 112 1021172 : void *passgen_stack_get(const passgen_stack *stack, size_t pos) { 113 1021172 : if(stack->len <= pos) { 114 734 : return NULL; 115 : } 116 : 117 1020438 : size_t bin = pos / stack->bin_size; 118 1020438 : size_t offset = pos % stack->bin_size; 119 1020438 : 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 1191 : void *passgen_stack_pop(passgen_stack *stack, void *element) { 126 1191 : if(!stack->len) { 127 1 : return NULL; 128 : } 129 : 130 1190 : if(element) { 131 254 : void *item = passgen_stack_top(stack); 132 254 : memcpy(element, item, stack->element_size); 133 : } 134 : 135 1190 : 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 1071 : } else if(stack->len <= stack->bin_size) { 141 882 : size_t entry_size = passgen_stack_bin_count(stack, stack->len); 142 882 : size_t new_size = passgen_stack_bin_count(stack, stack->len - 1); 143 882 : if(entry_size != new_size) { 144 826 : stack->data[0] = 145 826 : 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 1190 : stack->len -= 1; 157 : 158 1190 : return element; 159 : } 160 : 161 : // Returns the topmost element of the stack, or NULL if the stack is empty. 162 911162 : void *passgen_stack_top(const passgen_stack *stack) { 163 911162 : return passgen_stack_get(stack, stack->len > 0 ? stack->len - 1 : 0); 164 : }