Yusuf X
MBED port of https://github.com/ys1382/filagree . The only change is adding #define MBED
struct.c@0:1a89e28dea91, 2012-05-30 (annotated)
- Committer:
- yusufx
- Date:
- Wed May 30 21:13:01 2012 +0000
- Revision:
- 0:1a89e28dea91
Who changed what in which revision?
| User | Revision | Line number | New contents of line |
|---|---|---|---|
| yusufx | 0:1a89e28dea91 | 1 | /* struct.c |
| yusufx | 0:1a89e28dea91 | 2 | * |
| yusufx | 0:1a89e28dea91 | 3 | * implements array, byte_array, lifo and map |
| yusufx | 0:1a89e28dea91 | 4 | */ |
| yusufx | 0:1a89e28dea91 | 5 | |
| yusufx | 0:1a89e28dea91 | 6 | #include <stdio.h> |
| yusufx | 0:1a89e28dea91 | 7 | #include <stdlib.h> |
| yusufx | 0:1a89e28dea91 | 8 | #include <string.h> |
| yusufx | 0:1a89e28dea91 | 9 | #include <stdarg.h> |
| yusufx | 0:1a89e28dea91 | 10 | #include <assert.h> |
| yusufx | 0:1a89e28dea91 | 11 | #include <ctype.h> |
| yusufx | 0:1a89e28dea91 | 12 | |
| yusufx | 0:1a89e28dea91 | 13 | #include "vm.h" |
| yusufx | 0:1a89e28dea91 | 14 | #include "struct.h" |
| yusufx | 0:1a89e28dea91 | 15 | #include "util.h" |
| yusufx | 0:1a89e28dea91 | 16 | |
| yusufx | 0:1a89e28dea91 | 17 | #define BYTE_ARRAY_MAX_LEN 10000 |
| yusufx | 0:1a89e28dea91 | 18 | #define ERROR_BYTE_ARRAY_LEN "byte array too long" |
| yusufx | 0:1a89e28dea91 | 19 | |
| yusufx | 0:1a89e28dea91 | 20 | |
| yusufx | 0:1a89e28dea91 | 21 | // array /////////////////////////////////////////////////////////////////// |
| yusufx | 0:1a89e28dea91 | 22 | |
| yusufx | 0:1a89e28dea91 | 23 | struct array *array_new() { |
| yusufx | 0:1a89e28dea91 | 24 | return array_new_size(0); |
| yusufx | 0:1a89e28dea91 | 25 | } |
| yusufx | 0:1a89e28dea91 | 26 | |
| yusufx | 0:1a89e28dea91 | 27 | struct array *array_new_size(uint32_t size) { |
| yusufx | 0:1a89e28dea91 | 28 | struct array *a = (struct array*)malloc(sizeof(struct array)); |
| yusufx | 0:1a89e28dea91 | 29 | a->data = a->current = NULL; |
| yusufx | 0:1a89e28dea91 | 30 | a->length = 0; |
| yusufx | 0:1a89e28dea91 | 31 | return a; |
| yusufx | 0:1a89e28dea91 | 32 | } |
| yusufx | 0:1a89e28dea91 | 33 | |
| yusufx | 0:1a89e28dea91 | 34 | void array_del(struct array *a) { |
| yusufx | 0:1a89e28dea91 | 35 | for (int i=0; i<a->length; i++) |
| yusufx | 0:1a89e28dea91 | 36 | free(array_get(a, i)); |
| yusufx | 0:1a89e28dea91 | 37 | free(a->data); |
| yusufx | 0:1a89e28dea91 | 38 | free(a); |
| yusufx | 0:1a89e28dea91 | 39 | } |
| yusufx | 0:1a89e28dea91 | 40 | |
| yusufx | 0:1a89e28dea91 | 41 | void array_resize(struct array *a, uint32_t length) { |
| yusufx | 0:1a89e28dea91 | 42 | a->data = (void**)realloc(a->data, length * sizeof(void*)); |
| yusufx | 0:1a89e28dea91 | 43 | null_check(a->data); |
| yusufx | 0:1a89e28dea91 | 44 | memset(&a->data[a->length], 0, length-a->length); |
| yusufx | 0:1a89e28dea91 | 45 | a->length = length; |
| yusufx | 0:1a89e28dea91 | 46 | } |
| yusufx | 0:1a89e28dea91 | 47 | |
| yusufx | 0:1a89e28dea91 | 48 | uint32_t array_add(struct array *a, void *datum) { |
| yusufx | 0:1a89e28dea91 | 49 | a->data = (void**)realloc(a->data, (a->length+1) * sizeof(void*)); |
| yusufx | 0:1a89e28dea91 | 50 | a->data[a->length++] = datum; |
| yusufx | 0:1a89e28dea91 | 51 | return a->length-1; |
| yusufx | 0:1a89e28dea91 | 52 | } |
| yusufx | 0:1a89e28dea91 | 53 | |
| yusufx | 0:1a89e28dea91 | 54 | void array_insert(struct array *a, uint32_t index, void *datum) |
| yusufx | 0:1a89e28dea91 | 55 | { |
| yusufx | 0:1a89e28dea91 | 56 | a->data = (void**)realloc(a->data, (a->length+1) * sizeof(void*)); |
| yusufx | 0:1a89e28dea91 | 57 | uint32_t i; |
| yusufx | 0:1a89e28dea91 | 58 | for (i=a->length; i>index; i--) |
| yusufx | 0:1a89e28dea91 | 59 | a->data[i] = a->data[i-1]; |
| yusufx | 0:1a89e28dea91 | 60 | a->data[i] = datum; |
| yusufx | 0:1a89e28dea91 | 61 | a->length++; |
| yusufx | 0:1a89e28dea91 | 62 | } |
| yusufx | 0:1a89e28dea91 | 63 | |
| yusufx | 0:1a89e28dea91 | 64 | void* array_get(const struct array *a, uint32_t index) { |
| yusufx | 0:1a89e28dea91 | 65 | assert_message(a && index < a->length, ERROR_INDEX); |
| yusufx | 0:1a89e28dea91 | 66 | //DEBUGPRINT("array_get %d = %x\n", index, a->data[index]); |
| yusufx | 0:1a89e28dea91 | 67 | return a->data[index]; |
| yusufx | 0:1a89e28dea91 | 68 | } |
| yusufx | 0:1a89e28dea91 | 69 | |
| yusufx | 0:1a89e28dea91 | 70 | void array_set(struct array *a, uint32_t index, void* datum) { |
| yusufx | 0:1a89e28dea91 | 71 | null_check(a); |
| yusufx | 0:1a89e28dea91 | 72 | null_check(datum); |
| yusufx | 0:1a89e28dea91 | 73 | if (a->length <= index) |
| yusufx | 0:1a89e28dea91 | 74 | array_resize(a, index+1); |
| yusufx | 0:1a89e28dea91 | 75 | //DEBUGPRINT("array_set %d %x\n", index, datum); |
| yusufx | 0:1a89e28dea91 | 76 | a->data[index] = datum; |
| yusufx | 0:1a89e28dea91 | 77 | } |
| yusufx | 0:1a89e28dea91 | 78 | |
| yusufx | 0:1a89e28dea91 | 79 | void *list_remove(void *data, uint32_t *end, uint32_t start, int32_t length, size_t width) |
| yusufx | 0:1a89e28dea91 | 80 | { |
| yusufx | 0:1a89e28dea91 | 81 | null_check(data); |
| yusufx | 0:1a89e28dea91 | 82 | null_check(end); |
| yusufx | 0:1a89e28dea91 | 83 | length = length < 0 ? *end - start : length; |
| yusufx | 0:1a89e28dea91 | 84 | assert_message(start < *end && start+length <= *end, "index out of bounds"); |
| yusufx | 0:1a89e28dea91 | 85 | |
| yusufx | 0:1a89e28dea91 | 86 | memmove((uint8_t*)data+start*width, (uint8_t*)data+(start+length)*width, (*end-start-length)*width); |
| yusufx | 0:1a89e28dea91 | 87 | *end -= (uint32_t)length; |
| yusufx | 0:1a89e28dea91 | 88 | return realloc(data, *end * width); |
| yusufx | 0:1a89e28dea91 | 89 | } |
| yusufx | 0:1a89e28dea91 | 90 | |
| yusufx | 0:1a89e28dea91 | 91 | void array_remove(struct array *self, uint32_t start, int32_t length) { |
| yusufx | 0:1a89e28dea91 | 92 | self->data = (void**)list_remove(self->data, &self->length, start, length, sizeof(void*)); |
| yusufx | 0:1a89e28dea91 | 93 | } |
| yusufx | 0:1a89e28dea91 | 94 | |
| yusufx | 0:1a89e28dea91 | 95 | struct array *array_copy(const struct array* original) { |
| yusufx | 0:1a89e28dea91 | 96 | if (!original) |
| yusufx | 0:1a89e28dea91 | 97 | return NULL; |
| yusufx | 0:1a89e28dea91 | 98 | struct array* copy = (struct array*)malloc(sizeof(struct array)); |
| yusufx | 0:1a89e28dea91 | 99 | copy->data = (void**)malloc(original->length); |
| yusufx | 0:1a89e28dea91 | 100 | memcpy(copy->data, original->data, original->length); |
| yusufx | 0:1a89e28dea91 | 101 | copy->length = original->length; |
| yusufx | 0:1a89e28dea91 | 102 | copy->current = copy->data + (original->current - original->data); |
| yusufx | 0:1a89e28dea91 | 103 | return copy; |
| yusufx | 0:1a89e28dea91 | 104 | } |
| yusufx | 0:1a89e28dea91 | 105 | |
| yusufx | 0:1a89e28dea91 | 106 | struct array *array_part(struct array *within, uint32_t start, uint32_t length) |
| yusufx | 0:1a89e28dea91 | 107 | { |
| yusufx | 0:1a89e28dea91 | 108 | struct array *p = array_copy(within); |
| yusufx | 0:1a89e28dea91 | 109 | array_remove(p, start+length, within->length-start-length); |
| yusufx | 0:1a89e28dea91 | 110 | array_remove(p, 0, start); |
| yusufx | 0:1a89e28dea91 | 111 | return p; |
| yusufx | 0:1a89e28dea91 | 112 | } |
| yusufx | 0:1a89e28dea91 | 113 | |
| yusufx | 0:1a89e28dea91 | 114 | void array_append(struct array *a, const struct array* b) |
| yusufx | 0:1a89e28dea91 | 115 | { |
| yusufx | 0:1a89e28dea91 | 116 | null_check(a); |
| yusufx | 0:1a89e28dea91 | 117 | null_check(b); |
| yusufx | 0:1a89e28dea91 | 118 | array_resize(a, a->length + b->length); |
| yusufx | 0:1a89e28dea91 | 119 | memcpy(&a->data[a->length], b->data, b->length); |
| yusufx | 0:1a89e28dea91 | 120 | a->current = a->data + a->length; |
| yusufx | 0:1a89e28dea91 | 121 | } |
| yusufx | 0:1a89e28dea91 | 122 | |
| yusufx | 0:1a89e28dea91 | 123 | // byte_array /////////////////////////////////////////////////////////////// |
| yusufx | 0:1a89e28dea91 | 124 | |
| yusufx | 0:1a89e28dea91 | 125 | struct byte_array *byte_array_new() { |
| yusufx | 0:1a89e28dea91 | 126 | struct byte_array* ba = (struct byte_array*)malloc(sizeof(struct byte_array)); |
| yusufx | 0:1a89e28dea91 | 127 | ba->data = ba->current = 0; |
| yusufx | 0:1a89e28dea91 | 128 | ba->length = 0; |
| yusufx | 0:1a89e28dea91 | 129 | return ba; |
| yusufx | 0:1a89e28dea91 | 130 | } |
| yusufx | 0:1a89e28dea91 | 131 | |
| yusufx | 0:1a89e28dea91 | 132 | void byte_array_del(struct byte_array* ba) { |
| yusufx | 0:1a89e28dea91 | 133 | if (ba->data) |
| yusufx | 0:1a89e28dea91 | 134 | free(ba->data); |
| yusufx | 0:1a89e28dea91 | 135 | free(ba); |
| yusufx | 0:1a89e28dea91 | 136 | } |
| yusufx | 0:1a89e28dea91 | 137 | |
| yusufx | 0:1a89e28dea91 | 138 | struct byte_array *byte_array_new_size(uint32_t size) { |
| yusufx | 0:1a89e28dea91 | 139 | struct byte_array* ba = (struct byte_array*)malloc(sizeof(struct byte_array)); |
| yusufx | 0:1a89e28dea91 | 140 | ba->data = ba->current = (uint8_t*)malloc(size); |
| yusufx | 0:1a89e28dea91 | 141 | ba->length = size; |
| yusufx | 0:1a89e28dea91 | 142 | return ba; |
| yusufx | 0:1a89e28dea91 | 143 | } |
| yusufx | 0:1a89e28dea91 | 144 | |
| yusufx | 0:1a89e28dea91 | 145 | void byte_array_resize(struct byte_array* ba, uint32_t size) { |
| yusufx | 0:1a89e28dea91 | 146 | assert_message(ba->current >= ba->data, "byte_array corrupt"); |
| yusufx | 0:1a89e28dea91 | 147 | uint32_t delta = ba->current - ba->data; |
| yusufx | 0:1a89e28dea91 | 148 | ba->data = (uint8_t*)realloc(ba->data, size); |
| yusufx | 0:1a89e28dea91 | 149 | assert(ba->data); |
| yusufx | 0:1a89e28dea91 | 150 | ba->current = ba->data + delta; |
| yusufx | 0:1a89e28dea91 | 151 | ba->length = size; |
| yusufx | 0:1a89e28dea91 | 152 | } |
| yusufx | 0:1a89e28dea91 | 153 | |
| yusufx | 0:1a89e28dea91 | 154 | bool byte_array_equals(const struct byte_array *a, const struct byte_array* b) { |
| yusufx | 0:1a89e28dea91 | 155 | if (a==b) |
| yusufx | 0:1a89e28dea91 | 156 | return true; |
| yusufx | 0:1a89e28dea91 | 157 | if (!a != !b) // one is null and the other is not |
| yusufx | 0:1a89e28dea91 | 158 | return false; |
| yusufx | 0:1a89e28dea91 | 159 | if (a->length != b->length) |
| yusufx | 0:1a89e28dea91 | 160 | return false; |
| yusufx | 0:1a89e28dea91 | 161 | |
| yusufx | 0:1a89e28dea91 | 162 | int i; |
| yusufx | 0:1a89e28dea91 | 163 | for (i = 0; i<a->length; i++) |
| yusufx | 0:1a89e28dea91 | 164 | if (a->data[i] != b->data[i]) |
| yusufx | 0:1a89e28dea91 | 165 | return false; |
| yusufx | 0:1a89e28dea91 | 166 | return true; |
| yusufx | 0:1a89e28dea91 | 167 | } |
| yusufx | 0:1a89e28dea91 | 168 | |
| yusufx | 0:1a89e28dea91 | 169 | struct byte_array *byte_array_copy(const struct byte_array* original) { |
| yusufx | 0:1a89e28dea91 | 170 | if (!original) |
| yusufx | 0:1a89e28dea91 | 171 | return NULL; |
| yusufx | 0:1a89e28dea91 | 172 | struct byte_array* copy = (struct byte_array*)malloc(sizeof(struct byte_array)); |
| yusufx | 0:1a89e28dea91 | 173 | copy->data = (uint8_t*)malloc(original->length); |
| yusufx | 0:1a89e28dea91 | 174 | memcpy(copy->data, original->data, original->length); |
| yusufx | 0:1a89e28dea91 | 175 | copy->length = original->length; |
| yusufx | 0:1a89e28dea91 | 176 | copy->current = copy->data + (original->current - original->data); |
| yusufx | 0:1a89e28dea91 | 177 | return copy; |
| yusufx | 0:1a89e28dea91 | 178 | } |
| yusufx | 0:1a89e28dea91 | 179 | |
| yusufx | 0:1a89e28dea91 | 180 | void byte_array_append(struct byte_array *a, const struct byte_array* b) { |
| yusufx | 0:1a89e28dea91 | 181 | null_check(a); |
| yusufx | 0:1a89e28dea91 | 182 | null_check(b); |
| yusufx | 0:1a89e28dea91 | 183 | uint32_t offset = a->length; |
| yusufx | 0:1a89e28dea91 | 184 | byte_array_resize(a, a->length + b->length); |
| yusufx | 0:1a89e28dea91 | 185 | memcpy(&a->data[offset], b->data, b->length); |
| yusufx | 0:1a89e28dea91 | 186 | a->current = a->data + a->length; |
| yusufx | 0:1a89e28dea91 | 187 | } |
| yusufx | 0:1a89e28dea91 | 188 | |
| yusufx | 0:1a89e28dea91 | 189 | void byte_array_remove(struct byte_array *self, uint32_t start, int32_t length) { |
| yusufx | 0:1a89e28dea91 | 190 | self->data = (uint8_t*)list_remove(self->data, &self->length, start, length, sizeof(uint8_t)); |
| yusufx | 0:1a89e28dea91 | 191 | } |
| yusufx | 0:1a89e28dea91 | 192 | |
| yusufx | 0:1a89e28dea91 | 193 | struct byte_array *byte_array_part(struct byte_array *within, uint32_t start, uint32_t length) |
| yusufx | 0:1a89e28dea91 | 194 | { |
| yusufx | 0:1a89e28dea91 | 195 | struct byte_array *p = byte_array_copy(within); |
| yusufx | 0:1a89e28dea91 | 196 | byte_array_remove(p, start+length, within->length-start-length); |
| yusufx | 0:1a89e28dea91 | 197 | byte_array_remove(p, 0, start); |
| yusufx | 0:1a89e28dea91 | 198 | return p; |
| yusufx | 0:1a89e28dea91 | 199 | } |
| yusufx | 0:1a89e28dea91 | 200 | |
| yusufx | 0:1a89e28dea91 | 201 | struct byte_array *byte_array_from_string(const char* str) |
| yusufx | 0:1a89e28dea91 | 202 | { |
| yusufx | 0:1a89e28dea91 | 203 | int len = strlen(str); |
| yusufx | 0:1a89e28dea91 | 204 | struct byte_array* ba = byte_array_new_size(len); |
| yusufx | 0:1a89e28dea91 | 205 | memcpy(ba->data, str, len); |
| yusufx | 0:1a89e28dea91 | 206 | return ba; |
| yusufx | 0:1a89e28dea91 | 207 | } |
| yusufx | 0:1a89e28dea91 | 208 | |
| yusufx | 0:1a89e28dea91 | 209 | char* byte_array_to_string(const struct byte_array* ba) |
| yusufx | 0:1a89e28dea91 | 210 | { |
| yusufx | 0:1a89e28dea91 | 211 | int len = ba->length; |
| yusufx | 0:1a89e28dea91 | 212 | char* s = (char*)malloc(len+1); |
| yusufx | 0:1a89e28dea91 | 213 | memcpy(s, ba->data, len); |
| yusufx | 0:1a89e28dea91 | 214 | s[len] = 0; |
| yusufx | 0:1a89e28dea91 | 215 | return s; |
| yusufx | 0:1a89e28dea91 | 216 | } |
| yusufx | 0:1a89e28dea91 | 217 | |
| yusufx | 0:1a89e28dea91 | 218 | void byte_array_reset(struct byte_array* ba) { |
| yusufx | 0:1a89e28dea91 | 219 | ba->current = ba->data; |
| yusufx | 0:1a89e28dea91 | 220 | } |
| yusufx | 0:1a89e28dea91 | 221 | |
| yusufx | 0:1a89e28dea91 | 222 | struct byte_array *byte_array_concatenate(int n, const struct byte_array* ba, ...) |
| yusufx | 0:1a89e28dea91 | 223 | { |
| yusufx | 0:1a89e28dea91 | 224 | struct byte_array* result = byte_array_copy(ba); |
| yusufx | 0:1a89e28dea91 | 225 | |
| yusufx | 0:1a89e28dea91 | 226 | va_list argp; |
| yusufx | 0:1a89e28dea91 | 227 | for(va_start(argp, ba); --n;) { |
| yusufx | 0:1a89e28dea91 | 228 | struct byte_array* parameter = va_arg(argp, struct byte_array* ); |
| yusufx | 0:1a89e28dea91 | 229 | if (!parameter) |
| yusufx | 0:1a89e28dea91 | 230 | continue; |
| yusufx | 0:1a89e28dea91 | 231 | assert_message(result->length + parameter->length < BYTE_ARRAY_MAX_LEN, ERROR_BYTE_ARRAY_LEN); |
| yusufx | 0:1a89e28dea91 | 232 | byte_array_append(result, parameter); |
| yusufx | 0:1a89e28dea91 | 233 | } |
| yusufx | 0:1a89e28dea91 | 234 | |
| yusufx | 0:1a89e28dea91 | 235 | va_end(argp); |
| yusufx | 0:1a89e28dea91 | 236 | |
| yusufx | 0:1a89e28dea91 | 237 | if (result) |
| yusufx | 0:1a89e28dea91 | 238 | result->current = result->data + result->length; |
| yusufx | 0:1a89e28dea91 | 239 | return result; |
| yusufx | 0:1a89e28dea91 | 240 | } |
| yusufx | 0:1a89e28dea91 | 241 | |
| yusufx | 0:1a89e28dea91 | 242 | struct byte_array *byte_array_add_byte(struct byte_array *a, uint8_t b) { |
| yusufx | 0:1a89e28dea91 | 243 | byte_array_resize(a, a->length+1); |
| yusufx | 0:1a89e28dea91 | 244 | a->current = a->data + a->length; |
| yusufx | 0:1a89e28dea91 | 245 | a->data[a->length-1] = b; |
| yusufx | 0:1a89e28dea91 | 246 | return a; |
| yusufx | 0:1a89e28dea91 | 247 | } |
| yusufx | 0:1a89e28dea91 | 248 | |
| yusufx | 0:1a89e28dea91 | 249 | void byte_array_print(const char* text, const struct byte_array* ba) { |
| yusufx | 0:1a89e28dea91 | 250 | int offset = ba->current-ba->data; |
| yusufx | 0:1a89e28dea91 | 251 | if (text) |
| yusufx | 0:1a89e28dea91 | 252 | printf("%s @%d\n", text, offset); |
| yusufx | 0:1a89e28dea91 | 253 | for (int i=0; i<ba->length; i++) |
| yusufx | 0:1a89e28dea91 | 254 | printf("\t%s%d\n", i==offset?">":" ", ba->data[i]); |
| yusufx | 0:1a89e28dea91 | 255 | } |
| yusufx | 0:1a89e28dea91 | 256 | |
| yusufx | 0:1a89e28dea91 | 257 | int32_t byte_array_find(struct byte_array *within, struct byte_array *sought, uint32_t start) |
| yusufx | 0:1a89e28dea91 | 258 | { |
| yusufx | 0:1a89e28dea91 | 259 | null_check(within); |
| yusufx | 0:1a89e28dea91 | 260 | null_check(sought); |
| yusufx | 0:1a89e28dea91 | 261 | |
| yusufx | 0:1a89e28dea91 | 262 | uint32_t ws = within->length; |
| yusufx | 0:1a89e28dea91 | 263 | uint32_t ss = sought->length; |
| yusufx | 0:1a89e28dea91 | 264 | assert_message(start < within->length, "out of bounds"); |
| yusufx | 0:1a89e28dea91 | 265 | |
| yusufx | 0:1a89e28dea91 | 266 | uint8_t *wd = within->data; |
| yusufx | 0:1a89e28dea91 | 267 | uint8_t *sd = sought->data; |
| yusufx | 0:1a89e28dea91 | 268 | for (int32_t i=start; i<ws-ss+1; i++) |
| yusufx | 0:1a89e28dea91 | 269 | if (!memcmp(wd + i, sd, ss)) |
| yusufx | 0:1a89e28dea91 | 270 | return i; |
| yusufx | 0:1a89e28dea91 | 271 | |
| yusufx | 0:1a89e28dea91 | 272 | return -1; |
| yusufx | 0:1a89e28dea91 | 273 | } |
| yusufx | 0:1a89e28dea91 | 274 | |
| yusufx | 0:1a89e28dea91 | 275 | struct byte_array *byte_array_replace(struct byte_array *within, struct byte_array *replacement, uint32_t start, int32_t length) |
| yusufx | 0:1a89e28dea91 | 276 | { |
| yusufx | 0:1a89e28dea91 | 277 | null_check(within); |
| yusufx | 0:1a89e28dea91 | 278 | null_check(replacement); |
| yusufx | 0:1a89e28dea91 | 279 | uint32_t ws = within->length; |
| yusufx | 0:1a89e28dea91 | 280 | assert_message(start < ws, "index out of bounds"); |
| yusufx | 0:1a89e28dea91 | 281 | if (length < 0) |
| yusufx | 0:1a89e28dea91 | 282 | length = ws - start; |
| yusufx | 0:1a89e28dea91 | 283 | |
| yusufx | 0:1a89e28dea91 | 284 | int32_t new_length = within->length - length + replacement->length; |
| yusufx | 0:1a89e28dea91 | 285 | struct byte_array *replaced = byte_array_new_size(new_length); |
| yusufx | 0:1a89e28dea91 | 286 | |
| yusufx | 0:1a89e28dea91 | 287 | memcpy(replaced->data, within->data, start); |
| yusufx | 0:1a89e28dea91 | 288 | memcpy(replaced->data + start, replacement->data, replacement->length); |
| yusufx | 0:1a89e28dea91 | 289 | memcpy(replaced->data + start + replacement->length, within->data + start + length, within->length - start - length); |
| yusufx | 0:1a89e28dea91 | 290 | |
| yusufx | 0:1a89e28dea91 | 291 | return replaced; |
| yusufx | 0:1a89e28dea91 | 292 | } |
| yusufx | 0:1a89e28dea91 | 293 | |
| yusufx | 0:1a89e28dea91 | 294 | |
| yusufx | 0:1a89e28dea91 | 295 | // stack //////////////////////////////////////////////////////////////////// |
| yusufx | 0:1a89e28dea91 | 296 | |
| yusufx | 0:1a89e28dea91 | 297 | struct stack* stack_new() { |
| yusufx | 0:1a89e28dea91 | 298 | return (struct stack*)calloc(sizeof(struct stack), 1); |
| yusufx | 0:1a89e28dea91 | 299 | } |
| yusufx | 0:1a89e28dea91 | 300 | |
| yusufx | 0:1a89e28dea91 | 301 | struct stack_node* stack_node_new() { |
| yusufx | 0:1a89e28dea91 | 302 | return (struct stack_node*)calloc(sizeof(struct stack_node), 1); |
| yusufx | 0:1a89e28dea91 | 303 | } |
| yusufx | 0:1a89e28dea91 | 304 | |
| yusufx | 0:1a89e28dea91 | 305 | void stack_push(struct stack* stack, void* data) |
| yusufx | 0:1a89e28dea91 | 306 | { |
| yusufx | 0:1a89e28dea91 | 307 | null_check(data); |
| yusufx | 0:1a89e28dea91 | 308 | if (!stack->head) |
| yusufx | 0:1a89e28dea91 | 309 | stack->head = stack->tail = stack_node_new(); |
| yusufx | 0:1a89e28dea91 | 310 | else { |
| yusufx | 0:1a89e28dea91 | 311 | struct stack_node* old_head = stack->head; |
| yusufx | 0:1a89e28dea91 | 312 | stack->head = stack_node_new(); |
| yusufx | 0:1a89e28dea91 | 313 | null_check(stack->head); |
| yusufx | 0:1a89e28dea91 | 314 | stack->head->next = old_head; |
| yusufx | 0:1a89e28dea91 | 315 | } |
| yusufx | 0:1a89e28dea91 | 316 | stack->head->data = data; |
| yusufx | 0:1a89e28dea91 | 317 | } |
| yusufx | 0:1a89e28dea91 | 318 | |
| yusufx | 0:1a89e28dea91 | 319 | void* stack_pop(struct stack* stack) |
| yusufx | 0:1a89e28dea91 | 320 | { |
| yusufx | 0:1a89e28dea91 | 321 | if (!stack->head) |
| yusufx | 0:1a89e28dea91 | 322 | return NULL; |
| yusufx | 0:1a89e28dea91 | 323 | void* data = stack->head->data; |
| yusufx | 0:1a89e28dea91 | 324 | stack->head = stack->head->next; |
| yusufx | 0:1a89e28dea91 | 325 | null_check(data); |
| yusufx | 0:1a89e28dea91 | 326 | return data; |
| yusufx | 0:1a89e28dea91 | 327 | } |
| yusufx | 0:1a89e28dea91 | 328 | |
| yusufx | 0:1a89e28dea91 | 329 | void* stack_peek(const struct stack* stack, uint8_t index) |
| yusufx | 0:1a89e28dea91 | 330 | { |
| yusufx | 0:1a89e28dea91 | 331 | null_check(stack); |
| yusufx | 0:1a89e28dea91 | 332 | struct stack_node*p = stack->head; |
| yusufx | 0:1a89e28dea91 | 333 | for (; index && p; index--, p=p->next); |
| yusufx | 0:1a89e28dea91 | 334 | return p ? p->data : NULL; |
| yusufx | 0:1a89e28dea91 | 335 | } |
| yusufx | 0:1a89e28dea91 | 336 | |
| yusufx | 0:1a89e28dea91 | 337 | bool stack_empty(const struct stack* stack) |
| yusufx | 0:1a89e28dea91 | 338 | { |
| yusufx | 0:1a89e28dea91 | 339 | null_check(stack); |
| yusufx | 0:1a89e28dea91 | 340 | return stack->head == NULL;// && stack->tail == NULL; |
| yusufx | 0:1a89e28dea91 | 341 | } |
| yusufx | 0:1a89e28dea91 | 342 | |
| yusufx | 0:1a89e28dea91 | 343 | // map ///////////////////////////////////////////////////////////////////// |
| yusufx | 0:1a89e28dea91 | 344 | |
| yusufx | 0:1a89e28dea91 | 345 | static size_t def_hash_func(const struct byte_array* key) |
| yusufx | 0:1a89e28dea91 | 346 | { |
| yusufx | 0:1a89e28dea91 | 347 | size_t hash = 0; |
| yusufx | 0:1a89e28dea91 | 348 | int i = 0; |
| yusufx | 0:1a89e28dea91 | 349 | for (i = 0; i<key->length; i++) |
| yusufx | 0:1a89e28dea91 | 350 | hash += key->data[i]; |
| yusufx | 0:1a89e28dea91 | 351 | return hash; |
| yusufx | 0:1a89e28dea91 | 352 | } |
| yusufx | 0:1a89e28dea91 | 353 | |
| yusufx | 0:1a89e28dea91 | 354 | struct map* map_new() |
| yusufx | 0:1a89e28dea91 | 355 | { |
| yusufx | 0:1a89e28dea91 | 356 | struct map* m; |
| yusufx | 0:1a89e28dea91 | 357 | if (!(m =(struct map*)malloc(sizeof(struct map)))) return NULL; |
| yusufx | 0:1a89e28dea91 | 358 | m->size = 16; |
| yusufx | 0:1a89e28dea91 | 359 | m->hash_func = def_hash_func; |
| yusufx | 0:1a89e28dea91 | 360 | |
| yusufx | 0:1a89e28dea91 | 361 | if (!(m->nodes = (struct hash_node**)calloc(m->size, sizeof(struct hash_node*)))) { |
| yusufx | 0:1a89e28dea91 | 362 | free(m); |
| yusufx | 0:1a89e28dea91 | 363 | return NULL; |
| yusufx | 0:1a89e28dea91 | 364 | } |
| yusufx | 0:1a89e28dea91 | 365 | |
| yusufx | 0:1a89e28dea91 | 366 | return m; |
| yusufx | 0:1a89e28dea91 | 367 | } |
| yusufx | 0:1a89e28dea91 | 368 | |
| yusufx | 0:1a89e28dea91 | 369 | void map_del(struct map* m) |
| yusufx | 0:1a89e28dea91 | 370 | { |
| yusufx | 0:1a89e28dea91 | 371 | DEBUGPRINT("map_destroy\n"); |
| yusufx | 0:1a89e28dea91 | 372 | size_t n; |
| yusufx | 0:1a89e28dea91 | 373 | struct hash_node *node, *oldnode; |
| yusufx | 0:1a89e28dea91 | 374 | |
| yusufx | 0:1a89e28dea91 | 375 | for(n = 0; n<m->size; ++n) { |
| yusufx | 0:1a89e28dea91 | 376 | node = m->nodes[n]; |
| yusufx | 0:1a89e28dea91 | 377 | while (node) { |
| yusufx | 0:1a89e28dea91 | 378 | byte_array_del(node->key); |
| yusufx | 0:1a89e28dea91 | 379 | oldnode = node; |
| yusufx | 0:1a89e28dea91 | 380 | node = node->next; |
| yusufx | 0:1a89e28dea91 | 381 | free(oldnode); |
| yusufx | 0:1a89e28dea91 | 382 | } |
| yusufx | 0:1a89e28dea91 | 383 | } |
| yusufx | 0:1a89e28dea91 | 384 | free(m->nodes); |
| yusufx | 0:1a89e28dea91 | 385 | free(m); |
| yusufx | 0:1a89e28dea91 | 386 | } |
| yusufx | 0:1a89e28dea91 | 387 | |
| yusufx | 0:1a89e28dea91 | 388 | int map_insert(struct map* m, const struct byte_array* key, void *data) |
| yusufx | 0:1a89e28dea91 | 389 | { |
| yusufx | 0:1a89e28dea91 | 390 | struct hash_node *node; |
| yusufx | 0:1a89e28dea91 | 391 | size_t hash = m->hash_func(key) % m->size; |
| yusufx | 0:1a89e28dea91 | 392 | |
| yusufx | 0:1a89e28dea91 | 393 | node = m->nodes[hash]; |
| yusufx | 0:1a89e28dea91 | 394 | while (node) { |
| yusufx | 0:1a89e28dea91 | 395 | if (byte_array_equals(node->key, key)) { |
| yusufx | 0:1a89e28dea91 | 396 | node->data = data; |
| yusufx | 0:1a89e28dea91 | 397 | return 0; |
| yusufx | 0:1a89e28dea91 | 398 | } |
| yusufx | 0:1a89e28dea91 | 399 | node = node->next; |
| yusufx | 0:1a89e28dea91 | 400 | } |
| yusufx | 0:1a89e28dea91 | 401 | |
| yusufx | 0:1a89e28dea91 | 402 | if (!(node = (struct hash_node*)malloc(sizeof(struct hash_node)))) |
| yusufx | 0:1a89e28dea91 | 403 | return -1; |
| yusufx | 0:1a89e28dea91 | 404 | if (!(node->key = byte_array_copy(key))) { |
| yusufx | 0:1a89e28dea91 | 405 | free(node); |
| yusufx | 0:1a89e28dea91 | 406 | return -1; |
| yusufx | 0:1a89e28dea91 | 407 | } |
| yusufx | 0:1a89e28dea91 | 408 | node->data = data; |
| yusufx | 0:1a89e28dea91 | 409 | node->next = m->nodes[hash]; |
| yusufx | 0:1a89e28dea91 | 410 | m->nodes[hash] = node; |
| yusufx | 0:1a89e28dea91 | 411 | |
| yusufx | 0:1a89e28dea91 | 412 | return 0; |
| yusufx | 0:1a89e28dea91 | 413 | } |
| yusufx | 0:1a89e28dea91 | 414 | |
| yusufx | 0:1a89e28dea91 | 415 | struct array* map_keys(const struct map* m) { |
| yusufx | 0:1a89e28dea91 | 416 | struct array *a = array_new(); |
| yusufx | 0:1a89e28dea91 | 417 | for (int i=0; i<m->size; i++) |
| yusufx | 0:1a89e28dea91 | 418 | for (const struct hash_node* n = m->nodes[i]; n; n=n->next) |
| yusufx | 0:1a89e28dea91 | 419 | if (n->data) |
| yusufx | 0:1a89e28dea91 | 420 | array_add(a, n->key); |
| yusufx | 0:1a89e28dea91 | 421 | return a; |
| yusufx | 0:1a89e28dea91 | 422 | } |
| yusufx | 0:1a89e28dea91 | 423 | |
| yusufx | 0:1a89e28dea91 | 424 | struct array* map_values(const struct map* m) { |
| yusufx | 0:1a89e28dea91 | 425 | struct array *a = array_new(); |
| yusufx | 0:1a89e28dea91 | 426 | for (int i=0; i<m->size; i++) |
| yusufx | 0:1a89e28dea91 | 427 | for (const struct hash_node* n = m->nodes[i]; n; n=n->next) |
| yusufx | 0:1a89e28dea91 | 428 | if (n->data) |
| yusufx | 0:1a89e28dea91 | 429 | array_add(a, n->data); |
| yusufx | 0:1a89e28dea91 | 430 | return a; |
| yusufx | 0:1a89e28dea91 | 431 | } |
| yusufx | 0:1a89e28dea91 | 432 | |
| yusufx | 0:1a89e28dea91 | 433 | int map_remove(struct map* m, const struct byte_array* key) |
| yusufx | 0:1a89e28dea91 | 434 | { |
| yusufx | 0:1a89e28dea91 | 435 | struct hash_node *node, *prevnode = NULL; |
| yusufx | 0:1a89e28dea91 | 436 | size_t hash = m->hash_func(key)%m->size; |
| yusufx | 0:1a89e28dea91 | 437 | |
| yusufx | 0:1a89e28dea91 | 438 | node = m->nodes[hash]; |
| yusufx | 0:1a89e28dea91 | 439 | while(node) { |
| yusufx | 0:1a89e28dea91 | 440 | if (byte_array_equals(node->key, key)) { |
| yusufx | 0:1a89e28dea91 | 441 | byte_array_del(node->key); |
| yusufx | 0:1a89e28dea91 | 442 | if (prevnode) prevnode->next = node->next; |
| yusufx | 0:1a89e28dea91 | 443 | else m->nodes[hash] = node->next; |
| yusufx | 0:1a89e28dea91 | 444 | free(node); |
| yusufx | 0:1a89e28dea91 | 445 | return 0; |
| yusufx | 0:1a89e28dea91 | 446 | } |
| yusufx | 0:1a89e28dea91 | 447 | prevnode = node; |
| yusufx | 0:1a89e28dea91 | 448 | node = node->next; |
| yusufx | 0:1a89e28dea91 | 449 | } |
| yusufx | 0:1a89e28dea91 | 450 | return -1; |
| yusufx | 0:1a89e28dea91 | 451 | } |
| yusufx | 0:1a89e28dea91 | 452 | |
| yusufx | 0:1a89e28dea91 | 453 | bool map_has(const struct map* m, const struct byte_array* key) { |
| yusufx | 0:1a89e28dea91 | 454 | struct hash_node *node; |
| yusufx | 0:1a89e28dea91 | 455 | size_t hash = m->hash_func(key) % m->size; |
| yusufx | 0:1a89e28dea91 | 456 | node = m->nodes[hash]; |
| yusufx | 0:1a89e28dea91 | 457 | while (node) { |
| yusufx | 0:1a89e28dea91 | 458 | if (byte_array_equals(node->key, key)) |
| yusufx | 0:1a89e28dea91 | 459 | return true; |
| yusufx | 0:1a89e28dea91 | 460 | node = node->next; |
| yusufx | 0:1a89e28dea91 | 461 | } |
| yusufx | 0:1a89e28dea91 | 462 | return false; |
| yusufx | 0:1a89e28dea91 | 463 | } |
| yusufx | 0:1a89e28dea91 | 464 | |
| yusufx | 0:1a89e28dea91 | 465 | void *map_get(const struct map* m, const struct byte_array* key) |
| yusufx | 0:1a89e28dea91 | 466 | { |
| yusufx | 0:1a89e28dea91 | 467 | struct hash_node *node; |
| yusufx | 0:1a89e28dea91 | 468 | size_t hash = m->hash_func(key) % m->size; |
| yusufx | 0:1a89e28dea91 | 469 | node = m->nodes[hash]; |
| yusufx | 0:1a89e28dea91 | 470 | while (node) { |
| yusufx | 0:1a89e28dea91 | 471 | if (byte_array_equals(node->key, key)) |
| yusufx | 0:1a89e28dea91 | 472 | return node->data; |
| yusufx | 0:1a89e28dea91 | 473 | node = node->next; |
| yusufx | 0:1a89e28dea91 | 474 | } |
| yusufx | 0:1a89e28dea91 | 475 | return NULL; |
| yusufx | 0:1a89e28dea91 | 476 | } |
| yusufx | 0:1a89e28dea91 | 477 | |
| yusufx | 0:1a89e28dea91 | 478 | int map_resize(struct map* m, size_t size) |
| yusufx | 0:1a89e28dea91 | 479 | { |
| yusufx | 0:1a89e28dea91 | 480 | DEBUGPRINT("map_resize\n"); |
| yusufx | 0:1a89e28dea91 | 481 | struct map newtbl; |
| yusufx | 0:1a89e28dea91 | 482 | size_t n; |
| yusufx | 0:1a89e28dea91 | 483 | struct hash_node *node,*next; |
| yusufx | 0:1a89e28dea91 | 484 | |
| yusufx | 0:1a89e28dea91 | 485 | newtbl.size = size; |
| yusufx | 0:1a89e28dea91 | 486 | newtbl.hash_func = m->hash_func; |
| yusufx | 0:1a89e28dea91 | 487 | |
| yusufx | 0:1a89e28dea91 | 488 | if (!(newtbl.nodes = (struct hash_node**)calloc(size, sizeof(struct hash_node*)))) |
| yusufx | 0:1a89e28dea91 | 489 | return -1; |
| yusufx | 0:1a89e28dea91 | 490 | |
| yusufx | 0:1a89e28dea91 | 491 | for(n = 0; n<m->size; ++n) { |
| yusufx | 0:1a89e28dea91 | 492 | for(node = m->nodes[n]; node; node = next) { |
| yusufx | 0:1a89e28dea91 | 493 | next = node->next; |
| yusufx | 0:1a89e28dea91 | 494 | map_insert(&newtbl, node->key, node->data); |
| yusufx | 0:1a89e28dea91 | 495 | map_remove(m, node->key); |
| yusufx | 0:1a89e28dea91 | 496 | |
| yusufx | 0:1a89e28dea91 | 497 | } |
| yusufx | 0:1a89e28dea91 | 498 | } |
| yusufx | 0:1a89e28dea91 | 499 | |
| yusufx | 0:1a89e28dea91 | 500 | free(m->nodes); |
| yusufx | 0:1a89e28dea91 | 501 | m->size = newtbl.size; |
| yusufx | 0:1a89e28dea91 | 502 | m->nodes = newtbl.nodes; |
| yusufx | 0:1a89e28dea91 | 503 | |
| yusufx | 0:1a89e28dea91 | 504 | return 0; |
| yusufx | 0:1a89e28dea91 | 505 | } |
| yusufx | 0:1a89e28dea91 | 506 | |
| yusufx | 0:1a89e28dea91 | 507 | // in case of intersection, a wins |
| yusufx | 0:1a89e28dea91 | 508 | void map_update(struct map *a, const struct map *b) |
| yusufx | 0:1a89e28dea91 | 509 | { |
| yusufx | 0:1a89e28dea91 | 510 | const struct array *keys = map_keys(b); |
| yusufx | 0:1a89e28dea91 | 511 | for (int i=0; i<keys->length; i++) { |
| yusufx | 0:1a89e28dea91 | 512 | const struct byte_array *key = (const struct byte_array*)array_get(keys, i); |
| yusufx | 0:1a89e28dea91 | 513 | if (!map_has(a, key)) |
| yusufx | 0:1a89e28dea91 | 514 | map_insert(a, key, map_get(b, key)); |
| yusufx | 0:1a89e28dea91 | 515 | } |
| yusufx | 0:1a89e28dea91 | 516 | } |