[PATCH 1/4] speedup: use rbtree for sorted and shuffle list

Gregory Petrosyan

2010-09-16 16:44:20 UTC

From: Johannes Weißl <***@molb.org>

Since the only operations are sorted insert, sorted find (for removal)
and prev/next, a binary tree is much better suited than a flat list.

The shuffle list can completely be replaced by a rbtree (since the
random key is unique), but the sorted list can contain duplicate tracks.
In this case the tree contains the first of the the duplicate tracks.

The Linux 2.6.34 implementation of rbtree is used.

speedup: 98% cpu time for initial indexing
(~30k files, 85% mp3, 14% ogg, 1% other)
---
Makefile | 2 +-
editable.c | 5 +-
editable.h | 2 +
lib.c | 13 +-
list.h | 1 +
pl.c | 13 +-
rbtree.c | 385 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
rbtree.h | 205 ++++++++++++++++++++++++++++++++
track.c | 144 ++++++++++++++++++-----
track.h | 27 +++--
10 files changed, 744 insertions(+), 53 deletions(-)
create mode 100644 rbtree.c
create mode 100644 rbtree.h

diff --git a/Makefile b/Makefile
index 5259ecf..557aebc 100644
--- a/Makefile
+++ b/Makefile
@@ -35,7 +35,7 @@ cmus-y := \
format_print.o gbuf.o glob.o help.o history.o http.o id3.o input.o job.o \
keys.o keyval.o lib.o load_dir.o locking.o mergesort.o misc.o options.o \
output.o pcm.o pl.o play_queue.o player.o \
- read_wrapper.o server.o search.o \
+ rbtree.o read_wrapper.o server.o search.o \
search_mode.o spawn.o tabexp.o tabexp_file.o \
track.o track_info.o tree.o uchar.o ui_curses.o \
utf8_encode.lo window.o worker.o xstrjoin.o
diff --git a/editable.c b/editable.c
index ed92813..4eff9c0 100644
--- a/editable.c
+++ b/editable.c
@@ -35,6 +35,7 @@ void editable_init(struct editable *e, void (*free_track)(struct list_head *item
struct iter iter;

list_init(&e->head);
+ e->tree_root.rb_node = NULL;
e->nr_tracks = 0;
e->nr_marked = 0;
e->total_time = 0;
@@ -54,7 +55,7 @@ void editable_init(struct editable *e, void (*free_track)(struct list_head *item

void editable_add(struct editable *e, struct simple_track *track)
{
- sorted_list_add_track(&e->head, track, e->sort_keys);
+ sorted_list_add_track(&e->head, &e->tree_root, track, e->sort_keys);
e->nr_tracks++;
if (track->info->duration != -1)
e->total_time += track->info->duration;
@@ -75,6 +76,8 @@ void editable_remove_track(struct editable *e, struct simple_track *track)
e->total_time -= ti->duration;

list_del(&track->node);
+ if (!RB_EMPTY_NODE(&track->tree_node))
+ rb_erase(&track->tree_node, &e->tree_root);

e->free_track(&track->node);
}
diff --git a/editable.h b/editable.h
index 0520827..bff11b7 100644
--- a/editable.h
+++ b/editable.h
@@ -7,12 +7,14 @@

#include "window.h"
#include "list.h"
+#include "rbtree.h"
#include "track.h"
#include "locking.h"

struct editable {
struct window *win;
struct list_head head;
+ struct rb_root tree_root;
unsigned int nr_tracks;
unsigned int nr_marked;
unsigned int total_time;
diff --git a/lib.c b/lib.c
index a89b0a0..ebebf88 100644
--- a/lib.c
+++ b/lib.c
@@ -7,6 +7,7 @@
#include "track_info.h"
#include "options.h"
#include "xmalloc.h"
+#include "rbtree.h"
#include "debug.h"

#include <pthread.h>
@@ -17,7 +18,7 @@ struct tree_track *lib_cur_track = NULL;
unsigned int play_sorted = 0;
enum aaa_mode aaa_mode = AAA_MODE_ALL;

-static LIST_HEAD(lib_shuffle_head);
+static struct rb_root lib_shuffle_root;
static struct expr *filter = NULL;
static int remove_from_hash = 1;

@@ -53,7 +54,7 @@ static void all_wins_changed(void)

static void shuffle_add(struct tree_track *track)
{
- list_add_rand(&lib_shuffle_head, &track->shuffle_track.node, lib_editable.nr_tracks);
+ shuffle_list_add(&track->shuffle_track, &lib_shuffle_root);
}

static void views_add_track(struct track_info *ti)
@@ -281,7 +282,7 @@ static struct tree_track *normal_get_prev(void)

void lib_reshuffle(void)
{
- reshuffle(&lib_shuffle_head);
+ shuffle_list_reshuffle(&lib_shuffle_root);
}

static void free_lib_track(struct list_head *item)
@@ -295,7 +296,7 @@ static void free_lib_track(struct list_head *item)
if (remove_from_hash)
hash_remove(ti);

- list_del(&track->shuffle_track.node);
+ rb_erase(&track->shuffle_track.tree_node, &lib_shuffle_root);
tree_remove(track);

track_info_unref(ti);
@@ -331,7 +332,7 @@ struct track_info *lib_set_next(void)
return NULL;
}
if (shuffle) {
- track = (struct tree_track *)shuffle_list_get_next(&lib_shuffle_head,
+ track = (struct tree_track *)shuffle_list_get_next(&lib_shuffle_root,
(struct shuffle_track *)lib_cur_track, aaa_mode_filter);
} else if (play_sorted) {
track = (struct tree_track *)simple_list_get_next(&lib_editable.head,
@@ -351,7 +352,7 @@ struct track_info *lib_set_prev(void)
return NULL;
}
if (shuffle) {
- track = (struct tree_track *)shuffle_list_get_prev(&lib_shuffle_head,
+ track = (struct tree_track *)shuffle_list_get_prev(&lib_shuffle_root,
(struct shuffle_track *)lib_cur_track, aaa_mode_filter);
} else if (play_sorted) {
track = (struct tree_track *)simple_list_get_prev(&lib_editable.head,
diff --git a/list.h b/list.h
index beaac34..0a28cf2 100644
--- a/list.h
+++ b/list.h
@@ -203,6 +203,7 @@ static inline void list_splice_init(struct list_head *list,
* @member: the name of the member within the struct.
*
*/
+#undef container_of
#define container_of(ptr, type, member) ({ \
const __typeof__( ((type *)0)->member ) *__mptr = (ptr); \
(type *)( (char *)__mptr - offsetof(type,member) );})
diff --git a/pl.c b/pl.c
index c8f00af..c0e83b7 100644
--- a/pl.c
+++ b/pl.c
@@ -10,16 +10,17 @@
struct editable pl_editable;
struct simple_track *pl_cur_track = NULL;

-static LIST_HEAD(pl_shuffle_head);
+static struct rb_root pl_shuffle_root;

static void pl_free_track(struct list_head *item)
{
struct simple_track *track = to_simple_track(item);
+ struct shuffle_track *shuffle_track = (struct shuffle_track *) track;

if (track == pl_cur_track)
pl_cur_track = NULL;

- list_del(&((struct shuffle_track *)track)->node);
+ rb_erase(&shuffle_track->tree_node, &pl_shuffle_root);
track_info_unref(track->info);
free(track);
}
@@ -55,7 +56,7 @@ struct track_info *pl_set_next(void)
return NULL;

if (shuffle) {
- track = (struct simple_track *)shuffle_list_get_next(&pl_shuffle_head,
+ track = (struct simple_track *)shuffle_list_get_next(&pl_shuffle_root,
(struct shuffle_track *)pl_cur_track, dummy_filter);
} else {
track = simple_list_get_next(&pl_editable.head, pl_cur_track, dummy_filter);
@@ -71,7 +72,7 @@ struct track_info *pl_set_prev(void)
return NULL;

if (shuffle) {
- track = (struct simple_track *)shuffle_list_get_prev(&pl_shuffle_head,
+ track = (struct simple_track *)shuffle_list_get_prev(&pl_shuffle_root,
(struct shuffle_track *)pl_cur_track, dummy_filter);
} else {
track = simple_list_get_prev(&pl_editable.head, pl_cur_track, dummy_filter);
@@ -106,13 +107,13 @@ void pl_add_track(struct track_info *ti)

track_info_ref(ti);
simple_track_init((struct simple_track *)track, ti);
- list_add_rand(&pl_shuffle_head, &track->node, pl_editable.nr_tracks);
+ shuffle_list_add(track, &pl_shuffle_root);
editable_add(&pl_editable, (struct simple_track *)track);
}

void pl_reshuffle(void)
{
- reshuffle(&pl_shuffle_head);
+ shuffle_list_reshuffle(&pl_shuffle_root);
}

int pl_for_each(int (*cb)(void *data, struct track_info *ti), void *data)
diff --git a/rbtree.c b/rbtree.c
new file mode 100644
index 0000000..d8afdbb
--- /dev/null
+++ b/rbtree.c
@@ -0,0 +1,385 @@
+/* Stolen from Linux 2.6.34 */
+
+/*
+ Red Black Trees
+ (C) 1999 Andrea Arcangeli <***@suse.de>
+ (C) 2002 David Woodhouse <***@infradead.org>
+
+ This program is free software; you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation; either version 2 of the License, or
+ (at your option) any later version.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program; if not, write to the Free Software
+ Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+
+ linux/lib/rbtree.c
+*/
+
+#include "rbtree.h"
+
+static void __rb_rotate_left(struct rb_node *node, struct rb_root *root)
+{
+ struct rb_node *right = node->rb_right;
+ struct rb_node *parent = rb_parent(node);
+
+ if ((node->rb_right = right->rb_left))
+ rb_set_parent(right->rb_left, node);
+ right->rb_left = node;
+
+ rb_set_parent(right, parent);
+
+ if (parent)
+ {
+ if (node == parent->rb_left)
+ parent->rb_left = right;
+ else
+ parent->rb_right = right;
+ }
+ else
+ root->rb_node = right;
+ rb_set_parent(node, right);
+}
+
+static void __rb_rotate_right(struct rb_node *node, struct rb_root *root)
+{
+ struct rb_node *left = node->rb_left;
+ struct rb_node *parent = rb_parent(node);
+
+ if ((node->rb_left = left->rb_right))
+ rb_set_parent(left->rb_right, node);
+ left->rb_right = node;
+
+ rb_set_parent(left, parent);
+
+ if (parent)
+ {
+ if (node == parent->rb_right)
+ parent->rb_right = left;
+ else
+ parent->rb_left = left;
+ }
+ else
+ root->rb_node = left;
+ rb_set_parent(node, left);
+}
+
+void rb_insert_color(struct rb_node *node, struct rb_root *root)
+{
+ struct rb_node *parent, *gparent;
+
+ while ((parent = rb_parent(node)) && rb_is_red(parent))
+ {
+ gparent = rb_parent(parent);
+
+ if (parent == gparent->rb_left)
+ {
+ {
+ register struct rb_node *uncle = gparent->rb_right;
+ if (uncle && rb_is_red(uncle))
+ {
+ rb_set_black(uncle);
+ rb_set_black(parent);
+ rb_set_red(gparent);
+ node = gparent;
+ continue;
+ }
+ }
+
+ if (parent->rb_right == node)
+ {
+ register struct rb_node *tmp;
+ __rb_rotate_left(parent, root);
+ tmp = parent;
+ parent = node;
+ node = tmp;
+ }
+
+ rb_set_black(parent);
+ rb_set_red(gparent);
+ __rb_rotate_right(gparent, root);
+ } else {
+ {
+ register struct rb_node *uncle = gparent->rb_left;
+ if (uncle && rb_is_red(uncle))
+ {
+ rb_set_black(uncle);
+ rb_set_black(parent);
+ rb_set_red(gparent);
+ node = gparent;
+ continue;
+ }
+ }
+
+ if (parent->rb_left == node)
+ {
+ register struct rb_node *tmp;
+ __rb_rotate_right(parent, root);
+ tmp = parent;
+ parent = node;
+ node = tmp;
+ }
+
+ rb_set_black(parent);
+ rb_set_red(gparent);
+ __rb_rotate_left(gparent, root);
+ }
+ }
+
+ rb_set_black(root->rb_node);
+}
+
+static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
+ struct rb_root *root)
+{
+ struct rb_node *other;
+
+ while ((!node || rb_is_black(node)) && node != root->rb_node)
+ {
+ if (parent->rb_left == node)
+ {
+ other = parent->rb_right;
+ if (rb_is_red(other))
+ {
+ rb_set_black(other);
+ rb_set_red(parent);
+ __rb_rotate_left(parent, root);
+ other = parent->rb_right;
+ }
+ if ((!other->rb_left || rb_is_black(other->rb_left)) &&
+ (!other->rb_right || rb_is_black(other->rb_right)))
+ {
+ rb_set_red(other);
+ node = parent;
+ parent = rb_parent(node);
+ }
+ else
+ {
+ if (!other->rb_right || rb_is_black(other->rb_right))
+ {
+ rb_set_black(other->rb_left);
+ rb_set_red(other);
+ __rb_rotate_right(other, root);
+ other = parent->rb_right;
+ }
+ rb_set_color(other, rb_color(parent));
+ rb_set_black(parent);
+ rb_set_black(other->rb_right);
+ __rb_rotate_left(parent, root);
+ node = root->rb_node;
+ break;
+ }
+ }
+ else
+ {
+ other = parent->rb_left;
+ if (rb_is_red(other))
+ {
+ rb_set_black(other);
+ rb_set_red(parent);
+ __rb_rotate_right(parent, root);
+ other = parent->rb_left;
+ }
+ if ((!other->rb_left || rb_is_black(other->rb_left)) &&
+ (!other->rb_right || rb_is_black(other->rb_right)))
+ {
+ rb_set_red(other);
+ node = parent;
+ parent = rb_parent(node);
+ }
+ else
+ {
+ if (!other->rb_left || rb_is_black(other->rb_left))
+ {
+ rb_set_black(other->rb_right);
+ rb_set_red(other);
+ __rb_rotate_left(other, root);
+ other = parent->rb_left;
+ }
+ rb_set_color(other, rb_color(parent));
+ rb_set_black(parent);
+ rb_set_black(other->rb_left);
+ __rb_rotate_right(parent, root);
+ node = root->rb_node;
+ break;
+ }
+ }
+ }
+ if (node)
+ rb_set_black(node);
+}
+
+void rb_erase(struct rb_node *node, struct rb_root *root)
+{
+ struct rb_node *child, *parent;
+ int color;
+
+ if (!node->rb_left)
+ child = node->rb_right;
+ else if (!node->rb_right)
+ child = node->rb_left;
+ else
+ {
+ struct rb_node *old = node, *left;
+
+ node = node->rb_right;
+ while ((left = node->rb_left) != NULL)
+ node = left;
+
+ if (rb_parent(old)) {
+ if (rb_parent(old)->rb_left == old)
+ rb_parent(old)->rb_left = node;
+ else
+ rb_parent(old)->rb_right = node;
+ } else
+ root->rb_node = node;
+
+ child = node->rb_right;
+ parent = rb_parent(node);
+ color = rb_color(node);
+
+ if (parent == old) {
+ parent = node;
+ } else {
+ if (child)
+ rb_set_parent(child, parent);
+ parent->rb_left = child;
+
+ node->rb_right = old->rb_right;
+ rb_set_parent(old->rb_right, node);
+ }
+
+ node->rb_parent_color = old->rb_parent_color;
+ node->rb_left = old->rb_left;
+ rb_set_parent(old->rb_left, node);
+
+ goto color;
+ }
+
+ parent = rb_parent(node);
+ color = rb_color(node);
+
+ if (child)
+ rb_set_parent(child, parent);
+ if (parent)
+ {
+ if (parent->rb_left == node)
+ parent->rb_left = child;
+ else
+ parent->rb_right = child;
+ }
+ else
+ root->rb_node = child;
+
+ color:
+ if (color == RB_BLACK)
+ __rb_erase_color(child, parent, root);
+}
+
+/*
+ * This function returns the first node (in sort order) of the tree.
+ */
+struct rb_node *rb_first(const struct rb_root *root)
+{
+ struct rb_node *n;
+
+ n = root->rb_node;
+ if (!n)
+ return NULL;
+ while (n->rb_left)
+ n = n->rb_left;
+ return n;
+}
+
+struct rb_node *rb_last(const struct rb_root *root)
+{
+ struct rb_node *n;
+
+ n = root->rb_node;
+ if (!n)
+ return NULL;
+ while (n->rb_right)
+ n = n->rb_right;
+ return n;
+}
+
+struct rb_node *rb_next(const struct rb_node *node)
+{
+ struct rb_node *parent;
+
+ if (rb_parent(node) == node)
+ return NULL;
+
+ /* If we have a right-hand child, go down and then left as far
+ as we can. */
+ if (node->rb_right) {
+ node = node->rb_right;
+ while (node->rb_left)
+ node=node->rb_left;
+ return (struct rb_node *)node;
+ }
+
+ /* No right-hand children. Everything down and left is
+ smaller than us, so any 'next' node must be in the general
+ direction of our parent. Go up the tree; any time the
+ ancestor is a right-hand child of its parent, keep going
+ up. First time it's a left-hand child of its parent, said
+ parent is our 'next' node. */
+ while ((parent = rb_parent(node)) && node == parent->rb_right)
+ node = parent;
+
+ return parent;
+}
+
+struct rb_node *rb_prev(const struct rb_node *node)
+{
+ struct rb_node *parent;
+
+ if (rb_parent(node) == node)
+ return NULL;
+
+ /* If we have a left-hand child, go down and then right as far
+ as we can. */
+ if (node->rb_left) {
+ node = node->rb_left;
+ while (node->rb_right)
+ node=node->rb_right;
+ return (struct rb_node *)node;
+ }
+
+ /* No left-hand children. Go up till we find an ancestor which
+ is a right-hand child of its parent */
+ while ((parent = rb_parent(node)) && node == parent->rb_left)
+ node = parent;
+
+ return parent;
+}
+
+void rb_replace_node(struct rb_node *victim, struct rb_node *new,
+ struct rb_root *root)
+{
+ struct rb_node *parent = rb_parent(victim);
+
+ /* Set the surrounding nodes to point to the replacement */
+ if (parent) {
+ if (victim == parent->rb_left)
+ parent->rb_left = new;
+ else
+ parent->rb_right = new;
+ } else {
+ root->rb_node = new;
+ }
+ if (victim->rb_left)
+ rb_set_parent(victim->rb_left, new);
+ if (victim->rb_right)
+ rb_set_parent(victim->rb_right, new);
+
+ /* Copy the pointers/colour from the victim to the replacement */
+ *new = *victim;
+}
diff --git a/rbtree.h b/rbtree.h
new file mode 100644
index 0000000..10ab1e9
--- /dev/null
+++ b/rbtree.h
@@ -0,0 +1,205 @@
+/* Stolen from Linux 2.6.34 */
+
+/*
+ Red Black Trees
+ (C) 1999 Andrea Arcangeli <***@suse.de>
+
+ This program is free software; you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation; either version 2 of the License, or
+ (at your option) any later version.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program; if not, write to the Free Software
+ Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+
+ linux/include/linux/rbtree.h
+
+ To use rbtrees you'll have to implement your own insert and search cores.
+ This will avoid us to use callbacks and to drop drammatically performances.
+ I know it's not the cleaner way, but in C (not in C++) to get
+ performances and genericity...
+
+ Some example of insert and search follows here. The search is a plain
+ normal search over an ordered tree. The insert instead must be implemented
+ int two steps: as first thing the code must insert the element in
+ order as a red leaf in the tree, then the support library function
+ rb_insert_color() must be called. Such function will do the
+ not trivial work to rebalance the rbtree if necessary.
+
+-----------------------------------------------------------------------
+static inline struct page * rb_search_page_cache(struct inode * inode,
+ unsigned long offset)
+{
+ struct rb_node * n = inode->i_rb_page_cache.rb_node;
+ struct page * page;
+
+ while (n)
+ {
+ page = rb_entry(n, struct page, rb_page_cache);
+
+ if (offset < page->offset)
+ n = n->rb_left;
+ else if (offset > page->offset)
+ n = n->rb_right;
+ else
+ return page;
+ }
+ return NULL;
+}
+
+static inline struct page * __rb_insert_page_cache(struct inode * inode,
+ unsigned long offset,
+ struct rb_node * node)
+{
+ struct rb_node ** p = &inode->i_rb_page_cache.rb_node;
+ struct rb_node * parent = NULL;
+ struct page * page;
+
+ while (*p)
+ {
+ parent = *p;
+ page = rb_entry(parent, struct page, rb_page_cache);
+
+ if (offset < page->offset)
+ p = &(*p)->rb_left;
+ else if (offset > page->offset)
+ p = &(*p)->rb_right;
+ else
+ return page;
+ }
+
+ rb_link_node(node, parent, p);
+
+ return NULL;
+}
+
+static inline struct page * rb_insert_page_cache(struct inode * inode,
+ unsigned long offset,
+ struct rb_node * node)
+{
+ struct page * ret;
+ if ((ret = __rb_insert_page_cache(inode, offset, node)))
+ goto out;
+ rb_insert_color(node, &inode->i_rb_page_cache);
+ out:
+ return ret;
+}
+-----------------------------------------------------------------------
+*/
+
+#ifndef _LINUX_RBTREE_H
+#define _LINUX_RBTREE_H
+
+#include <stddef.h>
+
+/**
+ * container_of - cast a member of a structure out to the containing structure
+ *
+ * @ptr: the pointer to the member.
+ * @type: the type of the container struct this is embedded in.
+ * @member: the name of the member within the struct.
+ *
+ */
+#undef container_of
+#define container_of(ptr, type, member) ({ \
+ const __typeof__( ((type *)0)->member ) *__mptr = (ptr); \
+ (type *)( (char *)__mptr - offsetof(type,member) );})
+
+
+struct rb_node
+{
+ unsigned long rb_parent_color;
+#define RB_RED 0
+#define RB_BLACK 1
+ struct rb_node *rb_right;
+ struct rb_node *rb_left;
+} __attribute__((aligned(sizeof(long))));
+ /* The alignment might seem pointless, but allegedly CRIS needs it */
+
+struct rb_root
+{
+ struct rb_node *rb_node;
+};
+
+
+#define rb_parent(r) ((struct rb_node *)((r)->rb_parent_color & ~3))
+#define rb_color(r) ((r)->rb_parent_color & 1)
+#define rb_is_red(r) (!rb_color(r))
+#define rb_is_black(r) rb_color(r)
+#define rb_set_red(r) do { (r)->rb_parent_color &= ~1; } while (0)
+#define rb_set_black(r) do { (r)->rb_parent_color |= 1; } while (0)
+
+static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p)
+{
+ rb->rb_parent_color = (rb->rb_parent_color & 3) | (unsigned long)p;
+}
+static inline void rb_set_color(struct rb_node *rb, int color)
+{
+ rb->rb_parent_color = (rb->rb_parent_color & ~1) | color;
+}
+
+#define RB_ROOT (struct rb_root) { NULL, }
+#define rb_entry(ptr, type, member) container_of(ptr, type, member)
+
+#define RB_EMPTY_ROOT(root) ((root)->rb_node == NULL)
+#define RB_EMPTY_NODE(node) (rb_parent(node) == node)
+#define RB_CLEAR_NODE(node) (rb_set_parent(node, node))
+
+extern void rb_insert_color(struct rb_node *, struct rb_root *);
+extern void rb_erase(struct rb_node *, struct rb_root *);
+
+/* Find logical next and previous nodes in a tree */
+extern struct rb_node *rb_next(const struct rb_node *);
+extern struct rb_node *rb_prev(const struct rb_node *);
+extern struct rb_node *rb_first(const struct rb_root *);
+extern struct rb_node *rb_last(const struct rb_root *);
+
+/* Fast replacement of a single node without remove/rebalance/add/rebalance */
+extern void rb_replace_node(struct rb_node *victim, struct rb_node *new,
+ struct rb_root *root);
+
+static inline void rb_link_node(struct rb_node * node, struct rb_node * parent,
+ struct rb_node ** rb_link)
+{
+ node->rb_parent_color = (unsigned long )parent;
+ node->rb_left = node->rb_right = NULL;
+
+ *rb_link = node;
+}
+
+
+/* Cmus extensions */
+
+/**
+ * rbtree_for_each - iterate over a rbtree
+ * @pos: the &struct rb_node to use as a loop counter.
+ * @root: the root for your rbtree.
+ */
+#define rbtree_for_each(pos, root) \
+ for (pos = rb_first(root); pos; pos = rb_next(pos))
+
+/**
+ * rbtree_for_each_prev - iterate over a rbtree backwards
+ * @pos: the &struct rb_node to use as a loop counter.
+ * @root: the root for your rbtree.
+ */
+#define rbtree_for_each_prev(pos, root) \
+ for (pos = rb_last(root); pos; pos = rb_prev(pos))
+
+/**
+ * rbtree_for_each_safe - iterate over a rbtree safe against removal of rbtree node
+ * @pos: the &struct rb_node to use as a loop counter.
+ * @n: another &struct rb_node to use as temporary storage
+ * @root: the root for your rbtree.
+ */
+#define rbtree_for_each_safe(pos, n, root) \
+ for (pos = rb_first(root), n = pos ? rb_next(pos) : NULL; pos; \
+ pos = n, n = pos ? rb_next(pos) : NULL)
+
+#endif /* _LINUX_RBTREE_H */
diff --git a/track.c b/track.c
index eb2bd44..0895490 100644
--- a/track.c
+++ b/track.c
@@ -18,6 +18,7 @@ void simple_track_init(struct simple_track *track, struct track_info *ti)
{
track->info = ti;
track->marked = 0;
+ RB_CLEAR_NODE(&track->tree_node);
}

struct simple_track *simple_track_new(struct track_info *ti)
@@ -52,53 +53,53 @@ int simple_track_search_matches(void *data, struct iter *iter, const char *text)
return 1;
}

-struct shuffle_track *shuffle_list_get_next(struct list_head *head, struct shuffle_track *cur,
+struct shuffle_track *shuffle_list_get_next(struct rb_root *root, struct shuffle_track *cur,
int (*filter)(const struct simple_track *))
{
- struct list_head *item;
+ struct rb_node *node;

- if (cur == NULL)
- return to_shuffle_track(head->next);
+ if (!cur)
+ return tree_node_to_shuffle_track(rb_first(root));

- item = cur->node.next;
+ node = rb_next(&cur->tree_node);
again:
- while (item != head) {
- struct shuffle_track *track = to_shuffle_track(item);
+ while (node) {
+ struct shuffle_track *track = tree_node_to_shuffle_track(node);

if (filter((struct simple_track *)track))
return track;
- item = item->next;
+ node = rb_next(node);
}
if (repeat) {
if (auto_reshuffle)
- reshuffle(head);
- item = head->next;
+ shuffle_list_reshuffle(root);
+ node = rb_first(root);
goto again;
}
return NULL;
}

-struct shuffle_track *shuffle_list_get_prev(struct list_head *head, struct shuffle_track *cur,
+struct shuffle_track *shuffle_list_get_prev(struct rb_root *root, struct shuffle_track *cur,
int (*filter)(const struct simple_track *))
{
- struct list_head *item;
+ struct rb_node *node;

- if (cur == NULL)
- return to_shuffle_track(head->next);
+ if (!cur)
+ return tree_node_to_shuffle_track(rb_last(root));

- item = cur->node.prev;
+ node = rb_prev(&cur->tree_node);
again:
- while (item != head) {
- struct shuffle_track *track = to_shuffle_track(item);
+ while (node) {
+ struct shuffle_track *track = tree_node_to_shuffle_track(node);

if (filter((struct simple_track *)track))
return track;
- item = item->prev;
+ node = rb_prev(node);
}
if (repeat) {
if (auto_reshuffle)
- reshuffle(head);
- item = head->prev;
+ shuffle_list_reshuffle(root);
+ node = rb_last(root);
goto again;
}
return NULL;
@@ -150,26 +151,106 @@ again:
return NULL;
}

-void sorted_list_add_track(struct list_head *head, struct simple_track *track, const char * const *keys)
+void sorted_list_add_track(struct list_head *head, struct rb_root *tree_root, struct simple_track *track, const char * const *keys)
{
struct list_head *item;
+ struct rb_node **new = &(tree_root->rb_node), *parent = NULL, *curr, *prev;

- /* It is _much_ faster to iterate in reverse order because playlist
- * file is usually sorted.
- */
- item = head->prev;
- while (item != head) {
+ /* try to locate track in tree */
+ while (*new) {
+ // why not move this outside of loop?
const struct simple_track *a = to_simple_track(&track->node);
- const struct simple_track *b = to_simple_track(item);
-
- if (track_info_cmp(a->info, b->info, keys) >= 0)
+ const struct simple_track *b = tree_node_to_simple_track(*new);
+ int result = track_info_cmp(a->info, b->info, keys);
+
+ parent = *new;
+ if (result < 0)
+ new = &((*new)->rb_left);
+ else if (result > 0)
+ new = &((*new)->rb_right);
+ else
break;
- item = item->prev;
}
+
+ /* only add to tree if not there already */
+ if (!(*new)) {
+ rb_link_node(&track->tree_node, parent, new);
+ curr = *new;
+ rb_insert_color(&track->tree_node, tree_root);
+ } else
+ curr = *new;
+
+ /* locate previous list item or use list head */
+ prev = rb_prev(curr);
+ if (prev) {
+ struct simple_track *prev_track = tree_node_to_simple_track(prev);
+ item = &prev_track->node;
+ } else
+ item = head;
+
/* add after item */
- list_add(&track->node, item);
+ list_add_tail(&track->node, item);
+}
+
+static int compare_rand(const struct rb_node *a, const struct rb_node *b)
+{
+ struct shuffle_track *tr_a = tree_node_to_shuffle_track(a);
+ struct shuffle_track *tr_b = tree_node_to_shuffle_track(b);
+
+ if (tr_a->rand < tr_b->rand)
+ return -1;
+ if (tr_a->rand > tr_b->rand)
+ return +1;
+
+ return 0;
+}
+
+static void shuffle_track_init(struct shuffle_track *track)
+{
+ track->rand = rand() / ((double) RAND_MAX + 1);
+}
+
+void shuffle_list_add(struct shuffle_track *track, struct rb_root *tree_root)
+{
+ struct rb_node **new = &(tree_root->rb_node), *parent = NULL;
+
+ shuffle_track_init(track);
+
+ /* try to locate track in tree */
+ while (*new) {
+ int result = compare_rand(&track->tree_node, *new);
+
+ parent = *new;
+ if (result < 0)
+ new = &((*new)->rb_left);
+ else if (result > 0)
+ new = &((*new)->rb_right);
+ else {
+ /* very unlikely, try again! */
+ shuffle_list_add(track, tree_root);
+ return;
+ }
+ }
+
+ rb_link_node(&track->tree_node, parent, new);
+ rb_insert_color(&track->tree_node, tree_root);
+}
+
+void shuffle_list_reshuffle(struct rb_root *tree_root)
+{
+ struct rb_node *node, *tmp;
+ struct rb_root tmptree = RB_ROOT;
+
+ rbtree_for_each_safe(node, tmp, tree_root) {
+ struct shuffle_track *track = tree_node_to_shuffle_track(node);
+ rb_erase(node, tree_root);
+ shuffle_list_add(track, &tmptree);
+ }
+
+ tree_root->rb_node = tmptree.rb_node;
}

+/* expensive */
void list_add_rand(struct list_head *head, struct list_head *node, int nr)
{
struct list_head *item;
@@ -195,6 +276,7 @@ void list_add_rand(struct list_head *head, struct list_head *node, int nr)
}
}

+/* not used anymore */
void reshuffle(struct list_head *head)
{
struct list_head *item, *last;
diff --git a/track.h b/track.h
index f2a8258..99861ae 100644
--- a/track.h
+++ b/track.h
@@ -6,17 +6,20 @@
#define TRACK_H

#include "list.h"
+#include "rbtree.h"
#include "iter.h"

struct simple_track {
struct list_head node;
+ struct rb_node tree_node;
struct track_info *info;
unsigned int marked : 1;
};

struct shuffle_track {
struct simple_track simple_track;
- struct list_head node;
+ struct rb_node tree_node;
+ double rand;
};

static inline struct track_info *shuffle_track_info(const struct shuffle_track *track)
@@ -29,14 +32,19 @@ static inline struct simple_track *to_simple_track(const struct list_head *item)
return container_of(item, struct simple_track, node);
}

-static inline struct shuffle_track *to_shuffle_track(const struct list_head *item)
+static inline struct simple_track *iter_to_simple_track(const struct iter *iter)
{
- return container_of(item, struct shuffle_track, node);
+ return iter->data1;
}

-static inline struct simple_track *iter_to_simple_track(const struct iter *iter)
+static inline struct simple_track *tree_node_to_simple_track(const struct rb_node *node)
{
- return iter->data1;
+ return container_of(node, struct simple_track, tree_node);
+}
+
+static inline struct shuffle_track *tree_node_to_shuffle_track(const struct rb_node *node)
+{
+ return container_of(node, struct shuffle_track, tree_node);
}

/* NOTE: does not ref ti */
@@ -52,10 +60,10 @@ int simple_track_get_next(struct iter *);
int simple_track_search_get_current(void *data, struct iter *iter);
int simple_track_search_matches(void *data, struct iter *iter, const char *text);

-struct shuffle_track *shuffle_list_get_next(struct list_head *head, struct shuffle_track *cur,
+struct shuffle_track *shuffle_list_get_next(struct rb_root *root, struct shuffle_track *cur,
int (*filter)(const struct simple_track *));

-struct shuffle_track *shuffle_list_get_prev(struct list_head *head, struct shuffle_track *cur,
+struct shuffle_track *shuffle_list_get_prev(struct rb_root *root, struct shuffle_track *cur,
int (*filter)(const struct simple_track *));

struct simple_track *simple_list_get_next(struct list_head *head, struct simple_track *cur,
@@ -64,7 +72,7 @@ struct simple_track *simple_list_get_next(struct list_head *head, struct simple_
struct simple_track *simple_list_get_prev(struct list_head *head, struct simple_track *cur,
int (*filter)(const struct simple_track *));

-void sorted_list_add_track(struct list_head *head, struct simple_track *track, const char * const *keys);
+void sorted_list_add_track(struct list_head *head, struct rb_root *tree_root, struct simple_track *track, const char * const *keys);

void list_add_rand(struct list_head *head, struct list_head *node, int nr);
void reshuffle(struct list_head *head);
@@ -72,4 +80,7 @@ void reshuffle(struct list_head *head);
int simple_list_for_each_marked(struct list_head *head,
int (*cb)(void *data, struct track_info *ti), void *data, int reverse);

+void shuffle_list_add(struct shuffle_track *track, struct rb_root *tree_root);
+void shuffle_list_reshuffle(struct rb_root *tree_root);
+
#endif

--
1.7.0.4