It seems natural to use a tree to represent a tree.
speedup: 26% cpu time for initial indexing (~30k files)
---
command_mode.c | 21 ++--
iter.h | 50 +++++++
lib.c | 44 +++---
lib.h | 40 ++++---
rbtree.h | 32 +++++
tree.c | 396 ++++++++++++++++++++++++++++++--------------------------
6 files changed, 351 insertions(+), 232 deletions(-)
diff --git a/command_mode.c b/command_mode.c
index c236b6f..869f9d8 100644
--- a/command_mode.c
+++ b/command_mode.c
@@ -1801,11 +1801,11 @@ found:
static int count_albums(void)
{
struct artist *artist;
- struct list_head *item;
+ struct rb_node *tmp1, *tmp2;
int count = 0;
- list_for_each_entry(artist, &lib_artist_head, node) {
- list_for_each(item, &artist->album_head)
+ rb_for_each_entry(artist, tmp1, &lib_artist_root, tree_node) {
+ rb_for_each(tmp2, &artist->album_root)
count++;
}
return count;
@@ -1841,18 +1841,18 @@ static void cmd_lqueue(char *arg)
goto unlock;
r = rand_array(count, nmax);
- album = to_album(to_artist(lib_artist_head.next)->album_head.next);
+ album = to_album(rb_first(&to_artist(rb_first(&lib_artist_root))->album_root));
pos = 0;
for (i = 0; i < count; i++) {
struct album_list *a;
while (pos < r[i]) {
struct artist *artist = album->artist;
- if (album->node.next == &artist->album_head) {
- artist = to_artist(artist->node.next);
- album = to_album(artist->album_head.next);
+ if (!rb_next(&album->tree_node)) {
+ artist = to_artist(rb_next(&artist->tree_node));
+ album = to_album(rb_first(&artist->album_root));
} else {
- album = to_album(album->node.next);
+ album = to_album(rb_next(&album->tree_node));
}
pos++;
}
@@ -1867,8 +1867,9 @@ static void cmd_lqueue(char *arg)
struct list_head *next = item->next;
struct album_list *a = container_of(item, struct album_list, node);
struct tree_track *t;
-
- list_for_each_entry(t, &a->album->track_head, node)
+ struct rb_node *tmp;
+
+ rb_for_each_entry(t, tmp, &album->track_root, tree_node)
editable_add(&pq_editable, simple_track_new(tree_track_info(t)));
free(a);
item = next;
diff --git a/iter.h b/iter.h
index c8b596c..1669c49 100644
--- a/iter.h
+++ b/iter.h
@@ -120,4 +120,54 @@ int FUNC(struct iter *iter) \
return 1; \
}
+#define GENERIC_TREE_ITER_PREV(FUNC, TYPE, MEMBER) \
+int FUNC(struct iter *iter) \
+{ \
+ struct rb_root *root = iter->data0; \
+ TYPE *e = iter->data1; \
+ \
+ if (root == NULL) \
+ return 0; \
+ if (e == NULL) { \
+ /* head, get last */ \
+ if (rb_root_empty(root)) { \
+ /* empty, iter points to the head already */ \
+ return 0; \
+ } \
+ iter->data1 = container_of(rb_last(root), TYPE, MEMBER); \
+ return 1; \
+ } \
+ if (rb_prev(&e->MEMBER) == NULL) { \
+ iter->data1 = NULL; \
+ return 0; \
+ } \
+ iter->data1 = container_of(rb_prev(&e->MEMBER), TYPE, MEMBER); \
+ return 1; \
+}
+
+#define GENERIC_TREE_ITER_NEXT(FUNC, TYPE, MEMBER) \
+int FUNC(struct iter *iter) \
+{ \
+ struct rb_root *root = iter->data0; \
+ TYPE *e = iter->data1; \
+ \
+ if (root == NULL) \
+ return 0; \
+ if (e == NULL) { \
+ /* head, get first */ \
+ if (rb_root_empty(root)) { \
+ /* empty, iter points to the head already */ \
+ return 0; \
+ } \
+ iter->data1 = container_of(rb_first(root), TYPE, MEMBER); \
+ return 1; \
+ } \
+ if (rb_next(&e->MEMBER) == NULL) { \
+ iter->data1 = NULL; \
+ return 0; \
+ } \
+ iter->data1 = container_of(rb_next(&e->MEMBER), TYPE, MEMBER); \
+ return 1; \
+}
+
#endif
diff --git a/lib.c b/lib.c
index ebebf88..429678a 100644
--- a/lib.c
+++ b/lib.c
@@ -151,27 +151,27 @@ void lib_add_track(struct track_info *ti)
static struct tree_track *album_first_track(const struct album *album)
{
- return to_tree_track(album->track_head.next);
+ return to_tree_track(rb_first(&album->track_root));
}
static struct tree_track *artist_first_track(const struct artist *artist)
{
- return album_first_track(to_album(artist->album_head.next));
+ return album_first_track(to_album(rb_first(&artist->album_root)));
}
static struct tree_track *normal_get_first(void)
{
- return artist_first_track(to_artist(lib_artist_head.next));
+ return artist_first_track(to_artist(rb_first(&lib_artist_root)));
}
static struct tree_track *album_last_track(const struct album *album)
{
- return to_tree_track(album->track_head.prev);
+ return to_tree_track(rb_last(&album->track_root));
}
static struct tree_track *artist_last_track(const struct artist *artist)
{
- return album_last_track(to_album(artist->album_head.prev));
+ return album_last_track(to_album(rb_last(&artist->album_root)));
}
static int aaa_mode_filter(const struct simple_track *track)
@@ -196,9 +196,9 @@ static struct tree_track *normal_get_next(void)
return normal_get_first();
/* not last track of the album? */
- if (lib_cur_track->node.next != &CUR_ALBUM->track_head) {
+ if (rb_next(&lib_cur_track->tree_node)) {
/* next track of the current album */
- return to_tree_track(lib_cur_track->node.next);
+ return to_tree_track(rb_next(&lib_cur_track->tree_node));
}
if (aaa_mode == AAA_MODE_ALBUM) {
@@ -209,9 +209,9 @@ static struct tree_track *normal_get_next(void)
}
/* not last album of the artist? */
- if (CUR_ALBUM->node.next != &CUR_ARTIST->album_head) {
+ if (rb_next(&CUR_ALBUM->tree_node) != NULL) {
/* first track of the next album */
- return album_first_track(to_album(CUR_ALBUM->node.next));
+ return album_first_track(to_album(rb_next(&CUR_ALBUM->tree_node)));
}
if (aaa_mode == AAA_MODE_ARTIST) {
@@ -222,9 +222,9 @@ static struct tree_track *normal_get_next(void)
}
/* not last artist of the library? */
- if (CUR_ARTIST->node.next != &lib_artist_head) {
+ if (rb_next(&CUR_ARTIST->tree_node) != NULL) {
/* first track of the next artist */
- return artist_first_track(to_artist(CUR_ARTIST->node.next));
+ return artist_first_track(to_artist(rb_next(&CUR_ARTIST->tree_node)));
}
if (!repeat)
@@ -240,42 +240,42 @@ static struct tree_track *normal_get_prev(void)
return normal_get_first();
/* not first track of the album? */
- if (lib_cur_track->node.prev != &CUR_ALBUM->track_head) {
+ if (rb_prev(&lib_cur_track->tree_node)) {
/* prev track of the album */
- return to_tree_track(lib_cur_track->node.prev);
+ return to_tree_track(rb_prev(&lib_cur_track->tree_node));
}
if (aaa_mode == AAA_MODE_ALBUM) {
if (!repeat)
return NULL;
/* last track of the album */
- return to_tree_track(CUR_ALBUM->track_head.prev);
+ return to_tree_track(rb_prev(&CUR_ALBUM->tree_node));
}
/* not first album of the artist? */
- if (CUR_ALBUM->node.prev != &CUR_ARTIST->album_head) {
+ if (rb_prev(&CUR_ALBUM->tree_node) != NULL) {
/* last track of the prev album of the artist */
- return album_last_track(to_album(CUR_ALBUM->node.prev));
+ return album_last_track(to_album(rb_prev(&CUR_ALBUM->tree_node)));
}
if (aaa_mode == AAA_MODE_ARTIST) {
if (!repeat)
return NULL;
/* last track of the last album of the artist */
- return album_last_track(to_album(CUR_ARTIST->album_head.prev));
+ return album_last_track(to_album(rb_last(&CUR_ARTIST->album_root)));
}
/* not first artist of the library? */
- if (CUR_ARTIST->node.prev != &lib_artist_head) {
+ if (rb_prev(&CUR_ARTIST->tree_node) != NULL) {
/* last track of the last album of the prev artist */
- return artist_last_track(to_artist(CUR_ARTIST->node.prev));
+ return artist_last_track(to_artist(rb_prev(&CUR_ARTIST->tree_node)));
}
if (!repeat)
return NULL;
/* last track */
- return artist_last_track(to_artist(lib_artist_head.prev));
+ return artist_last_track(to_artist(rb_last(&lib_artist_root)));
}
/* set next/prev (tree) }}} */
@@ -327,7 +327,7 @@ struct track_info *lib_set_next(void)
{
struct tree_track *track;
- if (list_empty(&lib_artist_head)) {
+ if (rb_root_empty(&lib_artist_root)) {
BUG_ON(lib_cur_track != NULL);
return NULL;
}
@@ -347,7 +347,7 @@ struct track_info *lib_set_prev(void)
{
struct tree_track *track;
- if (list_empty(&lib_artist_head)) {
+ if (rb_root_empty(&lib_artist_root)) {
BUG_ON(lib_cur_track != NULL);
return NULL;
}
diff --git a/lib.h b/lib.h
index 2581b2a..e220c7f 100644
--- a/lib.h
+++ b/lib.h
@@ -9,12 +9,16 @@
#include "search.h"
#include "track_info.h"
#include "expr.h"
+#include "rbtree.h"
#include <sys/time.h>
struct tree_track {
struct shuffle_track shuffle_track;
- struct list_head node;
+
+ /* position in track search tree */
+ struct rb_node tree_node;
+
struct album *album;
};
@@ -23,30 +27,34 @@ static inline struct track_info *tree_track_info(const struct tree_track *track)
return ((struct simple_track *)track)->info;
}
-static inline struct tree_track *to_tree_track(const struct list_head *item)
+static inline struct tree_track *to_tree_track(const struct rb_node *node)
{
- return container_of(item, struct tree_track, node);
+ return container_of(node, struct tree_track, tree_node);
}
+
struct album {
- /* next/prev album */
- struct list_head node;
+ /* position in album search tree */
+ struct rb_node tree_node;
- /* list of tracks */
- struct list_head track_head;
+ /* root of track tree */
+ struct rb_root track_root;
struct artist *artist;
char *name;
/* date of the first track added to this album */
int date;
+
+ unsigned int is_compilation : 1;
};
struct artist {
- /* next/prev artist */
- struct list_head node;
+ /* position in artist search tree */
+ struct rb_node tree_node;
+
+ /* root of album tree */
+ struct rb_root album_root;
- /* list of albums */
- struct list_head album_head;
char *name;
char *sort_name;
char *auto_sort_name;
@@ -72,7 +80,7 @@ extern struct searchable *tree_searchable;
extern struct window *lib_tree_win;
extern struct window *lib_track_win;
extern struct window *lib_cur_win;
-extern struct list_head lib_artist_head;
+extern struct rb_root lib_artist_root;
#define CUR_ALBUM (lib_cur_track->album)
#define CUR_ARTIST (lib_cur_track->album->artist)
@@ -124,14 +132,14 @@ static inline struct tree_track *iter_to_tree_track(const struct iter *iter)
return iter->data1;
}
-static inline struct artist *to_artist(const struct list_head *item)
+static inline struct artist *to_artist(const struct rb_node *node)
{
- return container_of(item, struct artist, node);
+ return container_of(node, struct artist, tree_node);
}
-static inline struct album *to_album(const struct list_head *item)
+static inline struct album *to_album(const struct rb_node *node)
{
- return container_of(item, struct album, node);
+ return container_of(node, struct album, tree_node);
}
#endif
diff --git a/rbtree.h b/rbtree.h
index dfbb1ca..2554be6 100644
--- a/rbtree.h
+++ b/rbtree.h
@@ -176,6 +176,16 @@ static inline void rb_link_node(struct rb_node * node, struct rb_node * parent,
/* Cmus extensions */
+static inline void rb_root_init(struct rb_root *root)
+{
+ root->rb_node = NULL;
+}
+
+static inline int rb_root_empty(struct rb_root *root)
+{
+ return RB_EMPTY_ROOT(root);
+}
+
/**
* rb_for_each - iterate over a rbtree
* @pos: the &struct rb_node to use as a loop counter.
@@ -202,4 +212,26 @@ static inline void rb_link_node(struct rb_node * node, struct rb_node * parent,
for (pos = rb_first(root), n = pos ? rb_next(pos) : NULL; pos; \
pos = n, n = pos ? rb_next(pos) : NULL)
+/**
+ * rb_for_each_entry - iterate over a rbtree of given type
+ * @pos: the &struct rb_node to use as a loop counter.
+ * @t: the type * to use as a loop counter.
+ * @root: the root for your rbtree.
+ * @member: the name of the rb_node-struct within the struct.
+ */
+#define rb_for_each_entry(t, pos, root, member) \
+ for (pos = rb_first(root), t = pos ? rb_entry(pos, __typeof__(*t), member) : NULL; \
+ pos; pos = rb_next(pos), t = pos ? rb_entry(pos, __typeof__(*t), member) : NULL)
+
+/**
+ * rb_for_each_entry_reverse - iterate backwards over a rbtree of given type
+ * @pos: the &struct rb_node to use as a loop counter.
+ * @t: the type * to use as a loop counter.
+ * @root: the root for your rbtree.
+ * @member: the name of the rb_node-struct within the struct.
+ */
+#define rb_for_each_entry_reverse(t, pos, root, member) \
+ for (pos = rb_last(root), t = pos ? rb_entry(pos, __typeof__(*t), member) : NULL; \
+ pos; pos = rb_prev(pos), t = pos ? rb_entry(pos, __typeof__(*t), member) : NULL)
+
#endif /* _LINUX_RBTREE_H */
diff --git a/tree.c b/tree.c
index 5f11a6e..77401ca 100644
--- a/tree.c
+++ b/tree.c
@@ -11,6 +11,7 @@
#include "mergesort.h"
#include "options.h"
#include "u_collate.h"
+#include "rbtree.h"
#include <ctype.h>
#include <stdio.h>
@@ -19,46 +20,46 @@ struct searchable *tree_searchable;
struct window *lib_tree_win;
struct window *lib_track_win;
struct window *lib_cur_win;
-LIST_HEAD(lib_artist_head);
+struct rb_root lib_artist_root;
/* tree (search) iterators {{{ */
static int tree_search_get_prev(struct iter *iter)
{
- struct list_head *head = iter->data0;
+ struct rb_root *root = iter->data0;
struct tree_track *track = iter->data1;
struct artist *artist;
struct album *album;
BUG_ON(iter->data2);
- if (head == NULL)
+ if (root == NULL)
return 0;
if (track == NULL) {
/* head, get last track */
- if (head->prev == head) {
+ if (rb_root_empty(root)) {
/* empty, iter points to the head already */
return 0;
}
- artist = to_artist(head->prev);
- album = to_album(artist->album_head.prev);
- iter->data1 = to_tree_track(album->track_head.prev);
+ artist = to_artist(rb_last(root));
+ album = to_album(rb_last(&artist->album_root));
+ iter->data1 = to_tree_track(rb_last(&album->track_root));
return 1;
}
/* prev track */
- if (track->node.prev == &track->album->track_head || search_restricted) {
+ if (rb_prev(&track->tree_node) == NULL || search_restricted) {
/* prev album */
- if (track->album->node.prev == &track->album->artist->album_head) {
+ if (rb_prev(&track->album->tree_node) == NULL) {
/* prev artist */
- if (track->album->artist->node.prev == &lib_artist_head)
+ if (rb_prev(&track->album->artist->tree_node) == NULL)
return 0;
- artist = to_artist(track->album->artist->node.prev);
- album = to_album(artist->album_head.prev);
- track = to_tree_track(album->track_head.prev);
+ artist = to_artist(rb_prev(&track->album->artist->tree_node));
+ album = to_album(rb_last(&artist->album_root));
+ track = to_tree_track(rb_last(&album->track_root));
} else {
- album = to_album(track->album->node.prev);
- track = to_tree_track(album->track_head.prev);
+ album = to_album(rb_prev(&track->album->tree_node));
+ track = to_tree_track(rb_last(&album->track_root));
}
} else {
- track = to_tree_track(track->node.prev);
+ track = to_tree_track(rb_prev(&track->tree_node));
}
iter->data1 = track;
return 1;
@@ -66,41 +67,41 @@ static int tree_search_get_prev(struct iter *iter)
static int tree_search_get_next(struct iter *iter)
{
- struct list_head *head = iter->data0;
+ struct rb_root *root = iter->data0;
struct tree_track *track = iter->data1;
struct artist *artist;
struct album *album;
BUG_ON(iter->data2);
- if (head == NULL)
+ if (root == NULL)
return 0;
if (track == NULL) {
/* head, get first track */
- if (head->next == head) {
+ if (rb_root_empty(root)) {
/* empty, iter points to the head already */
return 0;
}
- artist = to_artist(head->next);
- album = to_album(artist->album_head.next);
- iter->data1 = to_tree_track(album->track_head.next);
+ artist = to_artist(rb_first(root));
+ album = to_album(rb_first(&artist->album_root));
+ iter->data1 = to_tree_track(rb_last(&album->track_root));
return 1;
}
/* next track */
- if (track->node.next == &track->album->track_head || search_restricted) {
+ if (rb_next(&track->tree_node) == NULL || search_restricted) {
/* next album */
- if (track->album->node.next == &track->album->artist->album_head) {
+ if (rb_next(&track->album->tree_node) == NULL) {
/* next artist */
- if (track->album->artist->node.next == &lib_artist_head)
+ if (rb_next(&track->album->artist->tree_node) == NULL)
return 0;
- artist = to_artist(track->album->artist->node.next);
- album = to_album(artist->album_head.next);
- track = to_tree_track(album->track_head.next);
+ artist = to_artist(rb_next(&track->album->artist->tree_node));
+ album = to_album(rb_first(&artist->album_root));
+ track = to_tree_track(rb_first(&album->track_root));
} else {
- album = to_album(track->album->node.next);
- track = to_tree_track(album->track_head.next);
+ album = to_album(rb_next(&track->album->tree_node));
+ track = to_tree_track(rb_first(&album->track_root));
}
} else {
- track = to_tree_track(track->node.next);
+ track = to_tree_track(rb_next(&track->tree_node));
}
iter->data1 = track;
return 1;
@@ -110,21 +111,21 @@ static int tree_search_get_next(struct iter *iter)
/* tree window iterators {{{ */
static int tree_get_prev(struct iter *iter)
{
- struct list_head *head = iter->data0;
+ struct rb_root *root = iter->data0;
struct artist *artist = iter->data1;
struct album *album = iter->data2;
- BUG_ON(head == NULL);
+ BUG_ON(root == NULL);
BUG_ON(artist == NULL && album != NULL);
if (artist == NULL) {
/* head, get last artist and/or album */
- if (head->prev == head) {
+ if (rb_root_empty(root)) {
/* empty, iter points to the head already */
return 0;
}
- artist = to_artist(head->prev);
+ artist = to_artist(rb_last(root));
if (artist->expanded) {
- album = to_album(artist->album_head.prev);
+ album = to_album(rb_last(&artist->album_root));
} else {
album = NULL;
}
@@ -134,46 +135,46 @@ static int tree_get_prev(struct iter *iter)
}
if (artist->expanded && album) {
/* prev album */
- if (album->node.prev == &artist->album_head) {
+ if (rb_prev(&album->tree_node) == NULL) {
iter->data2 = NULL;
return 1;
} else {
- iter->data2 = to_album(album->node.prev);
+ iter->data2 = to_album(rb_prev(&album->tree_node));
return 1;
}
}
/* prev artist */
- if (artist->node.prev == &lib_artist_head) {
+ if (rb_prev(&artist->tree_node) == NULL) {
iter->data1 = NULL;
iter->data2 = NULL;
return 0;
}
- artist = to_artist(artist->node.prev);
+ artist = to_artist(rb_prev(&artist->tree_node));
iter->data1 = artist;
iter->data2 = NULL;
if (artist->expanded) {
/* last album */
- iter->data2 = to_album(artist->album_head.prev);
+ iter->data2 = to_album(rb_last(&artist->album_root));
}
return 1;
}
static int tree_get_next(struct iter *iter)
{
- struct list_head *head = iter->data0;
+ struct rb_root *root = iter->data0;
struct artist *artist = iter->data1;
struct album *album = iter->data2;
- BUG_ON(head == NULL);
+ BUG_ON(root == NULL);
BUG_ON(artist == NULL && album != NULL);
if (artist == NULL) {
/* head, get first artist */
- if (head->next == head) {
+ if (rb_root_empty(root)) {
/* empty, iter points to the head already */
return 0;
}
- iter->data1 = to_artist(head->next);
+ iter->data1 = to_artist(rb_first(root));
iter->data2 = NULL;
return 1;
}
@@ -181,54 +182,54 @@ static int tree_get_next(struct iter *iter)
/* next album */
if (album == NULL) {
/* first album */
- iter->data2 = to_album(artist->album_head.next);
+ iter->data2 = to_album(rb_first(&artist->album_root));
return 1;
}
- if (album->node.next != &artist->album_head) {
- iter->data2 = to_album(album->node.next);
+ if (rb_next(&album->tree_node) != NULL) {
+ iter->data2 = to_album(rb_next(&album->tree_node));
return 1;
}
}
/* next artist */
- if (artist->node.next == head) {
+ if (rb_next(&artist->tree_node) == NULL) {
iter->data1 = NULL;
iter->data2 = NULL;
return 0;
}
- iter->data1 = to_artist(artist->node.next);
+ iter->data1 = to_artist(rb_next(&artist->tree_node));
iter->data2 = NULL;
return 1;
}
/* }}} */
-static GENERIC_ITER_PREV(tree_track_get_prev, struct tree_track, node)
-static GENERIC_ITER_NEXT(tree_track_get_next, struct tree_track, node)
+static GENERIC_TREE_ITER_PREV(tree_track_get_prev, struct tree_track, tree_node)
+static GENERIC_TREE_ITER_NEXT(tree_track_get_next, struct tree_track, tree_node)
static inline void tree_search_track_to_iter(struct tree_track *track, struct iter *iter)
{
- iter->data0 = &lib_artist_head;
+ iter->data0 = &lib_artist_root;
iter->data1 = track;
iter->data2 = NULL;
}
static inline void album_to_iter(struct album *album, struct iter *iter)
{
- iter->data0 = &lib_artist_head;
+ iter->data0 = &lib_artist_root;
iter->data1 = album->artist;
iter->data2 = album;
}
static inline void artist_to_iter(struct artist *artist, struct iter *iter)
{
- iter->data0 = &lib_artist_head;
+ iter->data0 = &lib_artist_root;
iter->data1 = artist;
iter->data2 = NULL;
}
static inline void tree_track_to_iter(struct tree_track *track, struct iter *iter)
{
- iter->data0 = &track->album->track_head;
+ iter->data0 = &track->album->track_root;
iter->data1 = track;
iter->data2 = NULL;
}
@@ -241,7 +242,7 @@ static int tree_search_get_current(void *data, struct iter *iter)
struct tree_track *track;
struct iter tmpiter;
- if (list_empty(&lib_artist_head))
+ if (rb_root_empty(&lib_artist_root))
return 0;
if (window_get_sel(lib_track_win, &tmpiter)) {
track = iter_to_tree_track(&tmpiter);
@@ -253,15 +254,15 @@ static int tree_search_get_current(void *data, struct iter *iter)
* set tmp to the first track of the selected artist */
window_get_sel(lib_tree_win, &tmpiter);
artist = iter_to_artist(&tmpiter);
- album = to_album(artist->album_head.next);
- track = to_tree_track(album->track_head.next);
+ album = to_album(rb_first(&artist->album_root));
+ track = to_tree_track(rb_first(&album->track_root));
tree_search_track_to_iter(track, iter);
return 1;
}
static inline struct tree_track *iter_to_tree_search_track(const struct iter *iter)
{
- BUG_ON(iter->data0 != &lib_artist_head);
+ BUG_ON(iter->data0 != &lib_artist_root);
return iter->data1;
}
@@ -312,7 +313,7 @@ static void tree_sel_changed(void)
if (album == NULL) {
window_set_empty(lib_track_win);
} else {
- window_set_contents(lib_track_win, &album->track_head);
+ window_set_contents(lib_track_win, &album->track_root);
}
}
@@ -358,7 +359,7 @@ static struct artist *artist_new(const char *name, const char *sort_name)
a->sort_name = sort_name ? xstrdup(sort_name) : NULL;
a->auto_sort_name = auto_artist_sort_name(name);
a->expanded = 0;
- list_init(&a->album_head);
+ rb_root_init(&a->album_root);
return a;
}
@@ -371,14 +372,15 @@ static void artist_free(struct artist *artist)
free(artist);
}
-static struct album *album_new(struct artist *artist, const char *name, int date)
+static struct album *album_new(struct artist *artist, const char *name, int date, int is_compilation)
{
struct album *album = xnew(struct album, 1);
album->name = xstrdup(name);
album->date = date;
- list_init(&album->track_head);
+ rb_root_init(&album->track_root);
album->artist = artist;
+ album->is_compilation = is_compilation;
return album;
}
@@ -393,7 +395,7 @@ void tree_init(void)
{
struct iter iter;
- list_init(&lib_artist_head);
+ rb_root_init(&lib_artist_root);
lib_tree_win = window_new(tree_get_prev, tree_get_next);
lib_track_win = window_new(tree_track_get_prev, tree_track_get_next);
@@ -402,9 +404,9 @@ void tree_init(void)
lib_tree_win->sel_changed = tree_sel_changed;
window_set_empty(lib_track_win);
- window_set_contents(lib_tree_win, &lib_artist_head);
+ window_set_contents(lib_tree_win, &lib_artist_root);
- iter.data0 = &lib_artist_head;
+ iter.data0 = &lib_artist_root;
iter.data1 = NULL;
iter.data2 = NULL;
tree_searchable = searchable_new(NULL, &iter, &tree_search_ops);
@@ -417,7 +419,7 @@ struct track_info *tree_set_selected(void)
struct track_info *info;
struct iter sel;
- if (list_empty(&lib_artist_head))
+ if (rb_root_empty(&lib_artist_root))
return NULL;
tree_win_get_selected(&artist, &album);
@@ -425,8 +427,8 @@ struct track_info *tree_set_selected(void)
/* only artist selected, track window is empty
* => get first album of the selected artist and first track of that album
*/
- album = to_album(artist->album_head.next);
- lib_cur_track = to_tree_track(album->track_head.next);
+ album = to_album(rb_first(&artist->album_root));
+ lib_cur_track = to_tree_track(rb_first(&album->track_root));
} else {
window_get_sel(lib_track_win, &sel);
lib_cur_track = iter_to_tree_track(&sel);
@@ -440,31 +442,6 @@ struct track_info *tree_set_selected(void)
return info;
}
-static void find_artist_and_album(const char *artist_name,
- const char *album_name, struct artist **_artist,
- struct album **_album)
-{
- struct artist *artist;
- struct album *album;
-
- list_for_each_entry(artist, &lib_artist_head, node) {
- if (u_strcase_equal(artist->name, artist_name)) {
- *_artist = artist;
- list_for_each_entry(album, &artist->album_head, node) {
- if (u_strcase_equal(album->name, album_name)) {
- *_album = album;
- return;
- }
- }
- *_album = NULL;
- return;
- }
- }
- *_artist = NULL;
- *_album = NULL;
- return;
-}
-
static int special_name_cmp(const char *a, const char *b)
{
/* keep <Stream> etc. top */
@@ -483,79 +460,121 @@ static int special_album_cmp(const struct album *a, const struct album *b)
if (cmp)
return cmp;
- if (a->date != b->date)
+ if (a->date != b->date && !a->is_compilation && !b->is_compilation)
return a->date - b->date;
return u_strcasecoll(a->name, b->name);
}
-static void insert_artist(struct artist *artist)
+static struct artist *do_find_artist(const struct artist *artist,
+ struct rb_root *root,
+ struct rb_node ***p_new,
+ struct rb_node **p_parent)
{
+ struct rb_node **new = &(root->rb_node), *parent = NULL;
const char *a = artist_sort_name(artist);
- struct list_head *item;
- list_for_each(item, &lib_artist_head) {
- const char *b = artist_sort_name(to_artist(item));
+ while (*new) {
+ struct artist *cur_artist = to_artist(*new);
+ const char *b = artist_sort_name(cur_artist);
+ int result = special_name_cmp(a, b);
- if (special_name_cmp(a, b) < 0)
- break;
+ parent = *new;
+ if (result < 0)
+ new = &((*new)->rb_left);
+ else if (result > 0)
+ new = &((*new)->rb_right);
+ else
+ return cur_artist;
}
- /* add before item */
- list_add_tail(&artist->node, item);
+ if (p_new)
+ *p_new = new;
+ if (p_parent)
+ *p_parent = parent;
+ return NULL;
}
-static int artist_cmp(const struct list_head *a, const struct list_head *b)
+static void insert_artist(struct artist *artist, struct rb_root *root)
{
- return special_name_cmp(artist_sort_name(to_artist(a)),
- artist_sort_name(to_artist(b)));
+ struct rb_node **new = &(root->rb_node), *parent = NULL;
+ struct artist *found;
+
+ found = do_find_artist(artist, root, &new, &parent);
+ if (!found) {
+ rb_link_node(&artist->tree_node, parent, new);
+ rb_insert_color(&artist->tree_node, root);
+ }
}
void tree_sort_artists(void)
{
- list_mergesort(&lib_artist_head, artist_cmp);
+ struct rb_node *node, *tmp;
+ struct rb_root tmptree = RB_ROOT;
+
+ rb_for_each_safe(node, tmp, &lib_artist_root) {
+ struct artist *a = to_artist(node);
+ rb_erase(node, &lib_artist_root);
+ insert_artist(a, &tmptree);
+ }
+ lib_artist_root.rb_node = tmptree.rb_node;
window_changed(lib_tree_win);
}
-static struct artist *add_artist(const char *name, const char *sort_name)
+static void add_artist(struct artist *artist)
{
- struct artist *a = artist_new(name, sort_name);
-
- insert_artist(a);
+ insert_artist(artist, &lib_artist_root);
+}
- return a;
+static struct artist *find_artist(const struct artist *artist)
+{
+ return do_find_artist(artist, &lib_artist_root, NULL, NULL);
}
-static struct album *artist_add_album(struct artist *artist, const char *name, int date, int is_compilation)
+static struct album *do_find_album(const struct album *album,
+ struct rb_node ***p_new,
+ struct rb_node **p_parent)
{
- struct list_head *item;
- struct album *album;
+ struct rb_node **new = &(album->artist->album_root.rb_node), *parent = NULL;
- album = album_new(artist, name, date);
+ while (*new) {
+ struct album *a = to_album(*new);
+ /*
+ * Sort regular albums by date, but sort compilations
+ * alphabetically.
+ */
+ int result = special_album_cmp(album, a);
- /*
- * Sort regular albums by date, but sort compilations
- * alphabetically.
- */
- if (is_compilation) {
- list_for_each(item, &artist->album_head) {
- struct album *a = to_album(item);
+ parent = *new;
+ if (result < 0)
+ new = &((*new)->rb_left);
+ else if (result > 0)
+ new = &((*new)->rb_right);
+ else
+ return a;
+ }
+ if (p_new)
+ *p_new = new;
+ if (p_parent)
+ *p_parent = parent;
+ return NULL;
+}
- if (special_name_cmp(name, a->name) < 0)
- break;
- }
- } else {
- list_for_each(item, &artist->album_head) {
- struct album *a = to_album(item);
+static struct album *find_album(const struct album *album)
+{
+ return do_find_album(album, NULL, NULL);
+}
- if (special_album_cmp(album, a) < 0)
- break;
- }
- }
+static void add_album(struct album *album)
+{
+ struct rb_node **new = &(album->artist->album_root.rb_node), *parent = NULL;
+ struct album *found;
- /* add before item */
- list_add_tail(&album->node, item);
- return album;
+ found = do_find_album(album, &new, &parent);
+ if (!found) {
+ rb_link_node(&album->tree_node, parent, new);
+ rb_insert_color(&album->tree_node, &album->artist->album_root);
+ }
}
static void album_add_track(struct album *album, struct tree_track *track)
@@ -569,26 +588,34 @@ static void album_add_track(struct album *album, struct tree_track *track)
static const char * const album_track_sort_keys[] = {
"discnumber", "tracknumber", "filename", NULL
};
- struct list_head *item;
+ struct rb_node **new = &(album->track_root.rb_node), *parent = NULL;
track->album = album;
- list_for_each(item, &album->track_head) {
- const struct simple_track *a = (const struct simple_track *)track;
- const struct simple_track *b = (const struct simple_track *)to_tree_track(item);
-
- if (track_info_cmp(a->info, b->info, album_track_sort_keys) < 0)
- break;
+ while (*new) {
+ const struct simple_track *a = (const struct simple_track *) track;
+ const struct simple_track *b = (const struct simple_track *) to_tree_track(*new);
+ int result = track_info_cmp(a->info, b->info, album_track_sort_keys);
+
+ parent = *new;
+ if (result < 0)
+ new = &((*new)->rb_left);
+ else if (result > 0)
+ new = &((*new)->rb_right);
+ else
+ /* only add to tree if not there already */
+ return;
}
- /* add before item */
- list_add_tail(&track->node, item);
+
+ rb_link_node(&track->tree_node, parent, new);
+ rb_insert_color(&track->tree_node, &album->track_root);
}
void tree_add_track(struct tree_track *track)
{
const struct track_info *ti = tree_track_info(track);
const char *album_name, *artist_name, *artistsort_name = NULL;
- struct artist *artist;
- struct album *album;
+ struct artist *artist, *new_artist;
+ struct album *album, *new_album;
int date;
int is_va_compilation = 0;
@@ -605,7 +632,18 @@ void tree_add_track(struct tree_track *track)
is_va_compilation = track_is_va_compilation(ti->comments);
}
- find_artist_and_album(artist_name, album_name, &artist, &album);
+ new_artist = artist_new(artist_name, artistsort_name);
+ new_album = album = NULL;
+
+ artist = find_artist(new_artist);
+ if (artist) {
+ artist_free(new_artist);
+ new_album = album_new(artist, album_name, date, is_va_compilation);
+ album = find_album(new_album);
+ if (album)
+ album_free(new_album);
+ } else
+ new_album = album_new(new_artist, album_name, date, is_va_compilation);
if (artist) {
/* If it makes sense to update sort_name, do it */
@@ -627,16 +665,16 @@ void tree_add_track(struct tree_track *track)
if (album_selected(album))
window_changed(lib_track_win);
} else if (artist) {
- album = artist_add_album(artist, album_name, date, is_va_compilation);
- album_add_track(album, track);
+ add_album(new_album);
+ album_add_track(new_album, track);
if (artist->expanded)
/* album is not selected => no need to update track_win */
window_changed(lib_tree_win);
} else {
- artist = add_artist(artist_name, artistsort_name);
- album = artist_add_album(artist, album_name, date, is_va_compilation);
- album_add_track(album, track);
+ add_artist(new_artist);
+ add_album(new_album);
+ album_add_track(new_album, track);
window_changed(lib_tree_win);
}
@@ -644,43 +682,31 @@ void tree_add_track(struct tree_track *track)
static void remove_sel_artist(struct artist *artist)
{
- struct list_head *aitem, *ahead;
+ struct rb_node *a_node, *a_tmp;
- ahead = &artist->album_head;
- aitem = ahead->next;
- while (aitem != ahead) {
- struct list_head *titem, *thead;
- struct list_head *anext = aitem->next;
- struct album *album = to_album(aitem);
+ rb_for_each_safe(a_node, a_tmp, &artist->album_root) {
+ struct rb_node *t_node, *t_tmp;
+ struct album *album = to_album(a_node);
- thead = &album->track_head;
- titem = thead->next;
- while (titem != thead) {
- struct list_head *tnext = titem->next;
- struct tree_track *track = to_tree_track(titem);
+ rb_for_each_safe(t_node, t_tmp, &album->track_root) {
+ struct tree_track *track = to_tree_track(t_node);
editable_remove_track(&lib_editable, (struct simple_track *)track);
- titem = tnext;
}
/* all tracks removed => album removed
* if the last album was removed then the artist was removed too
*/
- aitem = anext;
}
}
static void remove_sel_album(struct album *album)
{
- struct list_head *item, *head;
+ struct rb_node *node, *tmp;
- head = &album->track_head;
- item = head->next;
- while (item != head) {
- struct list_head *next = item->next;
- struct tree_track *track = to_tree_track(item);
+ rb_for_each_safe(node, tmp, &album->track_root) {
+ struct tree_track *track = to_tree_track(node);
editable_remove_track(&lib_editable, (struct simple_track *)track);
- item = next;
}
}
@@ -758,7 +784,7 @@ static void remove_track(struct tree_track *track)
tree_track_to_iter(track, &iter);
window_row_vanishes(lib_track_win, &iter);
}
- list_del(&track->node);
+ rb_erase(&track->tree_node, &track->album->track_root);
}
static void remove_album(struct album *album)
@@ -769,7 +795,7 @@ static void remove_album(struct album *album)
album_to_iter(album, &iter);
window_row_vanishes(lib_tree_win, &iter);
}
- list_del(&album->node);
+ rb_erase(&album->tree_node, &album->artist->album_root);
}
static void remove_artist(struct artist *artist)
@@ -778,7 +804,7 @@ static void remove_artist(struct artist *artist)
artist_to_iter(artist, &iter);
window_row_vanishes(lib_tree_win, &iter);
- list_del(&artist->node);
+ rb_erase(&artist->tree_node, &lib_artist_root);
}
void tree_remove(struct tree_track *track)
@@ -792,7 +818,7 @@ void tree_remove(struct tree_track *track)
remove_track(track);
/* don't free the track */
- if (list_empty(&album->track_head)) {
+ if (rb_root_empty(&album->track_root)) {
struct artist *artist = album->artist;
if (sel_album == album)
@@ -801,7 +827,7 @@ void tree_remove(struct tree_track *track)
remove_album(album);
album_free(album);
- if (list_empty(&artist->album_head)) {
+ if (rb_root_empty(&artist->album_root)) {
artist->expanded = 0;
remove_artist(artist);
artist_free(artist);
@@ -843,16 +869,17 @@ static int album_for_each_track(struct album *album, int (*cb)(void *data, struc
void *data, int reverse)
{
struct tree_track *track;
+ struct rb_node *tmp;
int rc = 0;
if (reverse) {
- list_for_each_entry_reverse(track, &album->track_head, node) {
+ rb_for_each_entry_reverse(track, tmp, &album->track_root, tree_node) {
rc = cb(data, tree_track_info(track));
if (rc)
break;
}
} else {
- list_for_each_entry(track, &album->track_head, node) {
+ rb_for_each_entry(track, tmp, &album->track_root, tree_node) {
rc = cb(data, tree_track_info(track));
if (rc)
break;
@@ -865,16 +892,17 @@ static int artist_for_each_track(struct artist *artist, int (*cb)(void *data, st
void *data, int reverse)
{
struct album *album;
+ struct rb_node *tmp;
int rc = 0;
if (reverse) {
- list_for_each_entry_reverse(album, &artist->album_head, node) {
+ rb_for_each_entry_reverse(album, tmp, &artist->album_root, tree_node) {
rc = album_for_each_track(album, cb, data, 1);
if (rc)
break;
}
} else {
- list_for_each_entry(album, &artist->album_head, node) {
+ rb_for_each_entry(album, tmp, &artist->album_root, tree_node) {
rc = album_for_each_track(album, cb, data, 0);
if (rc)
break;
--
1.7.2.3