Ethan Yonker | 6bb26b5 | 2016-01-10 22:26:51 -0600 | [diff] [blame] | 1 | #include "dynarray.h" |
| 2 | #include <stdlib.h> |
| 3 | #include <limits.h> |
| 4 | #include <string.h> |
| 5 | |
| 6 | void |
| 7 | dynarray_init( dynarray_t *a ) |
| 8 | { |
| 9 | a->count = a->capacity = 0; |
| 10 | a->items = NULL; |
| 11 | } |
| 12 | |
| 13 | |
| 14 | static void |
| 15 | dynarray_reserve_more( dynarray_t *a, int count ) |
| 16 | { |
| 17 | int old_cap = a->capacity; |
| 18 | int new_cap = old_cap; |
| 19 | const int max_cap = INT_MAX/sizeof(void*); |
| 20 | void** new_items; |
| 21 | int new_count = a->count + count; |
| 22 | |
| 23 | if (count <= 0) |
| 24 | return; |
| 25 | |
| 26 | if (count > max_cap - a->count) |
| 27 | abort(); |
| 28 | |
| 29 | new_count = a->count + count; |
| 30 | |
| 31 | while (new_cap < new_count) { |
| 32 | old_cap = new_cap; |
| 33 | new_cap += (new_cap >> 2) + 4; |
| 34 | if (new_cap < old_cap || new_cap > max_cap) { |
| 35 | new_cap = max_cap; |
| 36 | } |
| 37 | } |
| 38 | new_items = realloc(a->items, new_cap*sizeof(void*)); |
| 39 | if (new_items == NULL) |
| 40 | abort(); |
| 41 | |
| 42 | a->items = new_items; |
| 43 | a->capacity = new_cap; |
| 44 | } |
| 45 | |
| 46 | void |
| 47 | dynarray_append( dynarray_t *a, void* item ) |
| 48 | { |
| 49 | if (a->count >= a->capacity) |
| 50 | dynarray_reserve_more(a, 1); |
| 51 | |
| 52 | a->items[a->count++] = item; |
| 53 | } |
| 54 | |
| 55 | void |
| 56 | dynarray_done( dynarray_t *a ) |
| 57 | { |
| 58 | free(a->items); |
| 59 | a->items = NULL; |
| 60 | a->count = a->capacity = 0; |
| 61 | } |
| 62 | |
| 63 | // string arrays |
| 64 | |
| 65 | void strlist_init( strlist_t *list ) |
| 66 | { |
| 67 | dynarray_init(list); |
| 68 | } |
| 69 | |
| 70 | void strlist_append_b( strlist_t *list, const void* str, size_t slen ) |
| 71 | { |
| 72 | char *copy = malloc(slen+1); |
| 73 | memcpy(copy, str, slen); |
| 74 | copy[slen] = '\0'; |
| 75 | dynarray_append(list, copy); |
| 76 | } |
| 77 | |
| 78 | void strlist_append_dup( strlist_t *list, const char *str) |
| 79 | { |
| 80 | strlist_append_b(list, str, strlen(str)); |
| 81 | } |
| 82 | |
| 83 | void strlist_done( strlist_t *list ) |
| 84 | { |
| 85 | STRLIST_FOREACH(list, string, free(string)); |
| 86 | dynarray_done(list); |
| 87 | } |
| 88 | |
| 89 | static int strlist_compare_strings(const void* a, const void* b) |
| 90 | { |
| 91 | const char *sa = *(const char **)a; |
| 92 | const char *sb = *(const char **)b; |
| 93 | return strcmp(sa, sb); |
| 94 | } |
| 95 | |
| 96 | void strlist_sort( strlist_t *list ) |
| 97 | { |
| 98 | if (list->count > 0) { |
| 99 | qsort(list->items, |
| 100 | (size_t)list->count, |
| 101 | sizeof(void*), |
| 102 | strlist_compare_strings); |
| 103 | } |
| 104 | } |