Created
April 17, 2018 01:57
-
-
Save prhiggins/01e8dd3076a02625c21bf5f0016b100f to your computer and use it in GitHub Desktop.
binary search tree in C
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include "tldmap.h" | |
| #include <stdlib.h> | |
| #include <string.h> | |
| struct tldnode { | |
| char* tld; | |
| long value; | |
| TLDNode* parent; | |
| TLDNode* left; | |
| TLDNode* right; | |
| }; | |
| typedef struct map_data { | |
| int nitems; | |
| TLDNode* root; | |
| } Map_Data; | |
| static int map_insert(const TLDMap *tld, char *theTLD, long v) { | |
| Map_Data* mdata = (Map_Data*)tld->self; | |
| TLDNode* root = mdata->root; | |
| TLDNode* x = (TLDNode*)malloc(sizeof(TLDNode)); | |
| x->parent = NULL; | |
| x->left = NULL; | |
| x->right = NULL; | |
| if (x != NULL) { | |
| x->tld = strdup(theTLD); | |
| x->value = v; | |
| } | |
| TLDNode* y = NULL; | |
| TLDNode* z = root; | |
| while (z != NULL) { | |
| y = z; | |
| if (strcmp(x->tld, z->tld) < 0) { | |
| z = z->left; | |
| } | |
| else if (strcmp(x->tld, z->tld) == 0) { | |
| return 0; | |
| } | |
| else { | |
| z = z->right; | |
| } | |
| } | |
| x->parent = y; | |
| if (y == NULL) { | |
| root = x; | |
| } | |
| else if (strcmp(x->tld, y->tld) < 0) { | |
| y->left = x; | |
| } | |
| else { | |
| y->right = x; | |
| } | |
| mdata->nitems += 1; | |
| mdata->root = root; | |
| return 1; | |
| } | |
| static int map_reassign(const TLDMap *tld, char *theTLD, long v) { | |
| Map_Data* mdata = (Map_Data*)tld->self; | |
| TLDNode* root = mdata->root; | |
| TLDNode* x = root; | |
| while (x != NULL && strcmp(x->tld, theTLD) != 0) { | |
| if (strcmp(theTLD, x->tld) < 0) { | |
| x = x->left; | |
| } | |
| else { | |
| x = x->right; | |
| } | |
| } | |
| if (x != NULL) { | |
| x->value = v; | |
| return 1; | |
| } | |
| else { | |
| return 0; | |
| } | |
| } | |
| static int map_lookup(const TLDMap *tld, char *theTLD, long *v) { | |
| Map_Data* mdata = (Map_Data*)tld->self; | |
| TLDNode* root = mdata->root; | |
| TLDNode* x = root; | |
| while (x != NULL && strcmp(x->tld, theTLD) != 0) { | |
| if (strcmp(theTLD, x->tld) < 0) { | |
| x = x->left; | |
| } | |
| else { | |
| x = x->right; | |
| } | |
| } | |
| if (x != NULL) { | |
| *v = x->value; | |
| return 1; | |
| } | |
| else { | |
| return 0; | |
| } | |
| } | |
| static void map_inorder(const TLDMap* tld, TLDNode* node, TLDNode*** array, int* index) { | |
| if (node != NULL) { | |
| map_inorder(tld, node->left, array, index); | |
| (*array)[*index] = node; | |
| *index += 1; | |
| map_inorder(tld, node->right, array, index); | |
| } | |
| } | |
| static const Iterator* map_iterator(const TLDMap *tld) { | |
| Map_Data* md = (Map_Data*)tld->self; | |
| int length = md->nitems; | |
| if (length == 0) { | |
| return NULL; | |
| } | |
| TLDNode** nodes = malloc(sizeof(TLDNode*) * length); | |
| int index = 0; | |
| map_inorder(tld, md->root, &nodes, &index); | |
| return Iterator_create(length, (void**)nodes); | |
| } | |
| static void map_recursive_delete(const TLDMap* tld, TLDNode* node) { | |
| if (node != NULL) { | |
| map_recursive_delete(tld, node->left); | |
| map_recursive_delete(tld, node->right); | |
| free(node->tld); | |
| free(node); | |
| } | |
| } | |
| static void map_destroy(const TLDMap *tld) { | |
| Map_Data* md = (Map_Data*)tld->self; | |
| map_recursive_delete(tld, md->root); | |
| free(md); | |
| free((void*)tld); | |
| } | |
| const TLDMap* TLDMap_create(void) { | |
| TLDMap* map = (TLDMap*)malloc(sizeof(TLDMap)); | |
| if (map != NULL) { | |
| Map_Data* mdata = (Map_Data*)malloc(sizeof(Map_Data)); | |
| mdata->root = NULL; | |
| map->self = mdata; | |
| } | |
| map->insert = map_insert; | |
| map->reassign = map_reassign; | |
| map->lookup = map_lookup; | |
| map->itCreate = map_iterator; | |
| map->destroy = map_destroy; | |
| return map; | |
| } | |
| char *TLDNode_tldname(TLDNode *node) { | |
| return node->tld; | |
| } | |
| long TLDNode_count(TLDNode *node) { | |
| return node->value; | |
| } |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #ifndef _TLDMAP_H_INCLUDED_ | |
| #define _TLDMAP_H_INCLUDED_ | |
| #include "date.h" | |
| #include "iterator.h" | |
| typedef struct tldmap TLDMap; | |
| typedef struct tldnode TLDNode; | |
| /* | |
| * TLDMap_create generates a map structure for storing counts against | |
| * top level domains (TLDs) | |
| * | |
| * creates an empty TLDMap | |
| * returns a pointer to the list if successful, NULL if not | |
| */ | |
| const TLDMap *TLDMap_create(void); | |
| struct tldmap { | |
| void *self; /* instance specific data */ | |
| /* | |
| * destroy() destroys the list structure in `tld' | |
| * | |
| * all heap allocated storage associated with the map is returned to the heap | |
| */ | |
| void (*destroy)(const TLDMap *tld); | |
| /* | |
| * insert() inserts the key-value pair (theTLD, v) into the map; | |
| * returns 1 if the pair was added, returns 0 if there already exists en | |
| * entry corresponding to TLD | |
| */ | |
| int (*insert)(const TLDMap *tld, char *theTLD, long v); | |
| /* | |
| * reassign() replaces the current value corresponding to theTLD in the | |
| * map with v. | |
| * returns 1 if the value was replaced, returns 0 if no such key exists | |
| */ | |
| int (*reassign)(const TLDMap *tld, char *theTLD, long v); | |
| /* | |
| * lookup() returns the current value associated with theTLD in *v | |
| * returns 1 if the lookup was successful, returns 0 if no such key exists | |
| */ | |
| int (*lookup)(const TLDMap *tld, char *theTLD, long *v); | |
| /* | |
| * itCreate() creates an iterator over the map | |
| * returns the iterator if successful, NULL if unsuccessful | |
| */ | |
| const Iterator *(*itCreate)(const TLDMap *tld); | |
| }; | |
| /* | |
| * TLDNode_tldname returns the tld associated with the TLDNode | |
| */ | |
| char *TLDNode_tldname(TLDNode *node); | |
| /* | |
| * TLDNode_count returns the value currently associated with that TLD | |
| */ | |
| long TLDNode_count(TLDNode *node); | |
| #endif /* _TLDMAP_H_INCLUDED_ */ |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment