-
Notifications
You must be signed in to change notification settings - Fork 1
/
hashtable.h
124 lines (124 loc) · 3.47 KB
/
hashtable.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#ifndef SM_HASHTABLE
#define SM_HASHTABLE
#include<malloc.h>
#include<string.h>
#include<stdbool.h>
#include "algorithm.h"
#define __c_stl_num_prime 32
static size_t __c_stl_prime_list[__c_stl_num_prime]={
2,5,11,23,
53,97,193,389,769,
1543,3079,6151,12289,24593,
49157,98317,196613,393241,786433,
1572869,3145739,6291469,12582917,25165843,
50331653,100663319,201326611,402653189,805306457,
1610612741,3221225473ul,4294967291ul
};
static int size_t_cmp(const void *a,const void *b){
size_t A=*(size_t*)a,B=*(size_t*)b;
if(A!=B)return A<B?-1:1;
return 0;
}
static size_t __c_stl_next_prime(size_t n){
size_t *first=__c_stl_prime_list,*last=__c_stl_prime_list+__c_stl_num_prime;
const size_t *pos=lower_bound(first,last,sizeof(size_t),&n,size_t_cmp);
return pos==last?*(last-1):*pos;
}
#define BASE_SIZE __c_stl_prime_list[2]
typedef struct{
void *data;
}__bucket;
typedef struct{
size_t data_size,bucket_size,size;
__bucket *buckets;
size_t (*hash_function)(const void *);
int (*_cmp)(const void *,const void *);
}_Hashtable;
void _Hashtable_init(_Hashtable *h,size_t data_size,size_t (*function)(const void *),int (*cmp)(const void *,const void *)){
h->data_size=data_size;
h->bucket_size=BASE_SIZE;
h->size=0;
h->buckets=calloc(BASE_SIZE,sizeof(__bucket));
h->hash_function=function;
h->_cmp=cmp;
}
void _Hashtable_clear(_Hashtable *h){
h->bucket_size=BASE_SIZE;
h->size=0;
__bucket *tmp=h->buckets;
size_t i;
for(i=0;i<h->bucket_size;++i){
if(tmp[i].data)free(tmp[i].data);
}
h->buckets=calloc(BASE_SIZE,sizeof(__bucket));
free(tmp);
}
void _Hashtable_free(_Hashtable *h){
h->data_size=0;
h->bucket_size=0;
h->size=0;
size_t i;
for(i=0;i<h->bucket_size;++i){
if(h->buckets[i].data)free(h->buckets[i].data);
}
free(h->buckets);
h->buckets=0;
h->hash_function=0;
h->_cmp=0;
}
__bucket *_Hashtable_find_bucket(_Hashtable *h,__bucket *buckets,size_t bucket_size,const void *value){
size_t i=h->hash_function(value)%bucket_size,j=0;
while(buckets[i].data&&h->_cmp(buckets[i].data,value)){
i+=((++j)<<1)-1;
if(i>=bucket_size)
i-=bucket_size;
}
return buckets+i;
}
bool _Hashtable_insert_base(_Hashtable *h,__bucket *buckets,size_t bucket_size,const void *value){
__bucket *bucket=_Hashtable_find_bucket(h,buckets,bucket_size,value);
if(bucket->data)return 0;
bucket->data=malloc(h->data_size);
memcpy(bucket->data,value,h->data_size);
return 1;
}
void _Hashtable_resize(_Hashtable *h,size_t new_size){
new_size=__c_stl_next_prime(new_size);
__bucket *tmp=calloc(new_size,sizeof(__bucket));
static size_t i;
for(i=0;i<h->bucket_size;++i){
if(h->buckets[i].data){
_Hashtable_insert_base(h,tmp,new_size,h->buckets[i].data);
free(h->buckets[i].data);
}
}
free(h->buckets);
h->buckets=tmp;
h->bucket_size=new_size;
}
void _Hashtable_insert(_Hashtable *h,const void *value){
if(_Hashtable_insert_base(h,h->buckets,h->bucket_size,value))
++h->size;
if(h->size*2>h->bucket_size){
_Hashtable_resize(h,h->bucket_size+1);
}
}
void _Hashtable_erase(_Hashtable *h,const void *value){
__bucket *bucket=_Hashtable_find_bucket(h,h->buckets,h->bucket_size,value);
if(!bucket->data)return;
free(bucket->data);
bucket->data=0;
--h->size;
}
__bucket *_Hashtable_find_base(_Hashtable *h,const void *value){
__bucket *bucket=_Hashtable_find_bucket(h,h->buckets,h->bucket_size,value);
if(!bucket->data)return 0;
return bucket;
}
bool _Hashtable_find(_Hashtable *h,const void *value){
if(_Hashtable_find_base(h,value))return 1;
return 0;
}
#undef BASE_SIZE
#undef __c_stl_num_prime
#endif