comparison: ucx/stack.c
ucx/stack.c
- changeset 185
- a48428642b4e
- parent 182
- 998bf7c643b4
- child 192
- 1e51558b9d09
equal
deleted
inserted
replaced
| 184:5c0990c95f74 | 185:a48428642b4e |
|---|---|
| 27 */ | 27 */ |
| 28 | 28 |
| 29 #include "stack.h" | 29 #include "stack.h" |
| 30 #include <string.h> | 30 #include <string.h> |
| 31 | 31 |
| 32 UcxStack ucx_stack_new(char* space, size_t size) { | 32 static size_t ucx_stack_align(size_t n) { |
| 33 UcxStack stack; | 33 int align = n % sizeof(void*); |
| 34 stack.size = size; | 34 if (align) { |
| 35 stack.space = stack.top = space; | 35 n += sizeof(void*) - align; |
| 36 } | |
| 37 return n; | |
| 38 } | |
| 39 | |
| 40 void ucx_stack_init(UcxStack *stack, char* space, size_t size) { | |
| 41 stack->size = size - size % sizeof(void*); | |
| 42 stack->space = space; | |
| 43 stack->top = NULL; | |
| 36 | 44 |
| 37 UcxAllocator alloc; | 45 stack->allocator.pool = stack; |
| 38 alloc.pool = &stack; | 46 stack->allocator.malloc = (ucx_allocator_malloc) ucx_stack_malloc; |
| 39 alloc.malloc = (ucx_allocator_malloc) ucx_stack_malloc; | 47 stack->allocator.calloc = (ucx_allocator_calloc) ucx_stack_calloc; |
| 40 alloc.calloc = (ucx_allocator_calloc) ucx_stack_calloc; | 48 stack->allocator.realloc = (ucx_allocator_realloc) ucx_stack_realloc; |
| 41 alloc.realloc = (ucx_allocator_realloc) ucx_stack_realloc; | 49 stack->allocator.free = (ucx_allocator_free) ucx_stack_free; |
| 42 alloc.free = (ucx_allocator_free) ucx_stack_free; | |
| 43 | |
| 44 stack.allocator = alloc; | |
| 45 | |
| 46 return stack; | |
| 47 } | 50 } |
| 48 | 51 |
| 49 void *ucx_stack_malloc(UcxStack *stack, size_t n) { | 52 void *ucx_stack_malloc(UcxStack *stack, size_t n) { |
| 50 n += n % sizeof(void*); | |
| 51 | 53 |
| 52 if (stack->top + n + sizeof(size_t) > stack->space + stack->size) { | 54 if (ucx_stack_avail(stack) < ucx_stack_align(n)) { |
| 53 return NULL; | 55 return NULL; |
| 54 } else { | 56 } else { |
| 55 void *ptr = stack->top; | 57 char *prev = stack->top; |
| 58 if (stack->top) { | |
| 59 stack->top += ucx_stack_align(ucx_stack_topsize(stack)); | |
| 60 } else { | |
| 61 stack->top = stack->space; | |
| 62 } | |
| 56 | 63 |
| 57 *((size_t*) (stack->top + n)) = n; | 64 ((struct ucx_stack_metadata*)stack->top)->prev = prev; |
| 58 stack->top += n + sizeof(size_t); | 65 ((struct ucx_stack_metadata*)stack->top)->size = n; |
| 66 stack->top += sizeof(struct ucx_stack_metadata); | |
| 59 | 67 |
| 60 return ptr; | 68 return stack->top; |
| 61 } | 69 } |
| 62 } | 70 } |
| 63 | 71 |
| 64 void *ucx_stack_calloc(UcxStack *stack, size_t nelem, size_t elsize) { | 72 void *ucx_stack_calloc(UcxStack *stack, size_t nelem, size_t elsize) { |
| 65 void *mem = ucx_stack_malloc(stack, nelem*elsize); | 73 void *mem = ucx_stack_malloc(stack, nelem*elsize); |
| 66 memset(mem, 0, nelem*elsize); | 74 memset(mem, 0, nelem*elsize); |
| 67 return mem; | 75 return mem; |
| 68 } | 76 } |
| 69 | 77 |
| 70 void *ucx_stack_realloc(UcxStack *stack, void *ptr, size_t n) { | 78 void *ucx_stack_realloc(UcxStack *stack, void *ptr, size_t n) { |
| 71 if (ptr == stack->top - sizeof(size_t) - *((size_t*) stack->top - 1)) { | 79 if (ptr == stack->top) { |
| 72 | 80 if (stack->size - (stack->top - stack->space) < ucx_stack_align(n)) { |
| 73 stack->top = (char*)ptr + n; | 81 return NULL; |
| 74 *((size_t*)stack->top) = n; | 82 } else { |
| 75 stack->top += sizeof(size_t); | 83 ((struct ucx_stack_metadata*)stack->top - 1)->size = n; |
| 76 | 84 return ptr; |
| 77 return ptr; | 85 } |
| 78 } else { | 86 } else { |
| 79 size_t* sptr = (size_t*) (((char*) ptr)-sizeof(size_t)); | 87 if (ucx_stack_align(((struct ucx_stack_metadata*)ptr - 1)->size) < |
| 80 if (*sptr < n) { | 88 ucx_stack_align(n)) { |
| 81 void *nptr = ucx_stack_malloc(stack, n); | 89 void *nptr = ucx_stack_malloc(stack, n); |
| 82 if (nptr) { | 90 if (nptr) { |
| 83 memcpy(nptr, ptr, *sptr); | 91 memcpy(nptr, ptr, n); |
| 84 ucx_stack_free(stack, ptr); | 92 ucx_stack_free(stack, ptr); |
| 93 | |
| 85 return nptr; | 94 return nptr; |
| 86 } else { | 95 } else { |
| 87 return NULL; | 96 return NULL; |
| 88 } | 97 } |
| 89 } else { | 98 } else { |
| 90 *sptr = n; | 99 ((struct ucx_stack_metadata*)ptr - 1)->size = n; |
| 91 return ptr; | 100 return ptr; |
| 92 } | 101 } |
| 93 } | 102 } |
| 94 } | 103 } |
| 95 | 104 |
| 96 void ucx_stack_free(UcxStack *stack, void *ptr) { | 105 void ucx_stack_free(UcxStack *stack, void *ptr) { |
| 97 if (ptr == stack->top+sizeof(size_t)) { | 106 if (ptr == stack->top) { |
| 98 | 107 stack->top = ((struct ucx_stack_metadata*) stack->top - 1)->prev; |
| 99 } else { | 108 } else { |
| 100 | 109 struct ucx_stack_metadata *next = (struct ucx_stack_metadata*)( |
| 110 (char*)ptr + | |
| 111 ucx_stack_align(((struct ucx_stack_metadata*) ptr - 1)->size) | |
| 112 ); | |
| 113 next->prev = ((struct ucx_stack_metadata*) ptr - 1)->prev; | |
| 101 } | 114 } |
| 102 } | 115 } |
| 103 | 116 |
| 104 void ucx_stack_pop(UcxStack *stack, void *dest) { | 117 void ucx_stack_popn(UcxStack *stack, void *dest, size_t n) { |
| 118 if (ucx_stack_empty(stack)) { | |
| 119 return; | |
| 120 } | |
| 121 | |
| 122 size_t len = ucx_stack_topsize(stack); | |
| 123 if (len > n) { | |
| 124 len = n; | |
| 125 } | |
| 126 | |
| 127 memcpy(dest, stack->top, len); | |
| 128 | |
| 129 ucx_stack_free(stack, stack->top); | |
| 105 } | 130 } |
| 106 | 131 |
| 107 void ucx_stack_popn(UcxStack *stack, void *dest, size_t n) { | 132 size_t ucx_stack_avail(UcxStack *stack) { |
| 133 size_t avail = ((stack->top ? (stack->size | |
| 134 - (stack->top - stack->space) | |
| 135 - ucx_stack_align(ucx_stack_topsize(stack))) | |
| 136 : stack->size)); | |
| 137 | |
| 138 if (avail > sizeof(struct ucx_stack_metadata)) { | |
| 139 return avail - sizeof(struct ucx_stack_metadata); | |
| 140 } else { | |
| 141 return 0; | |
| 142 } | |
| 108 } | 143 } |
