1*1fb62fb0SOlivier Houchard /* 2*1fb62fb0SOlivier Houchard * Copyright 2012-2015 Samy Al Bahra. 3*1fb62fb0SOlivier Houchard * All rights reserved. 4*1fb62fb0SOlivier Houchard * 5*1fb62fb0SOlivier Houchard * Redistribution and use in source and binary forms, with or without 6*1fb62fb0SOlivier Houchard * modification, are permitted provided that the following conditions 7*1fb62fb0SOlivier Houchard * are met: 8*1fb62fb0SOlivier Houchard * 1. Redistributions of source code must retain the above copyright 9*1fb62fb0SOlivier Houchard * notice, this list of conditions and the following disclaimer. 10*1fb62fb0SOlivier Houchard * 2. Redistributions in binary form must reproduce the above copyright 11*1fb62fb0SOlivier Houchard * notice, this list of conditions and the following disclaimer in the 12*1fb62fb0SOlivier Houchard * documentation and/or other materials provided with the distribution. 13*1fb62fb0SOlivier Houchard * 14*1fb62fb0SOlivier Houchard * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 15*1fb62fb0SOlivier Houchard * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 16*1fb62fb0SOlivier Houchard * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 17*1fb62fb0SOlivier Houchard * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 18*1fb62fb0SOlivier Houchard * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 19*1fb62fb0SOlivier Houchard * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 20*1fb62fb0SOlivier Houchard * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 21*1fb62fb0SOlivier Houchard * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 22*1fb62fb0SOlivier Houchard * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 23*1fb62fb0SOlivier Houchard * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 24*1fb62fb0SOlivier Houchard * SUCH DAMAGE. 25*1fb62fb0SOlivier Houchard */ 26*1fb62fb0SOlivier Houchard 27*1fb62fb0SOlivier Houchard #ifndef CK_RHS_H 28*1fb62fb0SOlivier Houchard #define CK_RHS_H 29*1fb62fb0SOlivier Houchard 30*1fb62fb0SOlivier Houchard #include <ck_cc.h> 31*1fb62fb0SOlivier Houchard #include <ck_malloc.h> 32*1fb62fb0SOlivier Houchard #include <ck_md.h> 33*1fb62fb0SOlivier Houchard #include <ck_pr.h> 34*1fb62fb0SOlivier Houchard #include <ck_stdint.h> 35*1fb62fb0SOlivier Houchard #include <ck_stdbool.h> 36*1fb62fb0SOlivier Houchard #include <ck_stddef.h> 37*1fb62fb0SOlivier Houchard 38*1fb62fb0SOlivier Houchard /* 39*1fb62fb0SOlivier Houchard * Indicates a single-writer many-reader workload. Mutually 40*1fb62fb0SOlivier Houchard * exclusive with CK_RHS_MODE_MPMC 41*1fb62fb0SOlivier Houchard */ 42*1fb62fb0SOlivier Houchard #define CK_RHS_MODE_SPMC 1 43*1fb62fb0SOlivier Houchard 44*1fb62fb0SOlivier Houchard /* 45*1fb62fb0SOlivier Houchard * Indicates that values to be stored are not pointers but 46*1fb62fb0SOlivier Houchard * values. Allows for full precision. Mutually exclusive 47*1fb62fb0SOlivier Houchard * with CK_RHS_MODE_OBJECT. 48*1fb62fb0SOlivier Houchard */ 49*1fb62fb0SOlivier Houchard #define CK_RHS_MODE_DIRECT 2 50*1fb62fb0SOlivier Houchard 51*1fb62fb0SOlivier Houchard /* 52*1fb62fb0SOlivier Houchard * Indicates that the values to be stored are pointers. 53*1fb62fb0SOlivier Houchard * Allows for space optimizations in the presence of pointer 54*1fb62fb0SOlivier Houchard * packing. Mutually exclusive with CK_RHS_MODE_DIRECT. 55*1fb62fb0SOlivier Houchard */ 56*1fb62fb0SOlivier Houchard #define CK_RHS_MODE_OBJECT 8 57*1fb62fb0SOlivier Houchard 58*1fb62fb0SOlivier Houchard /* 59*1fb62fb0SOlivier Houchard * Indicated that the load is read-mostly, so get should be optimized 60*1fb62fb0SOlivier Houchard * over put and delete 61*1fb62fb0SOlivier Houchard */ 62*1fb62fb0SOlivier Houchard #define CK_RHS_MODE_READ_MOSTLY 16 63*1fb62fb0SOlivier Houchard 64*1fb62fb0SOlivier Houchard /* Currently unsupported. */ 65*1fb62fb0SOlivier Houchard #define CK_RHS_MODE_MPMC (void) 66*1fb62fb0SOlivier Houchard 67*1fb62fb0SOlivier Houchard /* 68*1fb62fb0SOlivier Houchard * Hash callback function. 69*1fb62fb0SOlivier Houchard */ 70*1fb62fb0SOlivier Houchard typedef unsigned long ck_rhs_hash_cb_t(const void *, unsigned long); 71*1fb62fb0SOlivier Houchard 72*1fb62fb0SOlivier Houchard /* 73*1fb62fb0SOlivier Houchard * Returns pointer to object if objects are equivalent. 74*1fb62fb0SOlivier Houchard */ 75*1fb62fb0SOlivier Houchard typedef bool ck_rhs_compare_cb_t(const void *, const void *); 76*1fb62fb0SOlivier Houchard 77*1fb62fb0SOlivier Houchard #if defined(CK_MD_POINTER_PACK_ENABLE) && defined(CK_MD_VMA_BITS) 78*1fb62fb0SOlivier Houchard #define CK_RHS_PP 79*1fb62fb0SOlivier Houchard #define CK_RHS_KEY_MASK ((1U << ((sizeof(void *) * 8) - CK_MD_VMA_BITS)) - 1) 80*1fb62fb0SOlivier Houchard #endif 81*1fb62fb0SOlivier Houchard 82*1fb62fb0SOlivier Houchard struct ck_rhs_map; 83*1fb62fb0SOlivier Houchard struct ck_rhs { 84*1fb62fb0SOlivier Houchard struct ck_malloc *m; 85*1fb62fb0SOlivier Houchard struct ck_rhs_map *map; 86*1fb62fb0SOlivier Houchard unsigned int mode; 87*1fb62fb0SOlivier Houchard unsigned int load_factor; 88*1fb62fb0SOlivier Houchard unsigned long seed; 89*1fb62fb0SOlivier Houchard ck_rhs_hash_cb_t *hf; 90*1fb62fb0SOlivier Houchard ck_rhs_compare_cb_t *compare; 91*1fb62fb0SOlivier Houchard }; 92*1fb62fb0SOlivier Houchard typedef struct ck_rhs ck_rhs_t; 93*1fb62fb0SOlivier Houchard 94*1fb62fb0SOlivier Houchard struct ck_rhs_stat { 95*1fb62fb0SOlivier Houchard unsigned long n_entries; 96*1fb62fb0SOlivier Houchard unsigned int probe_maximum; 97*1fb62fb0SOlivier Houchard }; 98*1fb62fb0SOlivier Houchard 99*1fb62fb0SOlivier Houchard struct ck_rhs_iterator { 100*1fb62fb0SOlivier Houchard void **cursor; 101*1fb62fb0SOlivier Houchard unsigned long offset; 102*1fb62fb0SOlivier Houchard }; 103*1fb62fb0SOlivier Houchard typedef struct ck_rhs_iterator ck_rhs_iterator_t; 104*1fb62fb0SOlivier Houchard 105*1fb62fb0SOlivier Houchard #define CK_RHS_ITERATOR_INITIALIZER { NULL, 0 } 106*1fb62fb0SOlivier Houchard 107*1fb62fb0SOlivier Houchard /* Convenience wrapper to table hash function. */ 108*1fb62fb0SOlivier Houchard #define CK_RHS_HASH(T, F, K) F((K), (T)->seed) 109*1fb62fb0SOlivier Houchard 110*1fb62fb0SOlivier Houchard typedef void *ck_rhs_apply_fn_t(void *, void *); 111*1fb62fb0SOlivier Houchard bool ck_rhs_apply(ck_rhs_t *, unsigned long, const void *, ck_rhs_apply_fn_t *, void *); 112*1fb62fb0SOlivier Houchard void ck_rhs_iterator_init(ck_rhs_iterator_t *); 113*1fb62fb0SOlivier Houchard bool ck_rhs_next(ck_rhs_t *, ck_rhs_iterator_t *, void **); 114*1fb62fb0SOlivier Houchard bool ck_rhs_move(ck_rhs_t *, ck_rhs_t *, ck_rhs_hash_cb_t *, 115*1fb62fb0SOlivier Houchard ck_rhs_compare_cb_t *, struct ck_malloc *); 116*1fb62fb0SOlivier Houchard bool ck_rhs_init(ck_rhs_t *, unsigned int, ck_rhs_hash_cb_t *, 117*1fb62fb0SOlivier Houchard ck_rhs_compare_cb_t *, struct ck_malloc *, unsigned long, unsigned long); 118*1fb62fb0SOlivier Houchard void ck_rhs_destroy(ck_rhs_t *); 119*1fb62fb0SOlivier Houchard void *ck_rhs_get(ck_rhs_t *, unsigned long, const void *); 120*1fb62fb0SOlivier Houchard bool ck_rhs_put(ck_rhs_t *, unsigned long, const void *); 121*1fb62fb0SOlivier Houchard bool ck_rhs_put_unique(ck_rhs_t *, unsigned long, const void *); 122*1fb62fb0SOlivier Houchard bool ck_rhs_set(ck_rhs_t *, unsigned long, const void *, void **); 123*1fb62fb0SOlivier Houchard bool ck_rhs_fas(ck_rhs_t *, unsigned long, const void *, void **); 124*1fb62fb0SOlivier Houchard void *ck_rhs_remove(ck_rhs_t *, unsigned long, const void *); 125*1fb62fb0SOlivier Houchard bool ck_rhs_grow(ck_rhs_t *, unsigned long); 126*1fb62fb0SOlivier Houchard bool ck_rhs_rebuild(ck_rhs_t *); 127*1fb62fb0SOlivier Houchard bool ck_rhs_gc(ck_rhs_t *); 128*1fb62fb0SOlivier Houchard unsigned long ck_rhs_count(ck_rhs_t *); 129*1fb62fb0SOlivier Houchard bool ck_rhs_reset(ck_rhs_t *); 130*1fb62fb0SOlivier Houchard bool ck_rhs_reset_size(ck_rhs_t *, unsigned long); 131*1fb62fb0SOlivier Houchard void ck_rhs_stat(ck_rhs_t *, struct ck_rhs_stat *); 132*1fb62fb0SOlivier Houchard bool ck_rhs_set_load_factor(ck_rhs_t *, unsigned int); 133*1fb62fb0SOlivier Houchard 134*1fb62fb0SOlivier Houchard #endif /* CK_RHS_H */ 135