1 /* 2 * Copyright (c) 2018 Apple Inc. All rights reserved. 3 * 4 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@ 5 * 6 * This file contains Original Code and/or Modifications of Original Code 7 * as defined in and that are subject to the Apple Public Source License 8 * Version 2.0 (the 'License'). You may not use this file except in 9 * compliance with the License. The rights granted to you under the License 10 * may not be used to create, or enable the creation or redistribution of, 11 * unlawful or unlicensed copies of an Apple operating system, or to 12 * circumvent, violate, or enable the circumvention or violation of, any 13 * terms of an Apple operating system software license agreement. 14 * 15 * Please obtain a copy of the License at 16 * http://www.opensource.apple.com/apsl/ and read it before using this file. 17 * 18 * The Original Code and all software distributed under the License are 19 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER 20 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, 21 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, 22 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. 23 * Please see the License for the specific language governing rights and 24 * limitations under the License. 25 * 26 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@ 27 */ 28 #ifndef _CUCKOO_HASHTABLE_H_ 29 #define _CUCKOO_HASHTABLE_H_ 30 31 #ifdef BSD_KERNEL_PRIVATE 32 33 SYSCTL_DECL(_kern_skywalk_libcuckoo); 34 35 /* 36 * Cuckoo Hash Table 37 * 38 * Cuckoo_hashtable is resizable, multi-reader/multi-write thread safe. 39 */ 40 #define CUCKOO_HASHTABLE_ENTRIES_MAX (1<<24) 41 42 /* 43 * Cuckoo_node is embedded in the object associated by cuckoo_hashtable, 44 * so cuckoo_hashtable doesn't need to store key/value pair. This is designed 45 * due to the fact that typical user of a hashtable would anyway have the key 46 * stored elsewhere (most often in the looked-up object). 47 * 48 * The cuckoo_hashtabl_node forms a singly linked list of objects that have 49 * exactly the same hash value (not just hash bucket collision). This is the 50 * result of not storing full length key in the table. So the caller has to 51 * traverse the list to add or find the correct object. 52 * 53 */ 54 struct cuckoo_node { 55 struct cuckoo_node *next; 56 }; 57 58 #ifndef container_of 59 #define container_of(ptr, type, member) \ 60 ((type*)(((uintptr_t)ptr) - offsetof(type, member))) 61 #endif 62 63 struct cuckoo_hashtable; 64 65 typedef int (*cuckoo_obj_cmp_func)(struct cuckoo_node *node, void *key); 66 typedef uint32_t (*cuckoo_obj_refcount_func)(struct cuckoo_node *); 67 typedef void (*cuckoo_obj_retain_func)(struct cuckoo_node *); 68 typedef void (*cuckoo_obj_release_func)(struct cuckoo_node *); 69 70 struct cuckoo_hashtable_params { 71 size_t cht_capacity; 72 cuckoo_obj_cmp_func cht_obj_cmp; 73 cuckoo_obj_retain_func cht_obj_retain; 74 cuckoo_obj_release_func cht_obj_release; 75 }; 76 77 __BEGIN_DECLS 78 79 struct cuckoo_hashtable * cuckoo_hashtable_create( 80 struct cuckoo_hashtable_params *p); 81 void cuckoo_hashtable_free(struct cuckoo_hashtable *ht); 82 83 size_t cuckoo_hashtable_entries(struct cuckoo_hashtable *h); 84 size_t cuckoo_hashtable_capacity(struct cuckoo_hashtable *h); 85 uint32_t cuckoo_hashtable_load_factor(struct cuckoo_hashtable *h); 86 size_t cuckoo_hashtable_memory_footprint(struct cuckoo_hashtable *h); 87 void cuckoo_hashtable_try_shrink(struct cuckoo_hashtable *h); 88 89 int cuckoo_hashtable_add_with_hash(struct cuckoo_hashtable *h, struct cuckoo_node *node, 90 uint32_t key); 91 int cuckoo_hashtable_del(struct cuckoo_hashtable *h, struct cuckoo_node *node, 92 uint32_t key); 93 struct cuckoo_node *cuckoo_hashtable_find_with_hash(struct cuckoo_hashtable *h, 94 void *key, uint32_t hv); 95 96 /* 97 * There is no guarantee that keys concurrently operated would be returned by 98 * walk function. But walk function won't return invalid key/node pairs. 99 */ 100 void cuckoo_hashtable_foreach(struct cuckoo_hashtable *ht, 101 void (^handler)(struct cuckoo_node *node, uint32_t hv)); 102 103 #if (DEVELOPMENT || DEBUG) 104 void cht_test_init(void); 105 void cht_test_fini(void); 106 int cuckoo_hashtable_health_check(struct cuckoo_hashtable *h); 107 void cuckoo_hashtable_dump(struct cuckoo_hashtable *h); 108 #endif /* !DEVELOPMENT && !DEBUG */ 109 110 __END_DECLS 111 #endif /* BSD_KERNEL_PRIVATE */ 112 #endif /* !_CUCKOO_HASHTABLE_H_ */ 113