1.1 --- a/types.c Sun Jun 15 23:15:59 2008 -0400
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,246 +0,0 @@
1.4 -#include <stdlib.h>
1.5 -#include <string.h>
1.6 -
1.7 -#include "types.h"
1.8 -
1.9 -void
1.10 -array_init(struct array *array)
1.11 -{
1.12 - memset(array, 0, sizeof *array);
1.13 -}
1.14 -
1.15 -void
1.16 -array_release(struct array *array)
1.17 -{
1.18 - free(array->data);
1.19 -}
1.20 -
1.21 -void *
1.22 -array_add(struct array *array, int size)
1.23 -{
1.24 - int alloc;
1.25 - void *data, *p;
1.26 -
1.27 - if (array->alloc > 0)
1.28 - alloc = array->alloc;
1.29 - else
1.30 - alloc = 16;
1.31 -
1.32 - while (alloc < array->size + size)
1.33 - alloc *= 2;
1.34 -
1.35 - if (array->alloc < alloc) {
1.36 - data = realloc(array->data, alloc);
1.37 - if (data == NULL)
1.38 - return 0;
1.39 - array->data = data;
1.40 - array->alloc = alloc;
1.41 - }
1.42 -
1.43 - p = array->data + array->size;
1.44 - array->size += size;
1.45 -
1.46 - return p;
1.47 -}
1.48 -
1.49 -/* RAZOR_IMMEDIATE and RAZOR_ENTRY_LAST must have the same value */
1.50 -#define RAZOR_ENTRY_LAST 0x80
1.51 -#define RAZOR_IMMEDIATE 0x80
1.52 -#define RAZOR_EMPTY_LIST 0xff
1.53 -
1.54 -void
1.55 -list_set_empty(struct list_head *head)
1.56 -{
1.57 - head->list_ptr = ~0;
1.58 - head->flags = RAZOR_EMPTY_LIST;
1.59 -}
1.60 -
1.61 -void
1.62 -list_set_ptr(struct list_head *head, uint32_t ptr)
1.63 -{
1.64 - head->list_ptr = ptr;
1.65 - head->flags = 0;
1.66 -}
1.67 -
1.68 -void
1.69 -list_set_array(struct list_head *head, struct array *pool,
1.70 - struct array *items, int force_indirect)
1.71 -{
1.72 - struct list *p;
1.73 -
1.74 - if (!force_indirect) {
1.75 - if (items->size == 0) {
1.76 - list_set_empty(head);
1.77 - return;
1.78 - } else if (items->size == sizeof (uint32_t)) {
1.79 - head->list_ptr = *(uint32_t *) items->data;
1.80 - head->flags = RAZOR_IMMEDIATE;
1.81 - return;
1.82 - }
1.83 - }
1.84 -
1.85 - p = array_add(pool, items->size);
1.86 - memcpy(p, items->data, items->size);
1.87 - p[items->size / sizeof *p - 1].flags = RAZOR_ENTRY_LAST;
1.88 - list_set_ptr(head, p - (struct list *) pool->data);
1.89 -}
1.90 -
1.91 -struct list *
1.92 -list_first(struct list_head *head, struct array *pool)
1.93 -{
1.94 - if (head->flags == RAZOR_EMPTY_LIST)
1.95 - return NULL;
1.96 - else if (head->flags == RAZOR_IMMEDIATE)
1.97 - return (struct list *) head;
1.98 - else
1.99 - return (struct list *) pool->data + head->list_ptr;
1.100 -}
1.101 -
1.102 -struct list *
1.103 -list_next(struct list *list)
1.104 -{
1.105 - if (list->flags)
1.106 - return NULL;
1.107 - return ++list;
1.108 -}
1.109 -
1.110 -void
1.111 -list_remap_pool(struct array *pool, uint32_t *map)
1.112 -{
1.113 - struct list *p, *end;
1.114 -
1.115 - end = pool->data + pool->size;
1.116 - for (p = pool->data; p < end; p++)
1.117 - p->data = map[p->data];
1.118 -}
1.119 -
1.120 -void
1.121 -list_remap_head(struct list_head *head, uint32_t *map)
1.122 -{
1.123 - if (head->flags == RAZOR_IMMEDIATE)
1.124 - head->list_ptr = map[head->list_ptr];
1.125 -}
1.126 -
1.127 -
1.128 -void
1.129 -hashtable_init(struct hashtable *table, struct array *pool)
1.130 -{
1.131 - array_init(&table->buckets);
1.132 - table->pool = pool;
1.133 -}
1.134 -
1.135 -void
1.136 -hashtable_release(struct hashtable *table)
1.137 -{
1.138 - array_release(&table->buckets);
1.139 -}
1.140 -
1.141 -static unsigned int
1.142 -hash_string(const char *key)
1.143 -{
1.144 - const char *p;
1.145 - unsigned int hash = 0;
1.146 -
1.147 - for (p = key; *p; p++)
1.148 - hash = (hash * 617) ^ *p;
1.149 -
1.150 - return hash;
1.151 -}
1.152 -
1.153 -uint32_t
1.154 -hashtable_lookup(struct hashtable *table, const char *key)
1.155 -{
1.156 - unsigned int mask, start, i;
1.157 - uint32_t *b;
1.158 - char *pool;
1.159 -
1.160 - pool = table->pool->data;
1.161 - mask = table->buckets.alloc - 1;
1.162 - start = hash_string(key) * sizeof(uint32_t);
1.163 -
1.164 - for (i = 0; i < table->buckets.alloc; i += sizeof *b) {
1.165 - b = table->buckets.data + ((start + i) & mask);
1.166 -
1.167 - if (*b == 0)
1.168 - return 0;
1.169 -
1.170 - if (strcmp(key, &pool[*b]) == 0)
1.171 - return *b;
1.172 - }
1.173 -
1.174 - return 0;
1.175 -}
1.176 -
1.177 -static void
1.178 -do_insert(struct hashtable *table, uint32_t value)
1.179 -{
1.180 - unsigned int mask, start, i;
1.181 - uint32_t *b;
1.182 - const char *key;
1.183 -
1.184 - key = (char *) table->pool->data + value;
1.185 - mask = table->buckets.alloc - 1;
1.186 - start = hash_string(key) * sizeof(uint32_t);
1.187 -
1.188 - for (i = 0; i < table->buckets.alloc; i += sizeof *b) {
1.189 - b = table->buckets.data + ((start + i) & mask);
1.190 - if (*b == 0) {
1.191 - *b = value;
1.192 - break;
1.193 - }
1.194 - }
1.195 -}
1.196 -
1.197 -static uint32_t
1.198 -add_to_string_pool(struct hashtable *table, const char *key)
1.199 -{
1.200 - int len;
1.201 - char *p;
1.202 -
1.203 - len = strlen(key) + 1;
1.204 - p = array_add(table->pool, len);
1.205 - memcpy(p, key, len);
1.206 -
1.207 - return p - (char *) table->pool->data;
1.208 -}
1.209 -
1.210 -uint32_t
1.211 -hashtable_insert(struct hashtable *table, const char *key)
1.212 -{
1.213 - uint32_t value, *buckets, *b, *end;
1.214 - int alloc;
1.215 -
1.216 - alloc = table->buckets.alloc;
1.217 - array_add(&table->buckets, 4 * sizeof *buckets);
1.218 - if (alloc != table->buckets.alloc) {
1.219 - end = table->buckets.data + alloc;
1.220 - memset(end, 0, table->buckets.alloc - alloc);
1.221 - for (b = table->buckets.data; b < end; b++) {
1.222 - value = *b;
1.223 - if (value != 0) {
1.224 - *b = 0;
1.225 - do_insert(table, value);
1.226 - }
1.227 - }
1.228 - }
1.229 -
1.230 - value = add_to_string_pool(table, key);
1.231 - do_insert (table, value);
1.232 -
1.233 - return value;
1.234 -}
1.235 -
1.236 -uint32_t
1.237 -hashtable_tokenize(struct hashtable *table, const char *string)
1.238 -{
1.239 - uint32_t token;
1.240 -
1.241 - if (string == NULL)
1.242 - string = "";
1.243 -
1.244 - token = hashtable_lookup(table, string);
1.245 - if (token != 0)
1.246 - return token;
1.247 -
1.248 - return hashtable_insert(table, string);
1.249 -}