use GArray for playlist instead of GList

Using a doubly linked list for the local playlist copy is a huge waste
of both memory and CPU cycles.  Use GArray instead of GList, which is
much faster in this case.

3 files changed, 76 insertions, 101 deletions

diff --git a/src/mpdclient.c b/src/mpdclient.c
index c59741115..f26b42cfd 100644
--- a/src/mpdclient.c
+++ b/src/mpdclient.c
@@ -163,6 +163,7 @@ mpdclient_new(void)
   mpdclient_t *c;
 
   c = g_malloc0(sizeof(mpdclient_t));
+  c->playlist.list = g_array_sized_new(FALSE, FALSE, sizeof(mpd_Song *), 1024);
 
   return c;
 }
@@ -459,8 +460,7 @@ mpdclient_cmd_delete(mpdclient_t *c, gint idx)
 	c->playlist.id++;
 
 	/* remove the song from the playlist */
-	c->playlist.list = g_list_remove(c->playlist.list, (gpointer) song);
-	c->playlist.length = g_list_length(c->playlist.list);
+	g_array_remove_index(c->playlist.list, idx);
 
 	/* call playlist updated callback */
 	mpdclient_playlist_callback(c, PLAYLIST_EVENT_DELETE, (gpointer) song);
@@ -484,13 +484,11 @@ mpdclient_cmd_delete(mpdclient_t *c, gint idx)
 gint
 mpdclient_cmd_move(mpdclient_t *c, gint old_index, gint new_index)
 {
-	gint n, index1, index2;
-	GList *item1, *item2;
-	gpointer data1, data2;
+	gint n;
 	mpd_Song *song1, *song2;
 
 	if (old_index == new_index || new_index < 0 ||
-	    (guint)new_index >= c->playlist.length)
+	    (guint)new_index >= c->playlist.list->len)
 		return -1;
 
 	song1 = playlist_get_song(c, old_index);
@@ -512,26 +510,9 @@ mpdclient_cmd_move(mpdclient_t *c, gint old_index, gint new_index)
 	n = song1->pos;
 	song1->pos = song2->pos;
 	song2->pos = n;
-	index1 = MIN(old_index, new_index);
-	index2 = MAX(old_index, new_index);
-	/* retreive the list items */
-	item1 = g_list_nth(c->playlist.list, index1);
-	item2 = g_list_nth(c->playlist.list, index2);
-	/* retrieve the songs */
-	data1 = item1->data;
-	data2 = item2->data;
-
-	/* move the second item */
-	c->playlist.list = g_list_remove(c->playlist.list, data2);
-	c->playlist.list = g_list_insert_before(c->playlist.list, item1, data2);
-
-	/* move the first item */
-	if (index2-index1 > 1) {
-		item2 = g_list_nth(c->playlist.list, index2);
-		c->playlist.list = g_list_remove(c->playlist.list, data1);
-		c->playlist.list = g_list_insert_before(c->playlist.list,
-							item2, data1);
-	}
+	/* update the array */
+	g_array_index(c->playlist.list, mpd_Song *, old_index) = song2;
+	g_array_index(c->playlist.list, mpd_Song *, new_index) = song1;
 
 	/* increment the playlist id, so we dont retrives a new playlist */
 	c->playlist.id++;
@@ -671,15 +652,14 @@ mpdclient_remove_error_callback(mpdclient_t *c, mpdc_error_cb_t cb)
 gint
 mpdclient_playlist_free(mpdclient_playlist_t *playlist)
 {
-  GList *list = g_list_first(playlist->list);
+	guint i;
 
-  while(list)
-    {
-      mpd_Song *song = (mpd_Song *) list->data;
-      mpd_freeSong(song);
-      list=list->next;
-    }
-  g_list_free(playlist->list);
+	for (i = 0; i < playlist->list->len; ++i) {
+		mpd_Song *song = g_array_index(playlist->list, mpd_Song *, i);
+		mpd_freeSong(song);
+	}
+
+	g_array_free(playlist->list, TRUE);
 	memset(playlist, 0, sizeof(mpdclient_playlist_t));
 	return 0;
 }
@@ -702,10 +682,7 @@ mpdclient_playlist_update(mpdclient_t *c)
 	while ((entity = mpd_getNextInfoEntity(c->connection))) {
 		if (entity->type == MPD_INFO_ENTITY_TYPE_SONG) {
 			mpd_Song *song = mpd_songDup(entity->info.song);
-
-			c->playlist.list = g_list_append(c->playlist.list,
-							 (gpointer)song);
-			c->playlist.length++;
+			g_array_append_val(c->playlist.list, song);
 		}
 		mpd_freeInfoEntity(entity);
 	}
@@ -737,41 +714,39 @@ mpdclient_playlist_update_changes(mpdclient_t *c)
 	mpd_sendPlChangesCommand(c->connection, c->playlist.id);
 
 	while ((entity = mpd_getNextInfoEntity(c->connection)) != NULL) {
-		mpd_Song *song = entity->info.song;
-
-		if (song->pos >= 0 && (guint)song->pos < c->playlist.length) {
-			GList *item = g_list_nth(c->playlist.list, song->pos);
+		mpd_Song *song = mpd_songDup(entity->info.song);
 
+		if (song->pos >= 0 && (guint)song->pos < c->playlist.list->len) {
 			/* update song */
-			D("updating pos:%d, id=%d [%p] - %s\n",
-			  song->pos, song->id, item, song->file);
-			mpd_freeSong((mpd_Song *) item->data);
-			item->data = mpd_songDup(song);
+			D("updating pos:%d, id=%d - %s\n",
+			  song->pos, song->id, song->file);
+			mpd_freeSong(g_array_index(c->playlist.list,
+						   mpd_Song *, song->pos));
+			g_array_index(c->playlist.list,
+				      mpd_Song *, song->pos) = song;
 		} else {
 			/* add a new song */
 			D("adding song at pos %d\n", song->pos);
-			c->playlist.list = g_list_append(c->playlist.list,
-							 (gpointer)mpd_songDup(song));
+			g_array_append_val(c->playlist.list, song);
 		}
 
 		mpd_freeInfoEntity(entity);
 	}
 
 	/* remove trailing songs */
-	while ((guint)c->status->playlistLength < c->playlist.length) {
-		GList *item = g_list_last(c->playlist.list);
+	while ((guint)c->status->playlistLength < c->playlist.list->len) {
+		guint pos = c->playlist.list->len - 1;
+		mpd_Song *song = g_array_index(c->playlist.list, mpd_Song *, pos);
 
 		/* Remove the last playlist entry */
-		D("removing song at pos %d\n", ((mpd_Song *) item->data)->pos);
-		mpd_freeSong((mpd_Song *) item->data);
-		c->playlist.list = g_list_delete_link(c->playlist.list, item);
-		c->playlist.length = g_list_length(c->playlist.list);
+		D("removing song at pos %d\n", pos);
+		mpd_freeSong(song);
+		g_array_remove_index(c->playlist.list, pos);
 	}
 
 	c->song = NULL;
 	c->playlist.id = c->status->playlist;
 	c->playlist.updated = TRUE;
-	c->playlist.length = g_list_length(c->playlist.list);
 
 	mpdclient_playlist_callback(c, PLAYLIST_EVENT_UPDATED, NULL);
 
@@ -789,34 +764,22 @@ mpdclient_playlist_update_changes(mpdclient_t *c)
 mpd_Song *
 playlist_get_song(mpdclient_t *c, gint idx)
 {
-	return (mpd_Song *) g_list_nth_data(c->playlist.list, idx);
-}
-
-GList *
-playlist_lookup(mpdclient_t *c, int id)
-{
-	GList *list = g_list_first(c->playlist.list);
-
-	while (list) {
-		mpd_Song *song = (mpd_Song *) list->data;
-		if( song->id == id )
-			return list;
-		list=list->next;
-	}
+	if (idx < 0 || (guint)idx >= c->playlist.list->len)
+		return NULL;
 
-	return NULL;
+	return g_array_index(c->playlist.list, mpd_Song *, idx);
 }
 
 mpd_Song *
 playlist_lookup_song(mpdclient_t *c, gint id)
 {
-	GList *list = c->playlist.list;
+	guint i;
 
-	while (list) {
-		mpd_Song *song = (mpd_Song *) list->data;
+	for (i = 0; i < c->playlist.list->len; ++i) {
+		mpd_Song *song = g_array_index(c->playlist.list,
+					       mpd_Song *, i);
 		if (song->id == id)
 			return song;
-		list=list->next;
 	}
 
 	return NULL;
@@ -825,30 +788,45 @@ playlist_lookup_song(mpdclient_t *c, gint id)
 gint
 playlist_get_index(mpdclient_t *c, mpd_Song *song)
 {
-	return g_list_index(c->playlist.list, song);
+	guint i;
+
+	for (i = 0; i < c->playlist.list->len; ++i) {
+		if (g_array_index(c->playlist.list, mpd_Song *, i)
+		    == song)
+			return (gint)i;
+	}
+
+	return -1;
 }
 
 gint
 playlist_get_index_from_id(mpdclient_t *c, gint id)
 {
-	return g_list_index(c->playlist.list, playlist_lookup_song(c, id));
+	guint i;
+
+	for (i = 0; i < c->playlist.list->len; ++i) {
+		mpd_Song *song = g_array_index(c->playlist.list,
+					       mpd_Song *, i);
+		if (song->id == id)
+			return (gint)i;
+	}
+
+	return -1;
 }
 
 gint
 playlist_get_index_from_file(mpdclient_t *c, gchar *filename)
 {
-  GList *list = c->playlist.list;
-  gint i=0;
+	guint i;
 
-  while( list )
-    {
-      mpd_Song *song = (mpd_Song *) list->data;
-      if( strcmp(song->file, filename ) == 0 )	
-	return i;
-      list=list->next;
-      i++;
-    }
-  return -1;
+	for (i = 0; i < c->playlist.list->len; ++i) {
+		mpd_Song *song = g_array_index(c->playlist.list,
+					       mpd_Song *, i);
+		if(strcmp(song->file, filename) == 0)
+			return (gint)i;
+	}
+
+	return -1;
 }
 
 
diff --git a/src/mpdclient.h b/src/mpdclient.h
index a93cec918..787839193 100644
--- a/src/mpdclient.h
+++ b/src/mpdclient.h
@@ -24,12 +24,10 @@ typedef struct
 {
   /* playlist id */
   long long id;
-  /* list length */
-  guint length;
   /* true if the list is updated */
   gboolean updated;
   /* the list */
-  GList *list;
+  GArray *list;
 
 } mpdclient_playlist_t;
 
@@ -135,7 +133,6 @@ gint mpdclient_playlist_update(mpdclient_t *c);
 /* get playlist changes */
 gint mpdclient_playlist_update_changes(mpdclient_t *c);
 
-GList *playlist_lookup(mpdclient_t *c, gint id);
 mpd_Song *playlist_lookup_song(mpdclient_t *c, gint id);
 mpd_Song *playlist_get_song(mpdclient_t *c, gint index);
 gint playlist_get_index(mpdclient_t *c, mpd_Song *song);
diff --git a/src/screen_play.c b/src/screen_play.c
index 2f9e6eba7..32c08ea73 100644
--- a/src/screen_play.c
+++ b/src/screen_play.c
@@ -70,7 +70,7 @@ playlist_changed_callback(mpdclient_t *c, int event, gpointer data)
 	/* make shure the playlist is repainted */
 	lw->clear = 1;
 	lw->repaint = 1;
-	list_window_check_selected(lw, c->playlist.length);
+	list_window_check_selected(lw, c->playlist.list->len);
 }
 
 static const char *
@@ -95,7 +95,7 @@ list_callback(unsigned idx, int *highlight, void *data)
 static int
 center_playing_item(mpdclient_t *c)
 {
-	unsigned length = c->playlist.length;
+	unsigned length = c->playlist.list->len;
 	unsigned offset = lw->selected - lw->start;
 	int idx;
 
@@ -402,9 +402,9 @@ play_update(screen_t *screen, mpdclient_t *c)
 	}
 
 	if( c->playlist.updated ) {
-		if( lw->selected >= c->playlist.length )
-			lw->selected = c->playlist.length-1;
-		if( lw->start    >= c->playlist.length )
+		if (lw->selected >= c->playlist.list->len)
+			lw->selected = c->playlist.list->len - 1;
+		if (lw->start >= c->playlist.list->len)
 			list_window_reset(lw);
 
 		play_paint(screen, c);
@@ -424,7 +424,7 @@ handle_mouse_event(mpd_unused screen_t *screen, mpdclient_t *c)
 	unsigned selected;
 	unsigned long bstate;
 
-	if (screen_get_mouse_event(c, lw, c->playlist.length, &bstate, &row))
+	if (screen_get_mouse_event(c, lw, c->playlist.list->len, &bstate, &row))
 		return 1;
 
 	if (bstate & BUTTON1_DOUBLE_CLICKED) {
@@ -437,7 +437,7 @@ handle_mouse_event(mpd_unused screen_t *screen, mpdclient_t *c)
 
 	if (bstate & BUTTON1_CLICKED) {
 		/* play */
-		if (lw->start + row < c->playlist.length)
+		if (lw->start + row < c->playlist.list->len)
 			mpdclient_cmd_play(c, lw->start + row);
 	} else if (bstate & BUTTON3_CLICKED) {
 		/* delete */
@@ -446,7 +446,7 @@ handle_mouse_event(mpd_unused screen_t *screen, mpdclient_t *c)
 	}
 
 	lw->selected = selected;
-	list_window_check_selected(lw, c->playlist.length);
+	list_window_check_selected(lw, c->playlist.list->len);
 
 	return 1;
 }
@@ -487,14 +487,14 @@ play_cmd(screen_t *screen, mpdclient_t *c, command_t cmd)
 	case CMD_LIST_FIND_NEXT:
 	case CMD_LIST_RFIND_NEXT:
 		return screen_find(screen,
-				   lw, c->playlist.length,
+				   lw, c->playlist.list->len,
 				   cmd, list_callback, (void *) c);
 	case CMD_MOUSE_EVENT:
 		return handle_mouse_event(screen,c);
 	default:
 		break;
 	}
-	return list_window_cmd(lw, c->playlist.length, cmd) ;
+	return list_window_cmd(lw, c->playlist.list->len, cmd);
 }
 
 static list_window_t *