code.delx.au - pulseaudio/blob - src/hashset.c

   1 #include <stdlib.h>
   2 #include <assert.h>
   3 #include <string.h>
   4
   5 #include "hashset.h"
   6 #include "idxset.h"
   7
   8 struct hashset_entry {
   9     struct hashset_entry *next, *previous, *bucket_next, *bucket_previous;
  10     unsigned hash;
  11     const void *key;
  12     void *value;
  13 };
  14
  15 struct hashset {
  16     unsigned size;
  17     struct hashset_entry **data;
  18     struct hashset_entry *first_entry;
  19
  20     unsigned n_entries;
  21     unsigned (*hash_func) (const void *p);
  22     int (*compare_func) (const void*a, const void*b);
  23 };
  24
  25 struct hashset *hashset_new(unsigned (*hash_func) (const void *p), int (*compare_func) (const void*a, const void*b)) {
  26     struct hashset *h;
  27     h = malloc(sizeof(struct hashset));
  28     assert(h);
  29     h->data = malloc(sizeof(struct hashset_entry*)*(h->size = 1023));
  30     assert(h->data);
  31     memset(h->data, 0, sizeof(struct hashset_entry*)*(h->size = 1023));
  32     h->first_entry = NULL;
  33     h->n_entries = 0;
  34     h->hash_func = hash_func ? hash_func : idxset_trivial_hash_func;
  35     h->compare_func = compare_func ? compare_func : idxset_trivial_compare_func;
  36     return h;
  37 }
  38
  39 static void remove(struct hashset *h, struct hashset_entry *e) {
  40     assert(e);
  41
  42     if (e->next)
  43         e->next->previous = e->previous;
  44     if (e->previous)
  45         e->previous->next = e->next;
  46     else
  47         h->first_entry = e->next;
  48
  49     if (e->bucket_next)
  50         e->bucket_next->bucket_previous = e->bucket_previous;
  51     if (e->bucket_previous)
  52         e->bucket_previous->bucket_next = e->bucket_next;
  53     else
  54         h->data[e->hash] = e->bucket_next;
  55
  56     free(e);
  57     h->n_entries--;
  58 }
  59
  60 void hashset_free(struct hashset*h, void (*free_func)(void *p, void *userdata), void *userdata) {
  61     assert(h);
  62
  63     while (h->first_entry) {
  64         if (free_func)
  65             free_func(h->first_entry->value, userdata);
  66         remove(h, h->first_entry);
  67     }
  68
  69     free(h->data);
  70     free(h);
  71 }
  72
  73 static struct hashset_entry *get(struct hashset *h, unsigned hash, const void *key) {
  74     struct hashset_entry *e;
  75
  76     for (e = h->data[hash]; e; e = e->bucket_next)
  77         if (h->compare_func(e->key, key) == 0)
  78             return e;
  79
  80     return NULL;
  81 }
  82
  83 int hashset_put(struct hashset *h, const void *key, void *value) {
  84     struct hashset_entry *e;
  85     unsigned hash;
  86     assert(h && key);
  87
  88     hash = h->hash_func(key) % h->size;
  89
  90     if ((e = get(h, hash, key)))
  91         return -1;
  92
  93     e = malloc(sizeof(struct hashset_entry));
  94     assert(e);
  95
  96     e->hash = hash;
  97     e->key = key;
  98     e->value = value;
  99
 100     e->previous = NULL;
 101     e->next = h->first_entry;
 102     if (h->first_entry)
 103         h->first_entry->previous = e;
 104     h->first_entry = e;
 105
 106     e->bucket_previous = NULL;
 107     e->bucket_next = h->data[hash];
 108     if (h->data[hash])
 109         h->data[hash]->bucket_previous = e;
 110     h->data[hash] = e;
 111
 112     h->n_entries ++;
 113     return 0;
 114 }
 115
 116 void* hashset_get(struct hashset *h, const void *key) {
 117     unsigned hash;
 118     struct hashset_entry *e;
 119     assert(h && key);
 120
 121     hash = h->hash_func(key) % h->size;
 122
 123     if (!(e = get(h, hash, key)))
 124         return NULL;
 125
 126     return e->value;
 127 }
 128
 129 int hashset_remove(struct hashset *h, const void *key) {
 130     struct hashset_entry *e;
 131     unsigned hash;
 132     assert(h && key);
 133
 134     hash = h->hash_func(key) % h->size;
 135
 136     if (!(e = get(h, hash, key)))
 137         return 1;
 138
 139     remove(h, e);
 140     return 0;
 141 }
 142
 143 unsigned hashset_ncontents(struct hashset *h) {
 144     return h->n_entries;
 145 }