+// ------------------------------- dictionary_t -------------------------------
+
+#define INITIAL_SIZE 1
+
+static int max(int x, int y) {
+ return x>y?x:y;
+}
+
+dict_t*dict_new()
+{
+ dict_t*d = rfx_alloc(sizeof(dict_t));
+ dict_init(d);
+ return d;
+}
+void dict_init(dict_t*h)
+{
+ memset(h, 0, sizeof(dict_t));
+ h->hashsize = INITIAL_SIZE;
+ h->slots = h->hashsize?(dictentry_t**)rfx_calloc(sizeof(dictentry_t*)*h->hashsize):0;
+ h->num = 0;
+}
+static void dict_expand(dict_t*h, int newlen)
+{
+ assert(h->hashsize < newlen);
+ dictentry_t**newslots = (dictentry_t**)rfx_calloc(sizeof(dictentry_t*)*newlen);
+ int t;
+ for(t=0;t<h->hashsize;t++) {
+ dictentry_t*e = h->slots[t];
+ while(e) {
+ dictentry_t*next = e->next;
+ unsigned int newhash = e->hash%newlen;
+ e->next = newslots[newhash];
+ newslots[newhash] = e;
+ e = next;
+ }
+ }
+ if(h->slots)
+ rfx_free(h->slots);
+ h->slots = newslots;
+ h->hashsize = newlen;
+}
+void dict_put(dict_t*h, string_t s, void* data)
+{
+ /* TODO: should we look for duplicates here? */
+ unsigned int hash = string_hash(&s);
+ dictentry_t*e = (dictentry_t*)rfx_alloc(sizeof(dictentry_t));
+
+ unsigned int hash2 = string_hash(&s) % h->hashsize;
+ char*sdata = rfx_alloc(s.len);
+ memcpy(sdata, s.str, s.len);
+ e->s = sdata;
+ e->len = s.len;
+ e->hash = hash; //for resizing
+ e->next = h->slots[hash2];
+ e->data = data;
+ h->slots[hash2] = e;
+ h->num++;
+}
+void dict_put2(dict_t*h, const char*s, void*data)
+{
+ string_t s2;
+ string_set(&s2, s);
+ dict_put(h, s2, data);
+}
+void dict_put3(dict_t*h, const char* s, int len, void*data)
+{
+ string_t s3;
+ string_set2(&s3, s, len);
+ dict_put(h, s3, data);
+}
+void dict_dump(dict_t*h, FILE*fi, const char*prefix)
+{
+ int t;
+ for(t=0;t<h->hashsize;t++) {
+ dictentry_t*e = h->slots[t];
+ while(e) {
+ char*s = strdup_n(e->s, e->len);
+ fprintf(fi, "%s%s=%08x\n", prefix, e->s, e->data);
+ rfx_free(s);
+ e = e->next;
+ }
+ }
+}
+
+int dict_count(dict_t*h)
+{
+ return h->num;
+}
+void* dict_lookup4(dict_t*h, const char*s, int len, const void*data)
+{
+ if(!h->num)
+ return 0;
+
+ unsigned int ohash = string_hash2(s);
+ unsigned int hash = ohash % h->hashsize;
+
+ /* check first entry for match */
+ dictentry_t*e = h->slots[hash];
+ if(e && e->len == len && !memcmp(e->s, s, len)) {
+ return e->data;
+ } else if(e) {
+ e = e->next;
+ }
+
+ /* if dict is 2/3 filled, double the size. Do
+ this the first time we have to actually iterate
+ through a slot to find our data */
+ if(e && h->num*3 >= h->hashsize*2) {
+ int newsize = h->hashsize;
+ while(h->num*3 >= newsize*2) {
+ newsize = newsize<15?15:(newsize+1)*2-1;
+ }
+ dict_expand(h, newsize);
+ hash = ohash % h->hashsize;
+ e = h->slots[hash];
+ }
+
+ /* check subsequent entries for a match */
+ while(e) {
+ if(e->len == len && !memcmp(e->s, s, len) && (!data || data==e->data)) {
+ return e->data;
+ }
+ e = e->next;
+ }
+ return 0;
+}
+void* dict_lookup3(dict_t*h, const char*s, const void*data)
+{
+ int l = strlen(s);
+ return dict_lookup4(h, s, l, data);
+}
+void* dict_lookup2(dict_t*h, const char*s, int len)
+{
+ return dict_lookup4(h, s, len, 0);
+}
+void* dict_lookup(dict_t*h, const char*s)
+{
+ int l = strlen(s);
+ return dict_lookup2(h, s, l);
+}
+char dict_del(dict_t*h, const char*s)
+{
+ if(!h->num)
+ return 0;
+ unsigned int hash = string_hash2(s) % h->hashsize;
+ int l = strlen(s);
+ dictentry_t*head = h->slots[hash];
+ dictentry_t*e = head, *prev=0;
+ while(e) {
+ if(e->len ==l && !memcmp(e->s, s, l)) {
+ dictentry_t*next = e->next;
+ rfx_free((void*)e->s);
+ memset(e, 0, sizeof(dictentry_t));
+ rfx_free(e);
+ if(e == head) {
+ h->slots[hash] = 0;
+ } else {
+ assert(prev);
+ prev->next = next;
+ }
+ h->num--;
+ return 1;
+ }
+ prev = e;
+ e = e->next;
+ }
+ return 0;
+}
+
+static dictentry_t* dict_get_all(dict_t*h, const char*s)
+{
+ if(!h->num)
+ return 0;
+ unsigned int ohash = string_hash2(s);
+ unsigned int hash = ohash % h->hashsize;
+ return h->slots[hash];
+}
+
+void dict_foreach_keyvalue(dict_t*h, void (*runFunction)(void*data, const char*key, void*val), void*data)
+{
+ int t;
+ for(t=0;t<h->hashsize;t++) {
+ dictentry_t*e = h->slots[t];
+ while(e) {
+ dictentry_t*next = e->next;
+ if(runFunction) {
+ char*s = strdup_n(e->s, e->len); //append \0
+ runFunction(data, s, e->data);
+ rfx_free(s);
+ }
+ e = e->next;
+ }
+ }
+}
+void dict_foreach_value(dict_t*h, void (*runFunction)(void*))
+{
+ int t;
+ for(t=0;t<h->hashsize;t++) {
+ dictentry_t*e = h->slots[t];
+ while(e) {
+ dictentry_t*next = e->next;
+ if(runFunction) {
+ runFunction(e->data);
+ }
+ e = e->next;
+ }
+ }
+}
+
+void dict_free_all(dict_t*h, void (*freeFunction)(void*))
+{
+ int t;
+ for(t=0;t<h->hashsize;t++) {
+ dictentry_t*e = h->slots[t];
+ while(e) {
+ dictentry_t*next = e->next;
+ rfx_free((void*)e->s);
+ if(freeFunction) {
+ freeFunction(e->data);
+ }
+ memset(e, 0, sizeof(dictentry_t));
+ rfx_free(e);
+ e = next;
+ }
+ }
+ rfx_free(h->slots);
+ memset(h, 0, sizeof(dict_t));
+}
+
+void dict_clear(dict_t*h)
+{
+ dict_free_all(h, 0);
+}
+
+void dict_destroy(dict_t*dict)
+{
+ dict_clear(dict);
+ rfx_free(dict);
+}
+