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
33SYSCTL_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 */
54struct 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
63struct cuckoo_hashtable;
64
65typedef int (*cuckoo_obj_cmp_func)(struct cuckoo_node *node, void *key);
66typedef uint32_t (*cuckoo_obj_refcount_func)(struct cuckoo_node *);
67typedef void (*cuckoo_obj_retain_func)(struct cuckoo_node *);
68typedef void (*cuckoo_obj_release_func)(struct cuckoo_node *);
69
70struct 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
79struct cuckoo_hashtable * cuckoo_hashtable_create(
80 struct cuckoo_hashtable_params *p);
81void cuckoo_hashtable_free(struct cuckoo_hashtable *ht);
82
83size_t cuckoo_hashtable_entries(struct cuckoo_hashtable *h);
84size_t cuckoo_hashtable_capacity(struct cuckoo_hashtable *h);
85uint32_t cuckoo_hashtable_load_factor(struct cuckoo_hashtable *h);
86size_t cuckoo_hashtable_memory_footprint(struct cuckoo_hashtable *h);
87void cuckoo_hashtable_try_shrink(struct cuckoo_hashtable *h);
88
89int cuckoo_hashtable_add_with_hash(struct cuckoo_hashtable *h, struct cuckoo_node *node,
90 uint32_t key);
91int cuckoo_hashtable_del(struct cuckoo_hashtable *h, struct cuckoo_node *node,
92 uint32_t key);
93struct 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 */
100void cuckoo_hashtable_foreach(struct cuckoo_hashtable *ht,
101 void (^handler)(struct cuckoo_node *node, uint32_t hv));
102
103#if (DEVELOPMENT || DEBUG)
104void cht_test_init(void);
105void cht_test_fini(void);
106int cuckoo_hashtable_health_check(struct cuckoo_hashtable *h);
107void 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