From 1639f7ce5fa0708bf579d4e83890ff2708f9b1a9 Mon Sep 17 00:00:00 2001 From: "Mike D. Lowis" Date: Tue, 7 Apr 2015 14:35:10 -0400 Subject: [PATCH] Started implementation of splaytree for pointer lookups --- source/runtime/heap.c | 70 ++++++++++++----------- source/runtime/splaytree.c | 113 +++++++++++++++++++++++-------------- source/runtime/splaytree.h | 22 +++++--- tests/test_splaytree.c | 3 +- 4 files changed, 125 insertions(+), 83 deletions(-) diff --git a/source/runtime/heap.c b/source/runtime/heap.c index 66ab2cd..f4be807 100644 --- a/source/runtime/heap.c +++ b/source/runtime/heap.c @@ -90,41 +90,47 @@ void heap_finish_collection(heap_t* heap) } static void* subheap_find_and_mark(heap_t* heap, uintptr_t addr) { - void* obj = NULL; - for (uintptr_t i = 0; i < NUM_HEAP_STACKS; i++) { - for(segment_t* curr = heap->heaps[i].available; curr != NULL; curr = curr->next) { - obj = segment_find_and_mark(heap->heaps[i].available, addr); - if (NULL != obj) { - i = NUM_HEAP_STACKS; - break; - } - } - } - return obj; +// void* obj = NULL; +// for (uintptr_t i = 0; i < NUM_HEAP_STACKS; i++) { +// for(segment_t* curr = heap->heaps[i].available; curr != NULL; curr = curr->next) { +// obj = segment_find_and_mark(heap->heaps[i].available, addr); +// if (NULL != obj) { +// i = NUM_HEAP_STACKS; +// break; +// } +// } +// } +// return obj; + (void)heap; + (void)addr; + return NULL; } static void* block_find_and_mark(heap_t* heap, uintptr_t addr) { - void* obj = NULL; - block_t* prev = NULL; - block_t* curr = heap->greylist; - while (curr != NULL) { - uintptr_t start = (uintptr_t)&(curr->data[0]); - uintptr_t end = start + curr->size; - if ((start <= addr) && (addr < end)) { - /* Remove it from the grey list */ - if (prev == NULL) - heap->greylist = curr->next; - else - prev->next = curr->next; - /* Add it to the in-use list and break */ - curr->next = heap->blocks; - heap->blocks = curr->next; - break; - } - prev = curr; - curr = curr->next; - } - return obj; +// void* obj = NULL; +// block_t* prev = NULL; +// block_t* curr = heap->greylist; +// while (curr != NULL) { +// uintptr_t start = (uintptr_t)&(curr->data[0]); +// uintptr_t end = start + curr->size; +// if ((start <= addr) && (addr < end)) { +// /* Remove it from the grey list */ +// if (prev == NULL) +// heap->greylist = curr->next; +// else +// prev->next = curr->next; +// /* Add it to the in-use list and break */ +// curr->next = heap->blocks; +// heap->blocks = curr->next; +// break; +// } +// prev = curr; +// curr = curr->next; +// } +// return obj; + (void)heap; + (void)addr; + return NULL; } void* heap_find_and_mark(heap_t* heap, uintptr_t addr) diff --git a/source/runtime/splaytree.c b/source/runtime/splaytree.c index 37d9c5d..c041843 100644 --- a/source/runtime/splaytree.c +++ b/source/runtime/splaytree.c @@ -5,13 +5,11 @@ #include "splaytree.h" #include -static node_t* create_tree(uintptr_t val) { - node_t* node = (node_t*)malloc(sizeof(node_t)); - node->value = val; - node->parent = NULL; - node->left = NULL; - node->right = NULL; - return node; +splaytree_t* splaytree_create(void) +{ + splaytree_t* splaytree = (splaytree_t*)malloc(sizeof(splaytree_t)); + splaytree->root = NULL; + return splaytree; } static void destroy_tree(node_t* node) { @@ -21,52 +19,85 @@ static void destroy_tree(node_t* node) { } } -splaytree_t* splaytree_create(comp_fn_t cfn) -{ - splaytree_t* splaytree = (splaytree_t*)malloc(sizeof(splaytree_t)); - splaytree->compare = cfn; - splaytree->root = NULL; - return splaytree; -} - void splaytree_destroy(splaytree_t* tree) { destroy_tree(tree->root); free(tree); } -void splaytree_insert(splaytree_t* tree, uintptr_t value) +static node_t* create_node(node_type_t tag, void* value) { + node_t* node = (node_t*)malloc(sizeof(node_t*)); + node->tag = tag; + node->ptr.raw = value; + node->left = NULL; + node->right = NULL; + return node; +} + +static uintptr_t get_start_addr(node_t* curr) { + if (curr->tag == SEGMENT) + return (uintptr_t)(curr->ptr.segment->start); + else + return (uintptr_t)(curr->ptr.block->data); +} + +static uintptr_t get_end_addr(node_t* curr) { + if (curr->tag == SEGMENT) + return (uintptr_t)(curr->ptr.segment->end); + else + return (uintptr_t)(curr->ptr.block->data + curr->ptr.block->size); +} + +static node_t** next_node(node_t* curr, uintptr_t address) { + uintptr_t curr_address = get_start_addr(curr); + if (address < curr_address) + return &(curr->left); + else + return &(curr->right); +} + +void splaytree_insert(splaytree_t* tree, node_type_t tag, void* value) { - if (tree->root == NULL) { - tree->root = create_tree(value); - } else { - node_t* curr = tree->root; - while (1) { - int cmp = tree->compare(value, curr->value); - if (0 == cmp) { - break; - } else if (cmp < 1) { - if (NULL == curr->left) { - curr->left = create_tree(value); - } else { - curr = curr->left; - } - } else if (cmp > 1) { - if (NULL == curr->right) { - curr->right = create_tree(value); - } else { - curr = curr->right; - } - } + /* Get the address of the start of the range */ + uintptr_t address; + if (SEGMENT == tag) + address = (uintptr_t)((segment_t*)value)->start; + else + address = (uintptr_t)((block_t*)value)->data; + /* Insert the item into the tree */ + if (tree->root == NULL) + tree->root = create_node(tag, value); + else { + node_t** current = &(tree->root); + while(*current != NULL) { + current = next_node(*current, address); } + *current = create_node(tag, value); } } -uintptr_t splaytree_lookup(splaytree_t* tree, uintptr_t value) +node_type_t splaytree_lookup(splaytree_t* tree, uintptr_t address, void** value) { - (void)tree; - (void)value; - return 0; + node_type_t tag = NONE; + node_t** current = &(tree->root); + while(*current != NULL) { + uintptr_t start = get_start_addr(*current); + uintptr_t end = get_end_addr(*current); + if ((start <= address) && (address < end)) { + *value = (*current)->ptr.raw; + break; + } else if (start < address) { + current = &((*current)->left); + } else { + current = &((*current)->right); + } + } + return tag; } +void splaytree_delete(splaytree_t* tree, uintptr_t address) +{ + (void)tree; + (void)address; +} diff --git a/source/runtime/splaytree.h b/source/runtime/splaytree.h index 2689ab0..71dc690 100644 --- a/source/runtime/splaytree.h +++ b/source/runtime/splaytree.h @@ -6,27 +6,33 @@ #define SPLAYTREE_H #include +#include "heap.h" + +typedef enum { SEGMENT, BLOCK, NONE } node_type_t; typedef struct node_t { - uintptr_t value; - struct node_t* parent; + node_type_t tag; + union { + segment_t* segment; + block_t* block; + void* raw; + } ptr; struct node_t* left; struct node_t* right; } node_t; -typedef int (*comp_fn_t)(uintptr_t key, uintptr_t cval); - typedef struct splaytree_t { - comp_fn_t compare; node_t* root; } splaytree_t; -splaytree_t* splaytree_create(comp_fn_t cfn); +splaytree_t* splaytree_create(void); void splaytree_destroy(splaytree_t* tree); -void splaytree_insert(splaytree_t* tree, uintptr_t value); +void splaytree_insert(splaytree_t* tree, node_type_t tag, void* value); + +node_type_t splaytree_lookup(splaytree_t* tree, uintptr_t address, void** value); -uintptr_t splaytree_lookup(splaytree_t* tree, uintptr_t value); +void splaytree_delete(splaytree_t* tree, uintptr_t address); #endif /* SPLAYTREE_H */ diff --git a/tests/test_splaytree.c b/tests/test_splaytree.c index 157e070..e4a783c 100644 --- a/tests/test_splaytree.c +++ b/tests/test_splaytree.c @@ -5,8 +5,7 @@ TEST_SUITE(SplayTree) { /* Verify: splaytree_create *************************************************************************/ TEST(Verify_Create_allocates_and_initializes_an_empty_tree) { - splaytree_t* tree = splaytree_create((comp_fn_t)0x1234); - CHECK(tree->compare == (comp_fn_t)0x1234); + splaytree_t* tree = splaytree_create(); CHECK(tree->root == NULL); splaytree_destroy(tree); } -- 2.52.0