kitten/kernel/htable.c

   1 /* Copyright (c) 2008, Sandia National Laboratories */
   2
   3 #include <lwk/kernel.h>
   4 #include <lwk/list.h>
   5 #include <lwk/htable.h>
   6 #include <lwk/hash.h>
   7
   8 struct htable {
   9         size_t              tbl_order;
  10         struct hlist_head * tbl;
  11         size_t              obj_key_offset;
  12         size_t              obj_link_offset;
  13         size_t              num_entries;
  14 };
  15
  16 static id_t
  17 obj2key(const struct htable *ht, const void *obj)
  18 {
  19         return *((id_t *)((uintptr_t)obj + ht->obj_key_offset));
  20 }
  21
  22 static struct hlist_node *
  23 obj2node(const struct htable *ht, const void *obj)
  24 {
  25         return (struct hlist_node *)((uintptr_t)obj + ht->obj_link_offset);
  26 }
  27
  28 static void *
  29 node2obj(const struct htable *ht, const struct hlist_node *node)
  30 {
  31         return (void *)((uintptr_t)node - ht->obj_link_offset);
  32 }
  33
  34 static id_t
  35 node2key(const struct htable *ht, const struct hlist_node *node)
  36 {
  37         return obj2key(ht, node2obj(ht, node));
  38 }
  39
  40 static struct hlist_head *
  41 key2head(const struct htable *ht, id_t key)
  42 {
  43         return &ht->tbl[hash_long(key, ht->tbl_order)];
  44 }
  45
  46 static struct hlist_head *
  47 obj2head(const struct htable *ht, const void *obj)
  48 {
  49         return &ht->tbl[hash_long(obj2key(ht, obj), ht->tbl_order)];
  50 }
  51
  52 int
  53 htable_create(size_t tbl_order,
  54               size_t obj_key_offset, size_t obj_link_offset, htable_t *tbl)
  55 {
  56         struct htable *ht;
  57         size_t tbl_size;
  58
  59         if (!(ht = kmem_alloc(sizeof(*ht))))
  60                 return -ENOMEM;
  61
  62         ht->tbl_order = tbl_order;
  63         tbl_size = (1 << tbl_order);
  64
  65         if (!(ht->tbl = kmem_alloc(tbl_size * sizeof(struct hlist_head))))
  66                 return -ENOMEM;
  67
  68         ht->obj_key_offset  = obj_key_offset;
  69         ht->obj_link_offset = obj_link_offset;
  70         ht->num_entries     = 0;
  71
  72         *tbl = ht;
  73         return 0;
  74 }
  75
  76 int
  77 htable_destroy(htable_t tbl)
  78 {
  79         struct htable *ht = tbl;
  80         if (ht->num_entries)
  81                 return -EEXIST;
  82         kmem_free(ht->tbl);
  83         kmem_free(ht);
  84         return 0;
  85 }
  86
  87 int
  88 htable_add(htable_t tbl, void *obj)
  89 {
  90         struct htable *ht = tbl;
  91         hlist_add_head(obj2node(ht, obj), obj2head(ht, obj));
  92         ++ht->num_entries;
  93         return 0;
  94 }
  95
  96 int
  97 htable_del(htable_t tbl, void *obj)
  98 {
  99         struct htable *ht = tbl;
 100         struct hlist_node *node;
 101         hlist_for_each(node, obj2head(ht, obj)) {
 102                 if (obj == node2obj(ht, node)) {
 103                         hlist_del(node);
 104                         --ht->num_entries;
 105                         return 0;
 106                 }
 107         }
 108         return -ENOENT;
 109 }
 110
 111 void *
 112 htable_lookup(htable_t tbl, id_t key)
 113 {
 114         struct htable *ht = tbl;
 115         struct hlist_node *node;
 116         hlist_for_each(node, key2head(ht, key)) {
 117                 if (key == node2key(ht, node))
 118                         return node2obj(ht, node);
 119         }
 120         return NULL;
 121 }