Mercurial > repos > rhope
view dict.c @ 75:0083b2f7b3c7
Partially working implementation of List. Modified build scripts to allow use of other compilers. Fixed some bugs involving method implementations on different types returning different numbers of outputs. Added Fold to the 'builtins' in the comipler.
author | Mike Pavone <pavone@retrodev.com> |
---|---|
date | Tue, 06 Jul 2010 07:52:59 -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; }