# HG changeset patch # User J. Ali Harlow # Date 1241901022 -3600 # Node ID 66ec30bde5e5e589fd642a4582a49bcdae83ecf3 # Parent c75a2d5caae9c56f26e22a4c8b5c27a5fdd2089a Add support for topological sorting (needed to order transactions) diff -r c75a2d5caae9 -r 66ec30bde5e5 configure.ac --- a/configure.ac Fri May 01 16:48:47 2009 +0100 +++ b/configure.ac Sat May 09 21:30:22 2009 +0100 @@ -251,6 +251,7 @@ data/razor.pc data/Makefile librazor/Makefile +librazor/types/Makefile src/Makefile docs/Makefile docs/version.xml diff -r c75a2d5caae9 -r 66ec30bde5e5 librazor/Makefile.am --- a/librazor/Makefile.am Fri May 01 16:48:47 2009 +0100 +++ b/librazor/Makefile.am Sat May 09 21:30:22 2009 +0100 @@ -1,5 +1,7 @@ ## Process this file with automake to produce Makefile.in +SUBDIRS = types + INCLUDES = \ -I$(top_builddir)/gl -I$(top_srcdir)/gl \ -I$(top_builddir)/src -I$(top_srcdir)/src \ @@ -12,9 +14,8 @@ -DPACKAGE_LIB_DIR=\""$(libdir)"\" lib_LTLIBRARIES = librazor.la -check_PROGRAMS = test-hashtable if HAVE_LUA - check_PROGRAMS += test-lua + check_PROGRAMS = test-lua endif librazorincludedir = $(includedir)/razor @@ -27,7 +28,6 @@ razor.h \ razor.c \ root.c \ - types.c \ util.c \ rpm.c \ iterator.c \ @@ -39,20 +39,16 @@ librazor_la_SOURCES += lua.c endif -librazor_la_LIBADD = $(ZLIB_LIBS) $(LUA_LIBS) ../gl/libgnu.la $(EXTRA_LIBS) +librazor_la_LIBADD = $(ZLIB_LIBS) types/libtypes.la $(LUA_LIBS) \ + ../gl/libgnu.la $(EXTRA_LIBS) librazor_la_LDFLAGS = -no-undefined -test_hashtable_SOURCES = test-hashtable.c -test_hashtable_LDADD = types.lo ../gl/libgnu.la $(EXTRA_LIBS) - -TESTS = test-hashtable - if HAVE_LUA test_lua_SOURCES = test-lua.c - test_lua_LDADD = lua.lo util.lo types.lo $(LUA_LIBS) ../gl/libgnu.la \ - $(EXTRA_LIBS) + test_lua_LDADD = lua.lo util.lo types/libtypes.la $(LUA_LIBS) \ + ../gl/libgnu.la $(EXTRA_LIBS) - TESTS += test-lua + TESTS = test-lua endif EXTRA_DIST = \ diff -r c75a2d5caae9 -r 66ec30bde5e5 librazor/razor-internal.h --- a/librazor/razor-internal.h Fri May 01 16:48:47 2009 +0100 +++ b/librazor/razor-internal.h Sat May 09 21:30:22 2009 +0100 @@ -26,6 +26,7 @@ #include #include "razor.h" +#include "types/types.h" /* GCC visibility */ #if defined(__GNUC__) && __GNUC__ >= 4 @@ -39,49 +40,6 @@ void *zalloc(size_t size); -struct array { - void *data; - int size, alloc; -}; - -void array_init(struct array *array); -void array_release(struct array *array); -void *array_add(struct array *array, int size); - - -struct list_head { - uint32_t list_ptr : 24; - uint32_t flags : 8; -}; - -struct list { - uint32_t data : 24; - uint32_t flags : 8; -}; - -void list_set_empty(struct list_head *head); -void list_set_ptr(struct list_head *head, uint32_t ptr); -void list_set_array(struct list_head *head, struct array *pool, struct array *items, int force_indirect); - -struct list *list_first(struct list_head *head, struct array *pool); -struct list *list_next(struct list *list); - -void list_remap_pool(struct array *pool, uint32_t *map); -void list_remap_head(struct list_head *list, uint32_t *map); - - -struct hashtable { - struct array buckets; - struct array *pool; -}; - -void hashtable_init(struct hashtable *table, struct array *pool); -void hashtable_release(struct hashtable *table); -uint32_t hashtable_insert(struct hashtable *table, const char *key); -uint32_t hashtable_lookup(struct hashtable *table, const char *key); -uint32_t hashtable_tokenize(struct hashtable *table, const char *string); - - struct razor_set_section { uint32_t name; uint32_t offset; diff -r c75a2d5caae9 -r 66ec30bde5e5 librazor/test-hashtable.c --- a/librazor/test-hashtable.c Fri May 01 16:48:47 2009 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,75 +0,0 @@ -/* - * Copyright (C) 2009 J. Ali Harlow - * - * This program is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation; either version 2 of the License, or - * (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License along - * with this program; if not, write to the Free Software Foundation, Inc., - * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. - */ - -#include "config.h" - -#include -#include -#include -#include "razor-internal.h" - -uint32_t invalid; -struct array pool; -struct hashtable table; - -static int test_key(const char *key) -{ - uint32_t value; - - value = hashtable_insert(&table, key); - if (value == invalid) { - fprintf(stderr, - "%s: hashtable_insert returned invalid value\n", key); - return 1; - } else if (value >= pool.size) { - fprintf(stderr, "%s: hashtable_insert returned value outside " - "pool\n", key); - return 1; - } else if (pool.size - value <= strlen(key) || - strcmp(pool.data + value, key)) { - fprintf(stderr, "%s: value returned by hashtable_insert does " - "not match key\n", key); - return 1; - } else if (hashtable_lookup(&table, key) != value) { - fprintf(stderr, "%s: hashtable_lookup didn't return expected " - "value\n", key); - return 1; - } else if (hashtable_tokenize(&table, key) != value) { - fprintf(stderr, "%s: hashtable_tokenize didn't return expected " - "value\n", key); - return 1; - } - return 0; -} - -int main(int argc, char *argv[]) -{ - int errors = 0; - - array_init(&pool); - hashtable_init(&table, &pool); - invalid = hashtable_lookup(&table, "non-existant"); - - errors += test_key("key1"); - errors += test_key("key2"); - - hashtable_release(&table); - array_release(&pool); - - exit(errors ? 1 : 0); -} diff -r c75a2d5caae9 -r 66ec30bde5e5 librazor/types.c --- a/librazor/types.c Fri May 01 16:48:47 2009 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,265 +0,0 @@ -/* - * Copyright (C) 2008 Kristian Høgsberg - * Copyright (C) 2008 Red Hat, Inc - * - * This program is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation; either version 2 of the License, or - * (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License along - * with this program; if not, write to the Free Software Foundation, Inc., - * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. - */ - -#include -#include - -#include "razor-internal.h" - -void -array_init(struct array *array) -{ - memset(array, 0, sizeof *array); -} - -void -array_release(struct array *array) -{ - free(array->data); -} - -void * -array_add(struct array *array, int size) -{ - int alloc; - void *data, *p; - - if (array->alloc > 0) - alloc = array->alloc; - else - alloc = 16; - - while (alloc < array->size + size) - alloc *= 2; - - if (array->alloc < alloc) { - data = realloc(array->data, alloc); - if (data == NULL) - return 0; - array->data = data; - array->alloc = alloc; - } - - p = array->data + array->size; - array->size += size; - - return p; -} - -/* RAZOR_IMMEDIATE and RAZOR_ENTRY_LAST must have the same value */ -#define RAZOR_ENTRY_LAST 0x80 -#define RAZOR_IMMEDIATE 0x80 -#define RAZOR_EMPTY_LIST 0xff - -void -list_set_empty(struct list_head *head) -{ - head->list_ptr = ~0; - head->flags = RAZOR_EMPTY_LIST; -} - -void -list_set_ptr(struct list_head *head, uint32_t ptr) -{ - head->list_ptr = ptr; - head->flags = 0; -} - -void -list_set_array(struct list_head *head, struct array *pool, - struct array *items, int force_indirect) -{ - struct list *p; - - if (!force_indirect) { - if (items->size == 0) { - list_set_empty(head); - return; - } else if (items->size == sizeof (uint32_t)) { - head->list_ptr = *(uint32_t *) items->data; - head->flags = RAZOR_IMMEDIATE; - return; - } - } - - p = array_add(pool, items->size); - memcpy(p, items->data, items->size); - p[items->size / sizeof *p - 1].flags = RAZOR_ENTRY_LAST; - list_set_ptr(head, p - (struct list *) pool->data); -} - -struct list * -list_first(struct list_head *head, struct array *pool) -{ - if (head->flags == RAZOR_EMPTY_LIST) - return NULL; - else if (head->flags == RAZOR_IMMEDIATE) - return (struct list *) head; - else - return (struct list *) pool->data + head->list_ptr; -} - -struct list * -list_next(struct list *list) -{ - if (list->flags) - return NULL; - return ++list; -} - -void -list_remap_pool(struct array *pool, uint32_t *map) -{ - struct list *p, *end; - - end = pool->data + pool->size; - for (p = pool->data; p < end; p++) - p->data = map[p->data]; -} - -void -list_remap_head(struct list_head *head, uint32_t *map) -{ - if (head->flags == RAZOR_IMMEDIATE) - head->list_ptr = map[head->list_ptr]; -} - - -void -hashtable_init(struct hashtable *table, struct array *pool) -{ - array_init(&table->buckets); - table->pool = pool; -} - -void -hashtable_release(struct hashtable *table) -{ - array_release(&table->buckets); -} - -static unsigned int -hash_string(const char *key) -{ - const char *p; - unsigned int hash = 0; - - for (p = key; *p; p++) - hash = (hash * 617) ^ *p; - - return hash; -} - -uint32_t -hashtable_lookup(struct hashtable *table, const char *key) -{ - unsigned int mask, start, i; - uint32_t *b; - char *pool; - - pool = table->pool->data; - mask = table->buckets.alloc - 1; - start = hash_string(key) * sizeof(uint32_t); - - for (i = 0; i < table->buckets.alloc; i += sizeof *b) { - b = table->buckets.data + ((start + i) & mask); - - if (*b == 0xFFFFFFFF) - return 0xFFFFFFFF; - - if (strcmp(key, &pool[*b]) == 0) - return *b; - } - - return 0xFFFFFFFF; -} - -static void -do_insert(struct hashtable *table, uint32_t value) -{ - unsigned int mask, start, i; - uint32_t *b; - const char *key; - - key = (char *) table->pool->data + value; - mask = table->buckets.alloc - 1; - start = hash_string(key) * sizeof(uint32_t); - - for (i = 0; i < table->buckets.alloc; i += sizeof *b) { - b = table->buckets.data + ((start + i) & mask); - if (*b == 0xFFFFFFFF) { - *b = value; - break; - } - } -} - -static uint32_t -add_to_string_pool(struct hashtable *table, const char *key) -{ - int len; - char *p; - - len = strlen(key) + 1; - p = array_add(table->pool, len); - memcpy(p, key, len); - - return p - (char *) table->pool->data; -} - -uint32_t -hashtable_insert(struct hashtable *table, const char *key) -{ - uint32_t value, *buckets, *b, *end; - int alloc; - - alloc = table->buckets.alloc; - array_add(&table->buckets, 4 * sizeof *buckets); - if (alloc != table->buckets.alloc) { - end = table->buckets.data + alloc; - memset(end, 0xFF, table->buckets.alloc - alloc); - for (b = table->buckets.data; b < end; b++) { - value = *b; - if (value != 0xFFFFFFFF) { - *b = 0xFFFFFFFF; - do_insert(table, value); - } - } - } - - value = add_to_string_pool(table, key); - do_insert (table, value); - - return value; -} - -uint32_t -hashtable_tokenize(struct hashtable *table, const char *string) -{ - uint32_t token; - - if (string == NULL) - string = ""; - - token = hashtable_lookup(table, string); - if (token != 0xFFFFFFFF) - return token; - - return hashtable_insert(table, string); -} diff -r c75a2d5caae9 -r 66ec30bde5e5 librazor/types/Makefile.am --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/librazor/types/Makefile.am Sat May 09 21:30:22 2009 +0100 @@ -0,0 +1,21 @@ +## Process this file with automake to produce Makefile.in + +noinst_LTLIBRARIES = libtypes.la +check_PROGRAMS = test-hashtable test-graph test-deque +LDADD = libtypes.la + +libtypes_la_SOURCES = \ + array.c \ + deque.c \ + graph.c \ + hashtable.c \ + list.c \ + types.h + +test_hashtable_SOURCES = test-hashtable.c +test_graph_SOURCES = test-graph.c + +TESTS = $(check_PROGRAMS) + +clean-local : + rm -f *~ diff -r c75a2d5caae9 -r 66ec30bde5e5 librazor/types/array.c --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/librazor/types/array.c Sat May 09 21:30:22 2009 +0100 @@ -0,0 +1,64 @@ +/* + * Copyright (C) 2008 Kristian Høgsberg + * Copyright (C) 2008 Red Hat, Inc + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License along + * with this program; if not, write to the Free Software Foundation, Inc., + * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. + */ + +#include +#include +#include + +#include "types.h" + +void +array_init(struct array *array) +{ + memset(array, 0, sizeof *array); +} + +void +array_release(struct array *array) +{ + free(array->data); +} + +void * +array_add(struct array *array, int size) +{ + int alloc; + void *data, *p; + + if (array->alloc > 0) + alloc = array->alloc; + else + alloc = 16; + + while (alloc < array->size + size) + alloc *= 2; + + if (array->alloc < alloc) { + data = realloc(array->data, alloc); + if (data == NULL) + return 0; + array->data = data; + array->alloc = alloc; + } + + p = array->data + array->size; + array->size += size; + + return p; +} diff -r c75a2d5caae9 -r 66ec30bde5e5 librazor/types/deque.c --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/librazor/types/deque.c Sat May 09 21:30:22 2009 +0100 @@ -0,0 +1,206 @@ +/* + * Copyright (C) 2009 J. Ali Harlow + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License along + * with this program; if not, write to the Free Software Foundation, Inc., + * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. + */ + +#include +#include +#include + +#include "types.h" + +int deque_init(struct deque *deque, int sized) +{ + assert(sized >= 0); + memset(deque, 0, sizeof *deque); + deque->alloc = (sized + 1) * sizeof(uint32_t); + deque->data = malloc(deque->alloc); + return deque->data ? 0 : -1; +} + +void deque_release(struct deque *deque) +{ + free(deque->data); +} + +struct deque *deque_new(int sized) +{ + struct deque *deque; + deque = calloc(1, sizeof(struct deque)); + if (deque_init(deque, sized)) { + free(deque); + return NULL; + } else + return deque; +} + +void deque_free(struct deque *deque) +{ + free(deque->data); + free(deque); +} + +struct deque *deque_dup(struct deque *deque) +{ + struct deque *dup; + dup = calloc(1, sizeof(struct deque)); + *dup = *deque; + dup->data = malloc(deque->alloc); + memcpy(dup->data, deque->data, dup->alloc); + return dup; +} + +/* ___ front + * V + * +---+---+---+---+---+---+---+---+ + * | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | Normalized case: { 0, 1, 2 } + * +---+---+---+---+---+---+---+---+ + * ^\__ back + * + * ___ front + * V + * +---+---+---+---+---+---+---+---+ + * | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | Denormalized case: { 2, 3, 4, 5 } + * +---+---+---+---+---+---+---+---+ + * ^\__ back + * + * ___ front + * V + * +---+---+---+---+---+---+---+---+ + * | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | Wrapped case: { 6, 7, 0 } + * +---+---+---+---+---+---+---+---+ + * ^\__ back + */ + +int deque_unshift(struct deque *deque, uint32_t datum) +{ + int alloc, ptr, nb; + void *data; + + if (deque->front) + ptr = deque->front - sizeof(uint32_t); + else + ptr = deque->alloc - sizeof(uint32_t); + + if (ptr == deque->back) { + alloc = 2 * deque->alloc; + if (deque->back) { + data = malloc(alloc); + if (data == NULL) + return -1; + if (deque->back < deque->front) { + nb = deque->alloc - deque->front; + ptr = alloc - deque->back - nb, + memcpy(data + ptr, + deque->data + deque->front, nb); + memcpy(data + ptr + nb, + deque->data, deque->back); + } else { + nb = deque->back - deque->front; + ptr = alloc - nb; + memcpy(data + ptr, + deque->data + deque->front, nb); + } + ptr -= sizeof(uint32_t); + free(deque->data); + deque->back = 0; + } else { + data = realloc(deque->data, alloc); + if (data == NULL) + return -1; + deque->back = deque->alloc; + } + deque->data = data; + deque->alloc = alloc; + } + + *(uint32_t *)(deque->data + ptr) = datum; + deque->front = ptr; + return 0; +} + +int deque_push(struct deque *deque, uint32_t datum) +{ + int alloc, ptr; + void *data; + + *(uint32_t *)(deque->data + deque->back) = datum; + + ptr = deque->back + sizeof(uint32_t); + if (ptr == deque->alloc) + ptr = 0; + + if (ptr == deque->front) { + alloc = 2 * deque->alloc; + if (deque->front) { + data = malloc(alloc); + if (data == NULL) + return -1; + memcpy(data, deque->data + deque->front, + deque->alloc - deque->front); + if (deque->back < deque->front) + memcpy(data + deque->alloc - deque->front, + deque->data, ptr); + free(deque->data); + deque->front = 0; + } else { + data = realloc(deque->data, alloc); + if (data == NULL) + return -1; + } + ptr = deque->alloc; + deque->data = data; + deque->alloc = alloc; + } + + deque->back = ptr; + + return 0; +} + +int deque_empty(struct deque *deque) +{ + return deque->front == deque->back; +} + +uint32_t deque_shift(struct deque *deque) +{ + uint32_t datum; + + if (deque->front == deque->back) + return 0xFFFFFFFF; + + datum = *(uint32_t *)(deque->data + deque->front); + + deque->front += sizeof(uint32_t); + if (deque->front == deque->alloc) + deque->front = 0; + + return datum; +} + +uint32_t deque_pop(struct deque *deque) +{ + if (deque->front == deque->back) + return 0xFFFFFFFF; + + if (deque->back) + deque->back -= sizeof(uint32_t); + else + deque->back = deque->alloc - sizeof(uint32_t); + + return *(uint32_t *)(deque->data + deque->back); +} diff -r c75a2d5caae9 -r 66ec30bde5e5 librazor/types/graph.c --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/librazor/types/graph.c Sat May 09 21:30:22 2009 +0100 @@ -0,0 +1,392 @@ +/* + * Copyright (C) 2009 J. Ali Harlow + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License along + * with this program; if not, write to the Free Software Foundation, Inc., + * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. + */ + +#include +#include +#include + +#include "types.h" + +void graph_init(struct graph *graph) +{ + array_init(&graph->edges); + //list_set_empty(&graph->head); + //array_init(&graph->sort_pool); +} + +void graph_release(struct graph *graph) +{ + array_release(&graph->edges); +} + +void graph_add_edge(struct graph *graph, uint32_t vertex1, uint32_t vertex2) +{ + struct graph_edge *edge; + + edge = array_add(&graph->edges, sizeof(*edge)); + edge->v1 = vertex1; + edge->v2 = vertex2; +} + +int graph_remove_edge(struct graph *graph, uint32_t vertex1, uint32_t vertex2) +{ + struct graph_edge *edge, *end; + + end = graph->edges.data + graph->edges.size; + for(edge = graph->edges.data; edge < end; edge++) + if (edge->v1 == vertex1 && edge->v2 == vertex2) { + if (edge != end - 1) + memcpy(edge, end - 1, sizeof(*edge)); + graph->edges.size -= sizeof(*edge); + return 1; + } + + return 0; +} + +uint32_t graph_get_no_edges(struct graph *graph) +{ + return graph->edges.size / sizeof(struct graph_edge); +} + +int graph_get_edge(struct graph *graph, int nth, uint32_t *v1, uint32_t *v2) +{ + struct graph_edge *edge; + + edge = graph->edges.data; + if (nth * sizeof(*edge) < graph->edges.size) { + edge += nth; + *v1 = edge->v1; + *v2 = edge->v2; + return 1; + } else + return 0; +} + +#define DFS_STOP 1 +#define DFS_IGNORE 2 +#define DFS_CONTINUE 3 + +static int +graph_edges_dfs(struct graph *graph, const struct bitset active_edges, + uint32_t root, int (*callback)(uint32_t v, void *userdata), + void *userdata) +{ + struct deque to_visit; + struct bitset visited; + struct bitset_iter bi; + struct graph_edge *edges; + int v, e, stopped = 0; + + deque_init(&to_visit, graph->edges.size / sizeof(uint32_t)); + bitset_init(visited); + edges = graph->edges.data; + + deque_push(&to_visit, root); + while(!stopped && !deque_empty(&to_visit)) { + v = deque_pop(&to_visit); + if (!bitset_test_bit(visited, v)) { + bitset_set_bit(visited, v); + if (!bitset_test_bit(visited, v)) { + /* Lack of memory shouldn't cause hang */ + break; + } + switch((*callback)(v, userdata)) + { + case DFS_STOP: + stopped = 1; + break; + case DFS_CONTINUE: + bitset_iter_init(active_edges, bi); + for(;;) { + bitset_iter_next_bit(active_edges, bi); + e = bitset_iter_get_bit(active_edges, + bi); + if (e < 0) + break; + if (edges[e].v1 == v) + deque_push(&to_visit, + edges[e].v2); + } + break; + case DFS_IGNORE: + break; + } + } + } + + deque_release(&to_visit); + bitset_release(visited); + return stopped; +} + +static int graph_edges_is_connected_cb(uint32_t v, void *userdata) +{ + uint32_t *needle = userdata; + return v == *needle ? DFS_STOP : DFS_CONTINUE; +} + +static int +graph_edges_is_connected(struct graph *graph, const struct bitset active_edges, + uint32_t v1, uint32_t v2) +{ + return graph_edges_dfs(graph, active_edges, v1, + graph_edges_is_connected_cb, &v2); +} + +/* + * Note: This function tests for simple connectivity. + * To test for a strong connection use: + * graph_is_connected(graph, v1, v2) && graph_is_connected(graph, v2, v1) + */ +int graph_is_connected(struct graph *graph, uint32_t v1, uint32_t v2) +{ + struct bitset active_edges; + int retval, n_edges; + + n_edges = graph->edges.size / sizeof(struct graph_edge); + bitset_init(active_edges); + bitset_set_n_bits(active_edges, 0, n_edges); + retval = graph_edges_is_connected(graph, active_edges, v1, v2); + bitset_release(active_edges); + return retval; +} + +struct find_cycle_baton { + struct graph *graph; + struct bitset in; + struct bitset vectors; + uint32_t root; +}; + +static int graph_edges_find_cycle_cb(uint32_t v, void *userdata) +{ + struct find_cycle_baton *fcb = userdata; + + if (graph_edges_is_connected(fcb->graph, fcb->in, v, fcb->root)) { + bitset_set_bit(fcb->vectors, v); + return DFS_CONTINUE; + } else + return DFS_IGNORE; +} + +/* + * Given a graph whose vectors all have incoming edges, find a cycle with none. + * A cycle is defined as a sub-graph which has the following properties: + * All vectors inside are strongly connected, + * No vectors outside are strongly connected to those inside. + */ +static int +graph_edges_find_cycle(struct graph *graph, const struct bitset in, + struct bitset *out) +{ + int e, v; + struct bitset visited; + struct graph_edge *edges; + struct bitset_iter bi; + struct find_cycle_baton baton; + + bitset_clear(*out); + edges = graph->edges.data; + bitset_iter_init(in, bi); + bitset_iter_next_bit(in, bi); + e = bitset_iter_get_bit(in, bi); + if (e < 0) + return 0; + v = edges[e].v1; + bitset_init(visited); + for(;;) { + bitset_set_bit(visited, v); + if (!bitset_test_bit(visited, v)) { + bitset_release(visited); + return 0; + } + bitset_iter_init(in, bi); + for(;;) { + bitset_iter_next_bit(in, bi); + e = bitset_iter_get_bit(in, bi); + assert(e >= 0); + if (edges[e].v2 == v && edges[e].v1 != v) + break; + } + v = edges[e].v1; + if (bitset_test_bit(visited, v)) + break; + } + bitset_release(visited); + + baton.graph = graph; + baton.in = in; + bitset_init(baton.vectors); + baton.root = v; + graph_edges_dfs(graph, in, v, graph_edges_find_cycle_cb, &baton); + + bitset_iter_init(in, bi); + for(;;) { + bitset_iter_next_bit(in, bi); + e = bitset_iter_get_bit(in, bi); + if (e < 0) + break; + if (bitset_test_bit(baton.vectors, edges[e].v1) && + bitset_test_bit(baton.vectors, edges[e].v2)) + bitset_set_bit(*out, e); + } + + bitset_release(baton.vectors); + return bitset_get_length(*out) != 0; +} + +static void +graph_edges_sort_remove_vertex(struct graph *graph, struct bitset *active_edges, + struct bitset *S, uint32_t n) +{ + struct graph_edge *edges; + struct bitset_iter bi, bi2; + int e, e2, m; + + edges = graph->edges.data; + bitset_iter_init(*active_edges, bi); + for(;;) { + bitset_iter_next_bit(*active_edges, bi); + e = bitset_iter_get_bit(*active_edges, bi); + if (e < 0) + break; + if (edges[e].v1 == n) { + bitset_clear_bit(*active_edges, e); + m = edges[e].v2; + if (m != n) { + bitset_iter_init(*active_edges, bi2); + for(;;) { + bitset_iter_next_bit(*active_edges, + bi2); + e2 = bitset_iter_get_bit(*active_edges, + bi2); + if (e2 < 0) + break; + if (edges[e2].v1 != m && + edges[e2].v2 == m) + break; + } + if (e2 < 0) + bitset_set_bit(*S, m); + } + } + } +} + +static struct deque *graph_edges_sort(struct graph *graph, + const struct bitset in) +{ + /* + * Standard topological sort (from Wikipedia) credited to Kahn (1962) + * modified to handle cycles as sub-graphs. This creates the ordering + * we require. The standard algorithm for solving this problem creates + * a DAG from the potentially cyclic graph and then sorts that. It + * might be possible to use such a solution but it would mean defining + * which of the multiple possible sort orders would be generated for + * a given DAG and then designing an algorithm for generating the FAS + * which would leave a DAG which will be sorted in the way we need. + * This algorithm, if unconventional, seems easier. + */ + struct bitset S, cycle, active_edges; + struct graph_edge *edges; + struct bitset_iter bi; + int n, e; + struct deque *L, *SL; + struct bitset vertices; + + L = deque_new(graph->edges.size / sizeof(struct graph_edge)); + bitset_init(cycle); + bitset_init(active_edges); + bitset_copy(active_edges, in); + bitset_init(S); + edges = graph->edges.data; + + bitset_iter_init(active_edges, bi); + for(;;) { + bitset_iter_next_bit(active_edges, bi); + e = bitset_iter_get_bit(active_edges, bi); + if (e < 0) + break; + bitset_set_bit(S, edges[e].v1); + } + + bitset_iter_init(active_edges, bi); + for(;;) { + bitset_iter_next_bit(active_edges, bi); + e = bitset_iter_get_bit(active_edges, bi); + if (e < 0) + break; + if (edges[e].v1 != edges[e].v2) + bitset_clear_bit(S, edges[e].v2); + } + + for(;;) { + bitset_iter_init(S, bi); + bitset_iter_next_bit(S, bi); + n = bitset_iter_get_bit(S, bi); + if (n < 0) { + if (!graph_edges_find_cycle(graph, active_edges, + &cycle)) + break; + bitset_iter_init(cycle, bi); + bitset_iter_next_bit(cycle, bi); + e = bitset_iter_get_bit(cycle, bi); + assert(e >= 0); + bitset_clear_bit(cycle, e); + SL = graph_edges_sort(graph, cycle); + bitset_init(vertices); + while(!deque_empty(SL)) { + n = deque_shift(SL); + deque_push(L, n); + bitset_set_bit(vertices, n); + graph_edges_sort_remove_vertex(graph, + &active_edges, + &S, n); + } + deque_free(SL); + bitset_and_inverted(S, vertices); + bitset_release(vertices); + } else { + bitset_clear_bit(S, n); + deque_push(L, n); + graph_edges_sort_remove_vertex(graph, &active_edges, + &S, n); + } + } + + bitset_release(active_edges); + bitset_release(cycle); + bitset_release(S); + return L; +} + +/* Use deque_pop for conventional ordering (A->B->C) + * and deque_shift for the reverse. + */ +struct deque *graph_sort(struct graph *graph) +{ + struct bitset active_edges; + int n_edges; + + n_edges = graph->edges.size / sizeof(struct graph_edge); + bitset_init(active_edges); + bitset_set_n_bits(active_edges, 0, n_edges); + + return graph_edges_sort(graph, active_edges); +} diff -r c75a2d5caae9 -r 66ec30bde5e5 librazor/types/hashtable.c --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/librazor/types/hashtable.c Sat May 09 21:30:22 2009 +0100 @@ -0,0 +1,147 @@ +/* + * Copyright (C) 2008 Kristian Høgsberg + * Copyright (C) 2008 Red Hat, Inc + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License along + * with this program; if not, write to the Free Software Foundation, Inc., + * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. + */ + +#include +#include +#include + +#include "types.h" + +void +hashtable_init(struct hashtable *table, struct array *pool) +{ + array_init(&table->buckets); + table->pool = pool; +} + +void +hashtable_release(struct hashtable *table) +{ + array_release(&table->buckets); +} + +static unsigned int +hash_string(const char *key) +{ + const char *p; + unsigned int hash = 0; + + for (p = key; *p; p++) + hash = (hash * 617) ^ *p; + + return hash; +} + +uint32_t +hashtable_lookup(struct hashtable *table, const char *key) +{ + unsigned int mask, start, i; + uint32_t *b; + char *pool; + + pool = table->pool->data; + mask = table->buckets.alloc - 1; + start = hash_string(key) * sizeof(uint32_t); + + for (i = 0; i < table->buckets.alloc; i += sizeof *b) { + b = table->buckets.data + ((start + i) & mask); + + if (*b == 0xFFFFFFFF) + return 0xFFFFFFFF; + + if (strcmp(key, &pool[*b]) == 0) + return *b; + } + + return 0xFFFFFFFF; +} + +static void +do_insert(struct hashtable *table, uint32_t value) +{ + unsigned int mask, start, i; + uint32_t *b; + const char *key; + + key = (char *) table->pool->data + value; + mask = table->buckets.alloc - 1; + start = hash_string(key) * sizeof(uint32_t); + + for (i = 0; i < table->buckets.alloc; i += sizeof *b) { + b = table->buckets.data + ((start + i) & mask); + if (*b == 0xFFFFFFFF) { + *b = value; + break; + } + } +} + +static uint32_t +add_to_string_pool(struct hashtable *table, const char *key) +{ + int len; + char *p; + + len = strlen(key) + 1; + p = array_add(table->pool, len); + memcpy(p, key, len); + + return p - (char *) table->pool->data; +} + +uint32_t +hashtable_insert(struct hashtable *table, const char *key) +{ + uint32_t value, *buckets, *b, *end; + int alloc; + + alloc = table->buckets.alloc; + array_add(&table->buckets, 4 * sizeof *buckets); + if (alloc != table->buckets.alloc) { + end = table->buckets.data + alloc; + memset(end, 0xFF, table->buckets.alloc - alloc); + for (b = table->buckets.data; b < end; b++) { + value = *b; + if (value != 0xFFFFFFFF) { + *b = 0xFFFFFFFF; + do_insert(table, value); + } + } + } + + value = add_to_string_pool(table, key); + do_insert (table, value); + + return value; +} + +uint32_t +hashtable_tokenize(struct hashtable *table, const char *string) +{ + uint32_t token; + + if (string == NULL) + string = ""; + + token = hashtable_lookup(table, string); + if (token != 0xFFFFFFFF) + return token; + + return hashtable_insert(table, string); +} diff -r c75a2d5caae9 -r 66ec30bde5e5 librazor/types/list.c --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/librazor/types/list.c Sat May 09 21:30:22 2009 +0100 @@ -0,0 +1,102 @@ +/* + * Copyright (C) 2008 Kristian Høgsberg + * Copyright (C) 2008 Red Hat, Inc + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License along + * with this program; if not, write to the Free Software Foundation, Inc., + * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. + */ + +#include +#include +#include + +#include "types.h" + +/* RAZOR_IMMEDIATE and RAZOR_ENTRY_LAST must have the same value */ +#define RAZOR_ENTRY_LAST 0x80 +#define RAZOR_IMMEDIATE 0x80 +#define RAZOR_EMPTY_LIST 0xff + +void +list_set_empty(struct list_head *head) +{ + head->list_ptr = ~0; + head->flags = RAZOR_EMPTY_LIST; +} + +void +list_set_ptr(struct list_head *head, uint32_t ptr) +{ + head->list_ptr = ptr; + head->flags = 0; +} + +void +list_set_array(struct list_head *head, struct array *pool, + struct array *items, int force_indirect) +{ + struct list *p; + + if (!force_indirect) { + if (items->size == 0) { + list_set_empty(head); + return; + } else if (items->size == sizeof (uint32_t)) { + head->list_ptr = *(uint32_t *) items->data; + head->flags = RAZOR_IMMEDIATE; + return; + } + } + + p = array_add(pool, items->size); + memcpy(p, items->data, items->size); + p[items->size / sizeof *p - 1].flags = RAZOR_ENTRY_LAST; + list_set_ptr(head, p - (struct list *) pool->data); +} + +struct list * +list_first(struct list_head *head, struct array *pool) +{ + if (head->flags == RAZOR_EMPTY_LIST) + return NULL; + else if (head->flags == RAZOR_IMMEDIATE) + return (struct list *) head; + else + return (struct list *) pool->data + head->list_ptr; +} + +struct list * +list_next(struct list *list) +{ + if (list->flags) + return NULL; + return ++list; +} + +void +list_remap_pool(struct array *pool, uint32_t *map) +{ + struct list *p, *end; + + end = pool->data + pool->size; + for (p = pool->data; p < end; p++) + p->data = map[p->data]; +} + +void +list_remap_head(struct list_head *head, uint32_t *map) +{ + if (head->flags == RAZOR_IMMEDIATE) + head->list_ptr = map[head->list_ptr]; +} diff -r c75a2d5caae9 -r 66ec30bde5e5 librazor/types/test-deque.c --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/librazor/types/test-deque.c Sat May 09 21:30:22 2009 +0100 @@ -0,0 +1,221 @@ +/* + * Copyright (C) 2009 J. Ali Harlow + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License along + * with this program; if not, write to the Free Software Foundation, Inc., + * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. + */ + +#include "config.h" + +#include +#include +#include +#include "types.h" + +static void dump_deque(struct deque *deque) +{ + int i; + fprintf(stderr, " +--------+\n"); + for(i = 0; i < deque->alloc; i += sizeof(uint32_t)) { + if (i == deque->front) + fprintf(stderr, "F>"); + else + fprintf(stderr, " "); + fprintf(stderr, " |%08X|", *(uint32_t *)(deque->data+i)); + if (i == deque->back) + fprintf(stderr, " size / sizeof (uint32_t); + items = array->data; + + DEQUE_TEST(deque_push, &deque, 0x25); + DEQUE_TEST(deque_push, &deque, 0x2A); + + for(n = 1; n <= count; n++) { + for(i = 0; i < n; i++) + DEQUE_TEST(deque_push, &deque, items[i]); + for(i = n - 1; i >= 0; i--) + DEQUE_CHECK(deque_pop, &deque, items[i]); + } + + DEQUE_CHECK(deque_pop, &deque, 0x2A); + DEQUE_CHECK(deque_pop, &deque, 0x25); + + DEQUE_ENSURE_EMPTY(&deque); + + deque_release(&deque); + return 0; +} + +static int test_unshift_shift(struct array *array) +{ + int i, n, count; + struct deque deque; + uint32_t *items; + + DEQUE_TEST(deque_init, &deque, 0); + + count = array->size / sizeof (uint32_t); + items = array->data; + + DEQUE_TEST(deque_unshift, &deque, 0x25); + DEQUE_TEST(deque_unshift, &deque, 0x2A); + + for(n = 1; n <= count; n++) { + for(i = 0; i < n; i++) + DEQUE_TEST(deque_unshift, &deque, items[i]); + for(i = n - 1; i >= 0; i--) + DEQUE_CHECK(deque_shift, &deque, items[i]); + } + + DEQUE_CHECK(deque_shift, &deque, 0x2A); + DEQUE_CHECK(deque_shift, &deque, 0x25); + + DEQUE_ENSURE_EMPTY(&deque); + + deque_release(&deque); + return 0; +} + +static int test_push_shift(struct array *array) +{ + int i, n, count; + struct deque deque; + uint32_t *items; + + DEQUE_TEST(deque_init, &deque, 0); + + count = array->size / sizeof (uint32_t); + items = array->data; + + for(n = 1; n <= count; n++) { + for(i = 0; i < n; i++) + DEQUE_TEST(deque_push, &deque, items[i]); + DEQUE_TEST(deque_push, &deque, 0x25); + DEQUE_TEST(deque_push, &deque, 0x2A); + for(i = 0; i < n; i++) + DEQUE_CHECK(deque_shift, &deque, items[i]); + DEQUE_CHECK(deque_shift, &deque, 0x25); + DEQUE_CHECK(deque_shift, &deque, 0x2A); + } + + DEQUE_ENSURE_EMPTY(&deque); + + deque_release(&deque); + return 0; +} + +static int test_unshift_pop(struct array *array) +{ + int i, n, count; + struct deque deque; + uint32_t *items; + + DEQUE_TEST(deque_init, &deque, 0); + + count = array->size / sizeof (uint32_t); + items = array->data; + + for(n = 1; n <= count; n++) { + for(i = 0; i < n; i++) + DEQUE_TEST(deque_unshift, &deque, items[i]); + DEQUE_TEST(deque_unshift, &deque, 0x25); + DEQUE_TEST(deque_unshift, &deque, 0x2A); + for(i = 0; i < n; i++) + DEQUE_CHECK(deque_pop, &deque, items[i]); + DEQUE_CHECK(deque_pop, &deque, 0x25); + DEQUE_CHECK(deque_pop, &deque, 0x2A); + } + + DEQUE_ENSURE_EMPTY(&deque); + + deque_release(&deque); + return 0; +} + +int main(int argc, char *argv[]) +{ + struct array array; + uint32_t *item; + int errors = 0; + + array_init(&array); + item = array_add(&array, sizeof(*item)); + *item = 0x7; + item = array_add(&array, sizeof(*item)); + *item = 0xC; + item = array_add(&array, sizeof(*item)); + *item = 0x3F; + item = array_add(&array, sizeof(*item)); + *item = 0x30; + item = array_add(&array, sizeof(*item)); + *item = 0x13; + item = array_add(&array, sizeof(*item)); + *item = 0x27; + item = array_add(&array, sizeof(*item)); + *item = 0x4A; + item = array_add(&array, sizeof(*item)); + *item = 0x7E; + item = array_add(&array, sizeof(*item)); + *item = 0x65; + + errors += test_push_pop(&array); + errors += test_push_shift(&array); + errors += test_unshift_pop(&array); + errors += test_unshift_shift(&array); + + array_release(&array); + + exit(errors ? 1 : 0); +} diff -r c75a2d5caae9 -r 66ec30bde5e5 librazor/types/test-graph.c --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/librazor/types/test-graph.c Sat May 09 21:30:22 2009 +0100 @@ -0,0 +1,196 @@ +/* + * Copyright (C) 2009 J. Ali Harlow + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License along + * with this program; if not, write to the Free Software Foundation, Inc., + * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. + */ + +#include "config.h" + +#include +#include +#include +#include "types.h" + +static int test_sort(struct graph *graph) +{ + struct bitset vertices; + struct bitset_iter bi; + struct deque *order, *deque; + int i, n_edges; + uint32_t v, v1, v2; + + order = graph_sort(graph); + + if (deque_empty(order)) + fprintf(stderr, "Empty sort ouput\n"); + else { + deque = deque_dup(order); + printf("%u", deque_pop(deque)); + while(!deque_empty(deque)) + printf(", %u", deque_pop(deque)); + printf("\n"); + deque_free(deque); + } + + bitset_init(vertices); + deque = deque_dup(order); + while(!deque_empty(deque)) { + v = deque_pop(deque); + if (bitset_test_bit(vertices, v)) { + fprintf(stderr, + "Vertex %u appears more than once\n", v); + return 1; + } else + bitset_set_bit(vertices, v); + } + deque_free(deque); + + n_edges = graph_get_no_edges(graph); + for(i = 0; i < n_edges; i++) { + if (!graph_get_edge(graph, i, &v1, &v2)) { + fprintf(stderr, "Failed to get edge %d\n", i); + return 1; + } + if (!bitset_test_bit(vertices, v1)) { + fprintf(stderr, "Vertex %u not in sort output\n", v1); + return 1; + } + if (!bitset_test_bit(vertices, v2)) { + fprintf(stderr, "Vertex %u not in sort output\n", v2); + return 1; + } + } + + for(i = 0; i < n_edges; i++) { + if (!graph_get_edge(graph, i, &v1, &v2)) { + fprintf(stderr, "Failed to get edge %d\n", i); + return 1; + } + bitset_clear_bit(vertices, v1); + bitset_clear_bit(vertices, v2); + } + bitset_iter_init(vertices, bi); + bitset_iter_next_bit(vertices, bi); + if (bitset_iter_get_bit(vertices, bi) >= 0) { + fprintf(stderr, "Vertex %u in sort output does not exist\n", + bitset_iter_get_bit(vertices, bi)); + return 1; + } + bitset_release(vertices); + + deque = deque_dup(order); + if (!deque_empty(deque)) + v1 = deque_pop(deque); + while(!deque_empty(deque)) { + v2 = v1; + v1 = deque_pop(deque); + if (graph_is_connected(graph, v2, v1) && + !graph_is_connected(graph, v1, v2)) { + fprintf(stderr, "Sort output pair %u, %u " + "is mis-ordered\n", v1, v2); + return 1; + } + } + deque_free(deque); + + return 0; +} + +int main(int argc, char *argv[]) +{ + struct graph graph; + int errors = 0; + + /* This test case is from: + * http://en.wikipedia.org/wiki/Topological_sort + */ + graph_init(&graph); + graph_add_edge(&graph, 7, 11); + graph_add_edge(&graph, 7, 8); + graph_add_edge(&graph, 5, 11); + graph_add_edge(&graph, 3, 8); + graph_add_edge(&graph, 3, 10); + graph_add_edge(&graph, 11, 2); + graph_add_edge(&graph, 11, 9); + graph_add_edge(&graph, 11, 10); + graph_add_edge(&graph, 8, 9); + + errors += test_sort(&graph); + + graph_release(&graph); + + /* This one includes a cycle */ + graph_init(&graph); + graph_add_edge(&graph, 9, 5); + graph_add_edge(&graph, 5, 1); + graph_add_edge(&graph, 10, 6); + graph_add_edge(&graph, 6, 2); + graph_add_edge(&graph, 11, 7); + graph_add_edge(&graph, 7, 3); + graph_add_edge(&graph, 12, 8); + graph_add_edge(&graph, 8, 4); + graph_add_edge(&graph, 5, 6); + graph_add_edge(&graph, 6, 7); + graph_add_edge(&graph, 7, 8); + graph_add_edge(&graph, 8, 5); + + errors += test_sort(&graph); + + graph_release(&graph); + + /* This one includes a cycle that isn't just a ring */ + graph_init(&graph); + graph_add_edge(&graph, 0, 1); + graph_add_edge(&graph, 1, 2); + graph_add_edge(&graph, 1, 3); + graph_add_edge(&graph, 1, 4); + graph_add_edge(&graph, 4, 3); + graph_add_edge(&graph, 3, 2); + graph_add_edge(&graph, 2, 5); + graph_add_edge(&graph, 4, 5); + graph_add_edge(&graph, 5, 6); + + errors += test_sort(&graph); + + graph_release(&graph); + + /* This one includes a number of vertices that have loops */ + graph_init(&graph); + graph_add_edge(&graph, 0, 0); + graph_add_edge(&graph, 1, 2); + graph_add_edge(&graph, 2, 2); + + errors += test_sort(&graph); + + graph_release(&graph); + + /* This one is a multigraph with a cycle */ + graph_init(&graph); + graph_add_edge(&graph, 0, 1); + graph_add_edge(&graph, 0, 1); + graph_add_edge(&graph, 1, 2); + graph_add_edge(&graph, 1, 2); + graph_add_edge(&graph, 3, 1); + graph_add_edge(&graph, 3, 2); + graph_add_edge(&graph, 2, 4); + graph_add_edge(&graph, 4, 2); + graph_add_edge(&graph, 4, 5); + + errors += test_sort(&graph); + + graph_release(&graph); + + exit(errors ? 1 : 0); +} diff -r c75a2d5caae9 -r 66ec30bde5e5 librazor/types/test-hashtable.c --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/librazor/types/test-hashtable.c Sat May 09 21:30:22 2009 +0100 @@ -0,0 +1,75 @@ +/* + * Copyright (C) 2009 J. Ali Harlow + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License along + * with this program; if not, write to the Free Software Foundation, Inc., + * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. + */ + +#include "config.h" + +#include +#include +#include +#include "types.h" + +uint32_t invalid; +struct array pool; +struct hashtable table; + +static int test_key(const char *key) +{ + uint32_t value; + + value = hashtable_insert(&table, key); + if (value == invalid) { + fprintf(stderr, + "%s: hashtable_insert returned invalid value\n", key); + return 1; + } else if (value >= pool.size) { + fprintf(stderr, "%s: hashtable_insert returned value outside " + "pool\n", key); + return 1; + } else if (pool.size - value <= strlen(key) || + strcmp(pool.data + value, key)) { + fprintf(stderr, "%s: value returned by hashtable_insert does " + "not match key\n", key); + return 1; + } else if (hashtable_lookup(&table, key) != value) { + fprintf(stderr, "%s: hashtable_lookup didn't return expected " + "value\n", key); + return 1; + } else if (hashtable_tokenize(&table, key) != value) { + fprintf(stderr, "%s: hashtable_tokenize didn't return expected " + "value\n", key); + return 1; + } + return 0; +} + +int main(int argc, char *argv[]) +{ + int errors = 0; + + array_init(&pool); + hashtable_init(&table, &pool); + invalid = hashtable_lookup(&table, "non-existant"); + + errors += test_key("key1"); + errors += test_key("key2"); + + hashtable_release(&table); + array_release(&pool); + + exit(errors ? 1 : 0); +} diff -r c75a2d5caae9 -r 66ec30bde5e5 librazor/types/types.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/librazor/types/types.h Sat May 09 21:30:22 2009 +0100 @@ -0,0 +1,284 @@ +/* + * Copyright (C) 2008 Kristian Høgsberg + * Copyright (C) 2008 Red Hat, Inc + * Copyright (C) 2009 J. Ali Harlow + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License along + * with this program; if not, write to the Free Software Foundation, Inc., + * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. + */ + +#ifndef _RAZOR_TYPES_H_ +#define _RAZOR_TYPES_H_ + +#include +#include + +struct array { + void *data; + int size, alloc; +}; + +void array_init(struct array *array); +void array_release(struct array *array); +void *array_add(struct array *array, int size); + + +struct list_head { + uint32_t list_ptr : 24; + uint32_t flags : 8; +}; + +struct list { + uint32_t data : 24; + uint32_t flags : 8; +}; + +void list_set_empty(struct list_head *head); +void list_set_ptr(struct list_head *head, uint32_t ptr); +void list_set_array(struct list_head *head, struct array *pool, struct array *items, int force_indirect); + +struct list *list_first(struct list_head *head, struct array *pool); +struct list *list_next(struct list *list); + +void list_remap_pool(struct array *pool, uint32_t *map); +void list_remap_head(struct list_head *list, uint32_t *map); + + +struct hashtable { + struct array buckets; + struct array *pool; +}; + +void hashtable_init(struct hashtable *table, struct array *pool); +void hashtable_release(struct hashtable *table); +uint32_t hashtable_insert(struct hashtable *table, const char *key); +uint32_t hashtable_lookup(struct hashtable *table, const char *key); +uint32_t hashtable_tokenize(struct hashtable *table, const char *string); + + +/* + * Double-ended queues. + * Use push/pop for LIFO behaviour and push/shift for FIFO. + * In general, unshift is more expensive than push. + */ + +struct deque { + void *data; + int front, back, alloc; +}; + +int deque_init(struct deque *deque, int sized); +void deque_release(struct deque *deque); +struct deque *deque_new(int sized); +void deque_free(struct deque *deque); +struct deque *deque_dup(struct deque *deque); +int deque_unshift(struct deque *deque, uint32_t datum); +int deque_push(struct deque *deque, uint32_t datum); +int deque_empty(struct deque *deque); +uint32_t deque_shift(struct deque *deque); +uint32_t deque_pop(struct deque *deque); + + +struct bitset { + uint32_t nb; + unsigned char *set; +}; + +#define bitset_init(bitset) memset(&(bitset), 0, sizeof bitset) + +#define bitset_release(bitset) free((bitset).set) + +#define bitset_clear(bitset) do { (bitset).nb = 0; } while (0) + +#define bitset_clear_bit(bitset, bit) \ + do { \ + if ((bit) < (bitset).nb * 8) \ + (bitset).set[(bit) / 8] &= ~(1U << (bit) % 8); \ + } while (0) + +#define bitset_set_bit(bitset, bit) \ + do { \ + if ((bit) >= (bitset).nb * 8) { \ + unsigned char *__bitset_new; \ + __bitset_new = realloc((bitset).set, (bit) / 8 + 1); \ + if (__bitset_new) { \ + (bitset).set = __bitset_new; \ + memset((bitset).set + (bitset).nb, 0, \ + (bit) / 8 + 1 - (bitset).nb); \ + (bitset).nb = (bit) / 8 + 1; \ + } \ + } \ + if ((bit) < (bitset).nb * 8) \ + (bitset).set[(bit) / 8] |= 1U << (bit) % 8; \ + } while (0) + +#define bitset_set_n_bits(bitset, first, count) \ + do { \ + if ((first) + (count) > (bitset).nb * 8) { \ + unsigned char *__bitset_new; \ + __bitset_new = \ + realloc((bitset).set, \ + ((first) + (count) - 1) / 8 + 1); \ + if (__bitset_new) { \ + (bitset).set = __bitset_new; \ + memset((bitset).set + (bitset).nb, 0, \ + ((first) + (count) - 1) / 8 + \ + 1 - (bitset).nb); \ + (bitset).nb = ((first) + (count) - 1) / 8 + 1; \ + } \ + } \ + if ((first) + (count) > (bitset).nb * 8) \ + break; \ + /* \ + * Cases to consider: \ + * \ + * +--------+--------+--------+ \ + * |01234567|01234567|01234567| case A \ + * +--------+--------+--------+ \ + * first -^ ^- first+count \ + * \ + * +--------+--------+--------+ \ + * |01234567|01234567|01234567| case B \ + * +--------+--------+--------+ \ + * first -^ first+count -^ \ + * \ + * +--------+--------+--------+ \ + * |01234567|01234567|01234567| case C \ + * +--------+--------+--------+ \ + * first -^ ^- first+count \ + * \ + * +--------+--------+--------+ \ + * |01234567|01234567|01234567| case D \ + * +--------+--------+--------+ \ + * first -^ ^- first+count \ + * \ + * +--------+--------+--------+ \ + * |01234567|01234567|01234567| case E \ + * +--------+--------+--------+ \ + * first -^ first+count -^ \ + * \ + * +--------+--------+--------+ \ + * |01234567|01234567|01234567| case F \ + * +--------+--------+--------+ \ + * first -^ ^- first+count \ + */ \ + if ((count) && (first) / 8 == ((first) + (count) - 1) / 8) \ + /* cases A & D */ \ + (bitset).set[(first) / 8] |= \ + ((1U << (count)) - 1) << (first) % 8; \ + else if (count) { \ + if ((first) % 8) /* cases E & F -> B & A/C */ \ + (bitset).set[(first) / 8] |= \ + ((1U << (first) % 8) - 1) ^ 0xFF; \ + if ((count) - (8 - (first) % 8) % 8 >= 8) \ + /* cases B & C -> / & A */ \ + memset((bitset).set + ((first) + 7) / 8, 0xFF, \ + ((count) - (8 - (first) % 8) % 8) / 8); \ + if (((first) + (count)) % 8) /* case A */ \ + (bitset).set[((first) + (count)) / 8] |= \ + (1U << ((first) + (count)) % 8) - 1; \ + } \ + } while (0) + +#define bitset_test_bit(bitset, bit) \ + ((bit) < (bitset).nb * 8 ? \ + (bitset).set[(bit) / 8] & 1U << (bit) % 8 : 0) + +/* dst <- (NOT src) AND dst */ +#define bitset_and_inverted(dst, src) \ + do { \ + unsigned int __bitset_nb; \ + __bitset_nb = (src).nb > (dst).nb ? (dst).nb : (src).nb; \ + if (__bitset_nb--) \ + do { \ + (dst).set[__bitset_nb] &= \ + ~(src).set[__bitset_nb]; \ + } while (__bitset_nb--); \ + } while(0) + +#define bitset_get_length(bitset) ((bitset).nb * 8) + +#define bitset_copy(dst, src) \ + do { \ + unsigned char *__bitset_new; \ + __bitset_new = realloc((dst).set, (src).nb); \ + if (__bitset_new) { \ + (dst).set = __bitset_new; \ + (dst).nb = (src).nb; \ + memcpy((dst).set, (src).set, (dst).nb); \ + } else \ + (dst).nb = 0; \ + } while(0) + +#define bitset_compact(bitset) \ + do { \ + unsigned char *__bitset_new; \ + while((bitset).nb && !(bitset).set[(bitset).nb - 1]) \ + (bitset).nb--; \ + __bitset_new = realloc((bitset).set, (bitset).nb); \ + if (__bitset_new || !(bitset).nb) \ + (bitset).set = __bitset_new; \ + } while (0) + +struct bitset_iter { + int byte; + int bit; +}; + +#define bitset_iter_init(bitset, iter) \ + do { (iter).byte = 0; (iter).bit = -1; } while (0) + +#define bitset_iter_next_bit(bitset, iter) \ + do { \ + if ((iter).byte < (bitset).nb) { \ + for((iter).bit++; (iter).bit < 8; (iter).bit++) \ + if ((bitset).set[(iter).byte] & \ + 1 << (iter).bit) \ + break; \ + if ((iter).bit >= 8) { \ + for((iter).byte++; (iter).byte < (bitset).nb; \ + (iter).byte++) { \ + (iter).bit = \ + ffs((bitset).set[(iter).byte]);\ + if ((iter).bit--) \ + break; \ + } \ + } \ + } \ + } while(0) + +#define bitset_iter_get_bit(bitset, iter) \ + ((iter).byte < (bitset).nb ? (iter).byte * 8 + (iter).bit : -1) + + +struct graph_edge { + uint32_t v1, v2; +}; + +struct graph { + struct array edges; + //struct list_head head; + //struct array sort_pool; +}; + +void graph_init(struct graph *graph); +void graph_release(struct graph *graph); +void graph_add_edge(struct graph *graph, uint32_t vertex1, uint32_t vertex2); +int graph_remove_edge(struct graph *graph, uint32_t vertex1, uint32_t vertex2); +uint32_t graph_get_no_edges(struct graph *graph); +int graph_get_edge(struct graph *graph, int nth, uint32_t *v1, uint32_t *v2); +int graph_is_connected(struct graph *graph, uint32_t v1, uint32_t v2); +struct deque *graph_sort(struct graph *graph); + +#endif /* _RAZOR_TYPES_H_ */