Mercurial > repos > rhope
diff dict.c @ 0:76568becd6d6
Rhope Alpha 2a source import
author | Mike Pavone <pavone@retrodev.com> |
---|---|
date | Tue, 28 Apr 2009 23:06:07 +0000 |
parents | |
children | 94c885692eb5 |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/dict.c Tue Apr 28 23:06:07 2009 +0000 @@ -0,0 +1,475 @@ +#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; + 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; + } + 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; + } + 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 + { + if(current->next >= 0) + { + //APPEND_KEY_STORE(key, key_store, key_size, current->letter); + decision = current;//nodes + current->next; + decision_key_size = key_size; + next_flag = TRUE; + } + else if(current->right >= 0) + { + decision = nodes + current->right; + decision_key_size = key_size; + next_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; +} + + +