From 0b432763727e8771aa02e64cd8a870c1171a5d80 Mon Sep 17 00:00:00 2001 From: "Michael D. Lowis" Date: Sat, 22 Aug 2015 12:00:12 -0400 Subject: [PATCH] Added an 'internals' header so the source directory stays clean and tidy --- source/gir_internals.h | 89 ++++++++++++++++ source/hamt.c | 230 +++++++++++++++++++++++++++++++++++++++++ source/slist.c | 2 +- source/slist.h | 43 -------- 4 files changed, 320 insertions(+), 44 deletions(-) create mode 100644 source/gir_internals.h create mode 100644 source/hamt.c delete mode 100644 source/slist.h diff --git a/source/gir_internals.h b/source/gir_internals.h new file mode 100644 index 0000000..6248ddd --- /dev/null +++ b/source/gir_internals.h @@ -0,0 +1,89 @@ +/** + @file gir_internals.h + @brief TODO: Describe this file + */ +#ifndef GIR_INTERNALS_H +#define GIR_INTERNALS_H + +#include +#include +#include +#include +#include + +/****************************************************************************** + * Singly Linked List + *****************************************************************************/ +typedef struct slist_node_t { + struct slist_node_t* next; +} slist_node_t; + +typedef struct { + slist_node_t* head; +} slist_t; + +void slist_init(slist_t* list); + +bool slist_empty(slist_t* list); + +size_t slist_size(slist_t* list); + +slist_node_t* slist_front(slist_t* list); + +void slist_push_front(slist_t* list, slist_node_t* node); + +slist_node_t* slist_pop_front(slist_t* list); + +slist_node_t* slist_back(slist_t* list); + +void slist_push_back(slist_t* list, slist_node_t* node); + +slist_node_t* slist_pop_back(slist_t* list); + +bool slist_node_has_next(slist_node_t* node); + +slist_node_t* slist_node_next(slist_node_t* node); + +#define slist_foreach(elem, list) \ + for(slist_node_t* elem = slist_front(list); elem != NULL; elem = elem->next) + +/****************************************************************************** + * Hash Array Mapped Trie + *****************************************************************************/ +typedef struct hamt_entry_t { + struct hamt_entry_t* next; +} hamt_entry_t; + +typedef struct hamt_node_t { + uintptr_t bitmap_or_key; /* bitmap or hash key */ + uintptr_t base_or_value; /* base of entry list or value */ +} hamt_node_t; + +typedef void (*hamt_keyfn_t)(void* entry, uint8_t** addr, size_t* len); + +typedef void (*hamt_delfn_t)(void* entry); + +typedef int (*hamt_cmpfn_t)(void* a, void* b); + +typedef struct hamt_t { + hamt_node_t* root; + hamt_keyfn_t getkey; + hamt_delfn_t delentry; + hamt_cmpfn_t cmpentry; +} hamt_t; + +typedef struct { + uint32_t hash; + uint32_t part; + uint32_t bits; + uint32_t level; + hamt_node_t* node; +} hamt_ctx_t; + +void hamt_init(hamt_t* trie, hamt_keyfn_t getkey, hamt_delfn_t delfn, hamt_cmpfn_t cmpfn); + +void* hamt_lookup(hamt_t* trie, void* key); + +void hamt_insert(hamt_t* trie, void* key); + +#endif /* GIR_INTERNALS_H */ diff --git a/source/hamt.c b/source/hamt.c new file mode 100644 index 0000000..4c66be7 --- /dev/null +++ b/source/hamt.c @@ -0,0 +1,230 @@ +#include "gir_internals.h" + +static bool is_subtrie(hamt_node_t* node) { + return (node->base_or_value & 1u); +} + +static void set_subtrie(hamt_node_t* node, hamt_node_t* value) { + node->base_or_value = ((uintptr_t)value | 1); +} + +static hamt_node_t* get_subtrie(hamt_node_t* node) { + return ((hamt_node_t*)((node->base_or_value | 1) ^ 1)); +} + +static void set_value(hamt_node_t* node, void* value) { + node->base_or_value = (uintptr_t)value; +} + +static void* get_value(hamt_node_t* node) { + return ((void*)node->base_or_value); +} + +/*****************************************************************************/ + +static uint32_t hash_key(uint8_t* key, size_t len) { + uint32_t a=31415u, b=27183u, hash; + for (hash=0; len > 0; key++, len--, a*=b) + hash = (a * hash) + *key; + return hash; +} + +static uint32_t rehash_key(uint8_t* key, size_t len, int level) { + uint32_t a=31415u, b=27183u, hash; + for (hash=0; len > 0; key++, len--, a*=b) + hash = (a * hash * level) + *key; + return hash; +} + +static uint32_t get_hash(hamt_t* trie, void* entry) { + uint8_t* addr; + size_t len; + trie->getkey(entry, &addr, &len); + uint32_t hash = hash_key(addr, len); + return hash; +} + +static uint32_t get_rehash(hamt_t* trie, void* entry, int level) { + uint8_t* addr; + size_t len; + trie->getkey(entry, &addr, &len); + return rehash_key(addr, len, level); +} + +/*****************************************************************************/ + +static uint64_t popcount(uint64_t bits) { +#ifdef __GNUC__ + return __builtin_popcount(bits); +#else + const uint64_t m1 = 0x5555555555555555; + const uint64_t m2 = 0x3333333333333333; + const uint64_t m4 = 0x0f0f0f0f0f0f0f0f; + const uint64_t h01 = 0x0101010101010101; + bits -= (bits >> 1) & m1; + bits = (bits & m2) + ((bits >> 2) & m2); + bits = (bits + (bits >> 4)) & m4; + return (bits * h01) >> 56; +#endif +} + +static uint32_t get_index(hamt_ctx_t* ctx) { + uint32_t mask = ~((~0ul) << ctx->part); + uint32_t lower_bits = ctx->node->bitmap_or_key & mask; + uint32_t count = popcount(lower_bits); + return count; +} + +static uint32_t get_size(hamt_ctx_t* ctx) { + return popcount(ctx->node->bitmap_or_key); +} + +/*****************************************************************************/ + +static void init_context(hamt_ctx_t* ctx, hamt_t* trie, void* entry) { + ctx->hash = get_hash(trie, entry); + ctx->part = (ctx->hash & 0x1F); + ctx->bits = 0; + ctx->level = 0; + ctx->node = &trie->root[ctx->part]; +} + +static void add_to_subtrie(hamt_ctx_t* ctx, void* key) +{ + uint32_t size; + uint32_t index; + hamt_node_t* newnodes; + /* Set the bit in the bitmap */ + ctx->node->bitmap_or_key |= (1 << ctx->part); + /* Count bits in the bitmap to determine new size */ + size = get_size(ctx); + newnodes = malloc(size * sizeof(hamt_node_t)); + /* Copy the old data to the new array leaving a gap for the new entry */ + index = get_index(ctx); + memcpy(newnodes, get_subtrie(ctx->node), index * sizeof(hamt_node_t)); + memcpy(&newnodes[index+1], &(get_subtrie(ctx->node))[index], (size-index-1) * sizeof(hamt_node_t)); + free(get_subtrie(ctx->node)); + /* Setup the new node */ + newnodes[index].bitmap_or_key = ctx->hash; + set_value(&newnodes[index], key); + set_subtrie(ctx->node, newnodes); +} + +static void build_subtrie(hamt_t* trie, hamt_ctx_t* ctx, void* key) +{ + uint32_t hash = ctx->node->bitmap_or_key; + while (true) { + uint32_t part; + /* Descend down the trie to the nodes that dont exist yet */ + ctx->bits += 5; + if (ctx->bits > 30) { + ctx->hash = get_rehash(trie, key, ctx->level); + hash = get_rehash(trie, (void*)(ctx->node->base_or_value), ctx->level); + ctx->bits = 0; + } + ctx->part = (ctx->hash >> ctx->bits) & 0x1F; + part = (hash >> ctx->bits) & 0x1F; + /* If the bits are equal, build a single entry node and keep going */ + if (part == ctx->part) { + hamt_node_t* newnode = (hamt_node_t*)calloc(1,sizeof(hamt_node_t)); + newnode->bitmap_or_key = hash; + newnode->base_or_value = ctx->node->base_or_value; + ctx->node->bitmap_or_key = 1 << ctx->part; + set_subtrie(ctx->node, newnode); + ctx->node = newnode; + ctx->level++; + /* Otherwise they differ, so build a two-entry node */ + } else { + hamt_node_t* newnodes = (hamt_node_t*)calloc(2,sizeof(hamt_node_t)); + /* copy nodes to new subtrie in order */ + if (part < ctx->part) { + newnodes[0].bitmap_or_key = hash; + newnodes[0].base_or_value = ctx->node->base_or_value; + newnodes[1].bitmap_or_key = ctx->hash; + set_value(&newnodes[1], key); + } else { + newnodes[0].bitmap_or_key = ctx->hash; + set_value(&newnodes[0], key); + newnodes[1].bitmap_or_key = hash; + newnodes[1].base_or_value = ctx->node->base_or_value; + } + /* Update the bitmap for the subtrie */ + ctx->node->bitmap_or_key = (1UL << ctx->part) | (1UL << part); + set_subtrie(ctx->node, newnodes); + break; + } + } +} + +/*****************************************************************************/ + +void hamt_init(hamt_t* trie, hamt_keyfn_t getkey, hamt_delfn_t delfn, hamt_cmpfn_t cmpfn) { + trie->root = calloc(32, sizeof(hamt_node_t)); + trie->getkey = getkey; + trie->delentry = delfn; + trie->cmpentry = cmpfn; +} + +static void* find_entry(hamt_t* trie, hamt_ctx_t* ctx, void* key) { + void* entry = NULL; + + /* If the slot is not empty, search the trie */ + if (0 != ctx->node->base_or_value) { + while (true) { + /* If we reached a leaf, check to see if we have a match */ + if (!is_subtrie(ctx->node)) { + if ((ctx->node->bitmap_or_key == ctx->hash) && + (0 == trie->cmpentry(key, get_value(ctx->node)))) { + entry = get_value(ctx->node); + } + break; + } + /* Otherwise, descend further down the tree */ + ctx->bits += 5; + if (ctx->bits > 30) { + ctx->hash = get_rehash(trie, key, ctx->level); + ctx->bits = 0; + } + ctx->part = (ctx->hash >> ctx->bits) & 0x1F; + /* If the trie is empty, bail */ + if (0 == (ctx->node->bitmap_or_key & (1 << ctx->part))) + break; + /* Otherwise, descend to the subtrie */ + ctx->node = &((get_subtrie(ctx->node))[get_index(ctx)]); + ctx->level++; + } + } + return entry; +} + +void* hamt_lookup(hamt_t* trie, void* key) { + hamt_ctx_t ctx; + init_context(&ctx, trie, key); + return find_entry(trie, &ctx, key); +} + +void hamt_insert(hamt_t* trie, void* key) { + hamt_ctx_t ctx; + void* entry; + init_context(&ctx, trie, key); + + /* If the root table entry is empty, then fill it in and bail */ + if (0 == ctx.node->base_or_value) { + ctx.node->bitmap_or_key = ctx.hash; + set_value(ctx.node, key); + } else { + entry = find_entry(trie, &ctx, key); + /* If we found an entry, replace it */ + if (entry != NULL) { + trie->delentry(get_value(ctx.node)); + set_value(ctx.node, entry); + /* If we ended on a subtrie, add the value to the node */ + } else if (is_subtrie(ctx.node)) { + add_to_subtrie(&ctx, key); + /* If we ended on a value, build the tree out until the keys differ */ + } else { + build_subtrie(trie, &ctx, key); + } + } +} + diff --git a/source/slist.c b/source/slist.c index e4308e7..4f8dcb0 100644 --- a/source/slist.c +++ b/source/slist.c @@ -1,4 +1,4 @@ -#include "slist.h" +#include "gir_internals.h" void slist_init(slist_t* list) { diff --git a/source/slist.h b/source/slist.h deleted file mode 100644 index cae7ba3..0000000 --- a/source/slist.h +++ /dev/null @@ -1,43 +0,0 @@ -/** - @file slist.h -*/ -#ifndef SLIST_H -#define SLIST_H - -#include -#include - -typedef struct slist_node_t { - struct slist_node_t* next; -} slist_node_t; - -typedef struct { - slist_node_t* head; -} slist_t; - -void slist_init(slist_t* list); - -bool slist_empty(slist_t* list); - -size_t slist_size(slist_t* list); - -slist_node_t* slist_front(slist_t* list); - -void slist_push_front(slist_t* list, slist_node_t* node); - -slist_node_t* slist_pop_front(slist_t* list); - -slist_node_t* slist_back(slist_t* list); - -void slist_push_back(slist_t* list, slist_node_t* node); - -slist_node_t* slist_pop_back(slist_t* list); - -bool slist_node_has_next(slist_node_t* node); - -slist_node_t* slist_node_next(slist_node_t* node); - -#define slist_foreach(elem, list) \ - for(slist_node_t* elem = slist_front(list); elem != NULL; elem = elem->next) - -#endif /* SLIST_H */ -- 2.54.0