include/ck_ht.h

   1 /*
   2  * Copyright 2012-2015 Samy Al Bahra.
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  * 1. Redistributions of source code must retain the above copyright
   9  *    notice, this list of conditions and the following disclaimer.
  10  * 2. Redistributions in binary form must reproduce the above copyright
  11  *    notice, this list of conditions and the following disclaimer in the
  12  *    documentation and/or other materials provided with the distribution.
  13  *
  14  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
  15  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  16  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  17  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  18  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  19  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  20  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  21  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  22  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  23  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  24  * SUCH DAMAGE.
  25  */
  26
  27 #ifndef CK_HT_H
  28 #define CK_HT_H
  29
  30 #include <ck_pr.h>
  31
  32 #define CK_F_HT
  33 #if defined(CK_F_PR_LOAD_64) && defined(CK_F_PR_STORE_64)
  34 #define CK_HT_TYPE uint64_t
  35 #define CK_HT_TYPE_LOAD         ck_pr_load_64
  36 #define CK_HT_TYPE_STORE        ck_pr_store_64
  37 #define CK_HT_TYPE_MAX          UINT64_MAX
  38 #else
  39 #define CK_HT_TYPE uint32_t
  40 #define CK_HT_TYPE_LOAD         ck_pr_load_32
  41 #define CK_HT_TYPE_STORE        ck_pr_store_32
  42 #define CK_HT_TYPE_MAX          UINT32_MAX
  43 #endif
  44
  45
  46 #include <ck_cc.h>
  47 #include <ck_malloc.h>
  48 #include <ck_md.h>
  49 #include <ck_stdint.h>
  50 #include <ck_stdbool.h>
  51 #include <ck_stddef.h>
  52
  53 struct ck_ht_hash {
  54         uint64_t value;
  55 };
  56 typedef struct ck_ht_hash ck_ht_hash_t;
  57
  58 #define CK_HT_MODE_DIRECT       1U
  59 #define CK_HT_MODE_BYTESTRING   2U
  60 #define CK_HT_WORKLOAD_DELETE   4U
  61
  62 #if defined(CK_MD_POINTER_PACK_ENABLE) && defined(CK_MD_VMA_BITS)
  63 #define CK_HT_PP
  64 #define CK_HT_KEY_LENGTH ((sizeof(void *) * 8) - CK_MD_VMA_BITS)
  65 #define CK_HT_KEY_MASK   ((1U << CK_HT_KEY_LENGTH) - 1)
  66 #else
  67 #define CK_HT_KEY_LENGTH 65535U
  68 #endif
  69
  70 struct ck_ht_entry {
  71 #ifdef CK_HT_PP
  72         uintptr_t key;
  73         uintptr_t value CK_CC_PACKED;
  74 } CK_CC_ALIGN(16);
  75 #else
  76         uintptr_t key;
  77         uintptr_t value;
  78         CK_HT_TYPE key_length;
  79         CK_HT_TYPE hash;
  80 } CK_CC_ALIGN(32);
  81 #endif
  82 typedef struct ck_ht_entry ck_ht_entry_t;
  83
  84 /*
  85  * The user is free to define their own stub values.
  86  */
  87 #ifndef CK_HT_KEY_EMPTY
  88 #define CK_HT_KEY_EMPTY         ((uintptr_t)0)
  89 #endif
  90
  91 #ifndef CK_HT_KEY_TOMBSTONE
  92 #define CK_HT_KEY_TOMBSTONE     (~CK_HT_KEY_EMPTY)
  93 #endif
  94
  95 /*
  96  * Hash callback function. First argument is updated to contain a hash value,
  97  * second argument is the key, third argument is key length and final argument
  98  * is the hash table seed value.
  99  */
 100 typedef void ck_ht_hash_cb_t(ck_ht_hash_t *, const void *, size_t, uint64_t);
 101
 102 struct ck_ht_map;
 103 struct ck_ht {
 104         struct ck_malloc *m;
 105         struct ck_ht_map *map;
 106         unsigned int mode;
 107         uint64_t seed;
 108         ck_ht_hash_cb_t *h;
 109 };
 110 typedef struct ck_ht ck_ht_t;
 111
 112 struct ck_ht_stat {
 113         uint64_t probe_maximum;
 114         uint64_t n_entries;
 115 };
 116
 117 struct ck_ht_iterator {
 118         struct ck_ht_entry *current;
 119         uint64_t offset;
 120 };
 121 typedef struct ck_ht_iterator ck_ht_iterator_t;
 122
 123 #define CK_HT_ITERATOR_INITIALIZER { NULL, 0 }
 124
 125 CK_CC_INLINE static void
 126 ck_ht_iterator_init(struct ck_ht_iterator *iterator)
 127 {
 128
 129         iterator->current = NULL;
 130         iterator->offset = 0;
 131         return;
 132 }
 133
 134 CK_CC_INLINE static bool
 135 ck_ht_entry_empty(ck_ht_entry_t *entry)
 136 {
 137
 138         return entry->key == CK_HT_KEY_EMPTY;
 139 }
 140
 141 CK_CC_INLINE static void
 142 ck_ht_entry_key_set_direct(ck_ht_entry_t *entry, uintptr_t key)
 143 {
 144
 145         entry->key = key;
 146         return;
 147 }
 148
 149 CK_CC_INLINE static void
 150 ck_ht_entry_key_set(ck_ht_entry_t *entry, const void *key, uint16_t key_length)
 151 {
 152
 153 #ifdef CK_HT_PP
 154         entry->key = (uintptr_t)key | ((uintptr_t)key_length << CK_MD_VMA_BITS);
 155 #else
 156         entry->key = (uintptr_t)key;
 157         entry->key_length = key_length;
 158 #endif
 159
 160         return;
 161 }
 162
 163 CK_CC_INLINE static void *
 164 ck_ht_entry_key(ck_ht_entry_t *entry)
 165 {
 166
 167 #ifdef CK_HT_PP
 168         return (void *)(entry->key & (((uintptr_t)1 << CK_MD_VMA_BITS) - 1));
 169 #else
 170         return (void *)entry->key;
 171 #endif
 172 }
 173
 174 CK_CC_INLINE static uint16_t
 175 ck_ht_entry_key_length(ck_ht_entry_t *entry)
 176 {
 177
 178 #ifdef CK_HT_PP
 179         return entry->key >> CK_MD_VMA_BITS;
 180 #else
 181         return entry->key_length;
 182 #endif
 183 }
 184
 185 CK_CC_INLINE static void *
 186 ck_ht_entry_value(ck_ht_entry_t *entry)
 187 {
 188
 189 #ifdef CK_HT_PP
 190         return (void *)(entry->value & (((uintptr_t)1 << CK_MD_VMA_BITS) - 1));
 191 #else
 192         return (void *)entry->value;
 193 #endif
 194 }
 195
 196 CK_CC_INLINE static void
 197 ck_ht_entry_set(struct ck_ht_entry *entry,
 198                 ck_ht_hash_t h,
 199                 const void *key,
 200                 uint16_t key_length,
 201                 const void *value)
 202 {
 203
 204 #ifdef CK_HT_PP
 205         entry->key = (uintptr_t)key | ((uintptr_t)key_length << CK_MD_VMA_BITS);
 206         entry->value = (uintptr_t)value | ((uintptr_t)(h.value >> 32) << CK_MD_VMA_BITS);
 207 #else
 208         entry->key = (uintptr_t)key;
 209         entry->value = (uintptr_t)value;
 210         entry->key_length = key_length;
 211         entry->hash = h.value;
 212 #endif
 213
 214         return;
 215 }
 216
 217 CK_CC_INLINE static void
 218 ck_ht_entry_set_direct(struct ck_ht_entry *entry,
 219                        ck_ht_hash_t h,
 220                        uintptr_t key,
 221                        uintptr_t value)
 222 {
 223
 224         entry->key = key;
 225         entry->value = value;
 226
 227 #ifndef CK_HT_PP
 228         entry->hash = h.value;
 229 #else
 230         (void)h;
 231 #endif
 232         return;
 233 }
 234
 235 CK_CC_INLINE static uintptr_t
 236 ck_ht_entry_key_direct(ck_ht_entry_t *entry)
 237 {
 238
 239         return entry->key;
 240 }
 241
 242 CK_CC_INLINE static uintptr_t
 243 ck_ht_entry_value_direct(ck_ht_entry_t *entry)
 244 {
 245
 246         return entry->value;
 247 }
 248
 249 /*
 250  * Iteration must occur without any concurrent mutations on
 251  * the hash table.
 252  */
 253 bool ck_ht_next(ck_ht_t *, ck_ht_iterator_t *, ck_ht_entry_t **entry);
 254
 255 void ck_ht_stat(ck_ht_t *, struct ck_ht_stat *);
 256 void ck_ht_hash(ck_ht_hash_t *, ck_ht_t *, const void *, uint16_t);
 257 void ck_ht_hash_direct(ck_ht_hash_t *, ck_ht_t *, uintptr_t);
 258 bool ck_ht_init(ck_ht_t *, unsigned int, ck_ht_hash_cb_t *,
 259     struct ck_malloc *, CK_HT_TYPE, uint64_t);
 260 void ck_ht_destroy(ck_ht_t *);
 261 bool ck_ht_set_spmc(ck_ht_t *, ck_ht_hash_t, ck_ht_entry_t *);
 262 bool ck_ht_put_spmc(ck_ht_t *, ck_ht_hash_t, ck_ht_entry_t *);
 263 bool ck_ht_get_spmc(ck_ht_t *, ck_ht_hash_t, ck_ht_entry_t *);
 264 bool ck_ht_gc(struct ck_ht *, unsigned long, unsigned long);
 265 bool ck_ht_grow_spmc(ck_ht_t *, CK_HT_TYPE);
 266 bool ck_ht_remove_spmc(ck_ht_t *, ck_ht_hash_t, ck_ht_entry_t *);
 267 bool ck_ht_reset_spmc(ck_ht_t *);
 268 bool ck_ht_reset_size_spmc(ck_ht_t *, CK_HT_TYPE);
 269 CK_HT_TYPE ck_ht_count(ck_ht_t *);
 270
 271 #endif /* CK_HT_H */