Mercurial > repos > rhope
view dict.c @ 32:9ee9adc696e7
Merged changes
author | Mike Pavone <pavone@retrodev.com> |
---|---|
date | Mon, 28 Sep 2009 19:49:06 -0400 |
parents | 94c885692eb5 |
children |
line wrap: on
line source
#include "datum.h" #include "structs.h" #include "debugmacros.h" #include <string.h> #include <stdlib.h> //Index, Swap, Remove, Set, Length, New ternary_node * find_node(datum * dict, datum * key, BOOL novalue) { int i = 0; ternary_node * nodes; ternary_node * current = ((dict_data *)dict->c.generic.data)->nodes; nodes = current; if(((dict_data *)dict->c.generic.data)->num_nodes <= 0 || key->c.generic.len <= 1) return NULL; while(current >= nodes) { DEBUGPRINTF("current->letter: %c, key[%d]: %c\n", current->letter, i, ((char*)key->c.generic.data)[i]); if(((char*)key->c.generic.data)[i] == current->letter) if(i == (key->c.generic.len-2)) if(current->payload || novalue) return current; else return NULL; else { current = nodes + current->next; ++i; } else if(((char *)key->c.generic.data)[i] > current->letter) current = nodes + current->right; else current = nodes + current->left; } return NULL; } int vis_dict_index(datum ** inputlist, queue_entry * worker_entry) { datum * output; int i = 0; ternary_node * found = find_node(inputlist[0], inputlist[1], FALSE); release_ref(inputlist[1]); if(found) { DEBUGPRINTF("Found payload: %X\n", found->payload); /*if(found->payload->type == BUILTIN_TYPE_STRING) { DEBUGPRINTF("Payload: %s\n", found->payload->c.generic.data); }*/ output = add_ref(found->payload); inputlist[1] = NULL; } else { inputlist[1] = new_datum(BUILTIN_TYPE_YESNO, 2, 0, worker_entry->instance->def->program); inputlist[1]->c.integers.num_a = 0; output = NULL; } release_ref(inputlist[0]); inputlist[0] = output; return 0; } int vis_dict_swap(datum ** inputlist, queue_entry * worker_entry) { ternary_node *first, *second; datum * temp; inputlist[0] = copy_datum(inputlist[0],0); first = find_node(inputlist[0], inputlist[1], FALSE); if(first) { second = find_node(inputlist[0], inputlist[2], FALSE); if(second) { temp = first->payload; first->payload = second->payload; second->payload = temp; } } release_ref(inputlist[1]); release_ref(inputlist[2]); return 0; } int vis_dict_remove(datum ** inputlist, queue_entry * worker_entry) { //NOTE: Currently optimized for speed not for memory usage //Doesn't remove ternary_nodes that are no longer needed ternary_node * found; dict_data * dict; inputlist[0] = copy_datum(inputlist[0],0); found = find_node(inputlist[0], inputlist[1], FALSE); release_ref(inputlist[1]); dict = (dict_data *)inputlist[0]->c.generic.data; if(found) { release_ref(found->payload); found->payload = NULL; --(dict->num_entries); } return 0; } int vis_dict_set(datum ** inputlist, queue_entry * worker_entry) { ternary_node * found, *current, *last; dict_data * dict, *new_dict; int new_node_storage,i,dir; int newlen; //DEBUGPRINTF("Payload: %s\n", inputlist[2]->c.generic.data); inputlist[0] = copy_datum(inputlist[0],0); found = find_node(inputlist[0], inputlist[1], TRUE); dict = (dict_data *)inputlist[0]->c.generic.data; DEBUGPRINTF("key: %s\n", inputlist[1]->c.generic.data); DEBUGPRINTF("Num nodes: %d, num entries: %d\n", dict->num_nodes, dict->num_entries); if(found) { if(found->payload) release_ref(found->payload); else ++(dict->num_entries); found->payload = inputlist[2]; } else if(inputlist[1]->c.generic.len > 1) //FIXME: silently fail on zero-length keys for now { if(dict->num_nodes) { current = dict->nodes; i = 0; while(current >= dict->nodes) { DEBUGPRINTF("Current node: %X\n", current); last = current; DEBUGPRINTF("Current letter: %c, key letter: %c\n", current->letter,((char *)inputlist[1]->c.generic.data)[i]); if(((char *)inputlist[1]->c.generic.data)[i] == current->letter) { DEBUGPUTS("Went straight\n"); ++i; current = dict->nodes + current->next; dir = 0; } else if(((char *)inputlist[1]->c.generic.data)[i] > current->letter) { DEBUGPUTS("Went right\n"); current = dict->nodes + current->right; dir = 1; } else { DEBUGPUTS("Went left\n"); current = dict->nodes + current->left; dir = 2; } } DEBUGPRINTF("Matched %d out of %d characters\n", i, (inputlist[1]->c.generic.len-1)); DEBUGPRINTF("node_storage: %d, num_nodes: %d\n", dict->node_storage, dict->num_nodes); if((dict->node_storage-dict->num_nodes) < ((inputlist[1]->c.generic.len-1) - i)) { DEBUGPUTS("Allocating more storage\n"); new_node_storage = inputlist[1]->c.generic.len - 1 - i + dict->num_nodes; new_node_storage += new_node_storage >> 1; //1.5 times required storage newlen = sizeof(dict_data) + sizeof(ternary_node) * (new_node_storage-1); new_dict = malloc(newlen); DEBUGPRINTF("After malloc: new_dict = %X, size: %d, new_node_storage: %d\n", new_dict, newlen, new_node_storage); memcpy(new_dict, dict, sizeof(dict_data) + sizeof(ternary_node) * (dict->num_nodes-1)); DEBUGPUTS("After memcpyy\n"); new_dict->node_storage = new_node_storage; //new_dict->num_entries = dict->num_entries + 1; new_dict->num_nodes = dict->num_nodes; DEBUGPRINTF("last was: %X, dict->nodes was: %X, ", last, dict->nodes); last = new_dict->nodes + (last - dict->nodes); DEBUGPRINTF("last is now: %X, dict->nodes is now : %X, ", last, new_dict->nodes); VIS_FREE(dict, "dictionary object"); DEBUGPUTS("After free\n"); dict = new_dict; inputlist[0]->c.generic.data = dict; inputlist[0]->c.generic.len = newlen; } ++(dict->num_entries); DEBUGPRINTF("Setting current to: %X\n", dict->nodes + dict->num_nodes); current =dict->nodes + dict->num_nodes; DEBUGPUTS("Setting left, right and next pointer to null\n"); current->left = current->right = current->next = -1; current->payload = NULL; current->letter = ((char *)inputlist[1]->c.generic.data)[i]; DEBUGPRINTF("Setting pointer in last node (%X) to current node\n", last); if(dir == 1) last->right = dict->num_nodes; else if(dir == 2) last->left = dict->num_nodes; else last->next = dict->num_nodes; ++i; ++(dict->num_nodes); last = current; DEBUGPUTS("Entering node add loop\n"); for(;i < (inputlist[1]->c.generic.len-1); ++i) { DEBUGPRINTF("Adding node at index %d\n", dict->num_nodes); current = dict->nodes + dict->num_nodes; last->next = dict->num_nodes; current->left = current->right = current->next = -1; current->payload = NULL; current->letter = ((char *)inputlist[1]->c.generic.data)[i]; ++(dict->num_nodes); last = current; } DEBUGPUTS("Loop complete\n"); last->payload = inputlist[2]; } else { if(dict->node_storage < (inputlist[1]->c.generic.len-1)) { VIS_FREE(dict, "dictionary object"); newlen = sizeof(dict_data) + sizeof(ternary_node) * ((inputlist[1]->c.generic.len-1)<<2); dict = malloc(newlen); dict->node_storage = ((inputlist[1]->c.generic.len-1)<<2) + 1; inputlist[0]->c.generic.data = dict; inputlist[0]->c.generic.len = newlen; } dict->num_entries = 1; dict->num_nodes = (inputlist[1]->c.generic.len-1); for(i = 0; i < dict->num_nodes; ++i) { dict->nodes[i].left = dict->nodes[i].right = -1; dict->nodes[i].letter = ((char *)inputlist[1]->c.generic.data)[i]; if(i == (dict->num_nodes - 1)) { dict->nodes[i].next = -1; dict->nodes[i].payload = inputlist[2]; } else { dict->nodes[i].next = i + 1; dict->nodes[i].payload = NULL; } } } } release_ref(inputlist[1]); DEBUGPRINTF("Num nodes after set: %d\n", dict->num_nodes); //DEBUGPRINTF("Payload: %s\n", inputlist[2]->c.generic.data); return 0; } int vis_dict_length(datum ** inputlist, queue_entry * worker_entry) { datum * output; dict_data * dict = ((dict_data *)inputlist[0]->c.generic.data); output = new_datum(BUILTIN_TYPE_WHOLE, 2, 0, worker_entry->instance->def->program); output->c.integers.num_a = dict->num_entries; release_ref(inputlist[0]); inputlist[0] = output; return 0; } datum * create_dict(program * prog) { dict_data * dict; datum * dat = new_datum(BUILTIN_TYPE_DICT, 1, sizeof(dict_data) + sizeof(ternary_node)*23, prog); dict = (dict_data *)dat->c.generic.data; dict->num_entries = 0; dict->num_nodes = 0; dict->node_storage = 24; return dat; } int vis_dict_new(datum ** inputlist, queue_entry * worker_entry) { inputlist[0] = create_dict(worker_entry->instance->def->program); return 0; } #define APPEND_KEY_STORE(key, key_store, key_size, val) if(key_size == key_store) { key_store = key_store + (key_store>>1); key = realloc(key, key_store); } key[key_size++] = val int vis_dict_first(datum ** inputlist, queue_entry * worker_entry) { dict_data * dict = inputlist[0]->c.generic.data; char * key; int key_store = 128; int key_size = 0; int i = 0; ternary_node * nodes; ternary_node * current = dict->nodes; nodes = current; if(dict->num_nodes <= 0) { inputlist[1] = inputlist[0]; inputlist[0] = NULL; } else { key = malloc(128); while(1) { if(current->left >= 0) { current = nodes + current->left; } else if(current->payload) { APPEND_KEY_STORE(key, key_store, key_size, current->letter); APPEND_KEY_STORE(key, key_store, key_size, '\0'); release_ref(inputlist[0]); inputlist[0] = new_datum(BUILTIN_TYPE_STRING, 2, 0, worker_entry->instance->def->program); inputlist[0]->union_type = 1; inputlist[0]->c.generic.data = key; inputlist[0]->c.generic.len = key_size; inputlist[1] = NULL; break; } else if(current->next >= 0) { APPEND_KEY_STORE(key, key_store, key_size, current->letter); current = nodes + current->next; } else if(current->right >= 0) { current = nodes + current->right; } else { inputlist[1] = inputlist[0]; inputlist[0] = NULL; VIS_FREE(key, "dictionary key store"); break; } } } return 0; } int vis_dict_next(datum ** inputlist, queue_entry * worker_entry) { dict_data * dict = inputlist[0]->c.generic.data; char * key; char * old_key = inputlist[1]->c.generic.data; int old_key_len = inputlist[1]->c.generic.len-2; int key_store = inputlist[1]->c.generic.len; int key_size = 0; int i = 0; ternary_node * nodes; ternary_node * current = dict->nodes; ternary_node * decision = NULL; int decision_key_size; BOOL next_flag = FALSE; BOOL this_flag = FALSE; nodes = current; if(dict->num_nodes <= 0) { release_ref(inputlist[1]); inputlist[1] = inputlist[0]; inputlist[0] = NULL; return 0; } else { key = malloc(key_store); while(current >= nodes) { if(old_key[i] == current->letter) if(i == (old_key_len)) { /*if(current->left >= 0) { current = nodes + current->left; break; } else */if(current->next >= 0) { APPEND_KEY_STORE(key, key_store, key_size, current->letter); current = nodes + current->next; break; } else if(current->right >= 0) { current = nodes + current->right; break; } else { if(decision) { key_size = decision_key_size; current = decision; if(next_flag) { APPEND_KEY_STORE(key, key_store, key_size, current->letter); current = nodes + current->next; } else if(this_flag) { APPEND_KEY_STORE(key, key_store, key_size, current->letter); APPEND_KEY_STORE(key, key_store, key_size, '\0'); release_ref(inputlist[0]); release_ref(inputlist[1]); inputlist[1] = NULL; inputlist[0] = new_datum(BUILTIN_TYPE_STRING, 2, 0, worker_entry->instance->def->program); inputlist[0]->union_type = 1; inputlist[0]->c.generic.data = key; inputlist[0]->c.generic.len = key_size; return 0; } break; } else { VIS_FREE(key, "dictionary key store"); release_ref(inputlist[1]); inputlist[1] = inputlist[0]; inputlist[0] = NULL; return 0; } } } else { if(current->right >= 0) { decision = nodes + current->right; decision_key_size = key_size; next_flag = FALSE; this_flag = FALSE; } APPEND_KEY_STORE(key, key_store, key_size, current->letter); ++i; current = nodes + current->next; } else if(old_key[i] > current->letter) current = nodes + current->right; else { //Hmm, what do I do here if there's a payload at this location? if(current->next >= 0 || current->payload) { //APPEND_KEY_STORE(key, key_store, key_size, current->letter); decision = current;//nodes + current->next; decision_key_size = key_size; if(current->payload) { next_flag = FALSE; this_flag = TRUE; } else { next_flag = TRUE; this_flag = FALSE; } } else if(current->right >= 0) { decision = nodes + current->right; decision_key_size = key_size; next_flag = FALSE; this_flag = FALSE; } current = nodes + current->left; } } if(current < nodes) { VIS_FREE(key, "dictionary key store"); release_ref(inputlist[1]); inputlist[1] = inputlist[0]; inputlist[0] = NULL; return 0; } while(1) { if(current->left >= 0) { current = nodes + current->left; } else if(current->payload) { APPEND_KEY_STORE(key, key_store, key_size, current->letter); APPEND_KEY_STORE(key, key_store, key_size, '\0'); release_ref(inputlist[0]); release_ref(inputlist[1]); inputlist[1] = NULL; inputlist[0] = new_datum(BUILTIN_TYPE_STRING, 2, 0, worker_entry->instance->def->program); inputlist[0]->union_type = 1; inputlist[0]->c.generic.data = key; inputlist[0]->c.generic.len = key_size; break; } else if(current->next >= 0) { APPEND_KEY_STORE(key, key_store, key_size, current->letter); current = nodes + current->next; } else if(current->right >= 0) { current = nodes + current->right; } else { release_ref(inputlist[1]); inputlist[1] = inputlist[0]; inputlist[0] = NULL; VIS_FREE(key, "dictionary key store"); break; } } } return 0; }