+dictentry_t* dict_put(dict_t*h, const void*key, void* data)
+{
+ unsigned int hash = h->key_type->hash(key);
+ dictentry_t*e = (dictentry_t*)rfx_alloc(sizeof(dictentry_t));
+
+ if(!h->hashsize)
+ dict_expand(h, 1);
+
+ unsigned int hash2 = hash % h->hashsize;
+
+ e->key = h->key_type->dup(key);
+ e->hash = hash; //for resizing
+ e->next = h->slots[hash2];
+ e->data = data;
+ h->slots[hash2] = e;
+ h->num++;
+ return e;
+}
+void dict_put2(dict_t*h, const char*s, void*data)
+{
+ assert(h->key_type == &charptr_type);
+ dict_put(h, s, 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) {
+ if(h->key_type!=&charptr_type) {
+ fprintf(fi, "%s%08x=%08x\n", prefix, e->key, e->data);
+ } else {
+ fprintf(fi, "%s%s=%08x\n", prefix, e->key, e->data);
+ }
+ e = e->next;
+ }
+ }
+}
+
+int dict_count(dict_t*h)
+{
+ return h->num;
+}
+
+static inline dictentry_t* dict_do_lookup(dict_t*h, const void*key)
+{
+ if(!h->num) {
+ return 0;
+ }
+
+ unsigned int ohash = h->key_type->hash(key);
+ unsigned int hash = ohash % h->hashsize;
+
+ /* check first entry for match */
+ dictentry_t*e = h->slots[hash];
+ if(e && h->key_type->equals(e->key, key)) {
+ return e;
+ } 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];
+ if(e && h->key_type->equals(e->key, key)) {
+ // omit move to front
+ return e;
+ } else if(e) {
+ e = e->next;
+ }
+ }
+
+ /* check subsequent entries for a match */
+ dictentry_t*last = h->slots[hash];
+ while(e) {
+ if(h->key_type->equals(e->key, key)) {
+ /* move to front- makes a difference of about 10% in most applications */
+ last->next = e->next;
+ e->next = h->slots[hash];
+ h->slots[hash] = e;
+ return e;
+ }
+ last=e;
+ e = e->next;
+ }
+ return 0;
+}
+void* dict_lookup(dict_t*h, const void*key)
+{
+ dictentry_t*e = dict_do_lookup(h, key);
+ if(e)
+ return e->data;
+ return 0;
+}
+char dict_contains(dict_t*h, const void*key)
+{
+ dictentry_t*e = dict_do_lookup(h, key);
+ return !!e;
+}
+
+char dict_del(dict_t*h, const void*key)
+{
+ if(!h->num)
+ return 0;
+ unsigned int hash = h->key_type->hash(key) % h->hashsize;
+ dictentry_t*head = h->slots[hash];
+ dictentry_t*e = head, *prev=0;
+ while(e) {
+ if(h->key_type->equals(e->key, key)) {
+ dictentry_t*next = e->next;
+ h->key_type->free(e->key);
+ memset(e, 0, sizeof(dictentry_t));
+ rfx_free(e);
+ if(e == head) {
+ h->slots[hash] = next;
+ } else {
+ assert(prev);
+ prev->next = next;
+ }
+ h->num--;
+ return 1;
+ }
+ prev = e;
+ e = e->next;
+ }
+ return 0;
+}
+
+char dict_del2(dict_t*h, const void*key, void*data)
+{
+ if(!h->num)
+ return 0;
+ unsigned int hash = h->key_type->hash(key) % h->hashsize;
+ dictentry_t*head = h->slots[hash];
+ dictentry_t*e = head, *prev=0;
+ while(e) {
+ if(h->key_type->equals(e->key, key) && e->data == data) {
+ dictentry_t*next = e->next;
+ h->key_type->free(e->key);
+ memset(e, 0, sizeof(dictentry_t));
+ rfx_free(e);
+ if(e == head) {
+ h->slots[hash] = next;
+ } else {
+ assert(prev);
+ prev->next = next;
+ }
+ h->num--;
+ return 1;
+ }
+ prev = e;
+ e = e->next;
+ }
+ return 0;
+}
+
+dictentry_t* dict_get_slot(dict_t*h, const void*key)
+{
+ if(!h->num)
+ return 0;
+ unsigned int ohash = h->key_type->hash(key);
+ unsigned int hash = ohash % h->hashsize;
+ return h->slots[hash];
+}
+
+void dict_foreach_keyvalue(dict_t*h, void (*runFunction)(void*data, const void*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) {
+ runFunction(data, e->key, e->data);
+ }
+ 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, char free_keys, void (*free_data_function)(void*))
+{
+ int t;
+ for(t=0;t<h->hashsize;t++) {
+ dictentry_t*e = h->slots[t];
+ while(e) {
+ dictentry_t*next = e->next;
+ if(free_keys) {
+ h->key_type->free(e->key);
+ }
+ if(free_data_function) {
+ free_data_function(e->data);
+ }
+ memset(e, 0, sizeof(dictentry_t));
+ rfx_free(e);
+ e = next;
+ }
+ h->slots[t]=0;
+ }
+ rfx_free(h->slots);
+ memset(h, 0, sizeof(dict_t));
+}
+
+void dict_clear_shallow(dict_t*h)
+{
+ dict_free_all(h, 0, 0);
+}
+
+void dict_clear(dict_t*h)
+{
+ dict_free_all(h, 1, 0);
+}
+
+void dict_destroy_shallow(dict_t*dict)
+{
+ dict_clear_shallow(dict);
+ rfx_free(dict);
+}
+
+void dict_destroy(dict_t*dict)
+{
+ if(!dict)
+ return;
+ dict_clear(dict);
+ rfx_free(dict);
+}