table.c 4.3 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186
  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. #include <string.h>
  29. #include <errno.h>
  30. #include <stdlib.h>
  31. #include <stdio.h>
  32. #include <stdint.h>
  33. #include "types.h"
  34. #include "table.h"
  35. // currently going with a binary lookup...
  36. static inline int compare(struct string a, struct string b) {
  37. size_t len;
  38. if (a.len > b.len)
  39. len = b.len;
  40. else
  41. len = a.len;
  42. int val = memcmp(a.data, b.data, len);
  43. if (val == 0) {
  44. if (a.len < b.len)
  45. return 1;
  46. else if (a.len > b.len)
  47. return -1;
  48. }
  49. return val;
  50. }
  51. static inline uint64_t search(struct table tbl, struct string name, uint8_t *exists) {
  52. if (tbl.len == 0) {
  53. *exists = 0;
  54. return 0;
  55. }
  56. size_t low = 0, high = tbl.len - 1;
  57. size_t mid = high/2;
  58. while (low != high) {
  59. int val = compare(tbl.array[mid].name, name);
  60. if (val == 0) {
  61. *exists = 1;
  62. return mid;
  63. } else if (val > 0) {
  64. low = mid + 1;
  65. if (mid > low)
  66. break;
  67. if (low > high)
  68. low = high;
  69. } else {
  70. high = mid - 1;
  71. if (mid < high)
  72. break;
  73. if (high < low)
  74. high = low;
  75. }
  76. mid = low + ((high-low)/2);
  77. }
  78. int val = compare(tbl.array[mid].name, name);
  79. if (val > 0) {
  80. *exists = 0;
  81. return mid+1;
  82. } else if (val == 0) {
  83. *exists = 1;
  84. return mid;
  85. } else {
  86. *exists = 0;
  87. return mid;
  88. }
  89. }
  90. int set_table_index(struct table *tbl, struct string name, void *ptr) {
  91. uint8_t exists;
  92. uint64_t index = search(*tbl, name, &exists);
  93. if (index == tbl->len) {
  94. void *tmp = realloc(tbl->array, sizeof(*(tbl->array)) * (tbl->len+1));
  95. if (tmp == 0)
  96. return 1;
  97. tbl->array = tmp;
  98. tbl->len++;
  99. } else if (!exists) {
  100. void *tmp = realloc(tbl->array, sizeof(*(tbl->array)) * (tbl->len+1));
  101. if (tmp == 0)
  102. return 1;
  103. tbl->array = tmp;
  104. memmove(&(tbl->array[index+1]), &(tbl->array[index]), (tbl->len - index) * sizeof(*(tbl->array)));
  105. tbl->len++;
  106. } else {
  107. tbl->array[index].ptr = ptr;
  108. return 0; // don't overwrite old allocated name
  109. }
  110. char *data = malloc(name.len);
  111. if (data == 0)
  112. return 1;
  113. memcpy(data, name.data, name.len);
  114. tbl->array[index] = (struct table_index){{data, name.len}, ptr};
  115. return 0;
  116. }
  117. void * get_table_index(struct table tbl, struct string name) {
  118. uint8_t exists;
  119. uint64_t index = search(tbl, name, &exists);
  120. if (!exists)
  121. return 0;
  122. return tbl.array[index].ptr;
  123. }
  124. uint8_t has_table_index(struct table tbl, struct string name) {
  125. uint8_t exists;
  126. search(tbl, name, &exists);
  127. return exists;
  128. }
  129. void * remove_table_index(struct table *tbl, struct string name) {
  130. uint8_t exists;
  131. uint64_t index = search(*tbl, name, &exists);
  132. if (!exists)
  133. return 0;
  134. void *ptr = tbl->array[index].ptr;
  135. free(tbl->array[index].name.data);
  136. memmove(&(tbl->array[index]), &(tbl->array[index+1]), (tbl->len - index - 1) * sizeof(*(tbl->array)));
  137. tbl->len--;
  138. void *tmp = realloc(tbl->array, sizeof(*(tbl->array)) * tbl->len);
  139. if (tmp || (tbl->len == 0))
  140. tbl->array = tmp;
  141. // else: realloc failed on shrinking... so now we have a table that's allocated a bit too big, not much of an issue
  142. return ptr;
  143. }
  144. void clear_table(struct table *tbl) {
  145. for (uint64_t i = 0; i < tbl->len; i++)
  146. free(tbl->array[i].name.data);
  147. tbl->array = realloc(tbl->array, 0);
  148. tbl->len = 0;
  149. }