最近做搜索用到了hash，网上找了一个uthash，用着补怎么爽，毕竟不是自己写的，而且名字很怪。。。
于是自己实现了一个，hash是网上看到的，来自暴雪公司
之前那一个不是很好，而且不支持多线程，改版如下
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 8 static unsigned long aval_size[23] = { 9 21911, 43853, 87719, 175447, 350899, 10 701819, 1403641, 2807303, 5614657, 11229331, 11 22458671, 44917381, 89834777, 179669557, 359339171, 12 718678369, 1437356741, 2147483647 13 }; 14 static int rehash(dict_t *dict); 15 static int expand(dict_t *dict); 16 static void free_ht(dictht_t *ht); 17 static int init_dictht(dict_t *dict, int index, int size); 18 static void init_crypt(unsigned long *crypt); 19 static unsigned long hash(dict_t *dict, char *key, int type); 20 static int get_pos(dict_t *dict, char *key, int type); 21 22 dict_t *trp_dict_init() 23 { 24 dict_t *dict = calloc(1, sizeof(dict_t)); 25 if (dict == NULL) 26 return NULL; 27 dict->rehashing = 0; 28 dict->index = 0; 29 init_crypt(dict->crypt); 30 if (init_dictht(dict, 0, aval_size[0]) == -1) 31 return NULL; 32 return dict; 33 } 34 35 int trp_dict_push(dict_t *dict, char *key, void *data) 36 { 37 dictht_t *ht = &dict->ht[dict->index]; 38 if (ht->size <= ht->used * 2) 39 expand(dict); 40 if (dict->rehashing != 1 && rehash(dict) == -1) 41 return -1; 42 ht = &dict->ht[dict->index]; 43 int pos = get_pos(dict, key, INSERT); 44 ht->node[pos].exist = EXIST; 45 strncpy(ht->node[pos].key, key, strlen(key)); 46 ht->node[pos].data = data; 47 ht->used++; 48 return 0; 49 } 50 51 int trp_dict_delete(dict_t *dict, char *key) 52 { 53 if (rehash(dict) == -1) 54 return -1; 55 int pos = get_pos(dict, key, SEARCH); 56 dictht_t *ht = &dict->ht[dict->index]; 57 if (ht->node[pos].exist == NON) 58 return -1; 59 ht->node[pos].exist = DELETE; 60 memset(ht->node[pos].key, 0, strlen(key)); 61 ht->used--; 62 return 0; 63 } 64 65 int trp_dict_search(dict_t *dict, char *key, void **result) 66 { 67 if (rehash(dict) == -1) 68 return -1; 69 int pos = get_pos(dict, key, SEARCH); 70 dictht_t *ht = &dict->ht[dict->index]; 71 if (ht->node[pos].exist == EXIST) { 72 *result = ht->node[pos].data; 73 return 0; 74 } 75 return -1; 76 } 77 78 void trp_dict_free(dict_t *dict) 79 { 80 free_ht(&dict->ht[dict->index]); 81 free(dict); 82 } 83 84 static void free_ht(dictht_t *ht) 85 { 86 int i; 87 for (i = 0; i < ht->size; i++) 88 if (ht->node[i].exist != NON) { 89 ht->node[i].exist = NON; 90 free(ht->node[i].data); 91 } 92 free(ht->node); 93 ht->size = ht->used = 0; 94 } 95 96 static int rehash(dict_t *dict) 97 { 98 int i; 99 dictht_t *ht = &dict->ht[1 - dict->index];100 if (ht->used <= 0)101 return 0;102 dict->rehashing = 1;103 for (i = ht->used - 1; i > ht->used - 101 && i >= 0; i--)104 if (ht->node[i].exist == EXIST 105 && trp_dict_push(dict, ht->node[i].key, ht->node[i].data) == -1) {106 dict->rehashing = 0;107 return -1;108 }109 ht->used = (ht->used - 100 > 0) ? ht->used - 100 : 0;110 dict->rehashing = 0;111 if (ht->used == 0)112 free(dict->ht[1 - dict->index].node);113 return 0;114 }115 116 static int expand(dict_t *dict)117 {118 int i;119 for (i = 0; i < 23; i++)120 if (aval_size[i] > dict->ht[dict->index].size)121 break;122 if (init_dictht(dict, 1 - dict->index, aval_size[i]) == -1)123 return -1;124 dict->ht[dict->index].used = dict->ht[dict->index].size;125 dict->index = 1 - dict->index;126 if (rehash(dict) == -1)127 return -1;128 return 0;129 }130 131 static int init_dictht(dict_t *dict, int index, int size)132 {133 dictht_t *ht = &dict->ht[index];134 ht->size = size;135 ht->used = 0;136 ht->node = calloc(size, sizeof(htnode_t));137 if (ht->node == NULL)138 return -1;139 return 0;140 }141 142 static void init_crypt(unsigned long *crypt)143 {144 unsigned long seed = 0x00100001, index1 = 0, index2 = 0;145 unsigned long i, temp1, temp2;146 for (index1 = 0; index1 < 0x100; index1++)147 for (index2 = index1, i = 0; i < 5; i++, index2 += 0x100) {148 seed = (seed * 125 + 3) % 0x2AAAAB;149 temp1 = (seed & 0xFFFF) << 0x10;150 seed = (seed * 125 + 3) % 0x2AAAAB;151 temp2 = (seed & 0xFFFF);152 crypt[index2] = (temp1 | temp2);153 }154 }155 156 static unsigned long hash(dict_t *dict, char *key, int type)157 {158 unsigned char *ukey = (unsigned char *)key;159 unsigned long seed1 = 0x7FED7FED;160 unsigned long seed2 = 0xEEEEEEEE;161 int ch;162 while (*ukey) {163 ch = toupper(*ukey++);164 seed1 = dict->crypt[(type << 8) + ch] ^ (seed1 + seed2);165 seed2 = ch + seed1 + seed2 + (seed2 << 5) + 3;166 }167 return seed1;168 }169 170 static int get_pos(dict_t *dict, char *key, int type)171 {172 unsigned long value = hash(dict, key, 0);173 dictht_t *ht = &dict->ht[dict->index];174 int start = value % ht->size;175 int pos = start; 176 if (type == INSERT)177 while (ht->node[pos].exist == EXIST)178 pos = (pos + 100) % ht->size;179 else if (type == SEARCH)180 while (ht->node[pos].exist != NON)181 if (ht->node[pos].exist != DELETE 182 && strcmp(ht->node[pos].key, key) == 0)183 break;184 else185 pos = (pos + 100) % ht->size;186 return pos;187 }
1 #ifndef __TRP_HASH_H__ 2 #define __TRP_HASH_H__ 3 4 #define MAXLEN 1024 5 6 #define INSERT 1 7 #define SEARCH 2 8 9 #define NON 010 #define DELETE 111 #define EXIST 212 13 typedef struct {14 int exist;15 char key[MAXLEN];16 void *data;17 } htnode_t;18 19 typedef struct {20 int size;21 int used;22 htnode_t *node;23 } dictht_t;24 25 typedef struct {26 int rehashing;27 int index;28 dictht_t ht[2];29 unsigned long crypt[0x500];30 } dict_t;31 32 dict_t *trp_dict_init();33 int trp_dict_push(dict_t *dict, char *key, void *data);34 int trp_dict_delete(dict_t *dict, char *key);35 int trp_dict_search(dict_t *dict, char *key, void **result);36 void trp_dict_free(dict_t *dict);37 #endif