filelist: use GPtrArray instead of GList

Since we do a lot of indexed accesses to the filelist, a linked list
doesn't seem appropriate.  Use GPtrArray instead.

5 files changed, 57 insertions, 63 deletions

diff --git a/src/filelist.c b/src/filelist.c
index bfc4c12b5..6cbca39df 100644
--- a/src/filelist.c
+++ b/src/filelist.c
@@ -29,9 +29,8 @@ filelist_new(const char *path)
 	struct filelist *filelist = g_malloc(sizeof(*filelist));
 
 	filelist->path = g_strdup(path);
-	filelist->length = 0;
 	filelist->updated = FALSE;
-	filelist->list = NULL;
+	filelist->entries = g_ptr_array_new();
 
 	return filelist;
 }
@@ -39,22 +38,18 @@ filelist_new(const char *path)
 void
 filelist_free(struct filelist *filelist)
 {
-	GList *list = g_list_first(filelist->list);
+	guint i;
 
-	if (list == NULL)
-		return;
-
-	while (list != NULL) {
-		filelist_entry_t *entry = list->data;
+	for (i = 0; i < filelist_length(filelist); ++i) {
+		struct filelist_entry *entry = filelist_get(filelist, i);
 
 		if (entry->entity)
 			mpd_freeInfoEntity(entry->entity);
 
 		g_free(entry);
-		list = list->next;
 	}
 
-	g_list_free(filelist->list);
+	g_ptr_array_free(filelist->entries, TRUE);
 	g_free(filelist->path);
 	g_free(filelist);
 }
@@ -67,8 +62,7 @@ filelist_append(struct filelist *filelist, struct mpd_InfoEntity *entity)
 	entry->flags = 0;
 	entry->entity = entity;
 
-	filelist->list = g_list_append(filelist->list, entry);
-	filelist->length++;
+	g_ptr_array_add(filelist->entries, entry);
 
 	return entry;
 }
@@ -78,11 +72,21 @@ filelist_prepend(struct filelist *filelist, struct mpd_InfoEntity *entity)
 {
 	struct filelist_entry *entry = g_malloc(sizeof(*entry));
 
-	entry->flags = 0;
-	entry->entity = entity;
+	/* this is very slow, but we should optimize screen_artist.c
+	   later so that this function can be removed, so I'm not in
+	   the mood to implement something better here */
+
+	entry = filelist_append(filelist, entity);
+
+	if (!filelist_is_empty(filelist)) {
+		guint i;
 
-	filelist->list = g_list_insert(filelist->list, entry, 0);
-	filelist->length++;
+		for (i = filelist_length(filelist) - 1; i > 0; --i)
+			g_ptr_array_index(filelist->entries, i) =
+				filelist_get(filelist, i - 1);
+
+		g_ptr_array_index(filelist->entries, 0) = entry;
+	}
 
 	return entry;
 }
@@ -90,27 +94,30 @@ filelist_prepend(struct filelist *filelist, struct mpd_InfoEntity *entity)
 void
 filelist_move(struct filelist *filelist, struct filelist *from)
 {
-	filelist->list = g_list_concat(filelist->list, from->list);
-	filelist->length += from->length;
-	from->list = NULL;
-	from->length = 0;
+	guint i;
+
+	for (i = 0; i < filelist_length(from); ++i)
+		g_ptr_array_add(filelist->entries,
+				g_ptr_array_index(from->entries, i));
+
+	g_ptr_array_set_size(from->entries, 0);
 }
 
 void
 filelist_sort(struct filelist *filelist, GCompareFunc compare_func)
 {
-	filelist->list = g_list_sort(filelist->list, compare_func);
+	g_ptr_array_sort(filelist->entries, compare_func);
 }
 
 struct filelist_entry *
 filelist_find_song(struct filelist *fl, const struct mpd_song *song)
 {
-	GList *list = g_list_first(fl->list);
+	guint i;
 
 	assert(song != NULL);
 
-	while (list != NULL) {
-		filelist_entry_t *entry = list->data;
+	for (i = 0; i < filelist_length(fl); ++i) {
+		struct filelist_entry *entry = filelist_get(fl, i);
 		mpd_InfoEntity *entity  = entry->entity;
 
 		if (entity && entity->type == MPD_INFO_ENTITY_TYPE_SONG) {
@@ -119,8 +126,6 @@ filelist_find_song(struct filelist *fl, const struct mpd_song *song)
 			if (strcmp(song->file, song2->file) == 0)
 				return entry;
 		}
-
-		list = list->next;
 	}
 
 	return NULL;
diff --git a/src/filelist.h b/src/filelist.h
index e2425d787..d96a67c9d 100644
--- a/src/filelist.h
+++ b/src/filelist.h
@@ -33,14 +33,11 @@ typedef struct filelist {
 	/* path */
 	gchar *path;
 
-	/* list length */
-	guint length;
-
 	/* true if the list is updated */
 	gboolean updated;
 
 	/* the list */
-	GList *list;
+	GPtrArray *entries;
 } mpdclient_filelist_t;
 
 struct filelist *
@@ -52,7 +49,7 @@ filelist_free(struct filelist *filelist);
 static inline guint
 filelist_length(const struct filelist *filelist)
 {
-	return filelist->length;
+	return filelist->entries->len;
 }
 
 static inline gboolean
@@ -64,8 +61,7 @@ filelist_is_empty(const struct filelist *filelist)
 static inline struct filelist_entry *
 filelist_get(const struct filelist *filelist, guint i)
 {
-	return (struct filelist_entry*)
-		g_list_nth_data(filelist->list, i);
+	return g_ptr_array_index(filelist->entries, i);
 }
 
 struct filelist_entry *
diff --git a/src/mpdclient.c b/src/mpdclient.c
index 20248215f..2c46d8e90 100644
--- a/src/mpdclient.c
+++ b/src/mpdclient.c
@@ -838,14 +838,15 @@ mpdclient_filelist_update(mpdclient_t *c, mpdclient_filelist_t *filelist)
 int
 mpdclient_filelist_add_all(mpdclient_t *c, mpdclient_filelist_t *fl)
 {
-	GList *list = g_list_first(fl->list);
+	guint i;
 
 	if (filelist_is_empty(fl))
 		return 0;
 
 	mpd_sendCommandListBegin(c->connection);
-	while (list) {
-		filelist_entry_t *entry = list->data;
+
+	for (i = 0; i < filelist_length(fl); ++i) {
+		filelist_entry_t *entry = filelist_get(fl, i);
 		mpd_InfoEntity *entity  = entry->entity;
 
 		if (entity && entity->type == MPD_INFO_ENTITY_TYPE_SONG) {
@@ -853,8 +854,6 @@ mpdclient_filelist_add_all(mpdclient_t *c, mpdclient_filelist_t *fl)
 
 			mpd_sendAddCommand(c->connection, song->file);
 		}
-
-		list = list->next;
 	}
 
 	mpd_sendCommandListEnd(c->connection);
diff --git a/src/screen_browser.c b/src/screen_browser.c
index b01e70c7a..d2c8aa08e 100644
--- a/src/screen_browser.c
+++ b/src/screen_browser.c
@@ -40,13 +40,12 @@
 static void
 clear_highlights(mpdclient_filelist_t *fl)
 {
-	GList *list = g_list_first(fl->list);
+	guint i;
 
-	while( list ) {
-		filelist_entry_t *entry = list->data;
+	for (i = 0; i < filelist_length(fl); ++i) {
+		struct filelist_entry *entry = filelist_get(fl, i);
 
 		entry->flags &= ~HIGHLIGHT;
-		list = list->next;
 	}
 }
 
@@ -71,13 +70,13 @@ set_highlight(mpdclient_filelist_t *fl, mpd_Song *song, int highlight)
 void
 sync_highlights(mpdclient_t *c, mpdclient_filelist_t *fl)
 {
-	GList *list = g_list_first(fl->list);
+	guint i;
 
-	while(list) {
-		filelist_entry_t *entry = list->data;
+	for (i = 0; i < filelist_length(fl); ++i) {
+		struct filelist_entry *entry = filelist_get(fl, i);
 		mpd_InfoEntity *entity = entry->entity;
 
-		if( entity && entity->type==MPD_INFO_ENTITY_TYPE_SONG ) {
+		if ( entity && entity->type==MPD_INFO_ENTITY_TYPE_SONG ) {
 			mpd_Song *song = entity->info.song;
 
 			if( playlist_get_index_from_file(c, song->file) >= 0 )
@@ -85,7 +84,6 @@ sync_highlights(mpdclient_t *c, mpdclient_filelist_t *fl)
 			else
 				entry->flags &= ~HIGHLIGHT;
 		}
-		list=list->next;
 	}
 }
 
@@ -125,10 +123,12 @@ browser_lw_callback(unsigned idx, int *highlight, void *data)
 	filelist_entry_t *entry;
 	mpd_InfoEntity *entity;
 
-	entry = filelist_get(fl, idx);
-	if (entry == NULL)
+	if (idx >= filelist_length(fl))
 		return NULL;
 
+	entry = filelist_get(fl, idx);
+	assert(entry != NULL);
+
 	entity = entry->entity;
 	*highlight = (entry->flags & HIGHLIGHT);
 
@@ -395,21 +395,17 @@ browser_handle_select(struct screen_browser *browser, mpdclient_t *c)
 void
 browser_handle_select_all(struct screen_browser *browser, mpdclient_t *c)
 {
-	filelist_entry_t *entry;
-	GList *temp = browser->filelist->list;
+	guint i;
 
 	if (browser->filelist == NULL)
 		return;
 
-	for (browser->filelist->list = g_list_first(browser->filelist->list);
-	     browser->filelist->list;
-	     browser->filelist->list = g_list_next(browser->filelist->list)) {
-		entry = browser->filelist->list->data;
+	for (i = 0; i < filelist_length(browser->filelist); ++i) {
+		struct filelist_entry *entry = filelist_get(browser->filelist, i);
+
 		if (entry != NULL && entry->entity != NULL)
 			browser_select_entry(c, entry, FALSE);
 	}
-
-	browser->filelist->list = temp;
 }
 
 #ifdef HAVE_GETMOUSE
diff --git a/src/utils.c b/src/utils.c
index 65eaceca2..574b8fa49 100644
--- a/src/utils.c
+++ b/src/utils.c
@@ -75,16 +75,16 @@ string_list_remove(GList *string_list, const gchar *str)
 GList *
 gcmp_list_from_path(mpdclient_t *c, const gchar *path, GList *list, gint types)
 {
-	GList *flist = NULL;
+	guint i;
 	mpdclient_filelist_t *filelist;
 
 	if ((filelist = mpdclient_filelist_get(c, path)) == NULL)
 		return list;
 
 	D("retrieved filelist!\n");
-	flist = filelist->list;
-	while (flist) {
-		filelist_entry_t *entry = flist->data;
+
+	for (i = 0; i < filelist_length(filelist); ++i) {
+		struct filelist_entry *entry = filelist_get(filelist, i);
 		mpd_InfoEntity *entity = entry ? entry->entity : NULL;
 		char *name = NULL;
 
@@ -112,8 +112,6 @@ gcmp_list_from_path(mpdclient_t *c, const gchar *path, GList *list, gint types)
 
 		if (name)
 			list = g_list_append(list, name);
-
-		flist = flist->next;
 	}
 
 	filelist_free(filelist);