6 #include <arch_atomic.h>
9 #include <urcu-defer.h>
12 #define HASH_SIZE 4096
14 typedef unsigned long (*ht_hash_fct
)(void *key
);
19 struct rcu_ht_node
*next
;
25 struct rcu_ht_node
*tbl
[HASH_SIZE
];
27 void (*free_fct
)(void *data
); /* fct to free data */
30 struct rcu_ht
*ht_new(ht_hash_fct hash_fct
, void (*free_fct
)(void *data
));
32 void ht_delete_all(struct rcu_ht
*ht
);
34 int ht_destroy(struct rcu_ht
*ht
);
36 void *ht_lookup(struct rcu_ht
*ht
, void *key
);
38 int ht_add(struct rcu_ht
*ht
, void *key
, void *data
);
40 int ht_delete(struct rcu_ht
*ht
, void *key
);
42 void *ht_steal(struct rcu_ht
*ht
, void *key
);
47 static unsigned long stupid_hash(void *key
)
49 return (unsigned long)key
% HASH_SIZE
;
52 struct rcu_ht
*ht_new(ht_hash_fct hash_fct
, void (*free_fct
)(void *data
))
56 ht
= calloc(1, sizeof(struct rcu_ht
));
57 ht
->hash_fct
= hash_fct
;
58 ht
->free_fct
= free_fct
;
61 /* delete all elements */
62 void ht_delete_all(struct rcu_ht
*ht
)
65 struct rcu_ht_node
**prev
, *node
;
67 for (i
= 0; i
< HASH_SIZE
; i
++) {
71 node
= rcu_dereference(*prev
);
73 * Cut the head, therefore whole bucket will be unused
74 * after GP. (except for concurrent additions)
76 rcu_assign_pointer(prev
, NULL
);
83 call_rcu(ht
->free_fct
, node
->data
);
85 node
= rcu_dereference(*prev
);
92 * Should only be called when no more concurrent readers nor writers can
93 * possibly access the table.
95 int ht_destroy(struct rcu_ht
*ht
)
101 void *ht_lookup(struct rcu_ht
*ht
, void *key
)
104 struct rcu_ht_node
*node
;
107 hash
= ht
->hash_fct(key
);
110 node
= rcu_dereference(ht
->tbl
[hash
]);
116 if (node
->key
== key
) {
120 node
= rcu_dereference(node
->next
);
126 * Will re-try until either:
127 * - The key is already there (-EEXIST)
128 * - We successfully add the key at the head of a table bucket.
130 int ht_add(struct rcu_ht
*ht
, void *key
, void *data
)
132 struct rcu_ht_node
*node
, *old_head
, *new_head
;
136 new_head
= calloc(1, sizeof(struct rcu_ht_node
));
138 new_head
->data
= data
;
139 hash
= ht
->hash_fct(key
);
141 /* here comes the fun and tricky part.
142 * Add at the beginning with a cmpxchg.
143 * Hold a read lock between the moment the first element is read
144 * and the nodes traversal (to find duplicates). This ensures
145 * the head pointer has not been reclaimed when cmpxchg is done.
146 * Always adding at the head ensures that we would have to
147 * re-try if a new item has been added concurrently. So we ensure that
148 * we never add duplicates. */
152 old_head
= node
= rcu_dereference(ht
->tbl
[hash
]);
157 if (node
->key
== key
) {
161 node
= rcu_dereference(node
->next
);
163 if (rcu_cmpxchg_pointer(&ht
->tbl
[hash
], old_head
, new_head
) != old_head
)
170 /* restart loop, release and re-take the read lock to be kind to GP */
177 * Restart until we successfully remove the entry, or no entry is left
178 * ((void *)(unsigned long)-ENOENT).
180 struct rcu_ht_node
*ht_steal(struct rcu_ht
*ht
, void *key
);
182 struct rcu_ht_node
**prev
, *node
;
185 hash
= ht
->hash_fct(key
);
190 prev
= &ht
->tbl
[hash
];
191 node
= rcu_dereference(*prev
);
194 node
= (void *)(unsigned long)-ENOENT
;
197 if (node
->key
== key
) {
201 node
= rcu_dereference(*prev
);
203 /* Found it ! pointer to object is in "prev" */
204 if (rcu_cmpxchg_pointer(prev
, node
, node
->next
) != node
)
211 /* restart loop, release and re-take the read lock to be kind to GP */
217 int ht_delete(struct rcu_ht
*ht
, void *key
)
219 struct rcu_ht_node
*node
;
221 node
= ht_steal(ht
, key
);
223 if (free_fct
&& node
->data
)
224 call_rcu(ht
->free_fct
, node
->data
);
225 call_rcu(free
, node
);
This page took 0.045658 seconds and 4 git commands to generate.