hashtable.c

   1 /*
   2  * Copyright (C) 2008 Eduard-Gabriel Munteanu
   3  *
   4  * This file is released under GPL version 2.
   5  */
   6
   7 /*
   8  * Simple hashtable for storing pointer-sized keyed data.
   9  */
  10
  11 #include <stdlib.h>
  12 #include <stdint.h>
  13
  14 #include "hashtable.h"
  15
  16 struct ht_table *__ht_create(size_t bits, size_t entry_size, size_t key_offset)
  17 {
  18         struct ht_table *ret;
  19         size_t n_entries = 1 << bits;
  20
  21         ret = malloc(sizeof(struct ht_table));
  22         if (!ret)
  23                 return NULL;
  24         ret->entry = calloc(n_entries, sizeof(struct ht_entry));
  25         ret->bits = bits;
  26         ret->entry_size = entry_size;
  27         ret->key_offset = key_offset;
  28
  29         return ret;
  30 }
  31
  32 void ht_destroy(struct ht_table *table)
  33 {
  34         free(table->entry);
  35         free(table);
  36 }
  37
  38 static inline unsigned long ht_hash(uint64_t key, size_t bits)
  39 {
  40         unsigned long ret = (unsigned long) key;
  41         unsigned long mask = (1 << bits) - 1;
  42
  43         return (ret ^ (ret >> 16)) & mask;
  44 }
  45
  46 static inline uint64_t *ht_get_key_ptr(struct ht_entry *entry,
  47                                        struct ht_table *table)
  48 {
  49         return (uint64_t *) (entry->data + table->key_offset);
  50 }
  51
  52 static inline void ht_set_key(struct ht_entry *entry,
  53                               struct ht_table *table,
  54                               uint64_t key)
  55 {
  56         *ht_get_key_ptr(entry, table) = key;
  57 }
  58
  59 static inline uint64_t ht_get_key(struct ht_entry *entry,
  60                                   struct ht_table *table)
  61 {
  62         return *ht_get_key_ptr(entry, table);
  63 }
  64
  65 struct ht_entry *ht_update_entry(struct ht_table *table, uint64_t key)
  66 {
  67         struct ht_entry *entry;
  68         unsigned long bucket = ht_hash(key, table->bits);
  69
  70         entry = &table->entry[bucket];
  71         if (!entry->data) {
  72                 entry->data = calloc(1, table->entry_size);
  73                 ht_set_key(entry, table, key);
  74                 return entry;
  75         } else {
  76                 while (entry) {
  77                         if (ht_get_key(entry, table) == key)
  78                                 return entry;
  79                         if (!entry->next) {
  80                                 entry->next =
  81                                         calloc(1, sizeof(struct ht_entry));
  82                                 entry->next->data =
  83                                         calloc(1, table->entry_size);
  84                                 ht_set_key(entry->next, table, key);
  85
  86                                 return entry->next;
  87                         }
  88
  89                         entry = entry->next;
  90                 }
  91         }
  92
  93         return NULL;
  94 }
  95
  96 void ht_action(struct ht_table *table, void (*action)(struct ht_entry *, int))
  97 {
  98         unsigned long i;
  99         struct ht_entry *entry, *next_entry;
 100
 101         for (i = 0; i < (1 << table->bits); i++) {
 102                 entry = &table->entry[i];
 103                 if (entry->data) {
 104                         next_entry = entry->next;
 105                         action(entry, 0);
 106                         entry = next_entry;
 107                 } else
 108                         continue;
 109                 while (entry) {
 110                         next_entry = entry->next;
 111                         action(entry, 1);
 112                         entry = next_entry;
 113                 }
 114         }
 115 }
 116
 117 void ht_free_entry(struct ht_entry *entry, int freeable)
 118 {
 119         free(entry->data);
 120         if (freeable)
 121                 free(entry);
 122 }