6 #include <arch_atomic.h>
9 #include <urcu-defer.h>
16 struct rcu_ht_node
*next
;
22 struct rcu_ht_node
*tbl
[HASH_SIZE
];
24 void (*free_fct
)(void *data
); /* fct to free data */
27 struct rcu_ht
*ht_new(ht_hash_fct hash_fct
, void (*free_fct
)(void *data
))
31 ht
= calloc(1, sizeof(struct rcu_ht
));
32 ht
->hash_fct
= hash_fct
;
33 ht
->free_fct
= free_fct
;
37 /* delete all elements */
38 void ht_delete_all(struct rcu_ht
*ht
)
41 struct rcu_ht_node
**prev
, *node
;
43 for (i
= 0; i
< HASH_SIZE
; i
++) {
47 node
= rcu_dereference(*prev
);
49 * Cut the head, therefore whole bucket will be unused
50 * after GP. (except for concurrent additions)
52 rcu_assign_pointer(prev
, NULL
);
59 call_rcu(ht
->free_fct
, node
->data
);
61 node
= rcu_dereference(*prev
);
68 * Should only be called when no more concurrent readers nor writers can
69 * possibly access the table.
71 void ht_destroy(struct rcu_ht
*ht
)
77 void *ht_lookup(struct rcu_ht
*ht
, void *key
)
80 struct rcu_ht_node
*node
;
83 hash
= ht
->hash_fct(key
);
86 node
= rcu_dereference(ht
->tbl
[hash
]);
92 if (node
->key
== key
) {
96 node
= rcu_dereference(node
->next
);
104 * Will re-try until either:
105 * - The key is already there (-EEXIST)
106 * - We successfully add the key at the head of a table bucket.
108 int ht_add(struct rcu_ht
*ht
, void *key
, void *data
)
110 struct rcu_ht_node
*node
, *old_head
, *new_head
;
114 new_head
= calloc(1, sizeof(struct rcu_ht_node
));
116 new_head
->data
= data
;
117 hash
= ht
->hash_fct(key
);
119 /* here comes the fun and tricky part.
120 * Add at the beginning with a cmpxchg.
121 * Hold a read lock between the moment the first element is read
122 * and the nodes traversal (to find duplicates). This ensures
123 * the head pointer has not been reclaimed when cmpxchg is done.
124 * Always adding at the head ensures that we would have to
125 * re-try if a new item has been added concurrently. So we ensure that
126 * we never add duplicates. */
130 old_head
= node
= rcu_dereference(ht
->tbl
[hash
]);
135 if (node
->key
== key
) {
139 node
= rcu_dereference(node
->next
);
141 if (rcu_cmpxchg_pointer(&ht
->tbl
[hash
], old_head
, new_head
) != old_head
)
148 /* restart loop, release and re-take the read lock to be kind to GP */
155 * Restart until we successfully remove the entry, or no entry is left
156 * ((void *)(unsigned long)-ENOENT).
158 void *ht_steal(struct rcu_ht
*ht
, void *key
)
160 struct rcu_ht_node
**prev
, *node
;
164 hash
= ht
->hash_fct(key
);
169 prev
= &ht
->tbl
[hash
];
170 node
= rcu_dereference(*prev
);
173 data
= (void *)(unsigned long)-ENOENT
;
176 if (node
->key
== key
) {
180 node
= rcu_dereference(*prev
);
182 /* Found it ! pointer to object is in "prev" */
183 if (rcu_cmpxchg_pointer(prev
, node
, node
->next
) != node
)
189 call_rcu(free
, node
);
193 /* restart loop, release and re-take the read lock to be kind to GP */
199 int ht_delete(struct rcu_ht
*ht
, void *key
)
203 data
= ht_steal(ht
, key
);
205 if (ht
->free_fct
&& data
)
206 call_rcu(ht
->free_fct
, data
);
213 unsigned long stupid_hash(void *key
)
215 return (unsigned long)key
% HASH_SIZE
;
This page took 0.034876 seconds and 5 git commands to generate.