The rbtree of editable.c now only contains unique tracks, while the
linked list contains all, e.g. for a sorted playlist:
________________D__________
/ . \
_B_______ . ____F_
/ . \ . / . \
A . C . E . G
. . . . . . .
A--B--B--B--C--C--C--D--D--E--E--F--G
For the play queue:
A
.
A--A--A--A--A--A--A
For the library:
____D____
/ . \
_B_ . _F_
/ . \ . / . \
A . C . E . G
. . . . . . .
A--B--C--D--E--F--G
This should reduce the segfaults due to tree/list degenerations in the
long run. It also simplifies play_queue.c a lot!
---
editable.c | 45 ++++++++++++++++++++-----------
editable.h | 1 +
job.c | 2 +-
play_queue.c | 64 +++++++------------------------------------
play_queue.h | 1 -
track.c | 85 +++++++++++++++++++++++++++++++++++++++++++--------------
track.h | 5 +++-
7 files changed, 109 insertions(+), 94 deletions(-)
diff --git a/editable.c b/editable.c
index c7a4420..8aa840b 100644
--- a/editable.c
+++ b/editable.c
@@ -67,15 +67,25 @@ void editable_init(struct editable *e, void (*free_track)(struct list_head *item
e->searchable = searchable_new(e->win, &iter, &simple_search_ops);
}
-void editable_add(struct editable *e, struct simple_track *track)
+static void do_editable_add(struct editable *e, struct simple_track *track, int tiebreak)
{
- sorted_list_add_track(&e->head, &e->tree_root, track, e->sort_keys);
+ sorted_list_add_track(&e->head, &e->tree_root, track, e->sort_keys, tiebreak);
e->nr_tracks++;
if (track->info->duration != -1)
e->total_time += track->info->duration;
window_changed(e->win);
}
+void editable_add(struct editable *e, struct simple_track *track)
+{
+ do_editable_add(e, track, +1);
+}
+
+void editable_add_before(struct editable *e, struct simple_track *track)
+{
+ do_editable_add(e, track, -1);
+}
+
void editable_remove_track(struct editable *e, struct simple_track *track)
{
struct track_info *ti = track->info;
@@ -89,10 +99,7 @@ void editable_remove_track(struct editable *e, struct simple_track *track)
if (ti->duration != -1)
e->total_time -= ti->duration;
- list_del(&track->node);
- if (!RB_EMPTY_NODE(&track->tree_node))
- rb_erase(&track->tree_node, &e->tree_root);
-
+ sorted_list_remove_track(&e->head, &e->tree_root, track);
e->free_track(&track->node);
}
@@ -120,16 +127,9 @@ void editable_remove_sel(struct editable *e)
void editable_sort(struct editable *e)
{
- struct rb_node *node, *tmp;
- struct rb_root tmptree = RB_ROOT;
-
- list_init(&e->head);
- rb_for_each_safe(node, tmp, &e->tree_root) {
- struct simple_track *track = tree_node_to_simple_track(node);
- rb_erase(node, &e->tree_root);
- sorted_list_add_track(&e->head, &tmptree, track, e->sort_keys);
- }
- e->tree_root.rb_node = tmptree.rb_node;
+ if (e->nr_tracks <= 1)
+ return;
+ sorted_list_rebuild(&e->head, &e->tree_root, e->sort_keys);
window_changed(e->win);
window_goto_top(e->win);
@@ -168,6 +168,18 @@ static void move_item(struct editable *e, struct list_head *head, struct list_he
list_add(item, head);
}
+static void reset_tree(struct editable *e)
+{
+ struct simple_track *old, *first_track;
+
+ old = tree_node_to_simple_track(rb_first(&e->tree_root));
+ first_track = to_simple_track(e->head.next);
+ if (old != first_track) {
+ rb_replace_node(&old->tree_node, &first_track->tree_node, &e->tree_root);
+ RB_CLEAR_NODE(&old->tree_node);
+ }
+}
+
static void move_sel(struct editable *e, struct list_head *after)
{
struct simple_track *t;
@@ -198,6 +210,7 @@ static void move_sel(struct editable *e, struct list_head *after)
list_add(item, after);
item = next;
}
+ reset_tree(e);
/* select top-most of the moved tracks */
editable_track_to_iter(e, to_simple_track(after->next), &iter);
diff --git a/editable.h b/editable.h
index a42451e..aa05245 100644
--- a/editable.h
+++ b/editable.h
@@ -43,6 +43,7 @@ extern pthread_mutex_t editable_mutex;
void editable_init(struct editable *e, void (*free_track)(struct list_head *item));
void editable_add(struct editable *e, struct simple_track *track);
+void editable_add_before(struct editable *e, struct simple_track *track);
void editable_remove_track(struct editable *e, struct simple_track *track);
void editable_remove_sel(struct editable *e);
void editable_sort(struct editable *e);
diff --git a/job.c b/job.c
index e827dff..c0b5925 100644
--- a/job.c
+++ b/job.c
@@ -369,7 +369,7 @@ void do_update_cache_job(void *data)
if (lib_remove(old) && new)
lib_add_track(new);
editable_update_track(&pl_editable, old, new);
- play_queue_update_track(old, new);
+ editable_update_track(&pq_editable, old, new);
if (player_info.ti == old && new) {
track_info_ref(new);
player_file_changed(new);
diff --git a/play_queue.c b/play_queue.c
index 6b1b966..4c9c9d1 100644
--- a/play_queue.c
+++ b/play_queue.c
@@ -40,52 +40,30 @@ void play_queue_append(struct track_info *ti)
{
struct simple_track *t = simple_track_new(ti);
- list_add_tail(&t->node, &pq_editable.head);
- pq_editable.nr_tracks++;
- if (t->info->duration != -1)
- pq_editable.total_time += t->info->duration;
- window_changed(pq_editable.win);
+ editable_add(&pq_editable, t);
}
void play_queue_prepend(struct track_info *ti)
{
struct simple_track *t = simple_track_new(ti);
- list_add(&t->node, &pq_editable.head);
- pq_editable.nr_tracks++;
- if (t->info->duration != -1)
- pq_editable.total_time += t->info->duration;
- window_changed(pq_editable.win);
+ editable_add_before(&pq_editable, t);
}
-static struct track_info *pq_remove_track(struct list_head *item)
+struct track_info *play_queue_remove(void)
{
- struct simple_track *t;
- struct track_info *info;
- struct iter iter;
-
- if (item == &pq_editable.head)
- return NULL;
-
- t = to_simple_track(item);
-
- editable_track_to_iter(&pq_editable, t, &iter);
- window_row_vanishes(pq_editable.win, &iter);
+ struct track_info *info = NULL;
- pq_editable.nr_marked -= t->marked;
- pq_editable.nr_tracks--;
- list_del(&t->node);
+ if (!list_empty(&pq_editable.head)) {
+ struct simple_track *t = to_simple_track(pq_editable.head.next);
+ info = t->info;
+ track_info_ref(info);
+ editable_remove_track(&pq_editable, t);
+ }
- info = t->info;
- free(t);
return info;
}
-struct track_info *play_queue_remove(void)
-{
- return pq_remove_track(pq_editable.head.next);
-}
-
int play_queue_for_each(int (*cb)(void *data, struct track_info *ti), void *data)
{
struct simple_track *track;
@@ -98,25 +76,3 @@ int play_queue_for_each(int (*cb)(void *data, struct track_info *ti), void *data
}
return rc;
}
-
-void play_queue_update_track(struct track_info *old, struct track_info *new)
-{
- struct list_head *item, *tmp;
- int changed = 0;
-
- list_for_each_safe(item, tmp, &pq_editable.head) {
- struct simple_track *track = to_simple_track(item);
- if (track->info == old) {
- if (new) {
- track_info_unref(old);
- track_info_ref(new);
- track->info = new;
- } else {
- pq_remove_track(item);
- }
- changed = 1;
- }
- }
- if (changed)
- window_changed(pq_editable.win);
-}
diff --git a/play_queue.h b/play_queue.h
index 942eba4..201ec79 100644
--- a/play_queue.h
+++ b/play_queue.h
@@ -29,6 +29,5 @@ void play_queue_append(struct track_info *ti);
void play_queue_prepend(struct track_info *ti);
struct track_info *play_queue_remove(void);
int play_queue_for_each(int (*cb)(void *data, struct track_info *ti), void *data);
-void play_queue_update_track(struct track_info *old, struct track_info *new);
#endif
diff --git a/track.c b/track.c
index 16545bb..852ae9c 100644
--- a/track.c
+++ b/track.c
@@ -163,42 +163,85 @@ again:
return NULL;
}
-void sorted_list_add_track(struct list_head *head, struct rb_root *tree_root, struct simple_track *track, const sort_key_t *keys)
+void sorted_list_add_track(struct list_head *head, struct rb_root *tree_root, struct simple_track *track,
+ const sort_key_t *keys, int tiebreak)
{
- struct rb_node **new = &(tree_root->rb_node), *parent = NULL, *curr, *prev, *next;
+ struct rb_node **new = &(tree_root->rb_node), *parent = NULL, *curr, *next;
+ struct list_head *node;
+ int result = 0;
/* try to locate track in tree */
while (*new) {
const struct simple_track *t = tree_node_to_simple_track(*new);
- int result = track_info_cmp(track->info, t->info, keys);
+ result = track_info_cmp(track->info, t->info, keys);
parent = *new;
if (result < 0)
- new = &((*new)->rb_left);
+ new = &(parent->rb_left);
+ else if (result > 0)
+ new = &(parent->rb_right);
else
- new = &((*new)->rb_right);
+ break;
}
- rb_link_node(&track->tree_node, parent, new);
- curr = *new;
- rb_insert_color(&track->tree_node, tree_root);
-
- next = rb_next(curr);
- if (next) {
- struct simple_track *next_track = tree_node_to_simple_track(next);
- list_add_tail(&track->node, &next_track->node);
- return;
+ /* duplicate is present in the tree */
+ if (parent && result == 0) {
+ if (tiebreak < 0) {
+ node = &(tree_node_to_simple_track(parent)->node);
+ rb_replace_node(parent, &track->tree_node, tree_root);
+ RB_CLEAR_NODE(parent);
+ } else {
+ next = rb_next(parent);
+ node = next ? &(tree_node_to_simple_track(next)->node) : head;
+ }
+ } else {
+ rb_link_node(&track->tree_node, parent, new);
+ curr = *new;
+ rb_insert_color(&track->tree_node, tree_root);
+ if (result < 0) {
+ node = &(tree_node_to_simple_track(parent)->node);
+ } else if (result > 0) {
+ next = rb_next(curr);
+ node = next ? &(tree_node_to_simple_track(next)->node) : head;
+ } else {
+ /* rbtree was empty, just add after list head */
+ node = head;
+ }
}
+ list_add(&track->node, node->prev);
+}
+
+void sorted_list_remove_track(struct list_head *head, struct rb_root *tree_root, struct simple_track *track)
+{
+ struct simple_track *next_track;
+ struct rb_node *tree_next;
- prev = rb_prev(curr);
- if (prev) {
- struct simple_track *prev_track = tree_node_to_simple_track(prev);
- list_add(&track->node, &prev_track->node);
- return;
+ if (!RB_EMPTY_NODE(&track->tree_node)) {
+ next_track = (track->node.next != head) ? to_simple_track(track->node.next) : NULL;
+ tree_next = rb_next(&track->tree_node);
+
+ if (next_track && (!tree_next || tree_node_to_simple_track(tree_next) != next_track)) {
+ rb_replace_node(&track->tree_node, &next_track->tree_node, tree_root);
+ RB_CLEAR_NODE(&track->tree_node);
+ } else
+ rb_erase(&track->tree_node, tree_root);
}
+ list_del(&track->node);
+}
- /* rbtree was empty, just add after list head */
- list_add(&track->node, head);
+void sorted_list_rebuild(struct list_head *head, struct rb_root *tree_root, const sort_key_t *keys)
+{
+ struct list_head *item, *tmp;
+ struct rb_root tmp_tree = RB_ROOT;
+ LIST_HEAD(tmp_head);
+
+ list_for_each_safe(item, tmp, head) {
+ struct simple_track *track = to_simple_track(item);
+ sorted_list_remove_track(head, tree_root, track);
+ sorted_list_add_track(&tmp_head, &tmp_tree, track, keys, 0);
+ }
+ tree_root->rb_node = tmp_tree.rb_node;
+ __list_add(head, tmp_head.prev, tmp_head.next);
}
static int compare_rand(const struct rb_node *a, const struct rb_node *b)
diff --git a/track.h b/track.h
index ee7b68a..0b4b24e 100644
--- a/track.h
+++ b/track.h
@@ -87,7 +87,10 @@ 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 rb_root *tree_root, struct simple_track *track, const sort_key_t *keys);
+void sorted_list_add_track(struct list_head *head, struct rb_root *tree_root, struct simple_track *track,
+ const sort_key_t *keys, int tiebreak);
+void sorted_list_remove_track(struct list_head *head, struct rb_root *tree_root, struct simple_track *track);
+void sorted_list_rebuild(struct list_head *head, struct rb_root *tree_root, const sort_key_t *keys);
void list_add_rand(struct list_head *head, struct list_head *node, int nr);
--
1.7.7