/* // Full copyright information is available in the file ../doc/CREDITS */ #include "defs.h" #include "dict.h" #define MALLOC_DELTA 0 #define HASHTAB_STARTING_SIZE 8 INTERNAL void insert_key(cDict *dict, Int i); INTERNAL Int search(cDict *dict, cData *key); INTERNAL void double_hashtab_size(cDict *dict); cDict *dict_new(cList *keys, cList *values) { cDict *cnew; Int i, j; /* Construct a new dictionary. */ cnew = EMALLOC(cDict, 1); cnew->keys = list_dup(keys); cnew->values = list_dup(values); /* Calculate initial size of chain and hash table. */ cnew->hashtab_size = HASHTAB_STARTING_SIZE; while (cnew->hashtab_size < keys->len) cnew->hashtab_size = cnew->hashtab_size * 2 + MALLOC_DELTA; /* Initialize chain entries and hash table. */ cnew->links = EMALLOC(Int, cnew->hashtab_size); cnew->hashtab = EMALLOC(Int, cnew->hashtab_size); for (i = 0; i < cnew->hashtab_size; i++) { cnew->links[i] = -1; cnew->hashtab[i] = -1; } /* Insert the keys into the hash table, eliminating duplicates. */ i = j = 0; while (i < cnew->keys->len) { if (i != j) { cnew->keys->el[j] = cnew->keys->el[i]; cnew->values->el[j] = cnew->values->el[i]; } if (search(cnew, &keys->el[i]) == F_FAILURE) { insert_key(cnew, j++); } else { data_discard(&cnew->keys->el[i]); data_discard(&cnew->values->el[i]); } i++; } cnew->keys->len = cnew->values->len = j; cnew->refs = 1; return cnew; } cDict *dict_new_empty(void) { cList *l1, *l2; cDict *dict; l1 = list_new(0); l2 = list_new(0); dict = dict_new(l1, l2); list_discard(l1); list_discard(l2); return dict; } cDict *dict_from_slices(cList *slices) { cList *keys, *values; cDict *dict; cData *d; /* Make lists for keys and values. */ keys = list_new(list_length(slices)); values = list_new(list_length(slices)); for (d = list_first(slices); d; d = list_next(slices, d)) { if (d->type != LIST || list_length(d->u.list) != 2) { /* Invalid slice. Throw away what we had and return NULL. */ list_discard(keys); list_discard(values); return NULL; } keys = list_add(keys, list_elem(d->u.list, 0)); values = list_add(values, list_elem(d->u.list, 1)); } /* Slices were all valid; return new dict. */ dict = dict_new(keys, values); list_discard(keys); list_discard(values); return dict; } cDict *dict_dup(cDict *dict) { dict->refs++; return dict; } void dict_discard(cDict *dict) { dict->refs--; if (!dict->refs) { list_discard(dict->keys); list_discard(dict->values); efree(dict->links); efree(dict->hashtab); efree(dict); } } Int dict_cmp(cDict *dict1, cDict *dict2) { if (list_cmp(dict1->keys, dict2->keys) == 0 && list_cmp(dict1->values, dict2->values) == 0) return 0; else return 1; } cDict *dict_add(cDict *dict, cData *key, cData *value) { Int pos; dict = dict_prep(dict); /* Just replace the value for the key if it already exists. */ pos = search(dict, key); if (pos != F_FAILURE) { dict->values = list_replace(dict->values, pos, value); return dict; } /* Add the key and value to the list. */ dict->keys = list_add(dict->keys, key); dict->values = list_add(dict->values, value); /* Check if we should resize the hash table. */ if (dict->keys->len > dict->hashtab_size) double_hashtab_size(dict); else insert_key(dict, dict->keys->len - 1); return dict; } /* Error-checking is the caller's responsibility; this routine assumes that it * will find the key in the dictionary. */ cDict *dict_del(cDict *dict, cData *key) { Int ind, *ip, i = -1, j; dict = dict_prep(dict); /* Search for a pointer to the key, either in the hash table entry or in * the chain links. */ ind = data_hash(key) % dict->hashtab_size; for (ip = &dict->hashtab[ind];; ip = &dict->links[*ip]) { i = *ip; if (data_cmp(&dict->keys->el[i], key) == 0) break; } /* Delete the element from the keys and values lists. */ dict->keys = list_delete(dict->keys, i); dict->values = list_delete(dict->values, i); /* Replace the pointer to the key index with the next link. */ *ip = dict->links[i]; /* Copy the links beyond i backward. */ MEMMOVE(dict->links + i, dict->links + i + 1, dict->keys->len - i); dict->links[dict->keys->len] = -1; /* Since we've renumbered all the elements beyond i, we have to check * all the links and hash table entries. If they're greater than i, * decrement them. Skip this step if the element we removed was the last * one. */ if (i < dict->keys->len) { for (j = 0; j < dict->keys->len; j++) { if (dict->links[j] > i) dict->links[j]--; } for (j = 0; j < dict->hashtab_size; j++) { if (dict->hashtab[j] > i) dict->hashtab[j]--; } } return dict; } Long dict_find(cDict *dict, cData *key, cData *ret) { Int pos; pos = search(dict, key); if (pos == F_FAILURE) return keynf_id; data_dup(ret, &dict->values->el[pos]); return NOT_AN_IDENT; } Int dict_contains(cDict *dict, cData *key) { Int pos; pos = search(dict, key); return (pos != F_FAILURE); } cList *dict_values(cDict *dict) { return list_dup(dict->values); } cList *dict_keys(cDict *dict) { return list_dup(dict->keys); } cList *dict_key_value_pair(cDict *dict, Int i) { cList *l; if (i >= dict->keys->len) return NULL; l = list_new(2); l->len = 2; data_dup(&l->el[0], &dict->keys->el[i]); data_dup(&l->el[1], &dict->values->el[i]); return l; } cStr *dict_add_literal_to_str(cStr *str, cDict *dict, Bool objnames) { Int i; str = string_add_chars(str, "#[", 2); for (i = 0; i < dict->keys->len; i++) { str = string_addc(str, '['); str = data_add_literal_to_str(str, &dict->keys->el[i], objnames); str = string_add_chars(str, ", ", 2); str = data_add_literal_to_str(str, &dict->values->el[i], objnames); str = string_addc(str, ']'); if (i < dict->keys->len - 1) str = string_add_chars(str, ", ", 2); } return string_addc(str, ']'); } cDict *dict_prep(cDict *dict) { cDict *cnew; if (dict->refs == 1) return dict; /* Duplicate the old dictionary. */ cnew = EMALLOC(cDict, 1); cnew->keys = list_dup(dict->keys); cnew->values = list_dup(dict->values); cnew->hashtab_size = dict->hashtab_size; cnew->links = EMALLOC(Int, cnew->hashtab_size); MEMCPY(cnew->links, dict->links, cnew->hashtab_size); cnew->hashtab = EMALLOC(Int, cnew->hashtab_size); MEMCPY(cnew->hashtab, dict->hashtab, cnew->hashtab_size); dict->refs--; cnew->refs = 1; return cnew; } INTERNAL void insert_key(cDict *dict, Int i) { Int ind; ind = data_hash(&dict->keys->el[i]) % dict->hashtab_size; dict->links[i] = dict->hashtab[ind]; dict->hashtab[ind] = i; } INTERNAL Int search(cDict *dict, cData *key) { Int ind, i; ind = data_hash(key) % dict->hashtab_size; for (i = dict->hashtab[ind]; i != -1; i = dict->links[i]) { if (data_cmp(&dict->keys->el[i], key) == 0) return i; } return F_FAILURE; } Int dict_size(cDict *dict) { return list_length(dict->keys); } INTERNAL void double_hashtab_size(cDict *dict) { Int i; dict->hashtab_size = dict->hashtab_size * 2 + MALLOC_DELTA; dict->links = EREALLOC(dict->links, Int, dict->hashtab_size); dict->hashtab = EREALLOC(dict->hashtab, Int, dict->hashtab_size); for (i = 0; i < dict->hashtab_size; i++) { dict->links[i] = -1; dict->hashtab[i] = -1; } for (i = 0; i < dict->keys->len; i++) insert_key(dict, i); } /* WARNING: This will discard both arguments! */ cDict *dict_union (cDict *d1, cDict *d2) { int i, pos; Bool swap; if (d1->keys->len > d2->keys->len) { cDict *t; t=d1; d1=d2; d2=t; swap = NO; } else { swap = YES; } d2=dict_prep(d2); for (i=0; i<d1->keys->len; i++) { cData *key=&d1->keys->el[i], *value=&d1->values->el[i]; pos = search(d2, key); /* forget the add if it's already there */ if (pos != F_FAILURE) { /* ... but if the args are in the wrong order, we want to overwrite the key */ if (swap) d2->values = list_replace(d2->values, pos, value); continue; } /* Add the key and value to the list. */ d2->keys = list_add(d2->keys, key); d2->values = list_add(d2->values, value); /* Check if we should resize the hash table. */ if (d2->keys->len > d2->hashtab_size) double_hashtab_size(d2); else insert_key(d2, d2->keys->len - 1); } dict_discard(d1); return d2; }