sys/contrib/ck/include/ck_hs.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_HS_H
  28 #define CK_HS_H
  29
  30 #include <ck_cc.h>
  31 #include <ck_malloc.h>
  32 #include <ck_md.h>
  33 #include <ck_pr.h>
  34 #include <ck_stdint.h>
  35 #include <ck_stdbool.h>
  36 #include <ck_stddef.h>
  37
  38 /*
  39  * Indicates a single-writer many-reader workload. Mutually
  40  * exclusive with CK_HS_MODE_MPMC
  41  */
  42 #define CK_HS_MODE_SPMC         1
  43
  44 /*
  45  * Indicates that values to be stored are not pointers but
  46  * values. Allows for full precision. Mutually exclusive
  47  * with CK_HS_MODE_OBJECT.
  48  */
  49 #define CK_HS_MODE_DIRECT       2
  50
  51 /*
  52  * Indicates that the values to be stored are pointers.
  53  * Allows for space optimizations in the presence of pointer
  54  * packing. Mutually exclusive with CK_HS_MODE_DIRECT.
  55  */
  56 #define CK_HS_MODE_OBJECT       8
  57
  58 /*
  59  * Indicates a delete-heavy workload. This will reduce the
  60  * need for garbage collection at the cost of approximately
  61  * 12% to 20% increased memory usage.
  62  */
  63 #define CK_HS_MODE_DELETE       16
  64
  65 /* Currently unsupported. */
  66 #define CK_HS_MODE_MPMC    (void)
  67
  68 /*
  69  * Hash callback function.
  70  */
  71 typedef unsigned long ck_hs_hash_cb_t(const void *, unsigned long);
  72
  73 /*
  74  * Returns pointer to object if objects are equivalent.
  75  */
  76 typedef bool ck_hs_compare_cb_t(const void *, const void *);
  77
  78 #if defined(CK_MD_POINTER_PACK_ENABLE) && defined(CK_MD_VMA_BITS)
  79 #define CK_HS_PP
  80 #define CK_HS_KEY_MASK ((1U << ((sizeof(void *) * 8) - CK_MD_VMA_BITS)) - 1)
  81 #endif
  82
  83 struct ck_hs_map;
  84 struct ck_hs {
  85         struct ck_malloc *m;
  86         struct ck_hs_map *map;
  87         unsigned int mode;
  88         unsigned long seed;
  89         ck_hs_hash_cb_t *hf;
  90         ck_hs_compare_cb_t *compare;
  91 };
  92 typedef struct ck_hs ck_hs_t;
  93
  94 struct ck_hs_stat {
  95         unsigned long tombstones;
  96         unsigned long n_entries;
  97         unsigned int probe_maximum;
  98 };
  99
 100 struct ck_hs_iterator {
 101         void **cursor;
 102         unsigned long offset;
 103 };
 104 typedef struct ck_hs_iterator ck_hs_iterator_t;
 105
 106 #define CK_HS_ITERATOR_INITIALIZER { NULL, 0 }
 107
 108 /* Convenience wrapper to table hash function. */
 109 #define CK_HS_HASH(T, F, K) F((K), (T)->seed)
 110
 111 typedef void *ck_hs_apply_fn_t(void *, void *);
 112 bool ck_hs_apply(ck_hs_t *, unsigned long, const void *, ck_hs_apply_fn_t *, void *);
 113 void ck_hs_iterator_init(ck_hs_iterator_t *);
 114 bool ck_hs_next(ck_hs_t *, ck_hs_iterator_t *, void **);
 115 bool ck_hs_move(ck_hs_t *, ck_hs_t *, ck_hs_hash_cb_t *,
 116     ck_hs_compare_cb_t *, struct ck_malloc *);
 117 bool ck_hs_init(ck_hs_t *, unsigned int, ck_hs_hash_cb_t *,
 118     ck_hs_compare_cb_t *, struct ck_malloc *, unsigned long, unsigned long);
 119 void ck_hs_destroy(ck_hs_t *);
 120 void *ck_hs_get(ck_hs_t *, unsigned long, const void *);
 121 bool ck_hs_put(ck_hs_t *, unsigned long, const void *);
 122 bool ck_hs_put_unique(ck_hs_t *, unsigned long, const void *);
 123 bool ck_hs_set(ck_hs_t *, unsigned long, const void *, void **);
 124 bool ck_hs_fas(ck_hs_t *, unsigned long, const void *, void **);
 125 void *ck_hs_remove(ck_hs_t *, unsigned long, const void *);
 126 bool ck_hs_grow(ck_hs_t *, unsigned long);
 127 bool ck_hs_rebuild(ck_hs_t *);
 128 bool ck_hs_gc(ck_hs_t *, unsigned long, unsigned long);
 129 unsigned long ck_hs_count(ck_hs_t *);
 130 bool ck_hs_reset(ck_hs_t *);
 131 bool ck_hs_reset_size(ck_hs_t *, unsigned long);
 132 void ck_hs_stat(ck_hs_t *, struct ck_hs_stat *);
 133
 134 #endif /* CK_HS_H */