M CMakeLists.txt +0 -1
@@ 103,7 103,6 @@ add_dependencies(blahg revisiontag)
target_link_libraries(blahg
md
- avl
m
${JEFFPC_LIBRARY}
)
M README +0 -1
@@ 50,7 50,6 @@ At present time, blahgd depends on a num
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:
M file_cache.c +13 -14
@@ 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_callback {
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 @@ free:
* disk.
*/
MXLOCK(&file_lock);
- avl_remove(&file_cache, node);
+ rb_remove(&file_cache, node);
MXUNLOCK(&file_lock);
MXUNLOCK(&node->lock);
@@ 230,8 229,8 @@ void init_file_cache(void)
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 str *file_cache_get_cb(const char
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 @@ struct str *file_cache_get_cb(const char
/* ...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 @@ struct str *file_cache_get_cb(const char
/* 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 @@ output:
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);
}
R iter.h => +0 -31
@@ 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
M post.c +13 -14
@@ 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 struct mem_cache *comment_cache;
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 @@ void revalidate_post(void *arg)
}
/* 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 @@ static void post_add_tags(avl_tree_t *ta
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 @@ struct post *load_post(int postid, bool
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 @@ err:
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)
M post.h +5 -5
@@ 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 @@ struct post {
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;
M post_index.c +65 -65
@@ 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 @@ enum entry_type {
};
struct post_global_index_entry {
- avl_node_t node;
+ struct rb_node node;
/* key */
unsigned int id;
@@ 139,7 138,7 @@ struct post_global_index_entry {
};
struct post_index_entry {
- avl_node_t node;
+ struct rb_node node;
struct post_global_index_entry *global;
@@ 161,19 160,19 @@ struct post_index_entry {
};
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 @@ static int post_tag_cmp(const void *va,
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 @@ void init_post_index(void)
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 *index_lookup_post(unsigned
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 index_get_posts(struct post **ret, s
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 @@ int index_get_posts(struct post **ret, s
}
/* 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 @@ int index_get_posts(struct post **ret, s
}
/* 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 @@ int index_get_posts(struct post **ret, s
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 @@ static int __insert_post_tags(avl_tree_t
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 @@ static int __insert_post_tags(avl_tree_t
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 @@ int index_insert_post(struct post *post)
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_cats:
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 @@ void revalidate_all_posts(void *arg)
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 @@ void index_for_each_tag(int (*init)(void
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 @@ void index_for_each_tag(int (*init)(void
*/
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 @@ static void __free_index(avl_tree_t *tre
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)
M post_nv.c +3 -4
@@ 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);
M template.y +0 -1
@@ 34,7 34,6 @@
#include <jeffpc/val.h>
#include "config.h"
-#include "iter.h"
#include "vars.h"
#include "render.h"
#include "pipeline.h"
M utils.c +1 -18
@@ 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 @@ time_t parse_time_cstr(const char *str)
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;
-}
M utils.h +2 -8
@@ 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 @@ static inline time_t parse_time_str(stru
return ret;
}
-/*
- * libavl extensions
- */
-
-extern void *safe_avl_add(avl_tree_t *tree, void *node);
-
#endif