Mercurial > blahgd > fmt4

changeset 1129:40e8a3bb0684 v4.5-rc2

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
convert to libjeffpc's red-black tree Signed-off-by: Josef 'Jeff' Sipek <jeffpc@josefsipek.net>
author Josef 'Jeff' Sipek <jeffpc@josefsipek.net>
date Sat, 13 Jan 2018 00:14:37 -0500
parents 87154fb110ca
children ec00d3f391a1
files CMakeLists.txt README file_cache.c iter.h post.c post.h post_index.c post_nv.c template.y utils.c utils.h
diffstat 11 files changed, 102 insertions(+), 162 deletions(-) [+]
line wrap: on
line diff
--- a/CMakeLists.txt	Wed Jul 25 12:20:42 2018 -0400
+++ b/CMakeLists.txt	Sat Jan 13 00:14:37 2018 -0500
@@ -103,7 +103,6 @@
 
 target_link_libraries(blahg
 	md
-	avl
 	m
 	${JEFFPC_LIBRARY}
 )
--- a/README	Wed Jul 25 12:20:42 2018 -0400
+++ b/README	Sat Jan 13 00:14:37 2018 -0500
@@ -50,7 +50,6 @@
 provided by illumos-based distros (e.g., OmniOS or OpenIndiana hipster).
 Specifically, blahgd requires:
 
-  - libavl.so (for AVL trees)
   - libmd.so (for SHA1)
 
 Other dependencies include:
--- a/file_cache.c	Wed Jul 25 12:20:42 2018 -0400
+++ b/file_cache.c	Sat Jan 13 00:14:37 2018 -0500
@@ -20,7 +20,6 @@
  * SOFTWARE.
  */
 
-#include <sys/avl.h>
 #include <fcntl.h>
 #include <sys/types.h>
 #include <sys/stat.h>
@@ -35,10 +34,10 @@
 #include <jeffpc/io.h>
 #include <jeffpc/list.h>
 #include <jeffpc/mem.h>
+#include <jeffpc/rbtree.h>
 
 #include "file_cache.h"
 #include "utils.h"
-#include "iter.h"
 #include "debug.h"
 
 #define FILE_EVENTS	(FILE_MODIFIED | FILE_ATTRIB)
@@ -46,7 +45,7 @@
 static LOCK_CLASS(file_lock_lc);
 static LOCK_CLASS(file_node_lc);
 
-static avl_tree_t file_cache;
+static struct rb_tree file_cache;
 static struct lock file_lock;
 
 static int filemon_port;
@@ -63,7 +62,7 @@
 
 struct file_node {
 	char *name;			/* the filename */
-	avl_node_t node;
+	struct rb_node node;
 	refcnt_t refcnt;
 	struct lock lock;
 
@@ -162,7 +161,7 @@
 	 * disk.
 	 */
 	MXLOCK(&file_lock);
-	avl_remove(&file_cache, node);
+	rb_remove(&file_cache, node);
 	MXUNLOCK(&file_lock);
 
 	MXUNLOCK(&node->lock);
@@ -230,8 +229,8 @@
 
 	MXINIT(&file_lock, &file_lock_lc);
 
-	avl_create(&file_cache, filename_cmp, sizeof(struct file_node),
-		   offsetof(struct file_node, node));
+	rb_create(&file_cache, filename_cmp, sizeof(struct file_node),
+		  offsetof(struct file_node, node));
 
 	file_node_cache = mem_cache_create("file-node-cache",
 					   sizeof(struct file_node), 0);
@@ -366,14 +365,14 @@
 	struct file_node *out, *tmp;
 	struct file_node key;
 	struct str *str;
-	avl_index_t where;
+	struct rb_cookie where;
 	int ret;
 
 	key.name = (char *) name;
 
 	/* do we have it? */
 	MXLOCK(&file_lock);
-	out = avl_find(&file_cache, &key, NULL);
+	out = rb_find(&file_cache, &key, NULL);
 	fn_getref(out);
 	MXUNLOCK(&file_lock);
 
@@ -398,7 +397,7 @@
 
 	/* ...and insert it into the cache */
 	MXLOCK(&file_lock);
-	tmp = avl_find(&file_cache, &key, &where);
+	tmp = rb_find(&file_cache, &key, &where);
 	if (tmp) {
 		/*
 		 * uh oh, someone beat us to it; free our copy & return
@@ -419,7 +418,7 @@
 	/* get a ref for the cache */
 	fn_getref(out);
 
-	avl_insert(&file_cache, out, where);
+	rb_insert_here(&file_cache, out, &where);
 
 	MXUNLOCK(&file_lock);
 	MXUNLOCK(&out->lock);
@@ -454,11 +453,11 @@
 void uncache_all_files(void)
 {
 	struct file_node *cur;
-	void *cookie;
+	struct rb_cookie cookie;
 
 	MXLOCK(&file_lock);
-	cookie = NULL;
-	while ((cur = avl_destroy_nodes(&file_cache, &cookie)))
+	memset(&cookie, 0, sizeof(cookie));
+	while ((cur = rb_destroy_nodes(&file_cache, &cookie)))
 		fn_putref(cur);
 	MXUNLOCK(&file_lock);
 }
--- a/iter.h	Wed Jul 25 12:20:42 2018 -0400
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,31 +0,0 @@
-/*
- * Copyright (c) 2014-2017 Josef 'Jeff' Sipek <jeffpc@josefsipek.net>
- *
- * Permission is hereby granted, free of charge, to any person obtaining a copy
- * of this software and associated documentation files (the "Software"), to deal
- * in the Software without restriction, including without limitation the rights
- * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
- * copies of the Software, and to permit persons to whom the Software is
- * furnished to do so, subject to the following conditions:
- *
- * The above copyright notice and this permission notice shall be included in
- * all copies or substantial portions of the Software.
- *
- * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
- * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
- * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
- * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
- * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
- * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
- * SOFTWARE.
- */
-
-#ifndef __ITER_H
-#define __ITER_H
-
-#include <stddef.h>
-
-#define avl_for_each(tree, pos) \
-	for (pos = avl_first(tree); pos; pos = AVL_NEXT(tree, pos))
-
-#endif
--- a/post.c	Wed Jul 25 12:20:42 2018 -0400
+++ b/post.c	Sat Jan 13 00:14:37 2018 -0500
@@ -38,7 +38,6 @@
 #include <jeffpc/io.h>
 #include <jeffpc/mem.h>
 
-#include "iter.h"
 #include "post.h"
 #include "vars.h"
 #include "req.h"
@@ -52,7 +51,7 @@
 
 static LOCK_CLASS(post_lc);
 
-static void post_remove_all_tags(avl_tree_t *taglist);
+static void post_remove_all_tags(struct rb_tree *taglist);
 static void post_remove_all_comments(struct post *post);
 
 static int tag_cmp(const void *va, const void *vb)
@@ -94,7 +93,7 @@
 }
 
 /* consumes the struct val reference */
-static void post_add_tags(avl_tree_t *taglist, struct val *list)
+static void post_add_tags(struct rb_tree *taglist, struct val *list)
 {
 	struct val *tagval;
 	struct val *tmp;
@@ -110,7 +109,7 @@
 
 		tag->tag = val_getref_str(tagval);
 
-		if (safe_avl_add(taglist, tag)) {
+		if (rb_insert(taglist, tag)) {
 			/* found a duplicate */
 			str_putref(tag->tag);
 			free(tag);
@@ -422,10 +421,10 @@
 	post->preview = preview;
 	post->needs_refresh = true;
 
-	avl_create(&post->tags, tag_cmp, sizeof(struct post_tag),
-		    offsetof(struct post_tag, node));
-	avl_create(&post->cats, tag_cmp, sizeof(struct post_tag),
-		    offsetof(struct post_tag, node));
+	rb_create(&post->tags, tag_cmp, sizeof(struct post_tag),
+		  offsetof(struct post_tag, node));
+	rb_create(&post->cats, tag_cmp, sizeof(struct post_tag),
+		  offsetof(struct post_tag, node));
 	list_create(&post->comments, sizeof(struct comment),
 		    offsetof(struct comment, list));
 	refcnt_init(&post->refcnt, 1);
@@ -447,19 +446,19 @@
 	return NULL;
 }
 
-static void post_remove_all_tags(avl_tree_t *taglist)
+static void post_remove_all_tags(struct rb_tree *taglist)
 {
 	struct post_tag *tag;
-	void *cookie;
+	struct rb_cookie cookie;
 
-	cookie = NULL;
-	while ((tag = avl_destroy_nodes(taglist, &cookie))) {
+	memset(&cookie, 0, sizeof(cookie));
+	while ((tag = rb_destroy_nodes(taglist, &cookie))) {
 		str_putref(tag->tag);
 		free(tag);
 	}
 
-	avl_create(taglist, tag_cmp, sizeof(struct post_tag),
-		    offsetof(struct post_tag, node));
+	rb_create(taglist, tag_cmp, sizeof(struct post_tag),
+		  offsetof(struct post_tag, node));
 }
 
 void post_destroy(struct post *post)
--- a/post.h	Wed Jul 25 12:20:42 2018 -0400
+++ b/post.h	Sat Jan 13 00:14:37 2018 -0500
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2009-2017 Josef 'Jeff' Sipek <jeffpc@josefsipek.net>
+ * Copyright (c) 2009-2018 Josef 'Jeff' Sipek <jeffpc@josefsipek.net>
  *
  * Permission is hereby granted, free of charge, to any person obtaining a copy
  * of this software and associated documentation files (the "Software"), to deal
@@ -25,16 +25,16 @@
 
 #include <time.h>
 #include <stdbool.h>
-#include <sys/avl.h>
 
 #include <jeffpc/synch.h>
 #include <jeffpc/refcnt.h>
 #include <jeffpc/list.h>
+#include <jeffpc/rbtree.h>
 
 #include "vars.h"
 
 struct post_tag {
-	avl_node_t node;
+	struct rb_node node;
 	struct str *tag;
 };
 
@@ -66,8 +66,8 @@
 	unsigned int fmt;
 
 	/* from 'post_tags' table */
-	avl_tree_t tags;
-	avl_tree_t cats;
+	struct rb_tree tags;
+	struct rb_tree cats;
 
 	/* from 'comments' table */
 	struct list comments;
--- a/post_index.c	Wed Jul 25 12:20:42 2018 -0400
+++ b/post_index.c	Sat Jan 13 00:14:37 2018 -0500
@@ -29,7 +29,6 @@
 #include <jeffpc/mem.h>
 
 #include "post.h"
-#include "iter.h"
 #include "utils.h"
 
 /*
@@ -49,14 +48,14 @@
  *
  * To maximize code reuse, the by-tag and by-category trees contain struct
  * post_subindex nodes for each (unique) tag/category.  Those nodes contain
- * AVL trees of their own with struct post_index_entry elements mapping
- * <timestamp, post id> (much like the by time index) to a post.
+ * binary search trees of their own with struct post_index_entry elements
+ * mapping <timestamp, post id> (much like the by time index) to a post.
  *
  * Because this isn't complex enough, we also keep a linked list of all the
  * tag entries rooted in the global index tree node.
  *
  *      +--------------------------------+
- *      | index_global AVL tree          |
+ *      | index_global tree              |
  *      |+-------------------------+     |   +------+
  *      || post global index entry | ... |   | post |
  *  +--->|   by_tag  by_cat  post  |     |   +------+
@@ -68,11 +67,11 @@
  *  | +--------+       +--------------------------+
  *  | |                                           |
  *  | | +-------------------------------------+   |
- *  | | |  index_by_tag AVL tree              |   |
+ *  | | |  index_by_tag tree                  |   |
  *  | | | +-----------------------------+     |   |
  *  | | | |  post subindex              |     |   |
  *  | | | | +-------------------------+ |     |   |
- *  | | | | |  subindex AVL tree      | |     |   |
+ *  | | | | |  subindex tree          | |     |   |
  *  | | | | | +-----------------+     | |     |   |
  *  | +-----> |post index entry | ... | |     |   |
  *  |   | | | |  global  xref   |     | | ... |   |
@@ -87,11 +86,11 @@
  *  | +-------------------------------------------+
  *  | |
  *  | | +-------------------------------------+
- *  | | |  index_by_cat AVL tree              |
+ *  | | |  index_by_cat tree                  |
  *  | | | +-----------------------------+     |
  *  | | | |  post subindex              |     |
  *  | | | | +-------------------------+ |     |
- *  | | | | |  subindex AVL tree      | |     |
+ *  | | | | |  subindex tree          | |     |
  *  | | | | | +-----------------+     | |     |
  *  | +-----> |post index entry | ... | |     |
  *  |   | | | |  global  xref   |     | | ... |
@@ -104,7 +103,7 @@
  *  |   +-------------------------------------+
  *  |
  *  |   +-------------------------+
- *  |   | index_by_time AVL tree  |
+ *  |   | index_by_time tree      |
  *  |   |+------------------+     |
  *  |   || post index entry | ... |
  *  |   ||   global         |     |
@@ -122,7 +121,7 @@
 };
 
 struct post_global_index_entry {
-	avl_node_t node;
+	struct rb_node node;
 
 	/* key */
 	unsigned int id;
@@ -139,7 +138,7 @@
 };
 
 struct post_index_entry {
-	avl_node_t node;
+	struct rb_node node;
 
 	struct post_global_index_entry *global;
 
@@ -161,19 +160,19 @@
 };
 
 struct post_subindex {
-	avl_node_t index;
+	struct rb_node index;
 
 	/* key */
 	struct str *name;
 
 	/* value */
-	avl_tree_t subindex;
+	struct rb_tree subindex;
 };
 
-static avl_tree_t index_global;
-static avl_tree_t index_by_time;
-static avl_tree_t index_by_tag;
-static avl_tree_t index_by_cat;
+static struct rb_tree index_global;
+static struct rb_tree index_by_time;
+static struct rb_tree index_by_tag;
+static struct rb_tree index_by_cat;
 
 static struct lock index_lock;
 static LOCK_CLASS(index_lock_lc);
@@ -236,25 +235,25 @@
 	return 0;
 }
 
-static void init_index_tree(avl_tree_t *tree)
+static void init_index_tree(struct rb_tree *tree)
 {
-	avl_create(tree, post_index_cmp, sizeof(struct post_index_entry),
-		   offsetof(struct post_index_entry, node));
+	rb_create(tree, post_index_cmp, sizeof(struct post_index_entry),
+		  offsetof(struct post_index_entry, node));
 }
 
 void init_post_index(void)
 {
-	avl_create(&index_global, post_global_index_cmp,
-		   sizeof(struct post_global_index_entry),
-		   offsetof(struct post_global_index_entry, node));
+	rb_create(&index_global, post_global_index_cmp,
+		  sizeof(struct post_global_index_entry),
+		  offsetof(struct post_global_index_entry, node));
 
 	init_index_tree(&index_by_time);
 
 	/* set up the by-tag/category indexes */
-	avl_create(&index_by_tag, post_tag_cmp, sizeof(struct post_subindex),
-		   offsetof(struct post_subindex, index));
-	avl_create(&index_by_cat, post_tag_cmp, sizeof(struct post_subindex),
-		   offsetof(struct post_subindex, index));
+	rb_create(&index_by_tag, post_tag_cmp, sizeof(struct post_subindex),
+		  offsetof(struct post_subindex, index));
+	rb_create(&index_by_cat, post_tag_cmp, sizeof(struct post_subindex),
+		  offsetof(struct post_subindex, index));
 
 	MXINIT(&index_lock, &index_lock_lc);
 
@@ -273,14 +272,15 @@
 	ASSERT(!IS_ERR(subindex_cache));
 }
 
-static avl_tree_t *__get_subindex(avl_tree_t *index, struct str *tagname)
+static struct rb_tree *__get_subindex(struct rb_tree *index,
+				       struct str *tagname)
 {
 	struct post_subindex *ret;
 	struct post_subindex key = {
 		.name = tagname,
 	};
 
-	ret = avl_find(index, &key, NULL);
+	ret = rb_find(index, &key, NULL);
 	if (!ret)
 		return NULL;
 
@@ -297,7 +297,7 @@
 	struct post *post;
 
 	MXLOCK(&index_lock);
-	ret = avl_find(&index_global, &key, NULL);
+	ret = rb_find(&index_global, &key, NULL);
 	if (ret)
 		post = post_getref(ret->post);
 	else
@@ -313,7 +313,7 @@
 		    int skip, int nposts)
 {
 	struct post_index_entry *cur;
-	avl_tree_t *tree;
+	struct rb_tree *tree;
 	int i;
 
 	MXLOCK(&index_lock);
@@ -332,7 +332,7 @@
 	}
 
 	/* skip over the first (listed) entries as requested */
-	for (cur = avl_last(tree); cur && skip; cur = AVL_PREV(tree, cur)) {
+	for (cur = rb_last(tree); cur && skip; cur = rb_prev(tree, cur)) {
 		if (!cur->global->post->listed)
 			continue; /* don't count non-listed posts */
 
@@ -340,7 +340,7 @@
 	}
 
 	/* get a reference for every post we're returning */
-	for (i = 0; cur && nposts; cur = AVL_PREV(tree, cur)) {
+	for (i = 0; cur && nposts; cur = rb_prev(tree, cur)) {
 		if (!cur->global->post->listed)
 			continue; /* skip non-listed posts */
 
@@ -358,23 +358,23 @@
 	return i;
 }
 
-static int __insert_post_tags(avl_tree_t *index,
+static int __insert_post_tags(struct rb_tree *index,
 			      struct post_global_index_entry *global,
-			      avl_tree_t *taglist, struct list *xreflist,
+			      struct rb_tree *taglist, struct list *xreflist,
 			      enum entry_type type)
 {
 	struct post_index_entry *tag_entry;
 	struct post_subindex *sub;
 	struct post_tag *tag;
-	avl_index_t where;
+	struct rb_cookie where;
 
-	avl_for_each(taglist, tag) {
+	rb_for_each(taglist, tag) {
 		struct post_subindex key = {
 			.name = tag->tag,
 		};
 
 		/* find the right subindex, or... */
-		sub = avl_find(index, &key, &where);
+		sub = rb_find(index, &key, &where);
 		if (!sub) {
 			/* ...allocate one if it doesn't exist */
 			sub = mem_cache_alloc(subindex_cache);
@@ -384,7 +384,7 @@
 			sub->name = str_getref(tag->tag);
 			init_index_tree(&sub->subindex);
 
-			avl_insert(index, sub, where);
+			rb_insert_here(index, sub, &where);
 		}
 
 		/* allocate & add a entry to the subindex */
@@ -396,7 +396,7 @@
 		tag_entry->name   = str_getref(tag->tag);
 		tag_entry->type   = type;
 
-		ASSERT3P(safe_avl_add(&sub->subindex, tag_entry), ==, NULL);
+		ASSERT3P(rb_insert(&sub->subindex, tag_entry), ==, NULL);
 		list_insert_tail(xreflist, tag_entry);
 	}
 
@@ -442,14 +442,14 @@
 	MXLOCK(&index_lock);
 
 	/* add the post to the global index */
-	if (safe_avl_add(&index_global, global)) {
+	if (rb_insert(&index_global, global)) {
 		MXUNLOCK(&index_lock);
 		ret = -EEXIST;
 		goto err_free_by_time;
 	}
 
 	/* add the post to the by-time index */
-	ASSERT3P(safe_avl_add(&index_by_time, by_time), ==, NULL);
+	ASSERT3P(rb_insert(&index_by_time, by_time), ==, NULL);
 
 	ret = __insert_post_tags(&index_by_tag, global, &post->tags,
 				 &global->by_tag, ET_TAG);
@@ -471,7 +471,7 @@
 err_free_tags:
 	// XXX: __remove_post_tags(&index_by_tag, &post->tags);
 
-	avl_remove(&index_by_time, by_time);
+	rb_remove(&index_by_time, by_time);
 
 	MXUNLOCK(&index_lock);
 
@@ -491,7 +491,7 @@
 	struct post_global_index_entry *cur;
 
 	MXLOCK(&index_lock);
-	avl_for_each(&index_global, cur)
+	rb_for_each(&index_global, cur)
 		revalidate_post(cur->post);
 	MXUNLOCK(&index_lock);
 }
@@ -511,7 +511,7 @@
 	MXLOCK(&index_lock);
 
 	if (init) {
-		ret = init(private, avl_numnodes(&index_by_tag));
+		ret = init(private, rb_numnodes(&index_by_tag));
 		if (ret)
 			goto err;
 	}
@@ -524,45 +524,45 @@
 	 */
 	cmin = ~0;
 	cmax = 0;
-	avl_for_each(&index_by_tag, tag) {
-		cmin = MIN(cmin, avl_numnodes(&tag->subindex));
-		cmax = MAX(cmax, avl_numnodes(&tag->subindex));
+	rb_for_each(&index_by_tag, tag) {
+		cmin = MIN(cmin, rb_numnodes(&tag->subindex));
+		cmax = MAX(cmax, rb_numnodes(&tag->subindex));
 	}
 
 	/*
 	 * finally, invoke the step callback for each tag
 	 */
-	avl_for_each(&index_by_tag, tag)
-		step(private, tag->name, avl_numnodes(&tag->subindex),
+	rb_for_each(&index_by_tag, tag)
+		step(private, tag->name, rb_numnodes(&tag->subindex),
 		     cmin, cmax);
 
 err:
 	MXUNLOCK(&index_lock);
 }
 
-static void __free_global_index(avl_tree_t *tree)
+static void __free_global_index(struct rb_tree *tree)
 {
 	struct post_global_index_entry *cur;
-	void *cookie;
+	struct rb_cookie cookie;
 
-	cookie = NULL;
-	while ((cur = avl_destroy_nodes(tree, &cookie))) {
+	memset(&cookie, 0, sizeof(cookie));
+	while ((cur = rb_destroy_nodes(tree, &cookie))) {
 		post_putref(cur->post);
 		list_destroy(&cur->by_tag);
 		list_destroy(&cur->by_cat);
 		mem_cache_free(global_index_entry_cache, cur);
 	}
 
-	avl_destroy(tree);
+	rb_destroy(tree);
 }
 
-static void __free_index(avl_tree_t *tree)
+static void __free_index(struct rb_tree *tree)
 {
 	struct post_index_entry *cur;
-	void *cookie;
+	struct rb_cookie cookie;
 
-	cookie = NULL;
-	while ((cur = avl_destroy_nodes(tree, &cookie))) {
+	memset(&cookie, 0, sizeof(cookie));
+	while ((cur = rb_destroy_nodes(tree, &cookie))) {
 		struct list *xreflist = NULL;
 
 		switch (cur->type) {
@@ -584,22 +584,22 @@
 		mem_cache_free(index_entry_cache, cur);
 	}
 
-	avl_destroy(tree);
+	rb_destroy(tree);
 }
 
-static void __free_tag_index(avl_tree_t *tree)
+static void __free_tag_index(struct rb_tree *tree)
 {
 	struct post_subindex *cur;
-	void *cookie;
+	struct rb_cookie cookie;
 
-	cookie = NULL;
-	while ((cur = avl_destroy_nodes(tree, &cookie))) {
+	memset(&cookie, 0, sizeof(cookie));
+	while ((cur = rb_destroy_nodes(tree, &cookie))) {
 		__free_index(&cur->subindex);
 		str_putref((struct str *) cur->name);
 		mem_cache_free(subindex_cache, cur);
 	}
 
-	avl_destroy(tree);
+	rb_destroy(tree);
 }
 
 void free_all_posts(void)
--- a/post_nv.c	Wed Jul 25 12:20:42 2018 -0400
+++ b/post_nv.c	Sat Jan 13 00:14:37 2018 -0500
@@ -24,25 +24,24 @@
 #include <jeffpc/list.h>
 #include <jeffpc/mem.h>
 
-#include "iter.h"
 #include "post.h"
 #include "req.h"
 
-static int __tag_val(struct nvlist *post, avl_tree_t *list)
+static int __tag_val(struct nvlist *post, struct rb_tree *list)
 {
 	struct post_tag *cur;
 	struct val **tags;
 	size_t ntags;
 	size_t i;
 
-	ntags = avl_numnodes(list);
+	ntags = rb_numnodes(list);
 
 	tags = mem_reallocarray(NULL, ntags, sizeof(struct val *));
 	if (!tags)
 		return -ENOMEM;
 
 	i = 0;
-	avl_for_each(list, cur)
+	rb_for_each(list, cur)
 		tags[i++] = str_getref_val(cur->tag);
 
 	return nvl_set_array(post, "tags", tags, ntags);
--- a/template.y	Wed Jul 25 12:20:42 2018 -0400
+++ b/template.y	Sat Jan 13 00:14:37 2018 -0500
@@ -34,7 +34,6 @@
 #include <jeffpc/val.h>
 
 #include "config.h"
-#include "iter.h"
 #include "vars.h"
 #include "render.h"
 #include "pipeline.h"
--- a/utils.c	Wed Jul 25 12:20:42 2018 -0400
+++ b/utils.c	Sat Jan 13 00:14:37 2018 -0500
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2011-2016 Josef 'Jeff' Sipek <jeffpc@josefsipek.net>
+ * Copyright (c) 2011-2018 Josef 'Jeff' Sipek <jeffpc@josefsipek.net>
  *
  * Permission is hereby granted, free of charge, to any person obtaining a copy
  * of this software and associated documentation files (the "Software"), to deal
@@ -153,20 +153,3 @@
 
 	return mktime(&tm);
 }
-
-/*
- * libavl extensions
- */
-
-/* like avl_add, but returns the existing node */
-void *safe_avl_add(avl_tree_t *tree, void *node)
-{
-	avl_index_t where;
-	void *tmp;
-
-	tmp = avl_find(tree, node, &where);
-	if (!tmp)
-		avl_insert(tree, node, where);
-
-	return tmp;
-}
--- a/utils.h	Wed Jul 25 12:20:42 2018 -0400
+++ b/utils.h	Sat Jan 13 00:14:37 2018 -0500
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2011-2017 Josef 'Jeff' Sipek <jeffpc@josefsipek.net>
+ * Copyright (c) 2011-2018 Josef 'Jeff' Sipek <jeffpc@josefsipek.net>
  *
  * Permission is hereby granted, free of charge, to any person obtaining a copy
  * of this software and associated documentation files (the "Software"), to deal
@@ -26,13 +26,13 @@
 #include <sys/sysmacros.h>
 #include <sys/stat.h>
 #include <string.h>
-#include <sys/avl.h>
 
 #include <jeffpc/error.h>
 #include <jeffpc/int.h>
 #include <jeffpc/val.h>
 #include <jeffpc/io.h>
 #include <jeffpc/time.h>
+#include <jeffpc/rbtree.h>
 
 extern int hasdotdot(const char *path);
 extern char *concat5(char *a, char *b, char *c, char *d, char *e);
@@ -72,10 +72,4 @@
 	return ret;
 }
 
-/*
- * libavl extensions
- */
-
-extern void *safe_avl_add(avl_tree_t *tree, void *node);
-
 #endif