diff options
| -rw-r--r-- | Makefile | 7 | ||||
| -rw-r--r-- | ll.c | 1 | ||||
| -rw-r--r-- | main.c | 8 | ||||
| -rw-r--r-- | nodelink.c | 44 | ||||
| -rw-r--r-- | nodelink.h | 20 | ||||
| -rw-r--r-- | read.c | 102 | ||||
| -rw-r--r-- | strbst.c | 130 | ||||
| -rw-r--r-- | strbst.h | 8 |
8 files changed, 208 insertions, 112 deletions
@@ -1,8 +1,13 @@ .POSIX: -OBJS = strbst.o +OBJS = strbst.o ll.o nodelink.o read.o main.o CFLAGS = -Wall -pedantic +CC = gcc tmplt: $(OBJS) $(CC) $(CFLAGS) $(LDFLAGS) $(OBJS) -o $@ clean: rm -f $(OBJS) inter strbst.o: strbst.c strbst.h +ll.o: ll.c ll.h +nodelink.o: nodelink.c nodelink.h strbst.h +read.o: read.c read.h strbst.h nodelink.h +main.o: main.c @@ -5,5 +5,6 @@ llnode* appendll(llnode* tail, char* str){ llnode* new = malloc(sizeof(llnode)); if (tail != NULL) tail->next = new; new->str = str; + new->next = NULL; return new; } @@ -0,0 +1,8 @@ +#include <stdio.h> + +#include "read.h" + +int main() { + node* root = readfile("template"); + printnode(root); +} diff --git a/nodelink.c b/nodelink.c new file mode 100644 index 0000000..ad6beb3 --- /dev/null +++ b/nodelink.c @@ -0,0 +1,44 @@ +#include <stdlib.h> +#include <stdio.h> + +#include "nodelink.h" +#include "strbst.h" + +node* newnode(void) { + node* new = malloc(sizeof(node)); + new->links = newbst(); + return new; +} + +link* newlink(node* to) { + link* new = malloc(sizeof(link)); + new->desc = ""; // preferred to NULL because it can be printed + new->to = to; + return new; +} + +static void printlink(char* name, link* conn) { + if (conn->desc[0]) + printf("Link to %s: %s", name, conn->desc); + else + printf("Link to %s", name); +} + +static void printeach(strbstnode* loc, char reprint) { + if (loc == NULL) return; + // loc->ind is the name of the connection and loc->data the link + if (!reprint) printf(" "); // indent on subnode + printlink(loc->ind, loc->data); // prints it + if (reprint) { // and their subnodes if iterating over root tree + printf("subnodes:\n"); + // prints the link's target's link tree + printeach( ( (link*)loc->data)->to->links->head, 0); + } + printeach(loc->left, reprint); + printeach(loc->right, reprint); // recursion +} + +void printnode(node* root) { + printf("Root node\n"); + printeach(root->links->head, 1); +} diff --git a/nodelink.h b/nodelink.h new file mode 100644 index 0000000..a1d5eed --- /dev/null +++ b/nodelink.h @@ -0,0 +1,20 @@ +#ifndef __NODELINK_H__ +#define __NODELINK_H__ + +#include "strbst.h" + +typedef struct node { + strbst* links; +} node; + +typedef struct link { + char* desc; + node* to; +} link; + +node* newnode(void); +link* newlink(node* to); + +void printnode(node* root); + +#endif @@ -9,103 +9,111 @@ #include "ll.h" void consumespaces(FILE* file) { + // used to consume spaces in an item ("- list item" -> "list item") int c; - while ( ( c = fgetc(file) ) != EOF && c != ' ' ); + while ( ( c = fgetc(file) ) != EOF && c == ' ' ); ungetc(c, file); } -void wsclean(char* str, size_t sz) { // - bool nl = false; - if (str[sz] == '\n') { - sz--; - nl = true; - } +void wsclean(char* txt, size_t sz){ // "string \n \n" -> "string\n\n" + int nl = 0; // count of newlines size_t i; - for (i = sz-1; i >= 0 && str[i] == ' '; i--); - if (nl) { - str[i+1] = '\n'; - str[i+2] = 0; - } else { - str[i+1] = 0; + for (i = sz-1; i >= 0; i--) { // start at end [i-1] and dec + if (txt[i] == '\n') nl++; // count up newlines + else if (txt[i] != ' ') break; // and break on unpadded text } - + memset(txt+i, '\n', nl); // add #nl newlines at [i, i+nl) + txt[i+nl] = 0; // finish string } char* empty(void) { + // "" with a freeable memory address char* str = malloc(sizeof(char)); *str = 0; return str; } -char* line(FILE* file) { +char* line(FILE* file) { // gets a line from file char* link = NULL; - size_t n; - getline(&link, &n, file); - wsclean(link, n); - if (*link == '\n') { + size_t n = 0; + getline(&link, &n, file); // getline stores a line of size n in link + wsclean(link, n); // removes trailing whitespace + if (*link == '\n') { // empty line treated as "" free(link); - link = empty(); + char* out = empty(); // DEBGUGU + return out; + } else { // else return obtained + return link; } - return link; } link* insorget(strbst* tgt, char* name) { link* get = query(tgt, name); - if (!(*get)) { + if (!get) { get = newlink(newnode()); insbst(tgt, name, get); } return get; } -char* getdesc(FILE* file) { - int c; - size_t sz; - llnode *head, *tail; - head = tail = appendll(NULL, NULL); - while ( (c = getc()) != EOF && c != ':' && c != '-' ) { - tail = tail->next = appendll(tail, line()); - sz += strlen(tail->str); // this should be traced but I haven't - } - if (c != EOF) ungetc(c, file); - tail = head->next; free(head); +link* addbstlink(strbst* tree, char* name, node* to) { + link* l = newlink(to); + insbst(tree, name, l); + return l; +} + +char* resolvell(llnode* head, size_t* sz) { + llnode* tail = head->next; + head->next = NULL; char *out, *pos; - pos = out = malloc(sizeof(char)*(sz+1)); out[sz] = 0; + pos = out = malloc(sizeof(char)*(*sz+1)); out[*sz] = 0; + *sz = 0; while (tail != NULL) { size_t len = strlen(tail->str); memcpy(pos, tail->str, len); pos += len; llnode* tmp = tail; tail = tail->next; - free(tmp); free(tmp->str); + free(tmp->str); free(tmp); } - return pos; + return out; } node* readfile(char* name) { FILE* read = fopen(name, "r"); node *root, *cur; cur = root = newnode(); - link* curl = insbst(root->links, name, root); - // getline - while ( ( int c = fgetc(read) ) != EOF ) { + link* curl = addbstlink(root->links, name, root); + + llnode start; + start.next = NULL; // empty desc isn't undefined + llnode *head, *tail; + head = tail = &start; + size_t sz = 0; + + int c; + while ( ( c = fgetc(read) ) != EOF ) { + if (c == ':' || c == '-') { + curl->desc = resolvell(head, &sz); + consumespaces(read); + } switch (c) { case ':': - consumespaces(file); - curl = insorget(root->links, line()); + curl = insorget(root->links, line(read)); cur = curl->to; break; - case '-': - consumespaces(file); - char* lname = line(); - curl = insbst(cur->links, lname, - insorget(root->links, lname)->to); + case '-': ; + char* lname = line(read); + node* at = insorget(root->links, lname)->to; + curl = addbstlink(cur->links, lname, at); break; default: ungetc(c, read); - curl->desc = getdesc(); + case '.': + tail = appendll(tail, line(read)); + sz += strlen(tail->str); break; } } @@ -3,18 +3,21 @@ #include <stdio.h> #include "strbst.h" +/* +strbst defines strbst with one member: strbstnode->head. +strbstnode has left, right, data, ind, and ht for avl balancing +*/ #define max(a,b) ((a > b) ? a : b) #define min(a,b) ((a < b) ? a : b) typedef char height; strbst* newbst(void) { - strbst* out = malloc(sizeof(strbst)); - out->head = NULL; - return out; + return calloc(sizeof(strbst),1); } -static strbstnode* newbstnode(char* ind, void* data) { // does not ins +static strbstnode* newbstnode(char* ind, void* data) { + // Doesn't insert, just allocates strbstnode* out = malloc(sizeof(strbstnode)); out->ind = ind; out->data = data; @@ -23,35 +26,69 @@ static strbstnode* newbstnode(char* ind, void* data) { // does not ins return out; } -int getht(strbstnode* node) { - return node ? node->ht : -1; +// A nonexistent node has height of -1 so that childless nodes are ht 0. +#define getht(node) ( (node) ? node->ht : -1 ) + +// The basic (and only) balancing operations for AVL: rotations +// Take address of top node so that the real tree can change. +static void rightrot(strbstnode** bst) { +/* + a b + / \ / \ + b e => c a + / \ / \ +c d d e +*/ + strbstnode* flip = (*bst)->left->right; // flip = d + (*bst)->left->right = *bst; // position of d = a + *bst = (*bst)->left; // tip = b + (*bst)->right->left = flip; } -static void rightrot(strbstnode** bst); -static void leftrot(strbstnode** bst); +static void leftrot(strbstnode** bst) { +/* + a b + / \ / \ +e b => a c + / \ / \ + d c e d +*/ + strbstnode* flip = (*bst)->right->left; // flip = d + (*bst)->right->left = *bst; // position of d = a + *bst = (*bst)->right; // tip = b + (*bst)->left->right = flip; +} -int insnode(strbstnode** bst, strbstnode* new) { // Find good parent - if (!*bst){ - *bst = new; - return 0; +int insnode(strbstnode** bst, strbstnode* new) { + // returns height of right node minus height of left node ("bias") + if (!*bst) { // When an empty node is reached, + *bst = new; // place the node + return 0; // no children, so height difference is zero } strbstnode** node; - if (strcmp(new->ind, (*bst)->ind) < 0) + if (strcmp(new->ind, (*bst)->ind) < 0) // bst < ind? + // the address of the new node has to be taken so that node's + // addr is not returned node = &((*bst)->left); - else + else // assumed that new's index is not contained in tree node = &((*bst)->right); + // node is the parent of the subtree which will contain new int heavy = insnode( node, new ); + // insert it into the subtree and get its bias int diff = getht((*bst)->right) - getht((*bst)->left); - if (diff > 1) { - if (heavy == -1) - rightrot(node); - leftrot(bst); - } else if (diff < -1){ + if (diff > 1) { // was originally valid (diff==1), so diff == 2 + if (heavy == -1) // if node is left heavy, + rightrot(node); // make it right heavy. ht shouldn't change. + leftrot(bst); // fixes, since heavy side is either right heavy + // or centered + } else if (diff < -1){ // diff == -2 if (heavy == 1) - leftrot(node); - rightrot(bst); + leftrot(node); // make left heavy + rightrot(bst); // fix } + // Calculate the current node's height (*bst)->ht = max( getht((*bst)->left), getht((*bst)->right) )+1; + // And return calculated bias return ( getht((*bst)->right) - getht((*bst)->left) ); } @@ -60,55 +97,30 @@ void insbst(strbst* bst, char* ind, void* data) { } void* querynode(strbstnode* node, char* ind){ + // tail-recursive finding algorithm + if (!node) return NULL; // NULL => node not found int cmp = strcmp(ind, node->ind); - if (cmp > 0) + if (cmp > 0) // ind > node->ind return querynode(node->right, ind); - else if (cmp < 0) + else if (cmp < 0) // ind < node->ind return querynode(node->left, ind); - else if (node) - return node->data; else - return NULL; + return node->data; // void* data is passed back up the chain } -void* querybst(strbst* bst, char* ind) { +void* query(strbst* bst, char* ind) { return querynode(bst->head, ind); } -void rightrot(strbstnode** bst) { -/* - a b - / \ / \ - b e => c a - / \ / \ -c d d e -*/ - strbstnode* flip = (*bst)->left->right; // flip = d - (*bst)->left->right = *bst; // position of d = a - *bst = (*bst)->left; // tip = b - (*bst)->right->left = flip; -} - -void leftrot(strbstnode** bst) { -/* - a b - / \ / \ -e b => a c - / \ / \ - d c e d -*/ - strbstnode* flip = (*bst)->right->left; // flip = d - (*bst)->right->left = *bst; // position of d = a - *bst = (*bst)->right; // tip = b - (*bst)->left->right = flip; -} - -void printnode(strbstnode* node) { +static void printbstnode(strbstnode* node) { if (!node) return; + // Recursive printing if (node->right) - printnode(node->right); + printbstnode(node->right); if (node->left) - printnode(node->left); + printbstnode(node->left); + // Print one line. + // With all components, "node %s (right) %s (left) %s\n" printf("node %s", node->ind); if (node->right) printf(" (right) %s",node->right->ind); @@ -118,5 +130,5 @@ void printnode(strbstnode* node) { } void printbst(strbst* bst) { - printnode(bst->head); + printbstnode(bst->head); } @@ -3,17 +3,15 @@ typedef struct strbstnode { char* ind; - void* data; + void* data; // as used, always link* struct strbstnode* left; struct strbstnode* right; int ht; } strbstnode; -struct strbst { +typedef struct strbst { strbstnode* head; -}; - -typedef struct strbst strbst; +} strbst; strbst* newbst(void); |