1*aa693e99SJason King /*
2*aa693e99SJason King * Copyright 2016 Jakub Klama <jceel@FreeBSD.org>
3*aa693e99SJason King * All rights reserved
4*aa693e99SJason King *
5*aa693e99SJason King * Redistribution and use in source and binary forms, with or without
6*aa693e99SJason King * modification, are permitted providing that the following conditions
7*aa693e99SJason King * are met:
8*aa693e99SJason King * 1. Redistributions of source code must retain the above copyright
9*aa693e99SJason King * notice, this list of conditions and the following disclaimer.
10*aa693e99SJason King * 2. Redistributions in binary form must reproduce the above copyright
11*aa693e99SJason King * notice, this list of conditions and the following disclaimer in the
12*aa693e99SJason King * documentation and/or other materials provided with the distribution.
13*aa693e99SJason King *
14*aa693e99SJason King * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
15*aa693e99SJason King * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
16*aa693e99SJason King * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
17*aa693e99SJason King * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
18*aa693e99SJason King * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
19*aa693e99SJason King * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
20*aa693e99SJason King * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
21*aa693e99SJason King * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
22*aa693e99SJason King * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
23*aa693e99SJason King * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
24*aa693e99SJason King * POSSIBILITY OF SUCH DAMAGE.
25*aa693e99SJason King *
26*aa693e99SJason King */
27*aa693e99SJason King
28*aa693e99SJason King #ifndef LIB9P_HASHTABLE_H
29*aa693e99SJason King #define LIB9P_HASHTABLE_H
30*aa693e99SJason King
31*aa693e99SJason King #include <pthread.h>
32*aa693e99SJason King #include <sys/queue.h>
33*aa693e99SJason King
34*aa693e99SJason King struct ht {
35*aa693e99SJason King struct ht_entry * ht_entries;
36*aa693e99SJason King ssize_t ht_nentries;
37*aa693e99SJason King pthread_rwlock_t ht_rwlock;
38*aa693e99SJason King };
39*aa693e99SJason King
40*aa693e99SJason King struct ht_entry {
41*aa693e99SJason King TAILQ_HEAD(, ht_item) hte_items;
42*aa693e99SJason King };
43*aa693e99SJason King
44*aa693e99SJason King struct ht_item {
45*aa693e99SJason King uint32_t hti_hash;
46*aa693e99SJason King void * hti_data;
47*aa693e99SJason King TAILQ_ENTRY(ht_item) hti_link;
48*aa693e99SJason King };
49*aa693e99SJason King
50*aa693e99SJason King struct ht_iter {
51*aa693e99SJason King struct ht * htit_parent;
52*aa693e99SJason King struct ht_item * htit_curr;
53*aa693e99SJason King struct ht_item * htit_next;
54*aa693e99SJason King ssize_t htit_slot;
55*aa693e99SJason King };
56*aa693e99SJason King
57*aa693e99SJason King #ifdef __clang__
58*aa693e99SJason King #pragma clang diagnostic push
59*aa693e99SJason King #pragma clang diagnostic ignored "-Wthread-safety-analysis"
60*aa693e99SJason King #endif
61*aa693e99SJason King
62*aa693e99SJason King /*
63*aa693e99SJason King * Obtain read-lock on hash table.
64*aa693e99SJason King */
65*aa693e99SJason King static inline int
ht_rdlock(struct ht * h)66*aa693e99SJason King ht_rdlock(struct ht *h)
67*aa693e99SJason King {
68*aa693e99SJason King
69*aa693e99SJason King return (pthread_rwlock_rdlock(&h->ht_rwlock));
70*aa693e99SJason King }
71*aa693e99SJason King
72*aa693e99SJason King /*
73*aa693e99SJason King * Obtain write-lock on hash table.
74*aa693e99SJason King */
75*aa693e99SJason King static inline int
ht_wrlock(struct ht * h)76*aa693e99SJason King ht_wrlock(struct ht *h)
77*aa693e99SJason King {
78*aa693e99SJason King
79*aa693e99SJason King return (pthread_rwlock_wrlock(&h->ht_rwlock));
80*aa693e99SJason King }
81*aa693e99SJason King
82*aa693e99SJason King /*
83*aa693e99SJason King * Release lock on hash table.
84*aa693e99SJason King */
85*aa693e99SJason King static inline int
ht_unlock(struct ht * h)86*aa693e99SJason King ht_unlock(struct ht *h)
87*aa693e99SJason King {
88*aa693e99SJason King
89*aa693e99SJason King return (pthread_rwlock_unlock(&h->ht_rwlock));
90*aa693e99SJason King }
91*aa693e99SJason King
92*aa693e99SJason King #ifdef __clang__
93*aa693e99SJason King #pragma clang diagnostic pop
94*aa693e99SJason King #endif
95*aa693e99SJason King
96*aa693e99SJason King void ht_init(struct ht *h, ssize_t size);
97*aa693e99SJason King void ht_destroy(struct ht *h);
98*aa693e99SJason King void *ht_find(struct ht *h, uint32_t hash);
99*aa693e99SJason King void *ht_find_locked(struct ht *h, uint32_t hash);
100*aa693e99SJason King int ht_add(struct ht *h, uint32_t hash, void *value);
101*aa693e99SJason King int ht_remove(struct ht *h, uint32_t hash);
102*aa693e99SJason King int ht_remove_locked(struct ht *h, uint32_t hash);
103*aa693e99SJason King int ht_remove_at_iter(struct ht_iter *iter);
104*aa693e99SJason King void ht_iter(struct ht *h, struct ht_iter *iter);
105*aa693e99SJason King void *ht_next(struct ht_iter *iter);
106*aa693e99SJason King
107*aa693e99SJason King #endif /* LIB9P_HASHTABLE_H */
108