From 290f2b95ee100735f55fe10af457cc65158af043 Mon Sep 17 00:00:00 2001
From: Holden Rohrer <hr@hrhr.dev>
Date: Wed, 27 May 2020 16:21:02 -0400
Subject: Initial working commit

There are still some errors when run through valgrind, but it performs
as expected for the test file.
---
 Makefile   |   7 +++-
 ll.c       |   1 +
 main.c     |   8 ++++
 nodelink.c |  44 +++++++++++++++++++++
 nodelink.h |  20 ++++++++++
 read.c     | 102 ++++++++++++++++++++++++++----------------------
 strbst.c   | 130 +++++++++++++++++++++++++++++++++----------------------------
 strbst.h   |   8 ++--
 8 files changed, 208 insertions(+), 112 deletions(-)
 create mode 100644 main.c
 create mode 100644 nodelink.c
 create mode 100644 nodelink.h

diff --git a/Makefile b/Makefile
index 7327ab6..d3b1b6e 100644
--- a/Makefile
+++ b/Makefile
@@ -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
diff --git a/ll.c b/ll.c
index aa0879a..910b869 100644
--- a/ll.c
+++ b/ll.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;
 }
diff --git a/main.c b/main.c
new file mode 100644
index 0000000..afbf18f
--- /dev/null
+++ b/main.c
@@ -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
diff --git a/read.c b/read.c
index e896863..879b03e 100644
--- a/read.c
+++ b/read.c
@@ -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;
         }
     }
diff --git a/strbst.c b/strbst.c
index 7bb53b1..b8b5dce 100644
--- a/strbst.c
+++ b/strbst.c
@@ -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);
 }
diff --git a/strbst.h b/strbst.h
index a58b8d3..7dbbae1 100644
--- a/strbst.h
+++ b/strbst.h
@@ -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);
 
-- 
cgit