6 * Permission is hereby granted, free of charge, to any person obtaining a copy of
7 * this software and associated documentation files (the "Software"), to deal in
8 * the Software without restriction, including without limitation the rights to
9 * use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
10 * of the Software, and to permit persons to whom the Software is furnished to do
11 * so, subject to the following conditions:
13 * The above copyright notice and this permission notice shall be included in all
14 * copies or substantial portions of the Software.
16 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
19 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
21 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
37 struct memblock_t *next;
38 struct memblock_t *prev;
41 static struct memblock_t *mem_start = NULL;
43 void *util_memory_a(size_t byte, unsigned int line, const char *file) {
44 struct memblock_t *info = malloc(sizeof(struct memblock_t) + byte);
45 void *data = (void*)(info+1);
46 if (!info) return NULL;
51 info->next = mem_start;
53 mem_start->prev = info;
56 util_debug("MEM", "allocation: % 8u (bytes) address 0x%08X @ %s:%u\n", byte, data, file, line);
63 void util_memory_d(void *ptrn, unsigned int line, const char *file) {
64 struct memblock_t *info = NULL;
67 info = ((struct memblock_t*)ptrn - 1);
69 util_debug("MEM", "released: % 8u (bytes) address 0x%08X @ %s:%u\n", info->byte, ptrn, file, line);
74 info->prev->next = info->next;
76 info->next->prev = info->prev;
77 if (info == mem_start)
78 mem_start = info->next;
83 void *util_memory_r(void *ptrn, size_t byte, unsigned int line, const char *file) {
84 struct memblock_t *oldinfo = NULL;
86 struct memblock_t *newinfo;
89 return util_memory_a(byte, line, file);
91 util_memory_d(ptrn, line, file);
95 oldinfo = ((struct memblock_t*)ptrn - 1);
96 newinfo = ((struct memblock_t*)malloc(sizeof(struct memblock_t) + byte));
98 util_debug("MEM", "reallocation: % 8u -> %u (bytes) address 0x%08X -> 0x%08X @ %s:%u\n", oldinfo->byte, byte, ptrn, (void*)(newinfo+1), file, line);
102 util_memory_d(oldinfo+1, line, file);
107 memcpy(newinfo+1, oldinfo+1, oldinfo->byte);
111 oldinfo->prev->next = oldinfo->next;
113 oldinfo->next->prev = oldinfo->prev;
114 if (oldinfo == mem_start)
115 mem_start = oldinfo->next;
118 newinfo->line = line;
119 newinfo->byte = byte;
120 newinfo->file = file;
121 newinfo->prev = NULL;
122 newinfo->next = mem_start;
124 mem_start->prev = newinfo;
127 mem_ab -= oldinfo->byte;
128 mem_ab += newinfo->byte;
135 void util_meminfo() {
136 struct memblock_t *info;
141 for (info = mem_start; info; info = info->next) {
142 util_debug("MEM", "lost: % 8u (bytes) at %s:%u\n",
148 util_debug("MEM", "Memory information:\n\
149 Total allocations: %llu\n\
150 Total deallocations: %llu\n\
151 Total allocated: %llu (bytes)\n\
152 Total deallocated: %llu (bytes)\n\
153 Leaks found: lost %llu (bytes) in %d allocations\n",
162 * Some string utility functions, because strdup uses malloc, and we want
163 * to track all memory (without replacing malloc).
165 char *util_strdup(const char *s) {
172 if ((len = strlen(s)) && (ptr = mem_a(len+1))) {
180 * Remove quotes from a string, escapes from \ in string
181 * as well. This function shouldn't be used to create a
182 * char array that is later freed (it uses pointer arith)
184 char *util_strrq(const char *s) {
185 char *dst = (char*)s;
186 char *src = (char*)s;
188 while ((chr = *src++) != '\0') {
191 if ((chr = *src++) == '\0')
194 } else if (chr != '"')
202 * Chops a substring from an existing string by creating a
203 * copy of it and null terminating it at the required position.
205 char *util_strchp(const char *s, const char *e) {
206 const char *c = NULL;
214 return util_strdup(s);
218 * Returns true if string is all uppercase, otherwise
221 bool util_strupper(const char *str) {
231 * Returns true if string is all digits, otherwise
234 bool util_strdigit(const char *str) {
243 bool util_strncmpexact(const char *src, const char *ned, size_t len) {
244 return (!strncmp(src, ned, len) && !src[len]);
247 void util_debug(const char *area, const char *ms, ...) {
252 if (!strcmp(area, "MEM") && !opts.memchk)
256 con_out ("[%s] ", area);
262 * Endianess swapping, all data must be stored little-endian. This
263 * reorders by stride and length, much nicer than other functions for
264 * certian-sized types like short or int.
267 void util_endianswap(void *m, int s, int l) {
271 /* ignore if we're already LE */
275 for(; w < (size_t)l; w++) {
276 for(; i < (size_t)(s << 1); i++) {
277 unsigned char *p = (unsigned char *)m+w*s;
278 unsigned char t = p[i];
286 static void util_swap16(uint16_t *d, size_t l) {
288 d[l] = (d[l] << 8) | (d[l] >> 8);
292 static void util_swap32(uint32_t *d, size_t l) {
295 v = ((d[l] << 8) & 0xFF00FF00) | ((d[l] >> 8) & 0x00FF00FF);
296 d[l] = (v << 16) | (v >> 16);
300 /* Some strange system doesn't like constants that big, AND doesn't recognize an ULL suffix
301 * so let's go the safe way
303 static void util_swap64(uint32_t *d, size_t l) {
307 v = ((d[l] << 8) & 0xFF00FF00FF00FF00) | ((d[l] >> 8) & 0x00FF00FF00FF00FF);
308 v = ((v << 16) & 0xFFFF0000FFFF0000) | ((v >> 16) & 0x0000FFFF0000FFFF);
309 d[l] = (v << 32) | (v >> 32);
313 for (i = 0; i < l; i += 2) {
321 void util_endianswap(void *_data, size_t length, unsigned int typesize) {
322 /* I'm guessing there's no GOOD way to do this at compile time:
325 if (*((char*)&typesize))
330 util_swap16((uint16_t*)_data, length>>1);
334 util_swap32((uint32_t*)_data, length>>2);
338 util_swap64((uint32_t*)_data, length>>3);
344 * CRC algorithms vary in the width of the polynomial, the value of said polynomial,
345 * the initial value used for the register, weather the bits of each byte are reflected
346 * before being processed, weather the algorithm itself feeds input bytes through the
347 * register or XORs them with a byte from one end and then straight into the table, as
348 * well as (but not limited to the idea of reflected versions) where the final register
349 * value becomes reversed, and finally weather the value itself is used to XOR the final
350 * register value. AS such you can already imagine how painfully annoying CRCs are,
351 * of course we stand to target Quake, which expects it's certian set of rules for proper
352 * calculation of a CRC.
354 * In most traditional CRC algorithms on uses a reflected table driven method where a value
355 * or register is reflected if it's bits are swapped around it's center. For example:
356 * take the bits 0101 is the 4-bit reflection of 1010, and respectfully 0011 would be the
357 * reflection of 1100. Quakle however expects a NON-Reflected CRC on the output, but still
358 * requires a final XOR on the values (0xFFFF and 0x0000) this is a standard CCITT CRC-16
359 * which I respectfully as a programmer don't agree with.
361 * So now you know what we target, and why we target it, despite how unsettling it may seem
362 * but those are what Quake seems to request.
366 * This is an implementation of CRC32 & CRC16. The polynomials have been
367 * offline computed for faster generation at the cost of larger code size.
369 * CRC32 Polynomial: 0xEDB88320
370 * CRC16 Polynomial: 0x00001021
372 static const uint32_t util_crc32_table[] = {
373 0x00000000, 0x77073096, 0xEE0E612C, 0x990951BA, 0x076DC419, 0x706AF48F,
374 0xE963A535, 0x9E6495A3, 0x0EDB8832, 0x79DCB8A4, 0xE0D5E91E, 0x97D2D988,
375 0x09B64C2B, 0x7EB17CBD, 0xE7B82D07, 0x90BF1D91, 0x1DB71064, 0x6AB020F2,
376 0xF3B97148, 0x84BE41DE, 0x1ADAD47D, 0x6DDDE4EB, 0xF4D4B551, 0x83D385C7,
377 0x136C9856, 0x646BA8C0, 0xFD62F97A, 0x8A65C9EC, 0x14015C4F, 0x63066CD9,
378 0xFA0F3D63, 0x8D080DF5, 0x3B6E20C8, 0x4C69105E, 0xD56041E4, 0xA2677172,
379 0x3C03E4D1, 0x4B04D447, 0xD20D85FD, 0xA50AB56B, 0x35B5A8FA, 0x42B2986C,
380 0xDBBBC9D6, 0xACBCF940, 0x32D86CE3, 0x45DF5C75, 0xDCD60DCF, 0xABD13D59,
381 0x26D930AC, 0x51DE003A, 0xC8D75180, 0xBFD06116, 0x21B4F4B5, 0x56B3C423,
382 0xCFBA9599, 0xB8BDA50F, 0x2802B89E, 0x5F058808, 0xC60CD9B2, 0xB10BE924,
383 0x2F6F7C87, 0x58684C11, 0xC1611DAB, 0xB6662D3D, 0x76DC4190, 0x01DB7106,
384 0x98D220BC, 0xEFD5102A, 0x71B18589, 0x06B6B51F, 0x9FBFE4A5, 0xE8B8D433,
385 0x7807C9A2, 0x0F00F934, 0x9609A88E, 0xE10E9818, 0x7F6A0DBB, 0x086D3D2D,
386 0x91646C97, 0xE6635C01, 0x6B6B51F4, 0x1C6C6162, 0x856530D8, 0xF262004E,
387 0x6C0695ED, 0x1B01A57B, 0x8208F4C1, 0xF50FC457, 0x65B0D9C6, 0x12B7E950,
388 0x8BBEB8EA, 0xFCB9887C, 0x62DD1DDF, 0x15DA2D49, 0x8CD37CF3, 0xFBD44C65,
389 0x4DB26158, 0x3AB551CE, 0xA3BC0074, 0xD4BB30E2, 0x4ADFA541, 0x3DD895D7,
390 0xA4D1C46D, 0xD3D6F4FB, 0x4369E96A, 0x346ED9FC, 0xAD678846, 0xDA60B8D0,
391 0x44042D73, 0x33031DE5, 0xAA0A4C5F, 0xDD0D7CC9, 0x5005713C, 0x270241AA,
392 0xBE0B1010, 0xC90C2086, 0x5768B525, 0x206F85B3, 0xB966D409, 0xCE61E49F,
393 0x5EDEF90E, 0x29D9C998, 0xB0D09822, 0xC7D7A8B4, 0x59B33D17, 0x2EB40D81,
394 0xB7BD5C3B, 0xC0BA6CAD, 0xEDB88320, 0x9ABFB3B6, 0x03B6E20C, 0x74B1D29A,
395 0xEAD54739, 0x9DD277AF, 0x04DB2615, 0x73DC1683, 0xE3630B12, 0x94643B84,
396 0x0D6D6A3E, 0x7A6A5AA8, 0xE40ECF0B, 0x9309FF9D, 0x0A00AE27, 0x7D079EB1,
397 0xF00F9344, 0x8708A3D2, 0x1E01F268, 0x6906C2FE, 0xF762575D, 0x806567CB,
398 0x196C3671, 0x6E6B06E7, 0xFED41B76, 0x89D32BE0, 0x10DA7A5A, 0x67DD4ACC,
399 0xF9B9DF6F, 0x8EBEEFF9, 0x17B7BE43, 0x60B08ED5, 0xD6D6A3E8, 0xA1D1937E,
400 0x38D8C2C4, 0x4FDFF252, 0xD1BB67F1, 0xA6BC5767, 0x3FB506DD, 0x48B2364B,
401 0xD80D2BDA, 0xAF0A1B4C, 0x36034AF6, 0x41047A60, 0xDF60EFC3, 0xA867DF55,
402 0x316E8EEF, 0x4669BE79, 0xCB61B38C, 0xBC66831A, 0x256FD2A0, 0x5268E236,
403 0xCC0C7795, 0xBB0B4703, 0x220216B9, 0x5505262F, 0xC5BA3BBE, 0xB2BD0B28,
404 0x2BB45A92, 0x5CB36A04, 0xC2D7FFA7, 0xB5D0CF31, 0x2CD99E8B, 0x5BDEAE1D,
405 0x9B64C2B0, 0xEC63F226, 0x756AA39C, 0x026D930A, 0x9C0906A9, 0xEB0E363F,
406 0x72076785, 0x05005713, 0x95BF4A82, 0xE2B87A14, 0x7BB12BAE, 0x0CB61B38,
407 0x92D28E9B, 0xE5D5BE0D, 0x7CDCEFB7, 0x0BDBDF21, 0x86D3D2D4, 0xF1D4E242,
408 0x68DDB3F8, 0x1FDA836E, 0x81BE16CD, 0xF6B9265B, 0x6FB077E1, 0x18B74777,
409 0x88085AE6, 0xFF0F6A70, 0x66063BCA, 0x11010B5C, 0x8F659EFF, 0xF862AE69,
410 0x616BFFD3, 0x166CCF45, 0xA00AE278, 0xD70DD2EE, 0x4E048354, 0x3903B3C2,
411 0xA7672661, 0xD06016F7, 0x4969474D, 0x3E6E77DB, 0xAED16A4A, 0xD9D65ADC,
412 0x40DF0B66, 0x37D83BF0, 0xA9BCAE53, 0xDEBB9EC5, 0x47B2CF7F, 0x30B5FFE9,
413 0xBDBDF21C, 0xCABAC28A, 0x53B39330, 0x24B4A3A6, 0xBAD03605, 0xCDD70693,
414 0x54DE5729, 0x23D967BF, 0xB3667A2E, 0xC4614AB8, 0x5D681B02, 0x2A6F2B94,
415 0xB40BBE37, 0xC30C8EA1, 0x5A05DF1B, 0x2D02EF8D
417 static const uint16_t util_crc16_table[] = {
418 0x0000, 0x1021, 0x2042, 0x3063, 0x4084, 0x50A5,
419 0x60C6, 0x70E7, 0x8108, 0x9129, 0xA14A, 0xB16B,
420 0xC18C, 0xD1AD, 0xE1CE, 0xF1EF, 0x1231, 0x0210,
421 0x3273, 0x2252, 0x52B5, 0x4294, 0x72F7, 0x62D6,
422 0x9339, 0x8318, 0xB37B, 0xA35A, 0xD3BD, 0xC39C,
423 0xF3FF, 0xE3DE, 0x2462, 0x3443, 0x0420, 0x1401,
424 0x64E6, 0x74C7, 0x44A4, 0x5485, 0xA56A, 0xB54B,
425 0x8528, 0x9509, 0xE5EE, 0xF5CF, 0xC5AC, 0xD58D,
426 0x3653, 0x2672, 0x1611, 0x0630, 0x76D7, 0x66F6,
427 0x5695, 0x46B4, 0xB75B, 0xA77A, 0x9719, 0x8738,
428 0xF7DF, 0xE7FE, 0xD79D, 0xC7BC, 0x48C4, 0x58E5,
429 0x6886, 0x78A7, 0x0840, 0x1861, 0x2802, 0x3823,
430 0xC9CC, 0xD9ED, 0xE98E, 0xF9AF, 0x8948, 0x9969,
431 0xA90A, 0xB92B, 0x5AF5, 0x4AD4, 0x7AB7, 0x6A96,
432 0x1A71, 0x0A50, 0x3A33, 0x2A12, 0xDBFD, 0xCBDC,
433 0xFBBF, 0xEB9E, 0x9B79, 0x8B58, 0xBB3B, 0xAB1A,
434 0x6CA6, 0x7C87, 0x4CE4, 0x5CC5, 0x2C22, 0x3C03,
435 0x0C60, 0x1C41, 0xEDAE, 0xFD8F, 0xCDEC, 0xDDCD,
436 0xAD2A, 0xBD0B, 0x8D68, 0x9D49, 0x7E97, 0x6EB6,
437 0x5ED5, 0x4EF4, 0x3E13, 0x2E32, 0x1E51, 0x0E70,
438 0xFF9F, 0xEFBE, 0xDFDD, 0xCFFC, 0xBF1B, 0xAF3A,
439 0x9F59, 0x8F78, 0x9188, 0x81A9, 0xB1CA, 0xA1EB,
440 0xD10C, 0xC12D, 0xF14E, 0xE16F, 0x1080, 0x00A1,
441 0x30C2, 0x20E3, 0x5004, 0x4025, 0x7046, 0x6067,
442 0x83B9, 0x9398, 0xA3FB, 0xB3DA, 0xC33D, 0xD31C,
443 0xE37F, 0xF35E, 0x02B1, 0x1290, 0x22F3, 0x32D2,
444 0x4235, 0x5214, 0x6277, 0x7256, 0xB5EA, 0xA5CB,
445 0x95A8, 0x8589, 0xF56E, 0xE54F, 0xD52C, 0xC50D,
446 0x34E2, 0x24C3, 0x14A0, 0x0481, 0x7466, 0x6447,
447 0x5424, 0x4405, 0xA7DB, 0xB7FA, 0x8799, 0x97B8,
448 0xE75F, 0xF77E, 0xC71D, 0xD73C, 0x26D3, 0x36F2,
449 0x0691, 0x16B0, 0x6657, 0x7676, 0x4615, 0x5634,
450 0xD94C, 0xC96D, 0xF90E, 0xE92F, 0x99C8, 0x89E9,
451 0xB98A, 0xA9AB, 0x5844, 0x4865, 0x7806, 0x6827,
452 0x18C0, 0x08E1, 0x3882, 0x28A3, 0xCB7D, 0xDB5C,
453 0xEB3F, 0xFB1E, 0x8BF9, 0x9BD8, 0xABBB, 0xBB9A,
454 0x4A75, 0x5A54, 0x6A37, 0x7A16, 0x0AF1, 0x1AD0,
455 0x2AB3, 0x3A92, 0xFD2E, 0xED0F, 0xDD6C, 0xCD4D,
456 0xBDAA, 0xAD8B, 0x9DE8, 0x8DC9, 0x7C26, 0x6C07,
457 0x5C64, 0x4C45, 0x3CA2, 0x2C83, 0x1CE0, 0x0CC1,
458 0xEF1F, 0xFF3E, 0xCF5D, 0xDF7C, 0xAF9B, 0xBFBA,
459 0x8FD9, 0x9FF8, 0x6E17, 0x7E36, 0x4E55, 0x5E74,
460 0x2E93, 0x3EB2, 0x0ED1, 0x1EF0
464 * Implements a CRC function for X worth bits using (uint[X]_t)
465 * as type. and util_crc[X]_table.
467 * Quake expects a non-reflective CRC.
470 uint##X##_t util_crc##X(uint##X##_t current, const char *k, size_t len) { \
471 register uint##X##_t h= current; \
472 for (; len; --len, ++k) \
473 h = util_crc##X##_table[(h>>8)^((unsigned char)*k)]^(h<<8); \
481 uint##X##_t util_crc##X(const char *k, int len, const short clamp) { \
482 register uint##X##_t h= (uint##X##_t)0xFFFFFFFF; \
483 for (; len; --len, ++k) \
484 h = util_crc##X##_table[(h^((unsigned char)*k))&0xFF]^(h>>8); \
491 * Implements libc getline for systems that don't have it, which is
492 * assmed all. This works the same as getline().
494 int util_getline(char **lineptr, size_t *n, FILE *stream) {
499 if (!lineptr || !n || !stream)
502 if (!(*lineptr = (char*)mem_a((*n=64))))
510 int c = getc(stream);
513 *n += (*n > 16) ? *n : 64;
514 chr = *n + *lineptr - pos;
515 if (!(*lineptr = (char*)mem_r(*lineptr,*n)))
517 pos = *n - chr + *lineptr;
535 return (ret = pos - *lineptr);
538 size_t util_strtocmd(const char *in, char *out, size_t outsz) {
540 for (; *in && sz < outsz; ++in, ++out, ++sz)
541 *out = (*in == '-') ? '_' : (isalpha(*in) && !isupper(*in)) ? *in + 'A' - 'a': *in;
546 size_t util_strtononcmd(const char *in, char *out, size_t outsz) {
548 for (; *in && sz < outsz; ++in, ++out, ++sz)
549 *out = (*in == '_') ? '-' : (isalpha(*in) && isupper(*in)) ? *in + 'a' - 'A' : *in;
555 FILE *util_fopen(const char *filename, const char *mode)
559 if (fopen_s(&out, filename, mode) != 0)
563 return fopen(filename, mode);
567 void _util_vec_grow(void **a, size_t i, size_t s) {
568 size_t m = *a ? 2*_vec_beg(*a)+i : i+1;
569 void *p = mem_r((*a ? _vec_raw(*a) : NULL), s * m + sizeof(size_t)*2);
572 *a = (void*)((size_t*)p + 2);
577 * Hash table for generic data, based on dynamic memory allocations
578 * all around. This is the internal interface, please look for
579 * EXPOSED INTERFACE comment below
581 typedef struct hash_node_t {
582 char *key; /* the key for this node in table */
583 void *value; /* pointer to the data as void* */
584 struct hash_node_t *next; /* next node (linked list) */
588 * x86 and x86_64 optimized murmur hash functions for the hashtable
589 * we have individual implementations for optimal performance.
591 * Forced inlined as we wrap these up in the actual utility function
592 * below. These should be autovectorized by gcc.
595 GMQCC_INLINE uint32_t util_hthashfunc(hash_table_t *ht, const char *key, size_t seed) {
596 const uint64_t mix = 0xC6A4A7935BD1E995;
598 size_t size = strlen(key);
599 uint64_t hash = seed ^ (size - mix);
601 const uint64_t *beg = (const uint64_t*)key;
602 const uint64_t *end = beg + (size / 8);
603 const unsigned char *final = NULL;
609 alias ^= alias >> rot;
616 final = (const unsigned char *)beg;
619 case 7: hash ^= (uint64_t)(final[6]) << 48;
620 case 6: hash ^= (uint64_t)(final[5]) << 40;
621 case 5: hash ^= (uint64_t)(final[4]) << 32;
622 case 4: hash ^= (uint64_t)(final[3]) << 24;
623 case 3: hash ^= (uint64_t)(final[2]) << 16;
624 case 2: hash ^= (uint64_t)(final[1]) << 8;
625 case 1: hash ^= (uint64_t)(final[0]);
633 return (uint32_t)(hash % ht->size);
637 GMQCC_INLINE uint32_t util_hthashfunc(hash_table_t *ht, const char *key, size_t seed) {
638 const uint32_t mix = 0x5BD1E995;
639 const uint32_t rot = 24;
640 size_t size = strlen(key);
641 uint32_t hash = seed ^ size;
643 const unsigned char *data = (const unsigned char*)key;
646 alias = *(uint32_t*)data;
649 alias ^= alias >> rot;
660 case 3: hash ^= data[2] << 16;
661 case 2: hash ^= data[1] << 8;
662 case 1: hash ^= data[0];
670 return hash % ht->size;
674 /* we use the crc table as seeds for the murmur hash :P */
675 size_t util_hthash(hash_table_t *ht, const char *key) {
676 static size_t seed = 0;
677 register size_t hash = util_hthashfunc(ht, key, util_crc32_table[seed]);
680 if (seed >= sizeof(util_crc32_table) / sizeof(*util_crc32_table))
686 hash_node_t *_util_htnewpair(const char *key, void *value) {
688 if (!(node = mem_a(sizeof(hash_node_t))))
691 if (!(node->key = util_strdup(key))) {
703 * EXPOSED INTERFACE for the hashtable implementation
704 * util_htnew(size) -- to make a new hashtable
705 * util_htset(table, key, value, sizeof(value)) -- to set something in the table
706 * util_htget(table, key) -- to get something from the table
707 * util_htdel(table) -- to delete the table
709 hash_table_t *util_htnew(size_t size) {
710 hash_table_t *hashtable = NULL;
714 if (!(hashtable = mem_a(sizeof(hash_table_t))))
717 if (!(hashtable->table = mem_a(sizeof(hash_node_t*) * size))) {
722 hashtable->size = size;
723 memset(hashtable->table, 0, sizeof(hash_node_t*) * size);
728 void util_htseth(hash_table_t *ht, const char *key, size_t bin, void *value) {
729 hash_node_t *newnode = NULL;
730 hash_node_t *next = NULL;
731 hash_node_t *last = NULL;
733 next = ht->table[bin];
735 while (next && next->key && strcmp(key, next->key) > 0)
736 last = next, next = next->next;
738 /* already in table, do a replace */
739 if (next && next->key && strcmp(key, next->key) == 0) {
742 /* not found, grow a pair man :P */
743 newnode = _util_htnewpair(key, value);
744 if (next == ht->table[bin]) {
745 newnode->next = next;
746 ht->table[bin] = newnode;
748 last->next = newnode;
750 newnode->next = next;
751 last->next = newnode;
756 void util_htset(hash_table_t *ht, const char *key, void *value) {
757 util_htseth(ht, key, util_hthash(ht, key), value);
760 void *util_htgeth(hash_table_t *ht, const char *key, size_t bin) {
761 hash_node_t *pair = ht->table[bin];
763 while (pair && pair->key && strcmp(key, pair->key) > 0)
766 if (!pair || !pair->key || strcmp(key, pair->key) != 0)
772 void *util_htget(hash_table_t *ht, const char *key) {
773 return util_htgeth(ht, key, util_hthash(ht, key));
777 * Free all allocated data in a hashtable, this is quite the amount
780 void util_htdel(hash_table_t *ht) {
782 for (; i < ht->size; i++) {
783 hash_node_t *n = ht->table[i];