1.1 --- a/librazor/types.c Fri May 01 16:48:47 2009 +0100
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,265 +0,0 @@
1.4 -/*
1.5 - * Copyright (C) 2008 Kristian Høgsberg <krh@redhat.com>
1.6 - * Copyright (C) 2008 Red Hat, Inc
1.7 - *
1.8 - * This program is free software; you can redistribute it and/or modify
1.9 - * it under the terms of the GNU General Public License as published by
1.10 - * the Free Software Foundation; either version 2 of the License, or
1.11 - * (at your option) any later version.
1.12 - *
1.13 - * This program is distributed in the hope that it will be useful,
1.14 - * but WITHOUT ANY WARRANTY; without even the implied warranty of
1.15 - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
1.16 - * GNU General Public License for more details.
1.17 - *
1.18 - * You should have received a copy of the GNU General Public License along
1.19 - * with this program; if not, write to the Free Software Foundation, Inc.,
1.20 - * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
1.21 - */
1.22 -
1.23 -#include <stdlib.h>
1.24 -#include <string.h>
1.25 -
1.26 -#include "razor-internal.h"
1.27 -
1.28 -void
1.29 -array_init(struct array *array)
1.30 -{
1.31 - memset(array, 0, sizeof *array);
1.32 -}
1.33 -
1.34 -void
1.35 -array_release(struct array *array)
1.36 -{
1.37 - free(array->data);
1.38 -}
1.39 -
1.40 -void *
1.41 -array_add(struct array *array, int size)
1.42 -{
1.43 - int alloc;
1.44 - void *data, *p;
1.45 -
1.46 - if (array->alloc > 0)
1.47 - alloc = array->alloc;
1.48 - else
1.49 - alloc = 16;
1.50 -
1.51 - while (alloc < array->size + size)
1.52 - alloc *= 2;
1.53 -
1.54 - if (array->alloc < alloc) {
1.55 - data = realloc(array->data, alloc);
1.56 - if (data == NULL)
1.57 - return 0;
1.58 - array->data = data;
1.59 - array->alloc = alloc;
1.60 - }
1.61 -
1.62 - p = array->data + array->size;
1.63 - array->size += size;
1.64 -
1.65 - return p;
1.66 -}
1.67 -
1.68 -/* RAZOR_IMMEDIATE and RAZOR_ENTRY_LAST must have the same value */
1.69 -#define RAZOR_ENTRY_LAST 0x80
1.70 -#define RAZOR_IMMEDIATE 0x80
1.71 -#define RAZOR_EMPTY_LIST 0xff
1.72 -
1.73 -void
1.74 -list_set_empty(struct list_head *head)
1.75 -{
1.76 - head->list_ptr = ~0;
1.77 - head->flags = RAZOR_EMPTY_LIST;
1.78 -}
1.79 -
1.80 -void
1.81 -list_set_ptr(struct list_head *head, uint32_t ptr)
1.82 -{
1.83 - head->list_ptr = ptr;
1.84 - head->flags = 0;
1.85 -}
1.86 -
1.87 -void
1.88 -list_set_array(struct list_head *head, struct array *pool,
1.89 - struct array *items, int force_indirect)
1.90 -{
1.91 - struct list *p;
1.92 -
1.93 - if (!force_indirect) {
1.94 - if (items->size == 0) {
1.95 - list_set_empty(head);
1.96 - return;
1.97 - } else if (items->size == sizeof (uint32_t)) {
1.98 - head->list_ptr = *(uint32_t *) items->data;
1.99 - head->flags = RAZOR_IMMEDIATE;
1.100 - return;
1.101 - }
1.102 - }
1.103 -
1.104 - p = array_add(pool, items->size);
1.105 - memcpy(p, items->data, items->size);
1.106 - p[items->size / sizeof *p - 1].flags = RAZOR_ENTRY_LAST;
1.107 - list_set_ptr(head, p - (struct list *) pool->data);
1.108 -}
1.109 -
1.110 -struct list *
1.111 -list_first(struct list_head *head, struct array *pool)
1.112 -{
1.113 - if (head->flags == RAZOR_EMPTY_LIST)
1.114 - return NULL;
1.115 - else if (head->flags == RAZOR_IMMEDIATE)
1.116 - return (struct list *) head;
1.117 - else
1.118 - return (struct list *) pool->data + head->list_ptr;
1.119 -}
1.120 -
1.121 -struct list *
1.122 -list_next(struct list *list)
1.123 -{
1.124 - if (list->flags)
1.125 - return NULL;
1.126 - return ++list;
1.127 -}
1.128 -
1.129 -void
1.130 -list_remap_pool(struct array *pool, uint32_t *map)
1.131 -{
1.132 - struct list *p, *end;
1.133 -
1.134 - end = pool->data + pool->size;
1.135 - for (p = pool->data; p < end; p++)
1.136 - p->data = map[p->data];
1.137 -}
1.138 -
1.139 -void
1.140 -list_remap_head(struct list_head *head, uint32_t *map)
1.141 -{
1.142 - if (head->flags == RAZOR_IMMEDIATE)
1.143 - head->list_ptr = map[head->list_ptr];
1.144 -}
1.145 -
1.146 -
1.147 -void
1.148 -hashtable_init(struct hashtable *table, struct array *pool)
1.149 -{
1.150 - array_init(&table->buckets);
1.151 - table->pool = pool;
1.152 -}
1.153 -
1.154 -void
1.155 -hashtable_release(struct hashtable *table)
1.156 -{
1.157 - array_release(&table->buckets);
1.158 -}
1.159 -
1.160 -static unsigned int
1.161 -hash_string(const char *key)
1.162 -{
1.163 - const char *p;
1.164 - unsigned int hash = 0;
1.165 -
1.166 - for (p = key; *p; p++)
1.167 - hash = (hash * 617) ^ *p;
1.168 -
1.169 - return hash;
1.170 -}
1.171 -
1.172 -uint32_t
1.173 -hashtable_lookup(struct hashtable *table, const char *key)
1.174 -{
1.175 - unsigned int mask, start, i;
1.176 - uint32_t *b;
1.177 - char *pool;
1.178 -
1.179 - pool = table->pool->data;
1.180 - mask = table->buckets.alloc - 1;
1.181 - start = hash_string(key) * sizeof(uint32_t);
1.182 -
1.183 - for (i = 0; i < table->buckets.alloc; i += sizeof *b) {
1.184 - b = table->buckets.data + ((start + i) & mask);
1.185 -
1.186 - if (*b == 0xFFFFFFFF)
1.187 - return 0xFFFFFFFF;
1.188 -
1.189 - if (strcmp(key, &pool[*b]) == 0)
1.190 - return *b;
1.191 - }
1.192 -
1.193 - return 0xFFFFFFFF;
1.194 -}
1.195 -
1.196 -static void
1.197 -do_insert(struct hashtable *table, uint32_t value)
1.198 -{
1.199 - unsigned int mask, start, i;
1.200 - uint32_t *b;
1.201 - const char *key;
1.202 -
1.203 - key = (char *) table->pool->data + value;
1.204 - mask = table->buckets.alloc - 1;
1.205 - start = hash_string(key) * sizeof(uint32_t);
1.206 -
1.207 - for (i = 0; i < table->buckets.alloc; i += sizeof *b) {
1.208 - b = table->buckets.data + ((start + i) & mask);
1.209 - if (*b == 0xFFFFFFFF) {
1.210 - *b = value;
1.211 - break;
1.212 - }
1.213 - }
1.214 -}
1.215 -
1.216 -static uint32_t
1.217 -add_to_string_pool(struct hashtable *table, const char *key)
1.218 -{
1.219 - int len;
1.220 - char *p;
1.221 -
1.222 - len = strlen(key) + 1;
1.223 - p = array_add(table->pool, len);
1.224 - memcpy(p, key, len);
1.225 -
1.226 - return p - (char *) table->pool->data;
1.227 -}
1.228 -
1.229 -uint32_t
1.230 -hashtable_insert(struct hashtable *table, const char *key)
1.231 -{
1.232 - uint32_t value, *buckets, *b, *end;
1.233 - int alloc;
1.234 -
1.235 - alloc = table->buckets.alloc;
1.236 - array_add(&table->buckets, 4 * sizeof *buckets);
1.237 - if (alloc != table->buckets.alloc) {
1.238 - end = table->buckets.data + alloc;
1.239 - memset(end, 0xFF, table->buckets.alloc - alloc);
1.240 - for (b = table->buckets.data; b < end; b++) {
1.241 - value = *b;
1.242 - if (value != 0xFFFFFFFF) {
1.243 - *b = 0xFFFFFFFF;
1.244 - do_insert(table, value);
1.245 - }
1.246 - }
1.247 - }
1.248 -
1.249 - value = add_to_string_pool(table, key);
1.250 - do_insert (table, value);
1.251 -
1.252 - return value;
1.253 -}
1.254 -
1.255 -uint32_t
1.256 -hashtable_tokenize(struct hashtable *table, const char *string)
1.257 -{
1.258 - uint32_t token;
1.259 -
1.260 - if (string == NULL)
1.261 - string = "";
1.262 -
1.263 - token = hashtable_lookup(table, string);
1.264 - if (token != 0xFFFFFFFF)
1.265 - return token;
1.266 -
1.267 - return hashtable_insert(table, string);
1.268 -}