From 7ccb32c30577df22043d05126144f1dd5829255f Mon Sep 17 00:00:00 2001 From: Joshua Haberman Date: Mon, 22 Jun 2009 12:46:14 -0700 Subject: Finished hashtable implementation, not yet tested. --- upb_table.h | 22 ++++++++++++---------- 1 file changed, 12 insertions(+), 10 deletions(-) (limited to 'upb_table.h') diff --git a/upb_table.h b/upb_table.h index f405e05..7565a52 100644 --- a/upb_table.h +++ b/upb_table.h @@ -23,6 +23,9 @@ extern "C" { typedef uint32_t upb_inttable_key_t; +#define UPB_END_OF_CHAIN (uint32_t)0 +#define UPB_INDEX(base, i, m) (void*)((char*)base + (i*m)) + struct upb_inttable_entry { upb_inttable_key_t key; uint32_t next; /* Internal chaining. */ @@ -78,8 +81,8 @@ INLINE uint32_t upb_strtable_size(struct upb_strtable *t) { void upb_inttable_insert(struct upb_inttable *t, struct upb_inttable_entry *e); void upb_strtable_insert(struct upb_strtable *t, struct upb_strtable_entry *e); -INLINE uint32_t upb_inttable_hash(struct upb_inttable *t, upb_inttable_key_t k) { - return k & (upb_inttable_size(t)-1); /* Identity hash for ints. */ +INLINE uint32_t upb_inttable_bucket(struct upb_inttable *t, upb_inttable_key_t k) { + return (k & (upb_inttable_size(t)-1)) + 1; /* Identity hash for ints. */ } /* Looks up key in this table. Inlined because this is in the critical path @@ -88,14 +91,13 @@ INLINE uint32_t upb_inttable_hash(struct upb_inttable *t, upb_inttable_key_t k) * compiler more ability to optimize. */ INLINE void *upb_inttable_lookup(struct upb_inttable *t, uint32_t key, uint32_t entry_size) { - uint32_t hash = upb_inttable_hash(t, key); - while(1) { - struct upb_inttable_entry *e = - (struct upb_inttable_entry*)(char*)t->t.entries + hash*entry_size; - if(e->key == 0) return NULL; - else if(e->key == key) return e; - hash = e->next; - } + uint32_t bucket = upb_inttable_bucket(t, key); + struct upb_inttable_entry *e; + do { + e = UPB_INDEX(t->t.entries, bucket-1, entry_size); + if(e->key == key) return e; + } while((bucket = e->next) != UPB_END_OF_CHAIN); + return NULL; /* Not found. */ } void *upb_strtable_lookup(struct upb_strtable *t, struct upb_string *key); -- cgit v1.2.3