From 8fa254b06d7772568069a32ad5f67d82165515e1 Mon Sep 17 00:00:00 2001 From: "Mike D. Lowis" Date: Wed, 23 Sep 2015 11:51:25 -0400 Subject: [PATCH] Added latest hamt code and fixed build error --- source/gir_internals.h | 8 ++- source/hamt.c | 116 +++++++++++++++++++++-------------------- source/parser.c | 2 +- 3 files changed, 64 insertions(+), 62 deletions(-) diff --git a/source/gir_internals.h b/source/gir_internals.h index 6248ddd..6c4b08b 100644 --- a/source/gir_internals.h +++ b/source/gir_internals.h @@ -50,10 +50,6 @@ slist_node_t* slist_node_next(slist_node_t* node); /****************************************************************************** * 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 */ @@ -77,7 +73,9 @@ typedef struct { uint32_t part; uint32_t bits; uint32_t level; - hamt_node_t* node; + hamt_node_t* grandparent; + hamt_node_t* parent; + hamt_node_t* current; } hamt_ctx_t; void hamt_init(hamt_t* trie, hamt_keyfn_t getkey, hamt_delfn_t delfn, hamt_cmpfn_t cmpfn); diff --git a/source/hamt.c b/source/hamt.c index 4c66be7..5fb222b 100644 --- a/source/hamt.c +++ b/source/hamt.c @@ -1,42 +1,42 @@ #include "gir_internals.h" -static bool is_subtrie(hamt_node_t* node) { +static inline 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) { +static inline 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) { +static inline 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) { +static inline void set_value(hamt_node_t* node, void* value) { node->base_or_value = (uintptr_t)value; } -static void* get_value(hamt_node_t* node) { +static inline void* get_value(hamt_node_t* node) { return ((void*)node->base_or_value); } /*****************************************************************************/ -static uint32_t hash_key(uint8_t* key, size_t len) { +static inline 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) { +static inline 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) { +static inline uint32_t get_hash(hamt_t* trie, void* entry) { uint8_t* addr; size_t len; trie->getkey(entry, &addr, &len); @@ -44,7 +44,7 @@ static uint32_t get_hash(hamt_t* trie, void* entry) { return hash; } -static uint32_t get_rehash(hamt_t* trie, void* entry, int level) { +static inline uint32_t get_rehash(hamt_t* trie, void* entry, int level) { uint8_t* addr; size_t len; trie->getkey(entry, &addr, &len); @@ -53,7 +53,7 @@ static uint32_t get_rehash(hamt_t* trie, void* entry, int level) { /*****************************************************************************/ -static uint64_t popcount(uint64_t bits) { +static inline uint64_t popcount(uint64_t bits) { #ifdef __GNUC__ return __builtin_popcount(bits); #else @@ -68,58 +68,60 @@ static uint64_t popcount(uint64_t bits) { #endif } -static uint32_t get_index(hamt_ctx_t* ctx) { +static inline 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 lower_bits = ctx->current->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 inline uint32_t get_size(hamt_ctx_t* ctx) { + return popcount(ctx->current->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 inline 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->grandparent = NULL; + ctx->parent = NULL; + ctx->current = &trie->root[ctx->part]; } -static void add_to_subtrie(hamt_ctx_t* ctx, void* key) +static inline 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); + ctx->current->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)); + memcpy(newnodes, get_subtrie(ctx->current), index * sizeof(hamt_node_t)); + memcpy(&newnodes[index+1], &(get_subtrie(ctx->current))[index], (size-index-1) * sizeof(hamt_node_t)); + free(get_subtrie(ctx->current)); /* Setup the new node */ newnodes[index].bitmap_or_key = ctx->hash; set_value(&newnodes[index], key); - set_subtrie(ctx->node, newnodes); + set_subtrie(ctx->current, newnodes); } -static void build_subtrie(hamt_t* trie, hamt_ctx_t* ctx, void* key) +static inline void build_subtrie(hamt_t* trie, hamt_ctx_t* ctx, void* key) { - uint32_t hash = ctx->node->bitmap_or_key; + uint32_t hash = ctx->current->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); + hash = get_rehash(trie, (void*)(ctx->current->base_or_value), ctx->level); ctx->bits = 0; } ctx->part = (ctx->hash >> ctx->bits) & 0x1F; @@ -128,10 +130,10 @@ static void build_subtrie(hamt_t* trie, hamt_ctx_t* ctx, void* key) 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; + newnode->base_or_value = ctx->current->base_or_value; + ctx->current->bitmap_or_key = 1 << ctx->part; + set_subtrie(ctx->current, newnode); + ctx->current = newnode; ctx->level++; /* Otherwise they differ, so build a two-entry node */ } else { @@ -139,18 +141,18 @@ static void build_subtrie(hamt_t* trie, hamt_ctx_t* ctx, void* key) /* 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[0].base_or_value = ctx->current->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; + newnodes[1].base_or_value = ctx->current->base_or_value; } /* Update the bitmap for the subtrie */ - ctx->node->bitmap_or_key = (1UL << ctx->part) | (1UL << part); - set_subtrie(ctx->node, newnodes); + ctx->current->bitmap_or_key = (1UL << ctx->part) | (1UL << part); + set_subtrie(ctx->current, newnodes); break; } } @@ -169,13 +171,13 @@ 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) { + if (0 != ctx->current->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); + if (!is_subtrie(ctx->current)) { + if ((ctx->current->bitmap_or_key == ctx->hash) && + (0 == trie->cmpentry(key, get_value(ctx->current)))) { + entry = get_value(ctx->current); } break; } @@ -187,39 +189,35 @@ static void* find_entry(hamt_t* trie, hamt_ctx_t* ctx, void* key) { } ctx->part = (ctx->hash >> ctx->bits) & 0x1F; /* If the trie is empty, bail */ - if (0 == (ctx->node->bitmap_or_key & (1 << ctx->part))) + if (0 == (ctx->current->bitmap_or_key & (1 << ctx->part))) break; /* Otherwise, descend to the subtrie */ - ctx->node = &((get_subtrie(ctx->node))[get_index(ctx)]); + ctx->grandparent = ctx->parent; + ctx->parent = ctx->current; + ctx->current = &((get_subtrie(ctx->current))[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); + if (0 == ctx.current->base_or_value) { + ctx.current->bitmap_or_key = ctx.hash; + set_value(ctx.current, 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); + trie->delentry(get_value(ctx.current)); + set_value(ctx.current, entry); /* If we ended on a subtrie, add the value to the node */ - } else if (is_subtrie(ctx.node)) { + } else if (is_subtrie(ctx.current)) { add_to_subtrie(&ctx, key); /* If we ended on a value, build the tree out until the keys differ */ } else { @@ -228,3 +226,9 @@ void hamt_insert(hamt_t* trie, void* key) { } } +void* hamt_lookup(hamt_t* trie, void* key) { + hamt_ctx_t ctx; + init_context(&ctx, trie, key); + return find_entry(trie, &ctx, key); +} + diff --git a/source/parser.c b/source/parser.c index afbca1d..a3094db 100644 --- a/source/parser.c +++ b/source/parser.c @@ -2,7 +2,7 @@ @file parser.c */ //#include "parser.h" -#include "slist.h" +#include "gir_internals.h" #include #include #include -- 2.52.0