1.1 --- a/configure.ac Fri May 01 16:48:47 2009 +0100
1.2 +++ b/configure.ac Sat May 09 21:30:22 2009 +0100
1.3 @@ -251,6 +251,7 @@
1.4 data/razor.pc
1.5 data/Makefile
1.6 librazor/Makefile
1.7 +librazor/types/Makefile
1.8 src/Makefile
1.9 docs/Makefile
1.10 docs/version.xml
2.1 --- a/librazor/Makefile.am Fri May 01 16:48:47 2009 +0100
2.2 +++ b/librazor/Makefile.am Sat May 09 21:30:22 2009 +0100
2.3 @@ -1,5 +1,7 @@
2.4 ## Process this file with automake to produce Makefile.in
2.5
2.6 +SUBDIRS = types
2.7 +
2.8 INCLUDES = \
2.9 -I$(top_builddir)/gl -I$(top_srcdir)/gl \
2.10 -I$(top_builddir)/src -I$(top_srcdir)/src \
2.11 @@ -12,9 +14,8 @@
2.12 -DPACKAGE_LIB_DIR=\""$(libdir)"\"
2.13
2.14 lib_LTLIBRARIES = librazor.la
2.15 -check_PROGRAMS = test-hashtable
2.16 if HAVE_LUA
2.17 - check_PROGRAMS += test-lua
2.18 + check_PROGRAMS = test-lua
2.19 endif
2.20
2.21 librazorincludedir = $(includedir)/razor
2.22 @@ -27,7 +28,6 @@
2.23 razor.h \
2.24 razor.c \
2.25 root.c \
2.26 - types.c \
2.27 util.c \
2.28 rpm.c \
2.29 iterator.c \
2.30 @@ -39,20 +39,16 @@
2.31 librazor_la_SOURCES += lua.c
2.32 endif
2.33
2.34 -librazor_la_LIBADD = $(ZLIB_LIBS) $(LUA_LIBS) ../gl/libgnu.la $(EXTRA_LIBS)
2.35 +librazor_la_LIBADD = $(ZLIB_LIBS) types/libtypes.la $(LUA_LIBS) \
2.36 + ../gl/libgnu.la $(EXTRA_LIBS)
2.37 librazor_la_LDFLAGS = -no-undefined
2.38
2.39 -test_hashtable_SOURCES = test-hashtable.c
2.40 -test_hashtable_LDADD = types.lo ../gl/libgnu.la $(EXTRA_LIBS)
2.41 -
2.42 -TESTS = test-hashtable
2.43 -
2.44 if HAVE_LUA
2.45 test_lua_SOURCES = test-lua.c
2.46 - test_lua_LDADD = lua.lo util.lo types.lo $(LUA_LIBS) ../gl/libgnu.la \
2.47 - $(EXTRA_LIBS)
2.48 + test_lua_LDADD = lua.lo util.lo types/libtypes.la $(LUA_LIBS) \
2.49 + ../gl/libgnu.la $(EXTRA_LIBS)
2.50
2.51 - TESTS += test-lua
2.52 + TESTS = test-lua
2.53 endif
2.54
2.55 EXTRA_DIST = \
3.1 --- a/librazor/razor-internal.h Fri May 01 16:48:47 2009 +0100
3.2 +++ b/librazor/razor-internal.h Sat May 09 21:30:22 2009 +0100
3.3 @@ -26,6 +26,7 @@
3.4 #include <unistd.h>
3.5
3.6 #include "razor.h"
3.7 +#include "types/types.h"
3.8
3.9 /* GCC visibility */
3.10 #if defined(__GNUC__) && __GNUC__ >= 4
3.11 @@ -39,49 +40,6 @@
3.12
3.13 void *zalloc(size_t size);
3.14
3.15 -struct array {
3.16 - void *data;
3.17 - int size, alloc;
3.18 -};
3.19 -
3.20 -void array_init(struct array *array);
3.21 -void array_release(struct array *array);
3.22 -void *array_add(struct array *array, int size);
3.23 -
3.24 -
3.25 -struct list_head {
3.26 - uint32_t list_ptr : 24;
3.27 - uint32_t flags : 8;
3.28 -};
3.29 -
3.30 -struct list {
3.31 - uint32_t data : 24;
3.32 - uint32_t flags : 8;
3.33 -};
3.34 -
3.35 -void list_set_empty(struct list_head *head);
3.36 -void list_set_ptr(struct list_head *head, uint32_t ptr);
3.37 -void list_set_array(struct list_head *head, struct array *pool, struct array *items, int force_indirect);
3.38 -
3.39 -struct list *list_first(struct list_head *head, struct array *pool);
3.40 -struct list *list_next(struct list *list);
3.41 -
3.42 -void list_remap_pool(struct array *pool, uint32_t *map);
3.43 -void list_remap_head(struct list_head *list, uint32_t *map);
3.44 -
3.45 -
3.46 -struct hashtable {
3.47 - struct array buckets;
3.48 - struct array *pool;
3.49 -};
3.50 -
3.51 -void hashtable_init(struct hashtable *table, struct array *pool);
3.52 -void hashtable_release(struct hashtable *table);
3.53 -uint32_t hashtable_insert(struct hashtable *table, const char *key);
3.54 -uint32_t hashtable_lookup(struct hashtable *table, const char *key);
3.55 -uint32_t hashtable_tokenize(struct hashtable *table, const char *string);
3.56 -
3.57 -
3.58 struct razor_set_section {
3.59 uint32_t name;
3.60 uint32_t offset;
4.1 --- a/librazor/test-hashtable.c Fri May 01 16:48:47 2009 +0100
4.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
4.3 @@ -1,75 +0,0 @@
4.4 -/*
4.5 - * Copyright (C) 2009 J. Ali Harlow <ali@juiblex.co.uk>
4.6 - *
4.7 - * This program is free software; you can redistribute it and/or modify
4.8 - * it under the terms of the GNU General Public License as published by
4.9 - * the Free Software Foundation; either version 2 of the License, or
4.10 - * (at your option) any later version.
4.11 - *
4.12 - * This program is distributed in the hope that it will be useful,
4.13 - * but WITHOUT ANY WARRANTY; without even the implied warranty of
4.14 - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
4.15 - * GNU General Public License for more details.
4.16 - *
4.17 - * You should have received a copy of the GNU General Public License along
4.18 - * with this program; if not, write to the Free Software Foundation, Inc.,
4.19 - * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
4.20 - */
4.21 -
4.22 -#include "config.h"
4.23 -
4.24 -#include <stdlib.h>
4.25 -#include <stdio.h>
4.26 -#include <string.h>
4.27 -#include "razor-internal.h"
4.28 -
4.29 -uint32_t invalid;
4.30 -struct array pool;
4.31 -struct hashtable table;
4.32 -
4.33 -static int test_key(const char *key)
4.34 -{
4.35 - uint32_t value;
4.36 -
4.37 - value = hashtable_insert(&table, key);
4.38 - if (value == invalid) {
4.39 - fprintf(stderr,
4.40 - "%s: hashtable_insert returned invalid value\n", key);
4.41 - return 1;
4.42 - } else if (value >= pool.size) {
4.43 - fprintf(stderr, "%s: hashtable_insert returned value outside "
4.44 - "pool\n", key);
4.45 - return 1;
4.46 - } else if (pool.size - value <= strlen(key) ||
4.47 - strcmp(pool.data + value, key)) {
4.48 - fprintf(stderr, "%s: value returned by hashtable_insert does "
4.49 - "not match key\n", key);
4.50 - return 1;
4.51 - } else if (hashtable_lookup(&table, key) != value) {
4.52 - fprintf(stderr, "%s: hashtable_lookup didn't return expected "
4.53 - "value\n", key);
4.54 - return 1;
4.55 - } else if (hashtable_tokenize(&table, key) != value) {
4.56 - fprintf(stderr, "%s: hashtable_tokenize didn't return expected "
4.57 - "value\n", key);
4.58 - return 1;
4.59 - }
4.60 - return 0;
4.61 -}
4.62 -
4.63 -int main(int argc, char *argv[])
4.64 -{
4.65 - int errors = 0;
4.66 -
4.67 - array_init(&pool);
4.68 - hashtable_init(&table, &pool);
4.69 - invalid = hashtable_lookup(&table, "non-existant");
4.70 -
4.71 - errors += test_key("key1");
4.72 - errors += test_key("key2");
4.73 -
4.74 - hashtable_release(&table);
4.75 - array_release(&pool);
4.76 -
4.77 - exit(errors ? 1 : 0);
4.78 -}
5.1 --- a/librazor/types.c Fri May 01 16:48:47 2009 +0100
5.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
5.3 @@ -1,265 +0,0 @@
5.4 -/*
5.5 - * Copyright (C) 2008 Kristian Høgsberg <krh@redhat.com>
5.6 - * Copyright (C) 2008 Red Hat, Inc
5.7 - *
5.8 - * This program is free software; you can redistribute it and/or modify
5.9 - * it under the terms of the GNU General Public License as published by
5.10 - * the Free Software Foundation; either version 2 of the License, or
5.11 - * (at your option) any later version.
5.12 - *
5.13 - * This program is distributed in the hope that it will be useful,
5.14 - * but WITHOUT ANY WARRANTY; without even the implied warranty of
5.15 - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
5.16 - * GNU General Public License for more details.
5.17 - *
5.18 - * You should have received a copy of the GNU General Public License along
5.19 - * with this program; if not, write to the Free Software Foundation, Inc.,
5.20 - * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
5.21 - */
5.22 -
5.23 -#include <stdlib.h>
5.24 -#include <string.h>
5.25 -
5.26 -#include "razor-internal.h"
5.27 -
5.28 -void
5.29 -array_init(struct array *array)
5.30 -{
5.31 - memset(array, 0, sizeof *array);
5.32 -}
5.33 -
5.34 -void
5.35 -array_release(struct array *array)
5.36 -{
5.37 - free(array->data);
5.38 -}
5.39 -
5.40 -void *
5.41 -array_add(struct array *array, int size)
5.42 -{
5.43 - int alloc;
5.44 - void *data, *p;
5.45 -
5.46 - if (array->alloc > 0)
5.47 - alloc = array->alloc;
5.48 - else
5.49 - alloc = 16;
5.50 -
5.51 - while (alloc < array->size + size)
5.52 - alloc *= 2;
5.53 -
5.54 - if (array->alloc < alloc) {
5.55 - data = realloc(array->data, alloc);
5.56 - if (data == NULL)
5.57 - return 0;
5.58 - array->data = data;
5.59 - array->alloc = alloc;
5.60 - }
5.61 -
5.62 - p = array->data + array->size;
5.63 - array->size += size;
5.64 -
5.65 - return p;
5.66 -}
5.67 -
5.68 -/* RAZOR_IMMEDIATE and RAZOR_ENTRY_LAST must have the same value */
5.69 -#define RAZOR_ENTRY_LAST 0x80
5.70 -#define RAZOR_IMMEDIATE 0x80
5.71 -#define RAZOR_EMPTY_LIST 0xff
5.72 -
5.73 -void
5.74 -list_set_empty(struct list_head *head)
5.75 -{
5.76 - head->list_ptr = ~0;
5.77 - head->flags = RAZOR_EMPTY_LIST;
5.78 -}
5.79 -
5.80 -void
5.81 -list_set_ptr(struct list_head *head, uint32_t ptr)
5.82 -{
5.83 - head->list_ptr = ptr;
5.84 - head->flags = 0;
5.85 -}
5.86 -
5.87 -void
5.88 -list_set_array(struct list_head *head, struct array *pool,
5.89 - struct array *items, int force_indirect)
5.90 -{
5.91 - struct list *p;
5.92 -
5.93 - if (!force_indirect) {
5.94 - if (items->size == 0) {
5.95 - list_set_empty(head);
5.96 - return;
5.97 - } else if (items->size == sizeof (uint32_t)) {
5.98 - head->list_ptr = *(uint32_t *) items->data;
5.99 - head->flags = RAZOR_IMMEDIATE;
5.100 - return;
5.101 - }
5.102 - }
5.103 -
5.104 - p = array_add(pool, items->size);
5.105 - memcpy(p, items->data, items->size);
5.106 - p[items->size / sizeof *p - 1].flags = RAZOR_ENTRY_LAST;
5.107 - list_set_ptr(head, p - (struct list *) pool->data);
5.108 -}
5.109 -
5.110 -struct list *
5.111 -list_first(struct list_head *head, struct array *pool)
5.112 -{
5.113 - if (head->flags == RAZOR_EMPTY_LIST)
5.114 - return NULL;
5.115 - else if (head->flags == RAZOR_IMMEDIATE)
5.116 - return (struct list *) head;
5.117 - else
5.118 - return (struct list *) pool->data + head->list_ptr;
5.119 -}
5.120 -
5.121 -struct list *
5.122 -list_next(struct list *list)
5.123 -{
5.124 - if (list->flags)
5.125 - return NULL;
5.126 - return ++list;
5.127 -}
5.128 -
5.129 -void
5.130 -list_remap_pool(struct array *pool, uint32_t *map)
5.131 -{
5.132 - struct list *p, *end;
5.133 -
5.134 - end = pool->data + pool->size;
5.135 - for (p = pool->data; p < end; p++)
5.136 - p->data = map[p->data];
5.137 -}
5.138 -
5.139 -void
5.140 -list_remap_head(struct list_head *head, uint32_t *map)
5.141 -{
5.142 - if (head->flags == RAZOR_IMMEDIATE)
5.143 - head->list_ptr = map[head->list_ptr];
5.144 -}
5.145 -
5.146 -
5.147 -void
5.148 -hashtable_init(struct hashtable *table, struct array *pool)
5.149 -{
5.150 - array_init(&table->buckets);
5.151 - table->pool = pool;
5.152 -}
5.153 -
5.154 -void
5.155 -hashtable_release(struct hashtable *table)
5.156 -{
5.157 - array_release(&table->buckets);
5.158 -}
5.159 -
5.160 -static unsigned int
5.161 -hash_string(const char *key)
5.162 -{
5.163 - const char *p;
5.164 - unsigned int hash = 0;
5.165 -
5.166 - for (p = key; *p; p++)
5.167 - hash = (hash * 617) ^ *p;
5.168 -
5.169 - return hash;
5.170 -}
5.171 -
5.172 -uint32_t
5.173 -hashtable_lookup(struct hashtable *table, const char *key)
5.174 -{
5.175 - unsigned int mask, start, i;
5.176 - uint32_t *b;
5.177 - char *pool;
5.178 -
5.179 - pool = table->pool->data;
5.180 - mask = table->buckets.alloc - 1;
5.181 - start = hash_string(key) * sizeof(uint32_t);
5.182 -
5.183 - for (i = 0; i < table->buckets.alloc; i += sizeof *b) {
5.184 - b = table->buckets.data + ((start + i) & mask);
5.185 -
5.186 - if (*b == 0xFFFFFFFF)
5.187 - return 0xFFFFFFFF;
5.188 -
5.189 - if (strcmp(key, &pool[*b]) == 0)
5.190 - return *b;
5.191 - }
5.192 -
5.193 - return 0xFFFFFFFF;
5.194 -}
5.195 -
5.196 -static void
5.197 -do_insert(struct hashtable *table, uint32_t value)
5.198 -{
5.199 - unsigned int mask, start, i;
5.200 - uint32_t *b;
5.201 - const char *key;
5.202 -
5.203 - key = (char *) table->pool->data + value;
5.204 - mask = table->buckets.alloc - 1;
5.205 - start = hash_string(key) * sizeof(uint32_t);
5.206 -
5.207 - for (i = 0; i < table->buckets.alloc; i += sizeof *b) {
5.208 - b = table->buckets.data + ((start + i) & mask);
5.209 - if (*b == 0xFFFFFFFF) {
5.210 - *b = value;
5.211 - break;
5.212 - }
5.213 - }
5.214 -}
5.215 -
5.216 -static uint32_t
5.217 -add_to_string_pool(struct hashtable *table, const char *key)
5.218 -{
5.219 - int len;
5.220 - char *p;
5.221 -
5.222 - len = strlen(key) + 1;
5.223 - p = array_add(table->pool, len);
5.224 - memcpy(p, key, len);
5.225 -
5.226 - return p - (char *) table->pool->data;
5.227 -}
5.228 -
5.229 -uint32_t
5.230 -hashtable_insert(struct hashtable *table, const char *key)
5.231 -{
5.232 - uint32_t value, *buckets, *b, *end;
5.233 - int alloc;
5.234 -
5.235 - alloc = table->buckets.alloc;
5.236 - array_add(&table->buckets, 4 * sizeof *buckets);
5.237 - if (alloc != table->buckets.alloc) {
5.238 - end = table->buckets.data + alloc;
5.239 - memset(end, 0xFF, table->buckets.alloc - alloc);
5.240 - for (b = table->buckets.data; b < end; b++) {
5.241 - value = *b;
5.242 - if (value != 0xFFFFFFFF) {
5.243 - *b = 0xFFFFFFFF;
5.244 - do_insert(table, value);
5.245 - }
5.246 - }
5.247 - }
5.248 -
5.249 - value = add_to_string_pool(table, key);
5.250 - do_insert (table, value);
5.251 -
5.252 - return value;
5.253 -}
5.254 -
5.255 -uint32_t
5.256 -hashtable_tokenize(struct hashtable *table, const char *string)
5.257 -{
5.258 - uint32_t token;
5.259 -
5.260 - if (string == NULL)
5.261 - string = "";
5.262 -
5.263 - token = hashtable_lookup(table, string);
5.264 - if (token != 0xFFFFFFFF)
5.265 - return token;
5.266 -
5.267 - return hashtable_insert(table, string);
5.268 -}
6.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
6.2 +++ b/librazor/types/Makefile.am Sat May 09 21:30:22 2009 +0100
6.3 @@ -0,0 +1,21 @@
6.4 +## Process this file with automake to produce Makefile.in
6.5 +
6.6 +noinst_LTLIBRARIES = libtypes.la
6.7 +check_PROGRAMS = test-hashtable test-graph test-deque
6.8 +LDADD = libtypes.la
6.9 +
6.10 +libtypes_la_SOURCES = \
6.11 + array.c \
6.12 + deque.c \
6.13 + graph.c \
6.14 + hashtable.c \
6.15 + list.c \
6.16 + types.h
6.17 +
6.18 +test_hashtable_SOURCES = test-hashtable.c
6.19 +test_graph_SOURCES = test-graph.c
6.20 +
6.21 +TESTS = $(check_PROGRAMS)
6.22 +
6.23 +clean-local :
6.24 + rm -f *~
7.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
7.2 +++ b/librazor/types/array.c Sat May 09 21:30:22 2009 +0100
7.3 @@ -0,0 +1,64 @@
7.4 +/*
7.5 + * Copyright (C) 2008 Kristian Høgsberg <krh@redhat.com>
7.6 + * Copyright (C) 2008 Red Hat, Inc
7.7 + *
7.8 + * This program is free software; you can redistribute it and/or modify
7.9 + * it under the terms of the GNU General Public License as published by
7.10 + * the Free Software Foundation; either version 2 of the License, or
7.11 + * (at your option) any later version.
7.12 + *
7.13 + * This program is distributed in the hope that it will be useful,
7.14 + * but WITHOUT ANY WARRANTY; without even the implied warranty of
7.15 + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
7.16 + * GNU General Public License for more details.
7.17 + *
7.18 + * You should have received a copy of the GNU General Public License along
7.19 + * with this program; if not, write to the Free Software Foundation, Inc.,
7.20 + * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
7.21 + */
7.22 +
7.23 +#include <stdlib.h>
7.24 +#include <string.h>
7.25 +#include <assert.h>
7.26 +
7.27 +#include "types.h"
7.28 +
7.29 +void
7.30 +array_init(struct array *array)
7.31 +{
7.32 + memset(array, 0, sizeof *array);
7.33 +}
7.34 +
7.35 +void
7.36 +array_release(struct array *array)
7.37 +{
7.38 + free(array->data);
7.39 +}
7.40 +
7.41 +void *
7.42 +array_add(struct array *array, int size)
7.43 +{
7.44 + int alloc;
7.45 + void *data, *p;
7.46 +
7.47 + if (array->alloc > 0)
7.48 + alloc = array->alloc;
7.49 + else
7.50 + alloc = 16;
7.51 +
7.52 + while (alloc < array->size + size)
7.53 + alloc *= 2;
7.54 +
7.55 + if (array->alloc < alloc) {
7.56 + data = realloc(array->data, alloc);
7.57 + if (data == NULL)
7.58 + return 0;
7.59 + array->data = data;
7.60 + array->alloc = alloc;
7.61 + }
7.62 +
7.63 + p = array->data + array->size;
7.64 + array->size += size;
7.65 +
7.66 + return p;
7.67 +}
8.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
8.2 +++ b/librazor/types/deque.c Sat May 09 21:30:22 2009 +0100
8.3 @@ -0,0 +1,206 @@
8.4 +/*
8.5 + * Copyright (C) 2009 J. Ali Harlow <ali@juiblex.co.uk>
8.6 + *
8.7 + * This program is free software; you can redistribute it and/or modify
8.8 + * it under the terms of the GNU General Public License as published by
8.9 + * the Free Software Foundation; either version 2 of the License, or
8.10 + * (at your option) any later version.
8.11 + *
8.12 + * This program is distributed in the hope that it will be useful,
8.13 + * but WITHOUT ANY WARRANTY; without even the implied warranty of
8.14 + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
8.15 + * GNU General Public License for more details.
8.16 + *
8.17 + * You should have received a copy of the GNU General Public License along
8.18 + * with this program; if not, write to the Free Software Foundation, Inc.,
8.19 + * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
8.20 + */
8.21 +
8.22 +#include <stdlib.h>
8.23 +#include <string.h>
8.24 +#include <assert.h>
8.25 +
8.26 +#include "types.h"
8.27 +
8.28 +int deque_init(struct deque *deque, int sized)
8.29 +{
8.30 + assert(sized >= 0);
8.31 + memset(deque, 0, sizeof *deque);
8.32 + deque->alloc = (sized + 1) * sizeof(uint32_t);
8.33 + deque->data = malloc(deque->alloc);
8.34 + return deque->data ? 0 : -1;
8.35 +}
8.36 +
8.37 +void deque_release(struct deque *deque)
8.38 +{
8.39 + free(deque->data);
8.40 +}
8.41 +
8.42 +struct deque *deque_new(int sized)
8.43 +{
8.44 + struct deque *deque;
8.45 + deque = calloc(1, sizeof(struct deque));
8.46 + if (deque_init(deque, sized)) {
8.47 + free(deque);
8.48 + return NULL;
8.49 + } else
8.50 + return deque;
8.51 +}
8.52 +
8.53 +void deque_free(struct deque *deque)
8.54 +{
8.55 + free(deque->data);
8.56 + free(deque);
8.57 +}
8.58 +
8.59 +struct deque *deque_dup(struct deque *deque)
8.60 +{
8.61 + struct deque *dup;
8.62 + dup = calloc(1, sizeof(struct deque));
8.63 + *dup = *deque;
8.64 + dup->data = malloc(deque->alloc);
8.65 + memcpy(dup->data, deque->data, dup->alloc);
8.66 + return dup;
8.67 +}
8.68 +
8.69 +/* ___ front
8.70 + * V
8.71 + * +---+---+---+---+---+---+---+---+
8.72 + * | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | Normalized case: { 0, 1, 2 }
8.73 + * +---+---+---+---+---+---+---+---+
8.74 + * ^\__ back
8.75 + *
8.76 + * ___ front
8.77 + * V
8.78 + * +---+---+---+---+---+---+---+---+
8.79 + * | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | Denormalized case: { 2, 3, 4, 5 }
8.80 + * +---+---+---+---+---+---+---+---+
8.81 + * ^\__ back
8.82 + *
8.83 + * ___ front
8.84 + * V
8.85 + * +---+---+---+---+---+---+---+---+
8.86 + * | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | Wrapped case: { 6, 7, 0 }
8.87 + * +---+---+---+---+---+---+---+---+
8.88 + * ^\__ back
8.89 + */
8.90 +
8.91 +int deque_unshift(struct deque *deque, uint32_t datum)
8.92 +{
8.93 + int alloc, ptr, nb;
8.94 + void *data;
8.95 +
8.96 + if (deque->front)
8.97 + ptr = deque->front - sizeof(uint32_t);
8.98 + else
8.99 + ptr = deque->alloc - sizeof(uint32_t);
8.100 +
8.101 + if (ptr == deque->back) {
8.102 + alloc = 2 * deque->alloc;
8.103 + if (deque->back) {
8.104 + data = malloc(alloc);
8.105 + if (data == NULL)
8.106 + return -1;
8.107 + if (deque->back < deque->front) {
8.108 + nb = deque->alloc - deque->front;
8.109 + ptr = alloc - deque->back - nb,
8.110 + memcpy(data + ptr,
8.111 + deque->data + deque->front, nb);
8.112 + memcpy(data + ptr + nb,
8.113 + deque->data, deque->back);
8.114 + } else {
8.115 + nb = deque->back - deque->front;
8.116 + ptr = alloc - nb;
8.117 + memcpy(data + ptr,
8.118 + deque->data + deque->front, nb);
8.119 + }
8.120 + ptr -= sizeof(uint32_t);
8.121 + free(deque->data);
8.122 + deque->back = 0;
8.123 + } else {
8.124 + data = realloc(deque->data, alloc);
8.125 + if (data == NULL)
8.126 + return -1;
8.127 + deque->back = deque->alloc;
8.128 + }
8.129 + deque->data = data;
8.130 + deque->alloc = alloc;
8.131 + }
8.132 +
8.133 + *(uint32_t *)(deque->data + ptr) = datum;
8.134 + deque->front = ptr;
8.135 + return 0;
8.136 +}
8.137 +
8.138 +int deque_push(struct deque *deque, uint32_t datum)
8.139 +{
8.140 + int alloc, ptr;
8.141 + void *data;
8.142 +
8.143 + *(uint32_t *)(deque->data + deque->back) = datum;
8.144 +
8.145 + ptr = deque->back + sizeof(uint32_t);
8.146 + if (ptr == deque->alloc)
8.147 + ptr = 0;
8.148 +
8.149 + if (ptr == deque->front) {
8.150 + alloc = 2 * deque->alloc;
8.151 + if (deque->front) {
8.152 + data = malloc(alloc);
8.153 + if (data == NULL)
8.154 + return -1;
8.155 + memcpy(data, deque->data + deque->front,
8.156 + deque->alloc - deque->front);
8.157 + if (deque->back < deque->front)
8.158 + memcpy(data + deque->alloc - deque->front,
8.159 + deque->data, ptr);
8.160 + free(deque->data);
8.161 + deque->front = 0;
8.162 + } else {
8.163 + data = realloc(deque->data, alloc);
8.164 + if (data == NULL)
8.165 + return -1;
8.166 + }
8.167 + ptr = deque->alloc;
8.168 + deque->data = data;
8.169 + deque->alloc = alloc;
8.170 + }
8.171 +
8.172 + deque->back = ptr;
8.173 +
8.174 + return 0;
8.175 +}
8.176 +
8.177 +int deque_empty(struct deque *deque)
8.178 +{
8.179 + return deque->front == deque->back;
8.180 +}
8.181 +
8.182 +uint32_t deque_shift(struct deque *deque)
8.183 +{
8.184 + uint32_t datum;
8.185 +
8.186 + if (deque->front == deque->back)
8.187 + return 0xFFFFFFFF;
8.188 +
8.189 + datum = *(uint32_t *)(deque->data + deque->front);
8.190 +
8.191 + deque->front += sizeof(uint32_t);
8.192 + if (deque->front == deque->alloc)
8.193 + deque->front = 0;
8.194 +
8.195 + return datum;
8.196 +}
8.197 +
8.198 +uint32_t deque_pop(struct deque *deque)
8.199 +{
8.200 + if (deque->front == deque->back)
8.201 + return 0xFFFFFFFF;
8.202 +
8.203 + if (deque->back)
8.204 + deque->back -= sizeof(uint32_t);
8.205 + else
8.206 + deque->back = deque->alloc - sizeof(uint32_t);
8.207 +
8.208 + return *(uint32_t *)(deque->data + deque->back);
8.209 +}
9.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
9.2 +++ b/librazor/types/graph.c Sat May 09 21:30:22 2009 +0100
9.3 @@ -0,0 +1,392 @@
9.4 +/*
9.5 + * Copyright (C) 2009 J. Ali Harlow <ali@juiblex.co.uk>
9.6 + *
9.7 + * This program is free software; you can redistribute it and/or modify
9.8 + * it under the terms of the GNU General Public License as published by
9.9 + * the Free Software Foundation; either version 2 of the License, or
9.10 + * (at your option) any later version.
9.11 + *
9.12 + * This program is distributed in the hope that it will be useful,
9.13 + * but WITHOUT ANY WARRANTY; without even the implied warranty of
9.14 + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
9.15 + * GNU General Public License for more details.
9.16 + *
9.17 + * You should have received a copy of the GNU General Public License along
9.18 + * with this program; if not, write to the Free Software Foundation, Inc.,
9.19 + * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
9.20 + */
9.21 +
9.22 +#include <stdlib.h>
9.23 +#include <string.h>
9.24 +#include <assert.h>
9.25 +
9.26 +#include "types.h"
9.27 +
9.28 +void graph_init(struct graph *graph)
9.29 +{
9.30 + array_init(&graph->edges);
9.31 + //list_set_empty(&graph->head);
9.32 + //array_init(&graph->sort_pool);
9.33 +}
9.34 +
9.35 +void graph_release(struct graph *graph)
9.36 +{
9.37 + array_release(&graph->edges);
9.38 +}
9.39 +
9.40 +void graph_add_edge(struct graph *graph, uint32_t vertex1, uint32_t vertex2)
9.41 +{
9.42 + struct graph_edge *edge;
9.43 +
9.44 + edge = array_add(&graph->edges, sizeof(*edge));
9.45 + edge->v1 = vertex1;
9.46 + edge->v2 = vertex2;
9.47 +}
9.48 +
9.49 +int graph_remove_edge(struct graph *graph, uint32_t vertex1, uint32_t vertex2)
9.50 +{
9.51 + struct graph_edge *edge, *end;
9.52 +
9.53 + end = graph->edges.data + graph->edges.size;
9.54 + for(edge = graph->edges.data; edge < end; edge++)
9.55 + if (edge->v1 == vertex1 && edge->v2 == vertex2) {
9.56 + if (edge != end - 1)
9.57 + memcpy(edge, end - 1, sizeof(*edge));
9.58 + graph->edges.size -= sizeof(*edge);
9.59 + return 1;
9.60 + }
9.61 +
9.62 + return 0;
9.63 +}
9.64 +
9.65 +uint32_t graph_get_no_edges(struct graph *graph)
9.66 +{
9.67 + return graph->edges.size / sizeof(struct graph_edge);
9.68 +}
9.69 +
9.70 +int graph_get_edge(struct graph *graph, int nth, uint32_t *v1, uint32_t *v2)
9.71 +{
9.72 + struct graph_edge *edge;
9.73 +
9.74 + edge = graph->edges.data;
9.75 + if (nth * sizeof(*edge) < graph->edges.size) {
9.76 + edge += nth;
9.77 + *v1 = edge->v1;
9.78 + *v2 = edge->v2;
9.79 + return 1;
9.80 + } else
9.81 + return 0;
9.82 +}
9.83 +
9.84 +#define DFS_STOP 1
9.85 +#define DFS_IGNORE 2
9.86 +#define DFS_CONTINUE 3
9.87 +
9.88 +static int
9.89 +graph_edges_dfs(struct graph *graph, const struct bitset active_edges,
9.90 + uint32_t root, int (*callback)(uint32_t v, void *userdata),
9.91 + void *userdata)
9.92 +{
9.93 + struct deque to_visit;
9.94 + struct bitset visited;
9.95 + struct bitset_iter bi;
9.96 + struct graph_edge *edges;
9.97 + int v, e, stopped = 0;
9.98 +
9.99 + deque_init(&to_visit, graph->edges.size / sizeof(uint32_t));
9.100 + bitset_init(visited);
9.101 + edges = graph->edges.data;
9.102 +
9.103 + deque_push(&to_visit, root);
9.104 + while(!stopped && !deque_empty(&to_visit)) {
9.105 + v = deque_pop(&to_visit);
9.106 + if (!bitset_test_bit(visited, v)) {
9.107 + bitset_set_bit(visited, v);
9.108 + if (!bitset_test_bit(visited, v)) {
9.109 + /* Lack of memory shouldn't cause hang */
9.110 + break;
9.111 + }
9.112 + switch((*callback)(v, userdata))
9.113 + {
9.114 + case DFS_STOP:
9.115 + stopped = 1;
9.116 + break;
9.117 + case DFS_CONTINUE:
9.118 + bitset_iter_init(active_edges, bi);
9.119 + for(;;) {
9.120 + bitset_iter_next_bit(active_edges, bi);
9.121 + e = bitset_iter_get_bit(active_edges,
9.122 + bi);
9.123 + if (e < 0)
9.124 + break;
9.125 + if (edges[e].v1 == v)
9.126 + deque_push(&to_visit,
9.127 + edges[e].v2);
9.128 + }
9.129 + break;
9.130 + case DFS_IGNORE:
9.131 + break;
9.132 + }
9.133 + }
9.134 + }
9.135 +
9.136 + deque_release(&to_visit);
9.137 + bitset_release(visited);
9.138 + return stopped;
9.139 +}
9.140 +
9.141 +static int graph_edges_is_connected_cb(uint32_t v, void *userdata)
9.142 +{
9.143 + uint32_t *needle = userdata;
9.144 + return v == *needle ? DFS_STOP : DFS_CONTINUE;
9.145 +}
9.146 +
9.147 +static int
9.148 +graph_edges_is_connected(struct graph *graph, const struct bitset active_edges,
9.149 + uint32_t v1, uint32_t v2)
9.150 +{
9.151 + return graph_edges_dfs(graph, active_edges, v1,
9.152 + graph_edges_is_connected_cb, &v2);
9.153 +}
9.154 +
9.155 +/*
9.156 + * Note: This function tests for simple connectivity.
9.157 + * To test for a strong connection use:
9.158 + * graph_is_connected(graph, v1, v2) && graph_is_connected(graph, v2, v1)
9.159 + */
9.160 +int graph_is_connected(struct graph *graph, uint32_t v1, uint32_t v2)
9.161 +{
9.162 + struct bitset active_edges;
9.163 + int retval, n_edges;
9.164 +
9.165 + n_edges = graph->edges.size / sizeof(struct graph_edge);
9.166 + bitset_init(active_edges);
9.167 + bitset_set_n_bits(active_edges, 0, n_edges);
9.168 + retval = graph_edges_is_connected(graph, active_edges, v1, v2);
9.169 + bitset_release(active_edges);
9.170 + return retval;
9.171 +}
9.172 +
9.173 +struct find_cycle_baton {
9.174 + struct graph *graph;
9.175 + struct bitset in;
9.176 + struct bitset vectors;
9.177 + uint32_t root;
9.178 +};
9.179 +
9.180 +static int graph_edges_find_cycle_cb(uint32_t v, void *userdata)
9.181 +{
9.182 + struct find_cycle_baton *fcb = userdata;
9.183 +
9.184 + if (graph_edges_is_connected(fcb->graph, fcb->in, v, fcb->root)) {
9.185 + bitset_set_bit(fcb->vectors, v);
9.186 + return DFS_CONTINUE;
9.187 + } else
9.188 + return DFS_IGNORE;
9.189 +}
9.190 +
9.191 +/*
9.192 + * Given a graph whose vectors all have incoming edges, find a cycle with none.
9.193 + * A cycle is defined as a sub-graph which has the following properties:
9.194 + * All vectors inside are strongly connected,
9.195 + * No vectors outside are strongly connected to those inside.
9.196 + */
9.197 +static int
9.198 +graph_edges_find_cycle(struct graph *graph, const struct bitset in,
9.199 + struct bitset *out)
9.200 +{
9.201 + int e, v;
9.202 + struct bitset visited;
9.203 + struct graph_edge *edges;
9.204 + struct bitset_iter bi;
9.205 + struct find_cycle_baton baton;
9.206 +
9.207 + bitset_clear(*out);
9.208 + edges = graph->edges.data;
9.209 + bitset_iter_init(in, bi);
9.210 + bitset_iter_next_bit(in, bi);
9.211 + e = bitset_iter_get_bit(in, bi);
9.212 + if (e < 0)
9.213 + return 0;
9.214 + v = edges[e].v1;
9.215 + bitset_init(visited);
9.216 + for(;;) {
9.217 + bitset_set_bit(visited, v);
9.218 + if (!bitset_test_bit(visited, v)) {
9.219 + bitset_release(visited);
9.220 + return 0;
9.221 + }
9.222 + bitset_iter_init(in, bi);
9.223 + for(;;) {
9.224 + bitset_iter_next_bit(in, bi);
9.225 + e = bitset_iter_get_bit(in, bi);
9.226 + assert(e >= 0);
9.227 + if (edges[e].v2 == v && edges[e].v1 != v)
9.228 + break;
9.229 + }
9.230 + v = edges[e].v1;
9.231 + if (bitset_test_bit(visited, v))
9.232 + break;
9.233 + }
9.234 + bitset_release(visited);
9.235 +
9.236 + baton.graph = graph;
9.237 + baton.in = in;
9.238 + bitset_init(baton.vectors);
9.239 + baton.root = v;
9.240 + graph_edges_dfs(graph, in, v, graph_edges_find_cycle_cb, &baton);
9.241 +
9.242 + bitset_iter_init(in, bi);
9.243 + for(;;) {
9.244 + bitset_iter_next_bit(in, bi);
9.245 + e = bitset_iter_get_bit(in, bi);
9.246 + if (e < 0)
9.247 + break;
9.248 + if (bitset_test_bit(baton.vectors, edges[e].v1) &&
9.249 + bitset_test_bit(baton.vectors, edges[e].v2))
9.250 + bitset_set_bit(*out, e);
9.251 + }
9.252 +
9.253 + bitset_release(baton.vectors);
9.254 + return bitset_get_length(*out) != 0;
9.255 +}
9.256 +
9.257 +static void
9.258 +graph_edges_sort_remove_vertex(struct graph *graph, struct bitset *active_edges,
9.259 + struct bitset *S, uint32_t n)
9.260 +{
9.261 + struct graph_edge *edges;
9.262 + struct bitset_iter bi, bi2;
9.263 + int e, e2, m;
9.264 +
9.265 + edges = graph->edges.data;
9.266 + bitset_iter_init(*active_edges, bi);
9.267 + for(;;) {
9.268 + bitset_iter_next_bit(*active_edges, bi);
9.269 + e = bitset_iter_get_bit(*active_edges, bi);
9.270 + if (e < 0)
9.271 + break;
9.272 + if (edges[e].v1 == n) {
9.273 + bitset_clear_bit(*active_edges, e);
9.274 + m = edges[e].v2;
9.275 + if (m != n) {
9.276 + bitset_iter_init(*active_edges, bi2);
9.277 + for(;;) {
9.278 + bitset_iter_next_bit(*active_edges,
9.279 + bi2);
9.280 + e2 = bitset_iter_get_bit(*active_edges,
9.281 + bi2);
9.282 + if (e2 < 0)
9.283 + break;
9.284 + if (edges[e2].v1 != m &&
9.285 + edges[e2].v2 == m)
9.286 + break;
9.287 + }
9.288 + if (e2 < 0)
9.289 + bitset_set_bit(*S, m);
9.290 + }
9.291 + }
9.292 + }
9.293 +}
9.294 +
9.295 +static struct deque *graph_edges_sort(struct graph *graph,
9.296 + const struct bitset in)
9.297 +{
9.298 + /*
9.299 + * Standard topological sort (from Wikipedia) credited to Kahn (1962)
9.300 + * modified to handle cycles as sub-graphs. This creates the ordering
9.301 + * we require. The standard algorithm for solving this problem creates
9.302 + * a DAG from the potentially cyclic graph and then sorts that. It
9.303 + * might be possible to use such a solution but it would mean defining
9.304 + * which of the multiple possible sort orders would be generated for
9.305 + * a given DAG and then designing an algorithm for generating the FAS
9.306 + * which would leave a DAG which will be sorted in the way we need.
9.307 + * This algorithm, if unconventional, seems easier.
9.308 + */
9.309 + struct bitset S, cycle, active_edges;
9.310 + struct graph_edge *edges;
9.311 + struct bitset_iter bi;
9.312 + int n, e;
9.313 + struct deque *L, *SL;
9.314 + struct bitset vertices;
9.315 +
9.316 + L = deque_new(graph->edges.size / sizeof(struct graph_edge));
9.317 + bitset_init(cycle);
9.318 + bitset_init(active_edges);
9.319 + bitset_copy(active_edges, in);
9.320 + bitset_init(S);
9.321 + edges = graph->edges.data;
9.322 +
9.323 + bitset_iter_init(active_edges, bi);
9.324 + for(;;) {
9.325 + bitset_iter_next_bit(active_edges, bi);
9.326 + e = bitset_iter_get_bit(active_edges, bi);
9.327 + if (e < 0)
9.328 + break;
9.329 + bitset_set_bit(S, edges[e].v1);
9.330 + }
9.331 +
9.332 + bitset_iter_init(active_edges, bi);
9.333 + for(;;) {
9.334 + bitset_iter_next_bit(active_edges, bi);
9.335 + e = bitset_iter_get_bit(active_edges, bi);
9.336 + if (e < 0)
9.337 + break;
9.338 + if (edges[e].v1 != edges[e].v2)
9.339 + bitset_clear_bit(S, edges[e].v2);
9.340 + }
9.341 +
9.342 + for(;;) {
9.343 + bitset_iter_init(S, bi);
9.344 + bitset_iter_next_bit(S, bi);
9.345 + n = bitset_iter_get_bit(S, bi);
9.346 + if (n < 0) {
9.347 + if (!graph_edges_find_cycle(graph, active_edges,
9.348 + &cycle))
9.349 + break;
9.350 + bitset_iter_init(cycle, bi);
9.351 + bitset_iter_next_bit(cycle, bi);
9.352 + e = bitset_iter_get_bit(cycle, bi);
9.353 + assert(e >= 0);
9.354 + bitset_clear_bit(cycle, e);
9.355 + SL = graph_edges_sort(graph, cycle);
9.356 + bitset_init(vertices);
9.357 + while(!deque_empty(SL)) {
9.358 + n = deque_shift(SL);
9.359 + deque_push(L, n);
9.360 + bitset_set_bit(vertices, n);
9.361 + graph_edges_sort_remove_vertex(graph,
9.362 + &active_edges,
9.363 + &S, n);
9.364 + }
9.365 + deque_free(SL);
9.366 + bitset_and_inverted(S, vertices);
9.367 + bitset_release(vertices);
9.368 + } else {
9.369 + bitset_clear_bit(S, n);
9.370 + deque_push(L, n);
9.371 + graph_edges_sort_remove_vertex(graph, &active_edges,
9.372 + &S, n);
9.373 + }
9.374 + }
9.375 +
9.376 + bitset_release(active_edges);
9.377 + bitset_release(cycle);
9.378 + bitset_release(S);
9.379 + return L;
9.380 +}
9.381 +
9.382 +/* Use deque_pop for conventional ordering (A->B->C)
9.383 + * and deque_shift for the reverse.
9.384 + */
9.385 +struct deque *graph_sort(struct graph *graph)
9.386 +{
9.387 + struct bitset active_edges;
9.388 + int n_edges;
9.389 +
9.390 + n_edges = graph->edges.size / sizeof(struct graph_edge);
9.391 + bitset_init(active_edges);
9.392 + bitset_set_n_bits(active_edges, 0, n_edges);
9.393 +
9.394 + return graph_edges_sort(graph, active_edges);
9.395 +}
10.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
10.2 +++ b/librazor/types/hashtable.c Sat May 09 21:30:22 2009 +0100
10.3 @@ -0,0 +1,147 @@
10.4 +/*
10.5 + * Copyright (C) 2008 Kristian Høgsberg <krh@redhat.com>
10.6 + * Copyright (C) 2008 Red Hat, Inc
10.7 + *
10.8 + * This program is free software; you can redistribute it and/or modify
10.9 + * it under the terms of the GNU General Public License as published by
10.10 + * the Free Software Foundation; either version 2 of the License, or
10.11 + * (at your option) any later version.
10.12 + *
10.13 + * This program is distributed in the hope that it will be useful,
10.14 + * but WITHOUT ANY WARRANTY; without even the implied warranty of
10.15 + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
10.16 + * GNU General Public License for more details.
10.17 + *
10.18 + * You should have received a copy of the GNU General Public License along
10.19 + * with this program; if not, write to the Free Software Foundation, Inc.,
10.20 + * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
10.21 + */
10.22 +
10.23 +#include <stdlib.h>
10.24 +#include <string.h>
10.25 +#include <assert.h>
10.26 +
10.27 +#include "types.h"
10.28 +
10.29 +void
10.30 +hashtable_init(struct hashtable *table, struct array *pool)
10.31 +{
10.32 + array_init(&table->buckets);
10.33 + table->pool = pool;
10.34 +}
10.35 +
10.36 +void
10.37 +hashtable_release(struct hashtable *table)
10.38 +{
10.39 + array_release(&table->buckets);
10.40 +}
10.41 +
10.42 +static unsigned int
10.43 +hash_string(const char *key)
10.44 +{
10.45 + const char *p;
10.46 + unsigned int hash = 0;
10.47 +
10.48 + for (p = key; *p; p++)
10.49 + hash = (hash * 617) ^ *p;
10.50 +
10.51 + return hash;
10.52 +}
10.53 +
10.54 +uint32_t
10.55 +hashtable_lookup(struct hashtable *table, const char *key)
10.56 +{
10.57 + unsigned int mask, start, i;
10.58 + uint32_t *b;
10.59 + char *pool;
10.60 +
10.61 + pool = table->pool->data;
10.62 + mask = table->buckets.alloc - 1;
10.63 + start = hash_string(key) * sizeof(uint32_t);
10.64 +
10.65 + for (i = 0; i < table->buckets.alloc; i += sizeof *b) {
10.66 + b = table->buckets.data + ((start + i) & mask);
10.67 +
10.68 + if (*b == 0xFFFFFFFF)
10.69 + return 0xFFFFFFFF;
10.70 +
10.71 + if (strcmp(key, &pool[*b]) == 0)
10.72 + return *b;
10.73 + }
10.74 +
10.75 + return 0xFFFFFFFF;
10.76 +}
10.77 +
10.78 +static void
10.79 +do_insert(struct hashtable *table, uint32_t value)
10.80 +{
10.81 + unsigned int mask, start, i;
10.82 + uint32_t *b;
10.83 + const char *key;
10.84 +
10.85 + key = (char *) table->pool->data + value;
10.86 + mask = table->buckets.alloc - 1;
10.87 + start = hash_string(key) * sizeof(uint32_t);
10.88 +
10.89 + for (i = 0; i < table->buckets.alloc; i += sizeof *b) {
10.90 + b = table->buckets.data + ((start + i) & mask);
10.91 + if (*b == 0xFFFFFFFF) {
10.92 + *b = value;
10.93 + break;
10.94 + }
10.95 + }
10.96 +}
10.97 +
10.98 +static uint32_t
10.99 +add_to_string_pool(struct hashtable *table, const char *key)
10.100 +{
10.101 + int len;
10.102 + char *p;
10.103 +
10.104 + len = strlen(key) + 1;
10.105 + p = array_add(table->pool, len);
10.106 + memcpy(p, key, len);
10.107 +
10.108 + return p - (char *) table->pool->data;
10.109 +}
10.110 +
10.111 +uint32_t
10.112 +hashtable_insert(struct hashtable *table, const char *key)
10.113 +{
10.114 + uint32_t value, *buckets, *b, *end;
10.115 + int alloc;
10.116 +
10.117 + alloc = table->buckets.alloc;
10.118 + array_add(&table->buckets, 4 * sizeof *buckets);
10.119 + if (alloc != table->buckets.alloc) {
10.120 + end = table->buckets.data + alloc;
10.121 + memset(end, 0xFF, table->buckets.alloc - alloc);
10.122 + for (b = table->buckets.data; b < end; b++) {
10.123 + value = *b;
10.124 + if (value != 0xFFFFFFFF) {
10.125 + *b = 0xFFFFFFFF;
10.126 + do_insert(table, value);
10.127 + }
10.128 + }
10.129 + }
10.130 +
10.131 + value = add_to_string_pool(table, key);
10.132 + do_insert (table, value);
10.133 +
10.134 + return value;
10.135 +}
10.136 +
10.137 +uint32_t
10.138 +hashtable_tokenize(struct hashtable *table, const char *string)
10.139 +{
10.140 + uint32_t token;
10.141 +
10.142 + if (string == NULL)
10.143 + string = "";
10.144 +
10.145 + token = hashtable_lookup(table, string);
10.146 + if (token != 0xFFFFFFFF)
10.147 + return token;
10.148 +
10.149 + return hashtable_insert(table, string);
10.150 +}
11.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
11.2 +++ b/librazor/types/list.c Sat May 09 21:30:22 2009 +0100
11.3 @@ -0,0 +1,102 @@
11.4 +/*
11.5 + * Copyright (C) 2008 Kristian Høgsberg <krh@redhat.com>
11.6 + * Copyright (C) 2008 Red Hat, Inc
11.7 + *
11.8 + * This program is free software; you can redistribute it and/or modify
11.9 + * it under the terms of the GNU General Public License as published by
11.10 + * the Free Software Foundation; either version 2 of the License, or
11.11 + * (at your option) any later version.
11.12 + *
11.13 + * This program is distributed in the hope that it will be useful,
11.14 + * but WITHOUT ANY WARRANTY; without even the implied warranty of
11.15 + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11.16 + * GNU General Public License for more details.
11.17 + *
11.18 + * You should have received a copy of the GNU General Public License along
11.19 + * with this program; if not, write to the Free Software Foundation, Inc.,
11.20 + * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
11.21 + */
11.22 +
11.23 +#include <stdlib.h>
11.24 +#include <string.h>
11.25 +#include <assert.h>
11.26 +
11.27 +#include "types.h"
11.28 +
11.29 +/* RAZOR_IMMEDIATE and RAZOR_ENTRY_LAST must have the same value */
11.30 +#define RAZOR_ENTRY_LAST 0x80
11.31 +#define RAZOR_IMMEDIATE 0x80
11.32 +#define RAZOR_EMPTY_LIST 0xff
11.33 +
11.34 +void
11.35 +list_set_empty(struct list_head *head)
11.36 +{
11.37 + head->list_ptr = ~0;
11.38 + head->flags = RAZOR_EMPTY_LIST;
11.39 +}
11.40 +
11.41 +void
11.42 +list_set_ptr(struct list_head *head, uint32_t ptr)
11.43 +{
11.44 + head->list_ptr = ptr;
11.45 + head->flags = 0;
11.46 +}
11.47 +
11.48 +void
11.49 +list_set_array(struct list_head *head, struct array *pool,
11.50 + struct array *items, int force_indirect)
11.51 +{
11.52 + struct list *p;
11.53 +
11.54 + if (!force_indirect) {
11.55 + if (items->size == 0) {
11.56 + list_set_empty(head);
11.57 + return;
11.58 + } else if (items->size == sizeof (uint32_t)) {
11.59 + head->list_ptr = *(uint32_t *) items->data;
11.60 + head->flags = RAZOR_IMMEDIATE;
11.61 + return;
11.62 + }
11.63 + }
11.64 +
11.65 + p = array_add(pool, items->size);
11.66 + memcpy(p, items->data, items->size);
11.67 + p[items->size / sizeof *p - 1].flags = RAZOR_ENTRY_LAST;
11.68 + list_set_ptr(head, p - (struct list *) pool->data);
11.69 +}
11.70 +
11.71 +struct list *
11.72 +list_first(struct list_head *head, struct array *pool)
11.73 +{
11.74 + if (head->flags == RAZOR_EMPTY_LIST)
11.75 + return NULL;
11.76 + else if (head->flags == RAZOR_IMMEDIATE)
11.77 + return (struct list *) head;
11.78 + else
11.79 + return (struct list *) pool->data + head->list_ptr;
11.80 +}
11.81 +
11.82 +struct list *
11.83 +list_next(struct list *list)
11.84 +{
11.85 + if (list->flags)
11.86 + return NULL;
11.87 + return ++list;
11.88 +}
11.89 +
11.90 +void
11.91 +list_remap_pool(struct array *pool, uint32_t *map)
11.92 +{
11.93 + struct list *p, *end;
11.94 +
11.95 + end = pool->data + pool->size;
11.96 + for (p = pool->data; p < end; p++)
11.97 + p->data = map[p->data];
11.98 +}
11.99 +
11.100 +void
11.101 +list_remap_head(struct list_head *head, uint32_t *map)
11.102 +{
11.103 + if (head->flags == RAZOR_IMMEDIATE)
11.104 + head->list_ptr = map[head->list_ptr];
11.105 +}
12.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
12.2 +++ b/librazor/types/test-deque.c Sat May 09 21:30:22 2009 +0100
12.3 @@ -0,0 +1,221 @@
12.4 +/*
12.5 + * Copyright (C) 2009 J. Ali Harlow <ali@juiblex.co.uk>
12.6 + *
12.7 + * This program is free software; you can redistribute it and/or modify
12.8 + * it under the terms of the GNU General Public License as published by
12.9 + * the Free Software Foundation; either version 2 of the License, or
12.10 + * (at your option) any later version.
12.11 + *
12.12 + * This program is distributed in the hope that it will be useful,
12.13 + * but WITHOUT ANY WARRANTY; without even the implied warranty of
12.14 + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12.15 + * GNU General Public License for more details.
12.16 + *
12.17 + * You should have received a copy of the GNU General Public License along
12.18 + * with this program; if not, write to the Free Software Foundation, Inc.,
12.19 + * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
12.20 + */
12.21 +
12.22 +#include "config.h"
12.23 +
12.24 +#include <stdlib.h>
12.25 +#include <stdio.h>
12.26 +#include <string.h>
12.27 +#include "types.h"
12.28 +
12.29 +static void dump_deque(struct deque *deque)
12.30 +{
12.31 + int i;
12.32 + fprintf(stderr, " +--------+\n");
12.33 + for(i = 0; i < deque->alloc; i += sizeof(uint32_t)) {
12.34 + if (i == deque->front)
12.35 + fprintf(stderr, "F>");
12.36 + else
12.37 + fprintf(stderr, " ");
12.38 + fprintf(stderr, " |%08X|", *(uint32_t *)(deque->data+i));
12.39 + if (i == deque->back)
12.40 + fprintf(stderr, " <B");
12.41 + fprintf(stderr, "\n +--------+\n");
12.42 + }
12.43 +}
12.44 +
12.45 +#define DEQUE_TEST(func, d, arg) \
12.46 + do { \
12.47 + if (func(d, arg)) { \
12.48 + fprintf(stderr, #func " failed\n"); \
12.49 + dump_deque(d); \
12.50 + return 1; \
12.51 + } \
12.52 + } while(0)
12.53 +
12.54 +#define DEQUE_CHECK(func, d, proto) \
12.55 + do { \
12.56 + uint32_t v = func(d); \
12.57 + if (v != proto) { \
12.58 + fprintf(stderr, #func " returned %X instead of %X\n", \
12.59 + v, proto); \
12.60 + dump_deque(d); \
12.61 + return 1; \
12.62 + } \
12.63 + } while(0)
12.64 +
12.65 +#define DEQUE_ENSURE_EMPTY(d) \
12.66 + do { \
12.67 + if (!deque_empty(d)) { \
12.68 + fprintf(stderr, "deque not empty\n"); \
12.69 + dump_deque(d); \
12.70 + return 1; \
12.71 + } \
12.72 + } while(0)
12.73 +
12.74 +static int test_push_pop(struct array *array)
12.75 +{
12.76 + int i, n, count;
12.77 + struct deque deque;
12.78 + uint32_t *items;
12.79 +
12.80 + DEQUE_TEST(deque_init, &deque, 0);
12.81 +
12.82 + count = array->size / sizeof (uint32_t);
12.83 + items = array->data;
12.84 +
12.85 + DEQUE_TEST(deque_push, &deque, 0x25);
12.86 + DEQUE_TEST(deque_push, &deque, 0x2A);
12.87 +
12.88 + for(n = 1; n <= count; n++) {
12.89 + for(i = 0; i < n; i++)
12.90 + DEQUE_TEST(deque_push, &deque, items[i]);
12.91 + for(i = n - 1; i >= 0; i--)
12.92 + DEQUE_CHECK(deque_pop, &deque, items[i]);
12.93 + }
12.94 +
12.95 + DEQUE_CHECK(deque_pop, &deque, 0x2A);
12.96 + DEQUE_CHECK(deque_pop, &deque, 0x25);
12.97 +
12.98 + DEQUE_ENSURE_EMPTY(&deque);
12.99 +
12.100 + deque_release(&deque);
12.101 + return 0;
12.102 +}
12.103 +
12.104 +static int test_unshift_shift(struct array *array)
12.105 +{
12.106 + int i, n, count;
12.107 + struct deque deque;
12.108 + uint32_t *items;
12.109 +
12.110 + DEQUE_TEST(deque_init, &deque, 0);
12.111 +
12.112 + count = array->size / sizeof (uint32_t);
12.113 + items = array->data;
12.114 +
12.115 + DEQUE_TEST(deque_unshift, &deque, 0x25);
12.116 + DEQUE_TEST(deque_unshift, &deque, 0x2A);
12.117 +
12.118 + for(n = 1; n <= count; n++) {
12.119 + for(i = 0; i < n; i++)
12.120 + DEQUE_TEST(deque_unshift, &deque, items[i]);
12.121 + for(i = n - 1; i >= 0; i--)
12.122 + DEQUE_CHECK(deque_shift, &deque, items[i]);
12.123 + }
12.124 +
12.125 + DEQUE_CHECK(deque_shift, &deque, 0x2A);
12.126 + DEQUE_CHECK(deque_shift, &deque, 0x25);
12.127 +
12.128 + DEQUE_ENSURE_EMPTY(&deque);
12.129 +
12.130 + deque_release(&deque);
12.131 + return 0;
12.132 +}
12.133 +
12.134 +static int test_push_shift(struct array *array)
12.135 +{
12.136 + int i, n, count;
12.137 + struct deque deque;
12.138 + uint32_t *items;
12.139 +
12.140 + DEQUE_TEST(deque_init, &deque, 0);
12.141 +
12.142 + count = array->size / sizeof (uint32_t);
12.143 + items = array->data;
12.144 +
12.145 + for(n = 1; n <= count; n++) {
12.146 + for(i = 0; i < n; i++)
12.147 + DEQUE_TEST(deque_push, &deque, items[i]);
12.148 + DEQUE_TEST(deque_push, &deque, 0x25);
12.149 + DEQUE_TEST(deque_push, &deque, 0x2A);
12.150 + for(i = 0; i < n; i++)
12.151 + DEQUE_CHECK(deque_shift, &deque, items[i]);
12.152 + DEQUE_CHECK(deque_shift, &deque, 0x25);
12.153 + DEQUE_CHECK(deque_shift, &deque, 0x2A);
12.154 + }
12.155 +
12.156 + DEQUE_ENSURE_EMPTY(&deque);
12.157 +
12.158 + deque_release(&deque);
12.159 + return 0;
12.160 +}
12.161 +
12.162 +static int test_unshift_pop(struct array *array)
12.163 +{
12.164 + int i, n, count;
12.165 + struct deque deque;
12.166 + uint32_t *items;
12.167 +
12.168 + DEQUE_TEST(deque_init, &deque, 0);
12.169 +
12.170 + count = array->size / sizeof (uint32_t);
12.171 + items = array->data;
12.172 +
12.173 + for(n = 1; n <= count; n++) {
12.174 + for(i = 0; i < n; i++)
12.175 + DEQUE_TEST(deque_unshift, &deque, items[i]);
12.176 + DEQUE_TEST(deque_unshift, &deque, 0x25);
12.177 + DEQUE_TEST(deque_unshift, &deque, 0x2A);
12.178 + for(i = 0; i < n; i++)
12.179 + DEQUE_CHECK(deque_pop, &deque, items[i]);
12.180 + DEQUE_CHECK(deque_pop, &deque, 0x25);
12.181 + DEQUE_CHECK(deque_pop, &deque, 0x2A);
12.182 + }
12.183 +
12.184 + DEQUE_ENSURE_EMPTY(&deque);
12.185 +
12.186 + deque_release(&deque);
12.187 + return 0;
12.188 +}
12.189 +
12.190 +int main(int argc, char *argv[])
12.191 +{
12.192 + struct array array;
12.193 + uint32_t *item;
12.194 + int errors = 0;
12.195 +
12.196 + array_init(&array);
12.197 + item = array_add(&array, sizeof(*item));
12.198 + *item = 0x7;
12.199 + item = array_add(&array, sizeof(*item));
12.200 + *item = 0xC;
12.201 + item = array_add(&array, sizeof(*item));
12.202 + *item = 0x3F;
12.203 + item = array_add(&array, sizeof(*item));
12.204 + *item = 0x30;
12.205 + item = array_add(&array, sizeof(*item));
12.206 + *item = 0x13;
12.207 + item = array_add(&array, sizeof(*item));
12.208 + *item = 0x27;
12.209 + item = array_add(&array, sizeof(*item));
12.210 + *item = 0x4A;
12.211 + item = array_add(&array, sizeof(*item));
12.212 + *item = 0x7E;
12.213 + item = array_add(&array, sizeof(*item));
12.214 + *item = 0x65;
12.215 +
12.216 + errors += test_push_pop(&array);
12.217 + errors += test_push_shift(&array);
12.218 + errors += test_unshift_pop(&array);
12.219 + errors += test_unshift_shift(&array);
12.220 +
12.221 + array_release(&array);
12.222 +
12.223 + exit(errors ? 1 : 0);
12.224 +}
13.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
13.2 +++ b/librazor/types/test-graph.c Sat May 09 21:30:22 2009 +0100
13.3 @@ -0,0 +1,196 @@
13.4 +/*
13.5 + * Copyright (C) 2009 J. Ali Harlow <ali@juiblex.co.uk>
13.6 + *
13.7 + * This program is free software; you can redistribute it and/or modify
13.8 + * it under the terms of the GNU General Public License as published by
13.9 + * the Free Software Foundation; either version 2 of the License, or
13.10 + * (at your option) any later version.
13.11 + *
13.12 + * This program is distributed in the hope that it will be useful,
13.13 + * but WITHOUT ANY WARRANTY; without even the implied warranty of
13.14 + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13.15 + * GNU General Public License for more details.
13.16 + *
13.17 + * You should have received a copy of the GNU General Public License along
13.18 + * with this program; if not, write to the Free Software Foundation, Inc.,
13.19 + * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
13.20 + */
13.21 +
13.22 +#include "config.h"
13.23 +
13.24 +#include <stdlib.h>
13.25 +#include <stdio.h>
13.26 +#include <string.h>
13.27 +#include "types.h"
13.28 +
13.29 +static int test_sort(struct graph *graph)
13.30 +{
13.31 + struct bitset vertices;
13.32 + struct bitset_iter bi;
13.33 + struct deque *order, *deque;
13.34 + int i, n_edges;
13.35 + uint32_t v, v1, v2;
13.36 +
13.37 + order = graph_sort(graph);
13.38 +
13.39 + if (deque_empty(order))
13.40 + fprintf(stderr, "Empty sort ouput\n");
13.41 + else {
13.42 + deque = deque_dup(order);
13.43 + printf("%u", deque_pop(deque));
13.44 + while(!deque_empty(deque))
13.45 + printf(", %u", deque_pop(deque));
13.46 + printf("\n");
13.47 + deque_free(deque);
13.48 + }
13.49 +
13.50 + bitset_init(vertices);
13.51 + deque = deque_dup(order);
13.52 + while(!deque_empty(deque)) {
13.53 + v = deque_pop(deque);
13.54 + if (bitset_test_bit(vertices, v)) {
13.55 + fprintf(stderr,
13.56 + "Vertex %u appears more than once\n", v);
13.57 + return 1;
13.58 + } else
13.59 + bitset_set_bit(vertices, v);
13.60 + }
13.61 + deque_free(deque);
13.62 +
13.63 + n_edges = graph_get_no_edges(graph);
13.64 + for(i = 0; i < n_edges; i++) {
13.65 + if (!graph_get_edge(graph, i, &v1, &v2)) {
13.66 + fprintf(stderr, "Failed to get edge %d\n", i);
13.67 + return 1;
13.68 + }
13.69 + if (!bitset_test_bit(vertices, v1)) {
13.70 + fprintf(stderr, "Vertex %u not in sort output\n", v1);
13.71 + return 1;
13.72 + }
13.73 + if (!bitset_test_bit(vertices, v2)) {
13.74 + fprintf(stderr, "Vertex %u not in sort output\n", v2);
13.75 + return 1;
13.76 + }
13.77 + }
13.78 +
13.79 + for(i = 0; i < n_edges; i++) {
13.80 + if (!graph_get_edge(graph, i, &v1, &v2)) {
13.81 + fprintf(stderr, "Failed to get edge %d\n", i);
13.82 + return 1;
13.83 + }
13.84 + bitset_clear_bit(vertices, v1);
13.85 + bitset_clear_bit(vertices, v2);
13.86 + }
13.87 + bitset_iter_init(vertices, bi);
13.88 + bitset_iter_next_bit(vertices, bi);
13.89 + if (bitset_iter_get_bit(vertices, bi) >= 0) {
13.90 + fprintf(stderr, "Vertex %u in sort output does not exist\n",
13.91 + bitset_iter_get_bit(vertices, bi));
13.92 + return 1;
13.93 + }
13.94 + bitset_release(vertices);
13.95 +
13.96 + deque = deque_dup(order);
13.97 + if (!deque_empty(deque))
13.98 + v1 = deque_pop(deque);
13.99 + while(!deque_empty(deque)) {
13.100 + v2 = v1;
13.101 + v1 = deque_pop(deque);
13.102 + if (graph_is_connected(graph, v2, v1) &&
13.103 + !graph_is_connected(graph, v1, v2)) {
13.104 + fprintf(stderr, "Sort output pair %u, %u "
13.105 + "is mis-ordered\n", v1, v2);
13.106 + return 1;
13.107 + }
13.108 + }
13.109 + deque_free(deque);
13.110 +
13.111 + return 0;
13.112 +}
13.113 +
13.114 +int main(int argc, char *argv[])
13.115 +{
13.116 + struct graph graph;
13.117 + int errors = 0;
13.118 +
13.119 + /* This test case is from:
13.120 + * http://en.wikipedia.org/wiki/Topological_sort
13.121 + */
13.122 + graph_init(&graph);
13.123 + graph_add_edge(&graph, 7, 11);
13.124 + graph_add_edge(&graph, 7, 8);
13.125 + graph_add_edge(&graph, 5, 11);
13.126 + graph_add_edge(&graph, 3, 8);
13.127 + graph_add_edge(&graph, 3, 10);
13.128 + graph_add_edge(&graph, 11, 2);
13.129 + graph_add_edge(&graph, 11, 9);
13.130 + graph_add_edge(&graph, 11, 10);
13.131 + graph_add_edge(&graph, 8, 9);
13.132 +
13.133 + errors += test_sort(&graph);
13.134 +
13.135 + graph_release(&graph);
13.136 +
13.137 + /* This one includes a cycle */
13.138 + graph_init(&graph);
13.139 + graph_add_edge(&graph, 9, 5);
13.140 + graph_add_edge(&graph, 5, 1);
13.141 + graph_add_edge(&graph, 10, 6);
13.142 + graph_add_edge(&graph, 6, 2);
13.143 + graph_add_edge(&graph, 11, 7);
13.144 + graph_add_edge(&graph, 7, 3);
13.145 + graph_add_edge(&graph, 12, 8);
13.146 + graph_add_edge(&graph, 8, 4);
13.147 + graph_add_edge(&graph, 5, 6);
13.148 + graph_add_edge(&graph, 6, 7);
13.149 + graph_add_edge(&graph, 7, 8);
13.150 + graph_add_edge(&graph, 8, 5);
13.151 +
13.152 + errors += test_sort(&graph);
13.153 +
13.154 + graph_release(&graph);
13.155 +
13.156 + /* This one includes a cycle that isn't just a ring */
13.157 + graph_init(&graph);
13.158 + graph_add_edge(&graph, 0, 1);
13.159 + graph_add_edge(&graph, 1, 2);
13.160 + graph_add_edge(&graph, 1, 3);
13.161 + graph_add_edge(&graph, 1, 4);
13.162 + graph_add_edge(&graph, 4, 3);
13.163 + graph_add_edge(&graph, 3, 2);
13.164 + graph_add_edge(&graph, 2, 5);
13.165 + graph_add_edge(&graph, 4, 5);
13.166 + graph_add_edge(&graph, 5, 6);
13.167 +
13.168 + errors += test_sort(&graph);
13.169 +
13.170 + graph_release(&graph);
13.171 +
13.172 + /* This one includes a number of vertices that have loops */
13.173 + graph_init(&graph);
13.174 + graph_add_edge(&graph, 0, 0);
13.175 + graph_add_edge(&graph, 1, 2);
13.176 + graph_add_edge(&graph, 2, 2);
13.177 +
13.178 + errors += test_sort(&graph);
13.179 +
13.180 + graph_release(&graph);
13.181 +
13.182 + /* This one is a multigraph with a cycle */
13.183 + graph_init(&graph);
13.184 + graph_add_edge(&graph, 0, 1);
13.185 + graph_add_edge(&graph, 0, 1);
13.186 + graph_add_edge(&graph, 1, 2);
13.187 + graph_add_edge(&graph, 1, 2);
13.188 + graph_add_edge(&graph, 3, 1);
13.189 + graph_add_edge(&graph, 3, 2);
13.190 + graph_add_edge(&graph, 2, 4);
13.191 + graph_add_edge(&graph, 4, 2);
13.192 + graph_add_edge(&graph, 4, 5);
13.193 +
13.194 + errors += test_sort(&graph);
13.195 +
13.196 + graph_release(&graph);
13.197 +
13.198 + exit(errors ? 1 : 0);
13.199 +}
14.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
14.2 +++ b/librazor/types/test-hashtable.c Sat May 09 21:30:22 2009 +0100
14.3 @@ -0,0 +1,75 @@
14.4 +/*
14.5 + * Copyright (C) 2009 J. Ali Harlow <ali@juiblex.co.uk>
14.6 + *
14.7 + * This program is free software; you can redistribute it and/or modify
14.8 + * it under the terms of the GNU General Public License as published by
14.9 + * the Free Software Foundation; either version 2 of the License, or
14.10 + * (at your option) any later version.
14.11 + *
14.12 + * This program is distributed in the hope that it will be useful,
14.13 + * but WITHOUT ANY WARRANTY; without even the implied warranty of
14.14 + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14.15 + * GNU General Public License for more details.
14.16 + *
14.17 + * You should have received a copy of the GNU General Public License along
14.18 + * with this program; if not, write to the Free Software Foundation, Inc.,
14.19 + * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
14.20 + */
14.21 +
14.22 +#include "config.h"
14.23 +
14.24 +#include <stdlib.h>
14.25 +#include <stdio.h>
14.26 +#include <string.h>
14.27 +#include "types.h"
14.28 +
14.29 +uint32_t invalid;
14.30 +struct array pool;
14.31 +struct hashtable table;
14.32 +
14.33 +static int test_key(const char *key)
14.34 +{
14.35 + uint32_t value;
14.36 +
14.37 + value = hashtable_insert(&table, key);
14.38 + if (value == invalid) {
14.39 + fprintf(stderr,
14.40 + "%s: hashtable_insert returned invalid value\n", key);
14.41 + return 1;
14.42 + } else if (value >= pool.size) {
14.43 + fprintf(stderr, "%s: hashtable_insert returned value outside "
14.44 + "pool\n", key);
14.45 + return 1;
14.46 + } else if (pool.size - value <= strlen(key) ||
14.47 + strcmp(pool.data + value, key)) {
14.48 + fprintf(stderr, "%s: value returned by hashtable_insert does "
14.49 + "not match key\n", key);
14.50 + return 1;
14.51 + } else if (hashtable_lookup(&table, key) != value) {
14.52 + fprintf(stderr, "%s: hashtable_lookup didn't return expected "
14.53 + "value\n", key);
14.54 + return 1;
14.55 + } else if (hashtable_tokenize(&table, key) != value) {
14.56 + fprintf(stderr, "%s: hashtable_tokenize didn't return expected "
14.57 + "value\n", key);
14.58 + return 1;
14.59 + }
14.60 + return 0;
14.61 +}
14.62 +
14.63 +int main(int argc, char *argv[])
14.64 +{
14.65 + int errors = 0;
14.66 +
14.67 + array_init(&pool);
14.68 + hashtable_init(&table, &pool);
14.69 + invalid = hashtable_lookup(&table, "non-existant");
14.70 +
14.71 + errors += test_key("key1");
14.72 + errors += test_key("key2");
14.73 +
14.74 + hashtable_release(&table);
14.75 + array_release(&pool);
14.76 +
14.77 + exit(errors ? 1 : 0);
14.78 +}
15.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
15.2 +++ b/librazor/types/types.h Sat May 09 21:30:22 2009 +0100
15.3 @@ -0,0 +1,284 @@
15.4 +/*
15.5 + * Copyright (C) 2008 Kristian Høgsberg <krh@redhat.com>
15.6 + * Copyright (C) 2008 Red Hat, Inc
15.7 + * Copyright (C) 2009 J. Ali Harlow <ali@juiblex.co.uk>
15.8 + *
15.9 + * This program is free software; you can redistribute it and/or modify
15.10 + * it under the terms of the GNU General Public License as published by
15.11 + * the Free Software Foundation; either version 2 of the License, or
15.12 + * (at your option) any later version.
15.13 + *
15.14 + * This program is distributed in the hope that it will be useful,
15.15 + * but WITHOUT ANY WARRANTY; without even the implied warranty of
15.16 + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15.17 + * GNU General Public License for more details.
15.18 + *
15.19 + * You should have received a copy of the GNU General Public License along
15.20 + * with this program; if not, write to the Free Software Foundation, Inc.,
15.21 + * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
15.22 + */
15.23 +
15.24 +#ifndef _RAZOR_TYPES_H_
15.25 +#define _RAZOR_TYPES_H_
15.26 +
15.27 +#include <stdlib.h>
15.28 +#include <stdint.h>
15.29 +
15.30 +struct array {
15.31 + void *data;
15.32 + int size, alloc;
15.33 +};
15.34 +
15.35 +void array_init(struct array *array);
15.36 +void array_release(struct array *array);
15.37 +void *array_add(struct array *array, int size);
15.38 +
15.39 +
15.40 +struct list_head {
15.41 + uint32_t list_ptr : 24;
15.42 + uint32_t flags : 8;
15.43 +};
15.44 +
15.45 +struct list {
15.46 + uint32_t data : 24;
15.47 + uint32_t flags : 8;
15.48 +};
15.49 +
15.50 +void list_set_empty(struct list_head *head);
15.51 +void list_set_ptr(struct list_head *head, uint32_t ptr);
15.52 +void list_set_array(struct list_head *head, struct array *pool, struct array *items, int force_indirect);
15.53 +
15.54 +struct list *list_first(struct list_head *head, struct array *pool);
15.55 +struct list *list_next(struct list *list);
15.56 +
15.57 +void list_remap_pool(struct array *pool, uint32_t *map);
15.58 +void list_remap_head(struct list_head *list, uint32_t *map);
15.59 +
15.60 +
15.61 +struct hashtable {
15.62 + struct array buckets;
15.63 + struct array *pool;
15.64 +};
15.65 +
15.66 +void hashtable_init(struct hashtable *table, struct array *pool);
15.67 +void hashtable_release(struct hashtable *table);
15.68 +uint32_t hashtable_insert(struct hashtable *table, const char *key);
15.69 +uint32_t hashtable_lookup(struct hashtable *table, const char *key);
15.70 +uint32_t hashtable_tokenize(struct hashtable *table, const char *string);
15.71 +
15.72 +
15.73 +/*
15.74 + * Double-ended queues.
15.75 + * Use push/pop for LIFO behaviour and push/shift for FIFO.
15.76 + * In general, unshift is more expensive than push.
15.77 + */
15.78 +
15.79 +struct deque {
15.80 + void *data;
15.81 + int front, back, alloc;
15.82 +};
15.83 +
15.84 +int deque_init(struct deque *deque, int sized);
15.85 +void deque_release(struct deque *deque);
15.86 +struct deque *deque_new(int sized);
15.87 +void deque_free(struct deque *deque);
15.88 +struct deque *deque_dup(struct deque *deque);
15.89 +int deque_unshift(struct deque *deque, uint32_t datum);
15.90 +int deque_push(struct deque *deque, uint32_t datum);
15.91 +int deque_empty(struct deque *deque);
15.92 +uint32_t deque_shift(struct deque *deque);
15.93 +uint32_t deque_pop(struct deque *deque);
15.94 +
15.95 +
15.96 +struct bitset {
15.97 + uint32_t nb;
15.98 + unsigned char *set;
15.99 +};
15.100 +
15.101 +#define bitset_init(bitset) memset(&(bitset), 0, sizeof bitset)
15.102 +
15.103 +#define bitset_release(bitset) free((bitset).set)
15.104 +
15.105 +#define bitset_clear(bitset) do { (bitset).nb = 0; } while (0)
15.106 +
15.107 +#define bitset_clear_bit(bitset, bit) \
15.108 + do { \
15.109 + if ((bit) < (bitset).nb * 8) \
15.110 + (bitset).set[(bit) / 8] &= ~(1U << (bit) % 8); \
15.111 + } while (0)
15.112 +
15.113 +#define bitset_set_bit(bitset, bit) \
15.114 + do { \
15.115 + if ((bit) >= (bitset).nb * 8) { \
15.116 + unsigned char *__bitset_new; \
15.117 + __bitset_new = realloc((bitset).set, (bit) / 8 + 1); \
15.118 + if (__bitset_new) { \
15.119 + (bitset).set = __bitset_new; \
15.120 + memset((bitset).set + (bitset).nb, 0, \
15.121 + (bit) / 8 + 1 - (bitset).nb); \
15.122 + (bitset).nb = (bit) / 8 + 1; \
15.123 + } \
15.124 + } \
15.125 + if ((bit) < (bitset).nb * 8) \
15.126 + (bitset).set[(bit) / 8] |= 1U << (bit) % 8; \
15.127 + } while (0)
15.128 +
15.129 +#define bitset_set_n_bits(bitset, first, count) \
15.130 + do { \
15.131 + if ((first) + (count) > (bitset).nb * 8) { \
15.132 + unsigned char *__bitset_new; \
15.133 + __bitset_new = \
15.134 + realloc((bitset).set, \
15.135 + ((first) + (count) - 1) / 8 + 1); \
15.136 + if (__bitset_new) { \
15.137 + (bitset).set = __bitset_new; \
15.138 + memset((bitset).set + (bitset).nb, 0, \
15.139 + ((first) + (count) - 1) / 8 + \
15.140 + 1 - (bitset).nb); \
15.141 + (bitset).nb = ((first) + (count) - 1) / 8 + 1; \
15.142 + } \
15.143 + } \
15.144 + if ((first) + (count) > (bitset).nb * 8) \
15.145 + break; \
15.146 + /* \
15.147 + * Cases to consider: \
15.148 + * \
15.149 + * +--------+--------+--------+ \
15.150 + * |01234567|01234567|01234567| case A \
15.151 + * +--------+--------+--------+ \
15.152 + * first -^ ^- first+count \
15.153 + * \
15.154 + * +--------+--------+--------+ \
15.155 + * |01234567|01234567|01234567| case B \
15.156 + * +--------+--------+--------+ \
15.157 + * first -^ first+count -^ \
15.158 + * \
15.159 + * +--------+--------+--------+ \
15.160 + * |01234567|01234567|01234567| case C \
15.161 + * +--------+--------+--------+ \
15.162 + * first -^ ^- first+count \
15.163 + * \
15.164 + * +--------+--------+--------+ \
15.165 + * |01234567|01234567|01234567| case D \
15.166 + * +--------+--------+--------+ \
15.167 + * first -^ ^- first+count \
15.168 + * \
15.169 + * +--------+--------+--------+ \
15.170 + * |01234567|01234567|01234567| case E \
15.171 + * +--------+--------+--------+ \
15.172 + * first -^ first+count -^ \
15.173 + * \
15.174 + * +--------+--------+--------+ \
15.175 + * |01234567|01234567|01234567| case F \
15.176 + * +--------+--------+--------+ \
15.177 + * first -^ ^- first+count \
15.178 + */ \
15.179 + if ((count) && (first) / 8 == ((first) + (count) - 1) / 8) \
15.180 + /* cases A & D */ \
15.181 + (bitset).set[(first) / 8] |= \
15.182 + ((1U << (count)) - 1) << (first) % 8; \
15.183 + else if (count) { \
15.184 + if ((first) % 8) /* cases E & F -> B & A/C */ \
15.185 + (bitset).set[(first) / 8] |= \
15.186 + ((1U << (first) % 8) - 1) ^ 0xFF; \
15.187 + if ((count) - (8 - (first) % 8) % 8 >= 8) \
15.188 + /* cases B & C -> / & A */ \
15.189 + memset((bitset).set + ((first) + 7) / 8, 0xFF, \
15.190 + ((count) - (8 - (first) % 8) % 8) / 8); \
15.191 + if (((first) + (count)) % 8) /* case A */ \
15.192 + (bitset).set[((first) + (count)) / 8] |= \
15.193 + (1U << ((first) + (count)) % 8) - 1; \
15.194 + } \
15.195 + } while (0)
15.196 +
15.197 +#define bitset_test_bit(bitset, bit) \
15.198 + ((bit) < (bitset).nb * 8 ? \
15.199 + (bitset).set[(bit) / 8] & 1U << (bit) % 8 : 0)
15.200 +
15.201 +/* dst <- (NOT src) AND dst */
15.202 +#define bitset_and_inverted(dst, src) \
15.203 + do { \
15.204 + unsigned int __bitset_nb; \
15.205 + __bitset_nb = (src).nb > (dst).nb ? (dst).nb : (src).nb; \
15.206 + if (__bitset_nb--) \
15.207 + do { \
15.208 + (dst).set[__bitset_nb] &= \
15.209 + ~(src).set[__bitset_nb]; \
15.210 + } while (__bitset_nb--); \
15.211 + } while(0)
15.212 +
15.213 +#define bitset_get_length(bitset) ((bitset).nb * 8)
15.214 +
15.215 +#define bitset_copy(dst, src) \
15.216 + do { \
15.217 + unsigned char *__bitset_new; \
15.218 + __bitset_new = realloc((dst).set, (src).nb); \
15.219 + if (__bitset_new) { \
15.220 + (dst).set = __bitset_new; \
15.221 + (dst).nb = (src).nb; \
15.222 + memcpy((dst).set, (src).set, (dst).nb); \
15.223 + } else \
15.224 + (dst).nb = 0; \
15.225 + } while(0)
15.226 +
15.227 +#define bitset_compact(bitset) \
15.228 + do { \
15.229 + unsigned char *__bitset_new; \
15.230 + while((bitset).nb && !(bitset).set[(bitset).nb - 1]) \
15.231 + (bitset).nb--; \
15.232 + __bitset_new = realloc((bitset).set, (bitset).nb); \
15.233 + if (__bitset_new || !(bitset).nb) \
15.234 + (bitset).set = __bitset_new; \
15.235 + } while (0)
15.236 +
15.237 +struct bitset_iter {
15.238 + int byte;
15.239 + int bit;
15.240 +};
15.241 +
15.242 +#define bitset_iter_init(bitset, iter) \
15.243 + do { (iter).byte = 0; (iter).bit = -1; } while (0)
15.244 +
15.245 +#define bitset_iter_next_bit(bitset, iter) \
15.246 + do { \
15.247 + if ((iter).byte < (bitset).nb) { \
15.248 + for((iter).bit++; (iter).bit < 8; (iter).bit++) \
15.249 + if ((bitset).set[(iter).byte] & \
15.250 + 1 << (iter).bit) \
15.251 + break; \
15.252 + if ((iter).bit >= 8) { \
15.253 + for((iter).byte++; (iter).byte < (bitset).nb; \
15.254 + (iter).byte++) { \
15.255 + (iter).bit = \
15.256 + ffs((bitset).set[(iter).byte]);\
15.257 + if ((iter).bit--) \
15.258 + break; \
15.259 + } \
15.260 + } \
15.261 + } \
15.262 + } while(0)
15.263 +
15.264 +#define bitset_iter_get_bit(bitset, iter) \
15.265 + ((iter).byte < (bitset).nb ? (iter).byte * 8 + (iter).bit : -1)
15.266 +
15.267 +
15.268 +struct graph_edge {
15.269 + uint32_t v1, v2;
15.270 +};
15.271 +
15.272 +struct graph {
15.273 + struct array edges;
15.274 + //struct list_head head;
15.275 + //struct array sort_pool;
15.276 +};
15.277 +
15.278 +void graph_init(struct graph *graph);
15.279 +void graph_release(struct graph *graph);
15.280 +void graph_add_edge(struct graph *graph, uint32_t vertex1, uint32_t vertex2);
15.281 +int graph_remove_edge(struct graph *graph, uint32_t vertex1, uint32_t vertex2);
15.282 +uint32_t graph_get_no_edges(struct graph *graph);
15.283 +int graph_get_edge(struct graph *graph, int nth, uint32_t *v1, uint32_t *v2);
15.284 +int graph_is_connected(struct graph *graph, uint32_t v1, uint32_t v2);
15.285 +struct deque *graph_sort(struct graph *graph);
15.286 +
15.287 +#endif /* _RAZOR_TYPES_H_ */