Python code coverage for Modules/hashtable.c

#	count	content
1	n/a	/* The implementation of the hash table (_Py_hashtable_t) is based on the
2	n/a	cfuhash project:
3	n/a	http://sourceforge.net/projects/libcfu/
4	n/a
5	n/a	Copyright of cfuhash:
6	n/a	----------------------------------
7	n/a	Creation date: 2005-06-24 21:22:40
8	n/a	Authors: Don
9	n/a	Change log:
10	n/a
11	n/a	Copyright (c) 2005 Don Owens
12	n/a	All rights reserved.
13	n/a
14	n/a	This code is released under the BSD license:
15	n/a
16	n/a	Redistribution and use in source and binary forms, with or without
17	n/a	modification, are permitted provided that the following conditions
18	n/a	are met:
19	n/a
20	n/a	* Redistributions of source code must retain the above copyright
21	n/a	notice, this list of conditions and the following disclaimer.
22	n/a
23	n/a	* Redistributions in binary form must reproduce the above
24	n/a	copyright notice, this list of conditions and the following
25	n/a	disclaimer in the documentation and/or other materials provided
26	n/a	with the distribution.
27	n/a
28	n/a	* Neither the name of the author nor the names of its
29	n/a	contributors may be used to endorse or promote products derived
30	n/a	from this software without specific prior written permission.
31	n/a
32	n/a	THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
33	n/a	"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
34	n/a	LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
35	n/a	FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
36	n/a	COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
37	n/a	INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
38	n/a	(INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
39	n/a	SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
40	n/a	HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
41	n/a	STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
42	n/a	ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
43	n/a	OF THE POSSIBILITY OF SUCH DAMAGE.
44	n/a	----------------------------------
45	n/a	*/
46	n/a
47	n/a	#include "Python.h"
48	n/a	#include "hashtable.h"
49	n/a
50	n/a	#define HASHTABLE_MIN_SIZE 16
51	n/a	#define HASHTABLE_HIGH 0.50
52	n/a	#define HASHTABLE_LOW 0.10
53	n/a	#define HASHTABLE_REHASH_FACTOR 2.0 / (HASHTABLE_LOW + HASHTABLE_HIGH)
54	n/a
55	n/a	#define BUCKETS_HEAD(SLIST) \
56	n/a	((_Py_hashtable_entry_t *)_Py_SLIST_HEAD(&(SLIST)))
57	n/a	#define TABLE_HEAD(HT, BUCKET) \
58	n/a	((_Py_hashtable_entry_t *)_Py_SLIST_HEAD(&(HT)->buckets[BUCKET]))
59	n/a	#define ENTRY_NEXT(ENTRY) \
60	n/a	((_Py_hashtable_entry_t *)_Py_SLIST_ITEM_NEXT(ENTRY))
61	n/a	#define HASHTABLE_ITEM_SIZE(HT) \
62	n/a	(sizeof(_Py_hashtable_entry_t) + (HT)->key_size + (HT)->data_size)
63	n/a
64	n/a	#define ENTRY_READ_PDATA(TABLE, ENTRY, DATA_SIZE, PDATA) \
65	n/a	do { \
66	n/a	assert((DATA_SIZE) == (TABLE)->data_size); \
67	n/a	memcpy((PDATA), _Py_HASHTABLE_ENTRY_PDATA(TABLE, (ENTRY)), \
68	n/a	(DATA_SIZE)); \
69	n/a	} while (0)
70	n/a
71	n/a	#define ENTRY_WRITE_PDATA(TABLE, ENTRY, DATA_SIZE, PDATA) \
72	n/a	do { \
73	n/a	assert((DATA_SIZE) == (TABLE)->data_size); \
74	n/a	memcpy((void *)_Py_HASHTABLE_ENTRY_PDATA((TABLE), (ENTRY)), \
75	n/a	(PDATA), (DATA_SIZE)); \
76	n/a	} while (0)
77	n/a
78	n/a	/* Forward declaration */
79	n/a	static void hashtable_rehash(_Py_hashtable_t *ht);
80	n/a
81	n/a	static void
82	n/a	_Py_slist_init(_Py_slist_t *list)
83	n/a	{
84	n/a	list->head = NULL;
85	n/a	}
86	n/a
87	n/a
88	n/a	static void
89	n/a	_Py_slist_prepend(_Py_slist_t list, _Py_slist_item_t item)
90	n/a	{
91	n/a	item->next = list->head;
92	n/a	list->head = item;
93	n/a	}
94	n/a
95	n/a
96	n/a	static void
97	n/a	_Py_slist_remove(_Py_slist_t list, _Py_slist_item_t previous,
98	n/a	_Py_slist_item_t *item)
99	n/a	{
100	n/a	if (previous != NULL)
101	n/a	previous->next = item->next;
102	n/a	else
103	n/a	list->head = item->next;
104	n/a	}
105	n/a
106	n/a
107	n/a	Py_uhash_t
108	n/a	_Py_hashtable_hash_ptr(struct _Py_hashtable_t ht, const void pkey)
109	n/a	{
110	n/a	void *key;
111	n/a
112	n/a	_Py_HASHTABLE_READ_KEY(ht, pkey, key);
113	n/a	return (Py_uhash_t)_Py_HashPointer(key);
114	n/a	}
115	n/a
116	n/a
117	n/a	int
118	n/a	_Py_hashtable_compare_direct(_Py_hashtable_t ht, const void pkey,
119	n/a	const _Py_hashtable_entry_t *entry)
120	n/a	{
121	n/a	const void *pkey2 = _Py_HASHTABLE_ENTRY_PKEY(entry);
122	n/a	return (memcmp(pkey, pkey2, ht->key_size) == 0);
123	n/a	}
124	n/a
125	n/a
126	n/a	/* makes sure the real size of the buckets array is a power of 2 */
127	n/a	static size_t
128	n/a	round_size(size_t s)
129	n/a	{
130	n/a	size_t i;
131	n/a	if (s < HASHTABLE_MIN_SIZE)
132	n/a	return HASHTABLE_MIN_SIZE;
133	n/a	i = 1;
134	n/a	while (i < s)
135	n/a	i <<= 1;
136	n/a	return i;
137	n/a	}
138	n/a
139	n/a
140	n/a	_Py_hashtable_t *
141	n/a	_Py_hashtable_new_full(size_t key_size, size_t data_size,
142	n/a	size_t init_size,
143	n/a	_Py_hashtable_hash_func hash_func,
144	n/a	_Py_hashtable_compare_func compare_func,
145	n/a	_Py_hashtable_allocator_t *allocator)
146	n/a	{
147	n/a	_Py_hashtable_t *ht;
148	n/a	size_t buckets_size;
149	n/a	_Py_hashtable_allocator_t alloc;
150	n/a
151	n/a	if (allocator == NULL) {
152	n/a	alloc.malloc = PyMem_RawMalloc;
153	n/a	alloc.free = PyMem_RawFree;
154	n/a	}
155	n/a	else
156	n/a	alloc = *allocator;
157	n/a
158	n/a	ht = (_Py_hashtable_t *)alloc.malloc(sizeof(_Py_hashtable_t));
159	n/a	if (ht == NULL)
160	n/a	return ht;
161	n/a
162	n/a	ht->num_buckets = round_size(init_size);
163	n/a	ht->entries = 0;
164	n/a	ht->key_size = key_size;
165	n/a	ht->data_size = data_size;
166	n/a
167	n/a	buckets_size = ht->num_buckets * sizeof(ht->buckets[0]);
168	n/a	ht->buckets = alloc.malloc(buckets_size);
169	n/a	if (ht->buckets == NULL) {
170	n/a	alloc.free(ht);
171	n/a	return NULL;
172	n/a	}
173	n/a	memset(ht->buckets, 0, buckets_size);
174	n/a
175	n/a	ht->hash_func = hash_func;
176	n/a	ht->compare_func = compare_func;
177	n/a	ht->alloc = alloc;
178	n/a	return ht;
179	n/a	}
180	n/a
181	n/a
182	n/a	_Py_hashtable_t *
183	n/a	_Py_hashtable_new(size_t key_size, size_t data_size,
184	n/a	_Py_hashtable_hash_func hash_func,
185	n/a	_Py_hashtable_compare_func compare_func)
186	n/a	{
187	n/a	return _Py_hashtable_new_full(key_size, data_size,
188	n/a	HASHTABLE_MIN_SIZE,
189	n/a	hash_func, compare_func,
190	n/a	NULL);
191	n/a	}
192	n/a
193	n/a
194	n/a	size_t
195	n/a	_Py_hashtable_size(_Py_hashtable_t *ht)
196	n/a	{
197	n/a	size_t size;
198	n/a
199	n/a	size = sizeof(_Py_hashtable_t);
200	n/a
201	n/a	/* buckets */
202	n/a	size += ht->num_buckets * sizeof(_Py_hashtable_entry_t *);
203	n/a
204	n/a	/* entries */
205	n/a	size += ht->entries * HASHTABLE_ITEM_SIZE(ht);
206	n/a
207	n/a	return size;
208	n/a	}
209	n/a
210	n/a
211	n/a	#ifdef Py_DEBUG
212	n/a	void
213	n/a	_Py_hashtable_print_stats(_Py_hashtable_t *ht)
214	n/a	{
215	n/a	size_t size;
216	n/a	size_t chain_len, max_chain_len, total_chain_len, nchains;
217	n/a	_Py_hashtable_entry_t *entry;
218	n/a	size_t hv;
219	n/a	double load;
220	n/a
221	n/a	size = _Py_hashtable_size(ht);
222	n/a
223	n/a	load = (double)ht->entries / ht->num_buckets;
224	n/a
225	n/a	max_chain_len = 0;
226	n/a	total_chain_len = 0;
227	n/a	nchains = 0;
228	n/a	for (hv = 0; hv < ht->num_buckets; hv++) {
229	n/a	entry = TABLE_HEAD(ht, hv);
230	n/a	if (entry != NULL) {
231	n/a	chain_len = 0;
232	n/a	for (; entry; entry = ENTRY_NEXT(entry)) {
233	n/a	chain_len++;
234	n/a	}
235	n/a	if (chain_len > max_chain_len)
236	n/a	max_chain_len = chain_len;
237	n/a	total_chain_len += chain_len;
238	n/a	nchains++;
239	n/a	}
240	n/a	}
241	n/a	printf("hash table %p: entries=%"
242	n/a	PY_FORMAT_SIZE_T "u/%" PY_FORMAT_SIZE_T "u (%.0f%%), ",
243	n/a	ht, ht->entries, ht->num_buckets, load * 100.0);
244	n/a	if (nchains)
245	n/a	printf("avg_chain_len=%.1f, ", (double)total_chain_len / nchains);
246	n/a	printf("max_chain_len=%" PY_FORMAT_SIZE_T "u, %" PY_FORMAT_SIZE_T "u kB\n",
247	n/a	max_chain_len, size / 1024);
248	n/a	}
249	n/a	#endif
250	n/a
251	n/a
252	n/a	_Py_hashtable_entry_t *
253	n/a	_Py_hashtable_get_entry(_Py_hashtable_t *ht,
254	n/a	size_t key_size, const void *pkey)
255	n/a	{
256	n/a	Py_uhash_t key_hash;
257	n/a	size_t index;
258	n/a	_Py_hashtable_entry_t *entry;
259	n/a
260	n/a	assert(key_size == ht->key_size);
261	n/a
262	n/a	key_hash = ht->hash_func(ht, pkey);
263	n/a	index = key_hash & (ht->num_buckets - 1);
264	n/a
265	n/a	for (entry = TABLE_HEAD(ht, index); entry != NULL; entry = ENTRY_NEXT(entry)) {
266	n/a	if (entry->key_hash == key_hash && ht->compare_func(ht, pkey, entry))
267	n/a	break;
268	n/a	}
269	n/a
270	n/a	return entry;
271	n/a	}
272	n/a
273	n/a
274	n/a	static int
275	n/a	_Py_hashtable_pop_entry(_Py_hashtable_t ht, size_t key_size, const void pkey,
276	n/a	void *data, size_t data_size)
277	n/a	{
278	n/a	Py_uhash_t key_hash;
279	n/a	size_t index;
280	n/a	_Py_hashtable_entry_t entry, previous;
281	n/a
282	n/a	assert(key_size == ht->key_size);
283	n/a
284	n/a	key_hash = ht->hash_func(ht, pkey);
285	n/a	index = key_hash & (ht->num_buckets - 1);
286	n/a
287	n/a	previous = NULL;
288	n/a	for (entry = TABLE_HEAD(ht, index); entry != NULL; entry = ENTRY_NEXT(entry)) {
289	n/a	if (entry->key_hash == key_hash && ht->compare_func(ht, pkey, entry))
290	n/a	break;
291	n/a	previous = entry;
292	n/a	}
293	n/a
294	n/a	if (entry == NULL)
295	n/a	return 0;
296	n/a
297	n/a	_Py_slist_remove(&ht->buckets[index], (_Py_slist_item_t *)previous,
298	n/a	(_Py_slist_item_t *)entry);
299	n/a	ht->entries--;
300	n/a
301	n/a	if (data != NULL)
302	n/a	ENTRY_READ_PDATA(ht, entry, data_size, data);
303	n/a	ht->alloc.free(entry);
304	n/a
305	n/a	if ((float)ht->entries / (float)ht->num_buckets < HASHTABLE_LOW)
306	n/a	hashtable_rehash(ht);
307	n/a	return 1;
308	n/a	}
309	n/a
310	n/a
311	n/a	int
312	n/a	_Py_hashtable_set(_Py_hashtable_t ht, size_t key_size, const void pkey,
313	n/a	size_t data_size, const void *data)
314	n/a	{
315	n/a	Py_uhash_t key_hash;
316	n/a	size_t index;
317	n/a	_Py_hashtable_entry_t *entry;
318	n/a
319	n/a	assert(key_size == ht->key_size);
320	n/a
321	n/a	assert(data != NULL \|\| data_size == 0);
322	n/a	#ifndef NDEBUG
323	n/a	/* Don't write the assertion on a single line because it is interesting
324	n/a	to know the duplicated entry if the assertion failed. The entry can
325	n/a	be read using a debugger. */
326	n/a	entry = _Py_hashtable_get_entry(ht, key_size, pkey);
327	n/a	assert(entry == NULL);
328	n/a	#endif
329	n/a
330	n/a	key_hash = ht->hash_func(ht, pkey);
331	n/a	index = key_hash & (ht->num_buckets - 1);
332	n/a
333	n/a	entry = ht->alloc.malloc(HASHTABLE_ITEM_SIZE(ht));
334	n/a	if (entry == NULL) {
335	n/a	/* memory allocation failed */
336	n/a	return -1;
337	n/a	}
338	n/a
339	n/a	entry->key_hash = key_hash;
340	n/a	memcpy((void *)_Py_HASHTABLE_ENTRY_PKEY(entry), pkey, ht->key_size);
341	n/a	if (data)
342	n/a	ENTRY_WRITE_PDATA(ht, entry, data_size, data);
343	n/a
344	n/a	_Py_slist_prepend(&ht->buckets[index], (_Py_slist_item_t*)entry);
345	n/a	ht->entries++;
346	n/a
347	n/a	if ((float)ht->entries / (float)ht->num_buckets > HASHTABLE_HIGH)
348	n/a	hashtable_rehash(ht);
349	n/a	return 0;
350	n/a	}
351	n/a
352	n/a
353	n/a	int
354	n/a	_Py_hashtable_get(_Py_hashtable_t ht, size_t key_size,const void pkey,
355	n/a	size_t data_size, void *data)
356	n/a	{
357	n/a	_Py_hashtable_entry_t *entry;
358	n/a
359	n/a	assert(data != NULL);
360	n/a
361	n/a	entry = _Py_hashtable_get_entry(ht, key_size, pkey);
362	n/a	if (entry == NULL)
363	n/a	return 0;
364	n/a	ENTRY_READ_PDATA(ht, entry, data_size, data);
365	n/a	return 1;
366	n/a	}
367	n/a
368	n/a
369	n/a	int
370	n/a	_Py_hashtable_pop(_Py_hashtable_t ht, size_t key_size, const void pkey,
371	n/a	size_t data_size, void *data)
372	n/a	{
373	n/a	assert(data != NULL);
374	n/a	return _Py_hashtable_pop_entry(ht, key_size, pkey, data, data_size);
375	n/a	}
376	n/a
377	n/a
378	n/a	/* Code commented since the function is not needed in Python */
379	n/a	#if 0
380	n/a	void
381	n/a	_Py_hashtable_delete(_Py_hashtable_t ht, size_t key_size, const void pkey)
382	n/a	{
383	n/a	#ifndef NDEBUG
384	n/a	int found = _Py_hashtable_pop_entry(ht, key_size, pkey, NULL, 0);
385	n/a	assert(found);
386	n/a	#else
387	n/a	(void)_Py_hashtable_pop_entry(ht, key_size, pkey, NULL, 0);
388	n/a	#endif
389	n/a	}
390	n/a	#endif
391	n/a
392	n/a
393	n/a	int
394	n/a	_Py_hashtable_foreach(_Py_hashtable_t *ht,
395	n/a	_Py_hashtable_foreach_func func,
396	n/a	void *arg)
397	n/a	{
398	n/a	_Py_hashtable_entry_t *entry;
399	n/a	size_t hv;
400	n/a
401	n/a	for (hv = 0; hv < ht->num_buckets; hv++) {
402	n/a	for (entry = TABLE_HEAD(ht, hv); entry; entry = ENTRY_NEXT(entry)) {
403	n/a	int res = func(ht, entry, arg);
404	n/a	if (res)
405	n/a	return res;
406	n/a	}
407	n/a	}
408	n/a	return 0;
409	n/a	}
410	n/a
411	n/a
412	n/a	static void
413	n/a	hashtable_rehash(_Py_hashtable_t *ht)
414	n/a	{
415	n/a	size_t buckets_size, new_size, bucket;
416	n/a	_Py_slist_t *old_buckets = NULL;
417	n/a	size_t old_num_buckets;
418	n/a
419	n/a	new_size = round_size((size_t)(ht->entries * HASHTABLE_REHASH_FACTOR));
420	n/a	if (new_size == ht->num_buckets)
421	n/a	return;
422	n/a
423	n/a	old_num_buckets = ht->num_buckets;
424	n/a
425	n/a	buckets_size = new_size * sizeof(ht->buckets[0]);
426	n/a	old_buckets = ht->buckets;
427	n/a	ht->buckets = ht->alloc.malloc(buckets_size);
428	n/a	if (ht->buckets == NULL) {
429	n/a	/* cancel rehash on memory allocation failure */
430	n/a	ht->buckets = old_buckets ;
431	n/a	/* memory allocation failed */
432	n/a	return;
433	n/a	}
434	n/a	memset(ht->buckets, 0, buckets_size);
435	n/a
436	n/a	ht->num_buckets = new_size;
437	n/a
438	n/a	for (bucket = 0; bucket < old_num_buckets; bucket++) {
439	n/a	_Py_hashtable_entry_t entry, next;
440	n/a	for (entry = BUCKETS_HEAD(old_buckets[bucket]); entry != NULL; entry = next) {
441	n/a	size_t entry_index;
442	n/a
443	n/a
444	n/a	assert(ht->hash_func(ht, _Py_HASHTABLE_ENTRY_PKEY(entry)) == entry->key_hash);
445	n/a	next = ENTRY_NEXT(entry);
446	n/a	entry_index = entry->key_hash & (new_size - 1);
447	n/a
448	n/a	_Py_slist_prepend(&ht->buckets[entry_index], (_Py_slist_item_t*)entry);
449	n/a	}
450	n/a	}
451	n/a
452	n/a	ht->alloc.free(old_buckets);
453	n/a	}
454	n/a
455	n/a
456	n/a	void
457	n/a	_Py_hashtable_clear(_Py_hashtable_t *ht)
458	n/a	{
459	n/a	_Py_hashtable_entry_t entry, next;
460	n/a	size_t i;
461	n/a
462	n/a	for (i=0; i < ht->num_buckets; i++) {
463	n/a	for (entry = TABLE_HEAD(ht, i); entry != NULL; entry = next) {
464	n/a	next = ENTRY_NEXT(entry);
465	n/a	ht->alloc.free(entry);
466	n/a	}
467	n/a	_Py_slist_init(&ht->buckets[i]);
468	n/a	}
469	n/a	ht->entries = 0;
470	n/a	hashtable_rehash(ht);
471	n/a	}
472	n/a
473	n/a
474	n/a	void
475	n/a	_Py_hashtable_destroy(_Py_hashtable_t *ht)
476	n/a	{
477	n/a	size_t i;
478	n/a
479	n/a	for (i = 0; i < ht->num_buckets; i++) {
480	n/a	_Py_slist_item_t *entry = ht->buckets[i].head;
481	n/a	while (entry) {
482	n/a	_Py_slist_item_t *entry_next = entry->next;
483	n/a	ht->alloc.free(entry);
484	n/a	entry = entry_next;
485	n/a	}
486	n/a	}
487	n/a
488	n/a	ht->alloc.free(ht->buckets);
489	n/a	ht->alloc.free(ht);
490	n/a	}
491	n/a
492	n/a
493	n/a	_Py_hashtable_t *
494	n/a	_Py_hashtable_copy(_Py_hashtable_t *src)
495	n/a	{
496	n/a	const size_t key_size = src->key_size;
497	n/a	const size_t data_size = src->data_size;
498	n/a	_Py_hashtable_t *dst;
499	n/a	_Py_hashtable_entry_t *entry;
500	n/a	size_t bucket;
501	n/a	int err;
502	n/a
503	n/a	dst = _Py_hashtable_new_full(key_size, data_size,
504	n/a	src->num_buckets,
505	n/a	src->hash_func,
506	n/a	src->compare_func,
507	n/a	&src->alloc);
508	n/a	if (dst == NULL)
509	n/a	return NULL;
510	n/a
511	n/a	for (bucket=0; bucket < src->num_buckets; bucket++) {
512	n/a	entry = TABLE_HEAD(src, bucket);
513	n/a	for (; entry; entry = ENTRY_NEXT(entry)) {
514	n/a	const void *pkey = _Py_HASHTABLE_ENTRY_PKEY(entry);
515	n/a	const void *pdata = _Py_HASHTABLE_ENTRY_PDATA(src, entry);
516	n/a	err = _Py_hashtable_set(dst, key_size, pkey, data_size, pdata);
517	n/a	if (err) {
518	n/a	_Py_hashtable_destroy(dst);
519	n/a	return NULL;
520	n/a	}
521	n/a	}
522	n/a	}
523	n/a	return dst;
524	n/a	}