table.c

   1 // My table library thing
   2 //
   3 // Written by: Test_User <hax@andrewyu.org>
   4 //
   5 // This is free and unencumbered software released into the public
   6 // domain.
   7 //
   8 // Anyone is free to copy, modify, publish, use, compile, sell, or
   9 // distribute this software, either in source code form or as a compiled
  10 // binary, for any purpose, commercial or non-commercial, and by any
  11 // means.
  12 //
  13 // In jurisdictions that recognize copyright laws, the author or authors
  14 // of this software dedicate any and all copyright interest in the
  15 // software to the public domain. We make this dedication for the benefit
  16 // of the public at large and to the detriment of our heirs and
  17 // successors. We intend this dedication to be an overt act of
  18 // relinquishment in perpetuity of all present and future rights to this
  19 // software under copyright law.
  20 //
  21 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  22 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  23 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
  24 // IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR
  25 // OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
  26 // ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
  27 // OTHER DEALINGS IN THE SOFTWARE.
  28
  29 #include <string.h>
  30 #include <errno.h>
  31 #include <stdlib.h>
  32 #include <stdio.h>
  33 #include <stdint.h>
  34
  35 #include "types.h"
  36 #include "table.h"
  37
  38 // currently going with a binary lookup...
  39
  40 static inline int compare(struct string a, struct string b) {
  41         size_t len;
  42         if (a.len > b.len)
  43                 len = b.len;
  44         else
  45                 len = a.len;
  46
  47         int val = memcmp(a.data, b.data, len);
  48
  49         if (val == 0) {
  50                 if (a.len < b.len)
  51                         return 1;
  52                 else if (a.len > b.len)
  53                         return -1;
  54         }
  55
  56         return val;
  57 }
  58
  59 static inline uint64_t search(struct table tbl, struct string name, uint8_t *exists) {
  60         if (tbl.len == 0) {
  61                 *exists = 0;
  62                 return 0;
  63         }
  64
  65         size_t low = 0, high = tbl.len - 1;
  66
  67         size_t mid = high/2;
  68
  69         while (low != high) {
  70                 int val = compare(tbl.array[mid].name, name);
  71
  72                 if (val == 0) {
  73                         *exists = 1;
  74                         return mid;
  75                 } else if (val > 0) {
  76                         low = mid + 1;
  77                         if (mid > low)
  78                                 break;
  79                         if (low > high)
  80                                 low = high;
  81                 } else {
  82                         high = mid - 1;
  83                         if (mid < high)
  84                                 break;
  85                         if (high < low)
  86                                 high = low;
  87                 }
  88
  89                 mid = low + ((high-low)/2);
  90         }
  91
  92         int val = compare(tbl.array[mid].name, name);
  93         if (val > 0) {
  94                 *exists = 0;
  95                 return mid+1;
  96         } else if (val == 0) {
  97                 *exists = 1;
  98                 return mid;
  99         } else {
 100                 *exists = 0;
 101                 return mid;
 102         }
 103 }
 104
 105 int set_table_index(struct table *tbl, struct string name, void *ptr) {
 106         uint8_t exists;
 107         uint64_t index = search(*tbl, name, &exists);
 108
 109         if (index == tbl->len) {
 110                 void *tmp = realloc(tbl->array, sizeof(*(tbl->array)) * (tbl->len+1));
 111                 if (tmp == 0)
 112                         return 1;
 113
 114                 tbl->array = tmp;
 115
 116                 tbl->len++;
 117         } else if (!exists) {
 118                 void *tmp = realloc(tbl->array, sizeof(*(tbl->array)) * (tbl->len+1));
 119                 if (tmp == 0)
 120                         return 1;
 121
 122                 tbl->array = tmp;
 123
 124                 memmove(&(tbl->array[index+1]), &(tbl->array[index]), (tbl->len - index) * sizeof(*(tbl->array)));
 125                 tbl->len++;
 126         } else {
 127                 tbl->array[index].ptr = ptr;
 128
 129                 return 0; // don't overwrite old allocated name
 130         }
 131
 132         char *data = malloc(name.len);
 133         if (data == 0)
 134                 return 1;
 135
 136         memcpy(data, name.data, name.len);
 137
 138         tbl->array[index] = (struct table_index){{data, name.len}, ptr};
 139
 140         return 0;
 141 }
 142
 143 void * get_table_index(struct table tbl, struct string name) {
 144         uint8_t exists;
 145         uint64_t index = search(tbl, name, &exists);
 146         if (!exists)
 147                 return 0;
 148
 149         return tbl.array[index].ptr;
 150 }
 151
 152 uint8_t has_table_index(struct table tbl, struct string name) {
 153         uint8_t exists;
 154         search(tbl, name, &exists);
 155         return exists;
 156 }
 157
 158 void * remove_table_index(struct table *tbl, struct string name) {
 159         uint8_t exists;
 160         uint64_t index = search(*tbl, name, &exists);
 161
 162         if (!exists)
 163                 return 0;
 164
 165         void *ptr = tbl->array[index].ptr;
 166         free(tbl->array[index].name.data);
 167
 168         memmove(&(tbl->array[index]), &(tbl->array[index+1]), (tbl->len - index - 1) * sizeof(*(tbl->array)));
 169         tbl->len--;
 170
 171         void *tmp = realloc(tbl->array, sizeof(*(tbl->array)) * tbl->len);
 172         if (tmp || (tbl->len == 0))
 173                 tbl->array = tmp;
 174         // else: realloc failed on shrinking... so now we have a table that's allocated a bit too big, not much of an issue
 175
 176         return ptr;
 177 }
 178
 179 void clear_table(struct table *tbl) {
 180         for (uint64_t i = 0; i < tbl->len; i++)
 181                 free(tbl->array[i].name.data);
 182
 183         tbl->array = realloc(tbl->array, 0);
 184         tbl->len = 0;
 185 }