aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--Makefile7
-rw-r--r--ll.c1
-rw-r--r--main.c8
-rw-r--r--nodelink.c44
-rw-r--r--nodelink.h20
-rw-r--r--read.c102
-rw-r--r--strbst.c130
-rw-r--r--strbst.h8
8 files changed, 208 insertions, 112 deletions
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);