wmii

git clone git://oldgit.suckless.org/wmii/
Log | Files | Refs | README | LICENSE

map.c (2153B)

      1 /* Written by Kris Maglione */
      2 /* Public domain */
      3 #include <assert.h>
      4 #include <string.h>
      5 #include <stuff/util.h>
      6 
      7 /* Edit s/^([a-zA-Z].*)\n([a-z].*) {/\1 \2;/g  x/^([^a-zA-Z]|static|$)/-+d  s/ (\*map|val|*str)//g */
      8 
      9 struct MapEnt {
     10 	ulong		hash;
     11 	const char*	key;
     12 	void*		val;
     13 	MapEnt*		next;
     14 };
     15 
     16 MapEnt *NM;
     17 
     18 /* By Dan Bernstein. Public domain. */
     19 static ulong
     20 hash(const char *str) {
     21 	ulong h;
     22 
     23 	h = 5381;
     24 	while (*str != '\0') {
     25 		h += h << 5; /* h *= 33 */
     26 		h ^= *str++;
     27 	}
     28 	return h;
     29 }
     30 
     31 static void
     32 insert(Map *m, MapEnt **e, ulong val, const char *key) {
     33 	MapEnt *te;
     34 
     35 	m->nmemb++;
     36 	te = emallocz(sizeof *te);
     37 	te->hash = val;
     38 	te->key = key;
     39 	te->next = *e;
     40 	*e = te;
     41 }
     42 
     43 static MapEnt**
     44 map_getp(Map *map, ulong val, int create) {
     45 	MapEnt **e;
     46 
     47 	e = &map->bucket[val%map->nhash];
     48 	for(; *e; e = &(*e)->next)
     49 		if((*e)->hash >= val) break;
     50 	if(*e == nil || (*e)->hash != val) {
     51 		if(create)
     52 			insert(map, e, val, nil);
     53 		else
     54 			e = &NM;
     55 	}
     56 	return e;
     57 }
     58 
     59 static MapEnt**
     60 hash_getp(Map *map, const char *str, int create) {
     61 	MapEnt **e;
     62 	ulong h;
     63 	int cmp;
     64 
     65 	h = hash(str);
     66 	e = map_getp(map, h, create);
     67 	if(*e && (*e)->key == nil)
     68 		(*e)->key = estrdup(str);
     69 	else {
     70 		SET(cmp);
     71 		for(; *e; e = &(*e)->next)
     72 			if((*e)->hash > h || (cmp = strcmp((*e)->key, str)) >= 0)
     73 				break;
     74 		if(*e == nil || (*e)->hash > h || cmp > 0)
     75 			if(create)
     76 				insert(map, e, h, estrdup(str));
     77 	}
     78 	return e;
     79 }
     80 
     81 void**
     82 map_get(Map *map, ulong val, bool create) {
     83 	MapEnt *e;
     84 
     85 	e = *map_getp(map, val, create);
     86 	return e ? &e->val : nil;
     87 }
     88 
     89 void**
     90 hash_get(Map *map, const char *str, bool create) {
     91 	MapEnt *e;
     92 
     93 	e = *hash_getp(map, str, create);
     94 	return e ? &e->val : nil;
     95 }
     96 
     97 void*
     98 map_rm(Map *map, ulong val) {
     99 	MapEnt **e, *te;
    100 	void *ret;
    101 
    102 	ret = nil;
    103 	e = map_getp(map, val, 0);
    104 	if(*e) {
    105 		te = *e;
    106 		ret = te->val;
    107 		*e = te->next;
    108 		assert(map->nmemb-- > 0);
    109 		free(te);
    110 	}
    111 	return ret;
    112 }
    113 
    114 void*
    115 hash_rm(Map *map, const char *str) {
    116 	MapEnt **e, *te;
    117 	void *ret;
    118 
    119 	ret = nil;
    120 	e = hash_getp(map, str, 0);
    121 	if(*e) {
    122 		te = *e;
    123 		ret = te->val;
    124 		*e = te->next;
    125 		assert(map->nmemb-- > 0);
    126 		free((void*)(uintptr_t)te->key);
    127 		free(te);
    128 	}
    129 	return ret;
    130 }
    131