a-similar-map-simple-hash-table.rar_Table

[C/C++]代码 001 /***************************************************** 002 ********* 配置文件处理库 作者：Panlatent ********** 003 *****************************************************/ 004 005 #include <string.h> 006 #include <unistd.h> 007 #include <stdio.h> 008 #include <stdarg.h> 009 #include <stdlib.h> 010 011 /*************************************************** 012 ***************** 实现哈希表功能的函数集 ************** 013 ***************************************************/ 014 015 struct nodes { 016 char *keystr; 017 char *valstr; 018 struct nodes *next; 019 } ; 020 021 struct nodelist{ 022 unsigned short int keyc; 023 unsigned short int valc; 024 unsigned short int len; 025 struct nodes **first; 026 } ; 027 028 typedef struct nodes * NODE; 029 typedef struct nodelist * NELT; 030 031 #define NODELIST_MAX_INIT 100 032 033 static struct nodes *infi_node_malloc(const char *keystr, const char *valstr) 034 { 035 struct nodes *node = malloc(sizeof(node)); 036 if (node == NULL) 037 return NULL; 038 char *newkeystr = malloc(strlen(keystr) + 1); 039 if (newkeystr == NULL) { 040 free(node); 041 return NULL; 042 } 043 char *newvalstr = malloc(strlen(valstr) + 1); 044 if (newvalstr == NULL) { 045 free(newkeystr); 046 free(node); 047 return NULL; 048 } 049 strcpy(newkeystr, keystr); 050 strcpy(newvalstr, valstr); 051 *(newkeystr + strlen(keystr)) = '\0'; 052 *(newvalstr + strlen(valstr)) = '\0'; 053 node->keystr = newkeystr; 054 node->valstr = newvalstr; 055 node->next = NULL; 056 return node; 057 } 058 059 static void infi_node_free(struct nodes *node) 060 { 061 struct nodes *nextnode = node->next, *nownode; 062 free(node->keystr); 063 free(node->valstr); 064 free(node); 065 while (nextnode != NULL) { 066 nownode = nextnode; 067 free(nownode->keystr); 068 free(nownode->valstr); 069 free(nownode); 070 nextnode = nextnode->next; 071 } 072 } 073 074 static int infi_node_cmp(const struct nodes *node, const char *keystr) 075 { 076 if (strcmp( node->keystr, keystr) == 0) 077 return 1; 078 else 079 return 0; 080 } 081 082 static unsigned int infi_hashkey(const char *keystr, const unsigned int hashlen) 083 { 084 unsigned long int i = 0; 085 unsigned long long int hashmovalue[4] = {0,0,0,0}; 086 while (*(keystr + i) != '\0') { 087 unsigned short int tent = *(keystr + i)/10 == 0 ? 1 : 10; 088 hashmovalue[i%4] = hashmovalue[i%4]*tent + (*(keystr + i) - 48); 089 i += 1; 090 } 091 long long int hashkey = hashmovalue[0] + hashmovalue[1] + hashmovalue[2] + hashmovalue[3]; 092 return hashkey%hashlen; 093 } 094 095 static int infi_hashd(int i) 096 { 097 int mul = 1, sign; 098 sign = (i % 2)? -1: 1; 099 mul = mul + i/2; 100 return mul*sign; 101 } 102 103 static struct nodelist *infi_nodelist_init(int max) 104 { 105 if (max <= 0) 106 max = NODELIST_MAX_INIT; 107 struct nodelist *nelt = malloc(sizeof(struct nodelist)); 108 if (nelt == NULL) 109 return NULL; 110 nelt->first = calloc(max, sizeof(struct nodes **)); 111 if (nelt->first == NULL) { 112 free(nelt); 113 return NULL; 114 } 115 nelt->keyc = 0; 116 nelt->valc = 0; 117 nelt->len = max; 118 return nelt; 119 } 120 121 static int infi_nodelist_exist(const struct nodelist *nelt, const unsigned int key) 122 { 123 if (*(nelt->first + key) == NULL) 124 return 0; 125 else 126 return 1; 127 } 128 129 /*释放整个表*/ 130 static void infi_nodelist_free(const struct nodelist *nelt) 131 { 132 if (nelt == NULL) 133 return; 134 int i; 135 for (i = 0; i < nelt->len; i++) 136 { 137 if (*(nelt->first + i) == NULL) 138 continue; 139 else 140 infi_node_free(*(nelt->first +i)); 141 } 142 } 143 144 static char **infi_nodelist_getall(const struct nodelist *nelt) 145 { 146 if (nelt == NULL) 147 return NULL; 148 int i, times = 0; 149 char **keyallstr = malloc(sizeof(char *) * nelt->valc); 150 for (i = 0; i < nelt->len; i++) 151 { 152 if (*(nelt->first + i) == NULL) 153 continue; 154 else { 155 *(keyallstr + times) = (*(nelt->first + i))->keystr; 156 times += 1; 157 } 158 } 159 return keyallstr; 160 } 161 162 /*关键字包含的参数数量查询*/ 163 static int infi_nodelist_valc(const struct nodelist *nelt, const char *keystr) 164 { 165 unsigned int key, i = 0, errortimes = 0, num; 166 key = infi_hashkey(keystr, nelt->len); 167 struct nodes *nownelt = NULL; 168 if (infi_nodelist_exist(nelt, key) == 1) { 169 do { 170 if (infi_node_cmp(*(nelt->first + key), keystr) == 1) { 171 nownelt = *(nelt->first + key); 172 num = 1; 173 do { 174 nownelt = nownelt->next; 175 if (nownelt == NULL) { 176 break; 177 } 178 num += 1; 179 } while(nownelt->next != NULL); 180 return num; 181 } 182 key = infi_hashkey(keystr, nelt->len) + infi_hashd(i); 183 if (key < 0 || key >= nelt->len) { 184 if(errortimes == 1) 185 return 0; 186 key = infi_hashkey(keystr, nelt->len); 187 errortimes = 1; 188 } 189 else 190 errortimes = 0; 191 i += 1; 192 } while(infi_nodelist_exist(nelt, key)); 193 return 0; 194 } 195 else 196 return 0; 197 } 198 199 /*添加属性*/ 200 static int infi_nodelist_write(struct nodelist * const nelt, const char *keystr,const char *valstr) 201 { 202 unsigned int key, i = 0, errortimes = 0; 203 key = infi_hashkey(keystr, nelt->len); 204 struct nodes *nownelt = NULL; 205 if (infi_nodelist_exist(nelt, key) == 1) { 206 do { 207 if (infi_node_cmp(*(nelt->first + key), keystr) == 1) { 208 nownelt = *(nelt->first + key); 209 while (nownelt->next != NULL) { 210 nownelt = nownelt->next; 211 } 212 nownelt->next = infi_node_malloc(keystr, valstr); 213 nelt->valc += 1; 214 return 1; 215 } 216 key = infi_hashkey(keystr, nelt->len) + infi_hashd(i); 217 if (key < 0 || key >= nelt->len) { 218 if(errortimes == 1) 219 return 0; 220 key = infi_hashkey(keystr, nelt->len); 221 errortimes = 1; 222 } 223 else 224 errortimes = 0; 225 i += 1; 226 } while(infi_nodelist_exist(nelt, key)); 227 nownelt = *(nelt->first + key); 228 *(nelt->first + key) = infi_node_malloc(keystr, valstr); 229 nelt->valc += 1; 230 nelt->keyc += 1; 231 return 1; 232 } 233 else { 234 nownelt = *(nelt->first + key); 235 *(nelt->first + key) = infi_node_malloc(keystr, valstr); 236 nelt->valc += 1; 237 nelt->keyc += 1; 238 return 1; 239 } 240 } 241 242