1 #ifdef HAVE_DIX_CONFIG_H
2 #include <dix-config.h>
12 #define INITHASHSIZE 6
13 #define MAXHASHSIZE 11
19 int elements
; /* number of elements inserted */
20 int bucketBits
; /* number of buckets is 1 << bucketBits */
21 struct xorg_list
*buckets
; /* array of bucket list heads */
24 HashCompareFunc compare
;
33 } BucketRec
, *BucketPtr
;
36 ht_create(int keySize
,
39 HashCompareFunc compare
,
44 HashTable ht
= malloc(sizeof(struct HashTableRec
));
50 ht
->keySize
= keySize
;
51 ht
->dataSize
= dataSize
;
53 ht
->compare
= compare
;
55 ht
->bucketBits
= INITHASHSIZE
;
56 numBuckets
= 1 << ht
->bucketBits
;
57 ht
->buckets
= malloc(numBuckets
* sizeof(*ht
->buckets
));
61 for (c
= 0; c
< numBuckets
; ++c
) {
62 xorg_list_init(&ht
->buckets
[c
]);
72 ht_destroy(HashTable ht
)
76 int numBuckets
= 1 << ht
->bucketBits
;
77 for (c
= 0; c
< numBuckets
; ++c
) {
78 xorg_list_for_each_entry_safe(it
, tmp
, &ht
->buckets
[c
], l
) {
79 xorg_list_del(&it
->l
);
87 double_size(HashTable ht
)
89 struct xorg_list
*newBuckets
;
90 int numBuckets
= 1 << ht
->bucketBits
;
91 int newBucketBits
= ht
->bucketBits
+ 1;
92 int newNumBuckets
= 1 << newBucketBits
;
95 newBuckets
= malloc(newNumBuckets
* sizeof(*ht
->buckets
));
97 for (c
= 0; c
< newNumBuckets
; ++c
) {
98 xorg_list_init(&newBuckets
[c
]);
101 for (c
= 0; c
< numBuckets
; ++c
) {
103 xorg_list_for_each_entry_safe(it
, tmp
, &ht
->buckets
[c
], l
) {
104 struct xorg_list
*newBucket
=
105 &newBuckets
[ht
->hash(ht
->cdata
, it
->key
, newBucketBits
)];
106 xorg_list_del(&it
->l
);
107 xorg_list_add(&it
->l
, newBucket
);
112 ht
->buckets
= newBuckets
;
113 ht
->bucketBits
= newBucketBits
;
121 ht_add(HashTable ht
, pointer key
)
123 unsigned index
= ht
->hash(ht
->cdata
, key
, ht
->bucketBits
);
124 struct xorg_list
*bucket
= &ht
->buckets
[index
];
125 BucketRec
*elem
= calloc(1, sizeof(BucketRec
));
129 elem
->key
= malloc(ht
->keySize
);
133 /* we avoid signaling an out-of-memory error if dataSize is 0 */
134 elem
->data
= calloc(1, ht
->dataSize
);
135 if (ht
->dataSize
&& !elem
->data
) {
138 xorg_list_add(&elem
->l
, bucket
);
141 memcpy(elem
->key
, key
, ht
->keySize
);
143 if (ht
->elements
> 4 * (1 << ht
->bucketBits
) &&
144 ht
->bucketBits
< MAXHASHSIZE
) {
145 if (!double_size(ht
)) {
147 xorg_list_del(&elem
->l
);
152 /* if memory allocation has failed due to dataSize being 0, return
153 a "dummy" pointer pointing at the of the key */
154 return elem
->data
? elem
->data
: ((char*) elem
->key
+ ht
->keySize
);
167 ht_remove(HashTable ht
, pointer key
)
169 unsigned index
= ht
->hash(ht
->cdata
, key
, ht
->bucketBits
);
170 struct xorg_list
*bucket
= &ht
->buckets
[index
];
173 xorg_list_for_each_entry(it
, bucket
, l
) {
174 if (ht
->compare(ht
->cdata
, key
, it
->key
) == 0) {
175 xorg_list_del(&it
->l
);
186 ht_find(HashTable ht
, pointer key
)
188 unsigned index
= ht
->hash(ht
->cdata
, key
, ht
->bucketBits
);
189 struct xorg_list
*bucket
= &ht
->buckets
[index
];
192 xorg_list_for_each_entry(it
, bucket
, l
) {
193 if (ht
->compare(ht
->cdata
, key
, it
->key
) == 0) {
194 return it
->data
? it
->data
: ((char*) it
->key
+ ht
->keySize
);
202 ht_dump_distribution(HashTable ht
)
205 int numBuckets
= 1 << ht
->bucketBits
;
206 for (c
= 0; c
< numBuckets
; ++c
) {
210 xorg_list_for_each_entry(it
, &ht
->buckets
[c
], l
) {
213 printf("%d: %d\n", c
, n
);
217 /* Picked the function from http://burtleburtle.net/bob/hash/doobs.html by
218 Bob Jenkins, which is released in public domain */
220 one_at_a_time_hash(const void *data
, int len
)
224 const char *key
= data
;
225 for (hash
=0, i
=0; i
<len
; ++i
) {
227 hash
+= (hash
<< 10);
231 hash
^= (hash
>> 11);
232 hash
+= (hash
<< 15);
237 ht_generic_hash(void *cdata
, const void *ptr
, int numBits
)
239 HtGenericHashSetupPtr setup
= cdata
;
240 return one_at_a_time_hash(ptr
, setup
->keySize
) & ~((~0) << numBits
);
244 ht_generic_compare(void *cdata
, const void *l
, const void *r
)
246 HtGenericHashSetupPtr setup
= cdata
;
247 return memcmp(l
, r
, setup
->keySize
);
251 ht_resourceid_hash(void * cdata
, const void * data
, int numBits
)
253 const XID
* idPtr
= data
;
254 XID id
= *idPtr
& RESOURCE_ID_MASK
;
256 return HashResourceID(id
, numBits
);
260 ht_resourceid_compare(void* cdata
, const void* a
, const void* b
)
272 ht_dump_contents(HashTable ht
,
273 void (*print_key
)(void *opaque
, void *key
),
274 void (*print_value
)(void *opaque
, void *value
),
278 int numBuckets
= 1 << ht
->bucketBits
;
279 for (c
= 0; c
< numBuckets
; ++c
) {
284 xorg_list_for_each_entry(it
, &ht
->buckets
[c
], l
) {
288 print_key(opaque
, it
->key
);
290 print_value(opaque
, it
->data
);