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 (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 | |