commit b073d4b0c2c1d4dce36adcc285ad5dfaf2f7599d
parent e456776063b61d339205c84bf884d0eeb761e57b
Author: Louis Burda <quent.burda@gmail.com>
Date: Thu, 27 Jan 2022 03:29:44 +0100
New list interface for fast tail access
Diffstat:
13 files changed, 143 insertions(+), 134 deletions(-)
diff --git a/src/history.c b/src/history.c
@@ -4,11 +4,10 @@
#include <string.h>
#include <wchar.h>
-
void
history_init(struct history *history)
{
- history->list = LIST_HEAD;
+ list_init(&history->list);
history->input = inputln_alloc();
history->sel = history->input;
}
@@ -41,13 +40,9 @@ history_free(struct history *history)
ln = link_pop(LINK(history->input));
inputln_free(UPCAST(ln, struct inputln));
- for (iter = history->list.next; iter; ) {
- next = iter->next;
- inputln_free(UPCAST(iter, struct inputln));
- iter = next;
- }
+ list_free(&history->list, (link_free_func) inputln_free,
+ LINK_OFFSET(struct inputln));
- history->list = LIST_HEAD;
history->input = NULL;
history->sel = NULL;
}
@@ -102,7 +97,7 @@ history_add(struct history *history, struct inputln *line)
if (list_len(&history->list) == HISTORY_MAX) {
/* pop last item to make space */
- back = link_pop(link_back(&history->list));
+ back = list_pop_back(&history->list);
inputln_free(UPCAST(back, struct inputln));
}
diff --git a/src/history.h b/src/history.h
@@ -15,7 +15,7 @@ struct inputln {
};
struct history {
- struct link list;
+ struct list list;
struct inputln *sel, *input;
};
diff --git a/src/list.c b/src/list.c
@@ -2,76 +2,90 @@
#include "util.h"
void
-list_free(struct link *head, void (*free_item)(void *), int offset)
+list_init(struct list *list)
+{
+ list->head.prev = NULL;
+ list->head.next = &list->tail;
+ list->tail.prev = &list->head;
+ list->tail.next = NULL;
+}
+
+void
+list_free(struct list *list, void (*free_item)(void *), int offset)
{
struct link *item;
- while (head->next) {
- item = link_pop(head->next);
+ ASSERT(list != NULL);
+
+ while (!list_empty(list)) {
+ item = link_pop(list->head.next);
free_item(((void *) item) - offset);
}
}
int
-list_empty(struct link *head)
+list_empty(struct list *list)
{
- ASSERT(head != NULL);
- return head->next == NULL;
+ ASSERT(list != NULL);
+
+ return list->head.next == &list->tail;
}
int
-list_len(struct link *head)
+list_len(struct list *list)
{
struct link *iter;
int len;
- ASSERT(head != NULL);
+ ASSERT(list != NULL);
len = 0;
- for (iter = head->next; iter; iter = iter->next)
+ for (LIST_ITER(list, iter))
len += 1;
return len;
}
-int
-list_ffind(struct link *head, struct link *link)
+struct link *
+list_at(struct list *list, int n)
{
- struct link *iter;
+ ASSERT(list != NULL);
- ASSERT(head != NULL);
- for (iter = head->next; iter && iter != link; iter = iter->next);
- return (iter == link);
+ return link_iter(list->head.next, n);
}
-struct link *
-list_at(struct link *head, int n)
+void
+list_push_front(struct list *list, struct link *link)
{
- ASSERT(head != NULL);
- return link_iter(head->next, n);
+ link_append(&list->head, link);
}
void
-list_push_front(struct link *head, struct link *link)
+list_push_back(struct list *list, struct link *link)
{
- link_append(head, link);
+ link_prepend(&list->tail, link);
}
-void
-list_push_back(struct link *cur, struct link *link)
+struct link *
+list_pop_front(struct list *list)
{
- struct link *back;
+ ASSERT(list != NULL);
+
+ if (list_empty(list))
+ return NULL;
- back = link_back(cur);
- link_append(back, link);
+ return link_pop(list->head.next);
}
struct link *
-list_pop_front(struct link *head)
+list_pop_back(struct list *list)
{
- ASSERT(head != NULL);
- if (!head->next) return NULL;
- return link_pop(head->next);
+ ASSERT(list != NULL);
+
+ if (list_empty(list))
+ return NULL;
+
+ return link_pop(list->tail.prev);
}
void
@@ -103,11 +117,14 @@ link_append(struct link *cur, struct link *link)
}
struct link *
-link_back(struct link *link)
+link_iter(struct link *link, int n)
{
- ASSERT(link != NULL);
+ int i;
- for (; link->next; link = link->next);
+ for (i = 0; i < n; i++) {
+ if (!link) return NULL;
+ link = link->next;
+ }
return link;
}
@@ -124,16 +141,3 @@ link_pop(struct link *link)
return link;
}
-
-struct link *
-link_iter(struct link *link, int n)
-{
- int i;
-
- for (i = 0; i < n; i++) {
- if (!link) return NULL;
- link = link->next;
- }
-
- return link;
-}
diff --git a/src/list.h b/src/list.h
@@ -7,29 +7,40 @@
const typeof( ((type *)0)->link ) *__mptr = (ptr); \
(type *)( (char *)__mptr - LINK_OFFSET(type) ); })
-#define LIST_HEAD ((struct link) { .prev = NULL, .next = NULL })
#define LINK_EMPTY ((struct link) { 0 })
#define LINK(p) (&(p)->link)
+#define LIST_INNER(list, link) \
+ (((link) != &(list)->head) && ((link) != &(list)->tail))
+
+#define LIST_ITER(list, iter) (iter) = (list)->head.next; \
+ (iter) != &(list)->tail; (iter) = (iter)->next
+
+typedef void (*link_free_func)(void *p);
+
struct link {
struct link *prev;
struct link *next;
};
-/* list_XXX functions operate on the list head */
+struct list {
+ struct link head;
+ struct link tail;
+};
-void list_free(struct link *head, void (*free_item)(void *), int offset);
-int list_empty(struct link *head);
-int list_len(struct link *head);
-int list_ffind(struct link *head, struct link *link);
-struct link *list_at(struct link *head, int n);
-void list_push_front(struct link *head, struct link *link);
-void list_push_back(struct link *head, struct link *link);
-struct link *list_pop_front(struct link *head);
+void list_init(struct list *list);
+void list_free(struct list *list, void (*free_item)(void *), int offset);
+int list_empty(struct list *list);
+int list_len(struct list *list);
+struct link *list_at(struct list *list, int n);
+void list_push_front(struct list *list, struct link *link);
+void list_push_back(struct list *list, struct link *link);
+struct link *list_pop_front(struct list *list);
+struct link *list_pop_back(struct list *list);
void link_prepend(struct link *list, struct link *link);
void link_append(struct link *list, struct link *link);
-struct link *link_back(struct link *list);
-struct link *link_pop(struct link *link);
struct link *link_iter(struct link *link, int n);
+struct link *link_pop(struct link *link);
+
diff --git a/src/main.c b/src/main.c
@@ -86,10 +86,10 @@ static struct pane *const panes[] = {
};
/* 'tracks' holds all *unique* tracks */
-static struct link tracks;
-static struct link tags;
-static struct link tags_sel;
-static struct link *tracks_vis;
+static struct list tracks;
+static struct list tags;
+static struct list tags_sel;
+static struct list *tracks_vis;
static int track_show_playlist;
/* bottom 'cmd' pane for search / exec */
@@ -271,6 +271,7 @@ void
tui_resize(void)
{
struct link *iter;
+ struct tag *tag;
int i, leftw;
getmaxyx(stdscr, scrh, scrw);
@@ -285,8 +286,10 @@ tui_resize(void)
/* adjust tag pane width to name lengths */
leftw = 0;
- for (iter = tags.next; iter; iter = iter->next)
- leftw = MAX(leftw, wcslen(UPCAST(iter, struct tag)->name));
+ for (LIST_ITER(&tags, iter)) {
+ tag = UPCAST(iter, struct tag);
+ leftw = MAX(leftw, wcslen(tag->name));
+ }
leftw = MAX(leftw + 1, 0.2f * scrw);
pane_resize(&pane_left, 0, 0, leftw, scrh - 3);
@@ -313,9 +316,9 @@ data_load(void)
char *path;
DIR *dir;
- tracks = LIST_HEAD;
- tags = LIST_HEAD;
- tags_sel = LIST_HEAD;
+ list_init(&tracks);
+ list_init(&tags);
+ list_init(&tags_sel);
datadir = getenv("TMUS_DATA");
ASSERT(datadir != NULL);
@@ -465,7 +468,7 @@ tracks_load(struct tag *tag)
ASSERT(ref != NULL);
list_push_back(&tag->tracks, LINK(ref));
- for (link = tracks.next; link; link = link->next) {
+ for (LIST_ITER(&tracks, link)) {
track2 = UPCAST(link, struct ref)->data;
if (track->fid == track2->fid)
break;
@@ -498,7 +501,7 @@ tracks_save(struct tag *tag)
file = fopen(index_path, "w+");
ASSERT(file != NULL);
- for (link = tracks.next; link; link = link->next) {
+ for (LIST_ITER(&tracks, link)) {
track = UPCAST(link, struct ref)->data;
fprintf(file, "%i:%s\n", track->fid, track->fname);
}
@@ -572,13 +575,13 @@ track_name_gen(const wchar_t *text, int fwd, int reset)
struct track *track;
if (reset) {
- cur = tracks.next;
+ cur = tracks.head.next;
iter = cur;
} else {
iter = fwd ? cur->next : cur->prev;
}
- while (iter && iter != &tracks) {
+ while (iter && LIST_INNER(&tracks, iter)) {
track = UPCAST(iter, struct ref)->data;
if (wcsstr(track->name, text)) {
cur = iter;
@@ -598,13 +601,13 @@ tag_name_gen(const wchar_t *text, int fwd, int reset)
struct tag *tag;
if (reset) {
- cur = tags.next;
+ cur = tags.head.next;
iter = cur;
} else {
iter = fwd ? cur->next : cur->prev;
}
- while (iter && iter != &tags) {
+ while (iter && LIST_INNER(&tags, iter)) {
tag = UPCAST(iter, struct tag);
if (wcsstr(tag->name, text)) {
cur = iter;
@@ -626,7 +629,8 @@ toggle_current_tag(void)
int in_tags, in_playlist;
if (list_empty(&tags)) return;
- link = link_iter(tags.next, tag_nav.sel);
+
+ link = list_at(&tags, tag_nav.sel);
ASSERT(link != NULL);
tag = UPCAST(link, struct tag);
@@ -640,9 +644,9 @@ toggle_current_tag(void)
/* rebuild the full playlist */
refs_free(&player->playlist);
- for (link = tags_sel.next; link; link = link->next) {
+ for (LIST_ITER(&tags_sel, link)) {
tag = UPCAST(link, struct ref)->data;
- for (iter = tag->tracks.next; iter; iter = iter->next) {
+ for (LIST_ITER(&tag->tracks, iter)) {
ref = ref_init(UPCAST(iter, struct ref)->data);
ASSERT(ref != NULL);
list_push_back(&player->playlist, LINK(ref));
@@ -691,11 +695,12 @@ tag_pane_vis(struct pane *pane, int sel)
listnav_update_bounds(&tag_nav, 0, list_len(&tags));
listnav_update_wlen(&tag_nav, pane->h - 1);
- index = 0;
- for (iter = tags.next; iter; iter = iter->next, index++) {
+ index = -1;
+ for (LIST_ITER(&tags, iter)) {
tag = UPCAST(iter, struct tag);
tagsel = refs_incl(&tags_sel, tag);
+ index += 1;
if (index < tag_nav.wmin) continue;
if (index >= tag_nav.wmax) break;
@@ -737,7 +742,7 @@ track_pane_input(wint_t c)
return 1;
case KEY_ENTER:
if (list_empty(tracks_vis)) return 1;
- link = link_iter(tracks_vis->next, track_nav.sel);
+ link = list_at(tracks_vis, track_nav.sel);
ASSERT(link != NULL);
track = UPCAST(link, struct ref)->data;
player_play_track(track);
@@ -769,10 +774,11 @@ track_pane_vis(struct pane *pane, int sel)
listnav_update_bounds(&track_nav, 0, list_len(tracks_vis));
listnav_update_wlen(&track_nav, pane->h - 1);
- index = 0;
- for (iter = tracks_vis->next; iter; iter = iter->next, index++) {
+ index = -1;
+ for (LIST_ITER(tracks_vis, iter)) {
track = UPCAST(iter, struct ref)->data;
+ index += 1;
if (index < track_nav.wmin) continue;
if (index >= track_nav.wmax) break;
@@ -823,7 +829,7 @@ play_track(const wchar_t *query)
struct track *track;
struct link *iter;
- for (iter = tracks.next; iter; iter = iter->next) {
+ for (LIST_ITER(&tracks, iter)) {
track = UPCAST(iter, struct ref)->data;
if (wcsstr(track->name, query)) {
player_play_track(track);
@@ -842,7 +848,7 @@ select_tag(const wchar_t *query)
int index;
index = 0;
- for (iter = tags.next; iter; iter = iter->next, index++) {
+ for (LIST_ITER(&tags, iter)) {
tag = UPCAST(iter, struct tag);
if (wcsstr(tag->name, query)) {
listnav_update_sel(&tag_nav, index);
@@ -1023,10 +1029,10 @@ cmd_pane_vis(struct pane *pane, int sel)
cmd = history->sel;
if (cmd != history->input) {
index = 0;
- iter = history->list.next;
- for (; iter; iter = iter->next, index++)
+ for (LIST_ITER(&history->list, iter)) {
if (UPCAST(iter, struct inputln) == cmd)
break;
+ }
line += swprintf(line, end - line, L"[%i] ",
iter ? index : -1);
} else {
@@ -1055,7 +1061,7 @@ queue_hover(void)
{
struct link *link;
- link = link_iter(player->playlist.next, track_nav.sel);
+ link = list_at(&player->playlist, track_nav.sel);
ASSERT(link != NULL);
player_queue_append(UPCAST(link, struct ref)->data);
}
@@ -1069,7 +1075,7 @@ update_track_playlist(void)
if (track_show_playlist) {
tracks_vis = &player->playlist;
} else {
- iter = link_iter(tags.next, tag_nav.sel);
+ iter = list_at(&tags, tag_nav.sel);
ASSERT(iter != NULL);
tag = UPCAST(iter, struct tag);
tracks_vis = &tag->tracks;
diff --git a/src/player.c b/src/player.c
@@ -61,10 +61,10 @@ player_init(void)
player->conn = mpd_connection_new(NULL, 0, 0);
ASSERT(player->conn != NULL);
- player->queue = LIST_HEAD;
- player->history = LIST_HEAD;
+ list_init(&player->queue);
+ list_init(&player->history);
- player->playlist = LIST_HEAD;
+ list_init(&player->playlist);
player->track = NULL;
player->loaded = 0;
@@ -118,11 +118,10 @@ player_play_next(struct track *prev)
if (player->shuffle) {
/* TODO better algorithm for random sequence */
index = rand() % list_len(&player->playlist);
- iter = link_iter(player->playlist.next, index);
+ iter = list_at(&player->playlist, index);
ASSERT(iter != NULL);
} else if (player->loaded) {
- iter = player->playlist.next;
- for (; iter; iter = iter->next) {
+ for (LIST_ITER(&player->playlist, iter)) {
track = UPCAST(iter, struct ref)->data;
if (track == prev)
break;
@@ -130,7 +129,7 @@ player_play_next(struct track *prev)
if (iter) iter = iter->next;
}
- if (!iter) iter = player->playlist.next;
+ if (!iter) iter = list_at(&player->playlist, 0);
track = UPCAST(iter, struct ref)->data;
player_play_track(track);
@@ -251,12 +250,7 @@ player_update(void)
void
player_queue_clear(void)
{
- struct ref *ref;
-
- while (player->queue.next) {
- ref = UPCAST(link_pop(player->queue.next), struct ref);
- ref_free(ref);
- }
+ refs_free(&player->queue);
}
void
@@ -266,8 +260,7 @@ player_queue_append(struct track *track)
struct link *link;
ref = ref_init(track);
- link = link_back(&player->queue);
- link_append(link, LINK(ref));
+ list_push_back(&player->queue, LINK(ref));
}
void
@@ -277,7 +270,7 @@ player_queue_insert(struct track *track, size_t pos)
struct link *link;
ref = ref_init(track);
- link = link_iter(player->queue.next, pos);
+ link = list_at(&player->queue, pos);
link_prepend(link, LINK(ref));
}
diff --git a/src/player.h b/src/player.h
@@ -38,11 +38,11 @@ struct player {
/* TODO combine with index */
/* for navigating forward and backwards in time */
- struct link queue;
- struct link history;
+ struct list queue;
+ struct list history;
/* list of track refs to choose from on prev / next */
- struct link playlist;
+ struct list playlist;
/* last player track */
struct track *track;
diff --git a/src/ref.c b/src/ref.c
@@ -20,18 +20,20 @@ ref_free(void *ref)
}
void
-refs_free(struct link *head)
+refs_free(struct list *list)
{
- list_free(head, ref_free, LINK_OFFSET(struct ref));
+ list_free(list, ref_free, LINK_OFFSET(struct ref));
}
static struct link *
-refs_ffind(struct link *head, void *data)
+refs_ffind(struct list *list, void *data)
{
struct link *iter;
+ struct ref *ref;
- for (iter = head->next; iter; iter = iter->next) {
- if (UPCAST(iter, struct ref)->data == data)
+ for (LIST_ITER(list, iter)) {
+ ref = UPCAST(iter, struct ref);
+ if (ref->data == data)
return iter;
}
@@ -39,21 +41,21 @@ refs_ffind(struct link *head, void *data)
}
int
-refs_incl(struct link *head, void *data)
+refs_incl(struct list *list, void *data)
{
struct link *ref;
- ref = refs_ffind(head, data);
+ ref = refs_ffind(list, data);
return ref != NULL;
}
void
-refs_rm(struct link *head, void *data)
+refs_rm(struct list *list, void *data)
{
struct link *ref;
struct ref *dataref;
- ref = refs_ffind(head, data);
+ ref = refs_ffind(list, data);
if (!ref) return;
dataref = UPCAST(ref, struct ref);
diff --git a/src/ref.h b/src/ref.h
@@ -11,6 +11,6 @@ struct ref {
struct ref *ref_init(void *data);
void ref_free(void *ref);
-void refs_free(struct link *head);
-int refs_incl(struct link *head, void *data);
-void refs_rm(struct link *head, void *data);
+void refs_free(struct list *list);
+int refs_incl(struct list *list, void *data);
+void refs_rm(struct list *list, void *data);
diff --git a/src/tag.c b/src/tag.c
@@ -29,7 +29,7 @@ tag_init(const char *path, const char *fname)
tag->link = LINK_EMPTY;
- tag->tracks = LIST_HEAD;
+ list_init(&tag->tracks);
return tag;
}
diff --git a/src/tag.h b/src/tag.h
@@ -9,7 +9,7 @@ struct tag {
char *new_fname;
- struct link tracks;
+ struct list tracks;
struct link link;
};
diff --git a/src/track.c b/src/track.c
@@ -5,7 +5,6 @@
#include <string.h>
#include <sys/stat.h>
-
struct track *
track_init(const char *dir, const char *fname, int fid)
{
@@ -29,7 +28,7 @@ track_init(const char *dir, const char *fname, int fid)
track->fid = fid;
- track->tags = LIST_HEAD;
+ list_init(&track->tags);
return track;
}
diff --git a/src/track.h b/src/track.h
@@ -3,10 +3,9 @@
#include "list.h"
#include "util.h"
-
struct track {
wchar_t *name;
- struct link tags;
+ struct list tags;
char *fname, *fpath;
int fid;
};
