Sync OpenBSD patchset 806:

Store sessions in an RB tree by name rather than a list, this is tidier
and allows them to easily be shown sorted in various lists
(list-sessions/choose-sessions).

Keep a session index which is used in a couple of places internally but
make it an ever-increasing number rather than filling in gaps with new
sessions.

12 files changed, 154 insertions, 194 deletions

diff --git a/cmd-attach-session.c b/cmd-attach-session.c
index 0dea764f..86fe53f0 100644
--- a/cmd-attach-session.c
+++ b/cmd-attach-session.c
@@ -1,4 +1,4 @@
-/* $Id: cmd-attach-session.c,v 1.36 2010-02-08 18:27:34 tcunha Exp $ */
+/* $Id: cmd-attach-session.c,v 1.37 2010-12-22 15:36:44 tcunha Exp $ */
 
 /*
  * Copyright (c) 2007 Nicholas Marriott <nicm@users.sourceforge.net>
@@ -47,7 +47,7 @@ cmd_attach_session_exec(struct cmd *self, struct cmd_ctx *ctx)
 	char			*overrides, *cause;
 	u_int			 i;
 
-	if (ARRAY_LENGTH(&sessions) == 0) {
+	if (RB_EMPTY(&sessions)) {
 		ctx->error(ctx, "no sessions");
 		return (-1);
 	}
diff --git a/cmd-choose-session.c b/cmd-choose-session.c
index 9dabf58e..200ed849 100644
--- a/cmd-choose-session.c
+++ b/cmd-choose-session.c
@@ -1,4 +1,4 @@
-/* $Id: cmd-choose-session.c,v 1.16 2010-12-22 15:25:07 tcunha Exp $ */
+/* $Id: cmd-choose-session.c,v 1.17 2010-12-22 15:36:44 tcunha Exp $ */
 
 /*
  * Copyright (c) 2009 Nicholas Marriott <nicm@users.sourceforge.net>
@@ -55,7 +55,7 @@ cmd_choose_session_exec(struct cmd *self, struct cmd_ctx *ctx)
 	struct winlink			*wl;
 	struct session			*s;
 	struct session_group		*sg;
-	u_int			 	 i, idx, sgidx, cur;
+	u_int			 	 idx, sgidx, cur;
 	char				 tmp[64];
 
 	if (ctx->curclient == NULL) {
@@ -70,10 +70,7 @@ cmd_choose_session_exec(struct cmd *self, struct cmd_ctx *ctx)
 		return (0);
 
 	cur = idx = 0;
-	for (i = 0; i < ARRAY_LENGTH(&sessions); i++) {
-		s = ARRAY_ITEM(&sessions, i);
-		if (s == NULL)
-			continue;
+	RB_FOREACH(s, sessions, &sessions) {
 		if (s == ctx->curclient->session)
 			cur = idx;
 		idx++;
@@ -86,7 +83,7 @@ cmd_choose_session_exec(struct cmd *self, struct cmd_ctx *ctx)
 			xsnprintf(tmp, sizeof tmp, " (group %u)", sgidx);
 		}
 
-		window_choose_add(wl->window->active, i,
+		window_choose_add(wl->window->active, s->idx,
 		    "%s: %u windows [%ux%u]%s%s", s->name,
 		    winlink_count(&s->windows), s->sx, s->sy,
 		    tmp, s->flags & SESSION_UNATTACHED ? "" : " (attached)");
@@ -120,9 +117,7 @@ cmd_choose_session_callback(void *data, int idx)
 	if (cdata->client->flags & CLIENT_DEAD)
 		return;
 
-	if ((u_int) idx > ARRAY_LENGTH(&sessions) - 1)
-		return;
-	s = ARRAY_ITEM(&sessions, idx);
+	s = session_find_by_index(idx);
 	if (s == NULL)
 		return;
 	template = cmd_template_replace(cdata->template, s->name, 1);
diff --git a/cmd-list-sessions.c b/cmd-list-sessions.c
index f6ac2438..30ac6861 100644
--- a/cmd-list-sessions.c
+++ b/cmd-list-sessions.c
@@ -1,4 +1,4 @@
-/* $Id: cmd-list-sessions.c,v 1.25 2009-11-28 14:50:36 tcunha Exp $ */
+/* $Id: cmd-list-sessions.c,v 1.26 2010-12-22 15:36:44 tcunha Exp $ */
 
 /*
  * Copyright (c) 2007 Nicholas Marriott <nicm@users.sourceforge.net>
@@ -46,14 +46,10 @@ cmd_list_sessions_exec(unused struct cmd *self, struct cmd_ctx *ctx)
 	struct session		*s;
 	struct session_group	*sg;
 	char			*tim, tmp[64];
-	u_int			 i, idx;
+	u_int			 idx;
 	time_t			 t;
 
-	for (i = 0; i < ARRAY_LENGTH(&sessions); i++) {
-		s = ARRAY_ITEM(&sessions, i);
-		if (s == NULL)
-			continue;
-
+	RB_FOREACH(s, sessions, &sessions) {
 		sg = session_group_find(s);
 		if (sg == NULL)
 			*tmp = '\0';
diff --git a/cmd-rename-session.c b/cmd-rename-session.c
index 23fcd7f2..24b0acb5 100644
--- a/cmd-rename-session.c
+++ b/cmd-rename-session.c
@@ -1,4 +1,4 @@
-/* $Id: cmd-rename-session.c,v 1.20 2010-08-11 22:19:03 tcunha Exp $ */
+/* $Id: cmd-rename-session.c,v 1.21 2010-12-22 15:36:44 tcunha Exp $ */
 
 /*
  * Copyright (c) 2007 Nicholas Marriott <nicm@users.sourceforge.net>
@@ -53,8 +53,10 @@ cmd_rename_session_exec(struct cmd *self, struct cmd_ctx *ctx)
 	if ((s = cmd_find_session(ctx, data->target)) == NULL)
 		return (-1);
 
+	RB_REMOVE(sessions, &sessions, s);
 	xfree(s->name);
 	s->name = xstrdup(data->arg);
+	RB_INSERT(sessions, &sessions, s);
 
 	server_status_session(s);
 
diff --git a/cmd-server-info.c b/cmd-server-info.c
index d168071d..aa950330 100644
--- a/cmd-server-info.c
+++ b/cmd-server-info.c
@@ -1,4 +1,4 @@
-/* $Id: cmd-server-info.c,v 1.37 2009-12-10 16:59:02 tcunha Exp $ */
+/* $Id: cmd-server-info.c,v 1.38 2010-12-22 15:36:44 tcunha Exp $ */
 
 /*
  * Copyright (c) 2008 Nicholas Marriott <nicm@users.sourceforge.net>
@@ -81,8 +81,6 @@ cmd_server_info_exec(unused struct cmd *self, struct cmd_ctx *ctx)
 	else
 		ctx->print(ctx, "configuration file not specified");
 	ctx->print(ctx, "protocol version is %d", PROTOCOL_VERSION);
-	ctx->print(ctx, "%u clients, %u sessions",
-	    ARRAY_LENGTH(&clients), ARRAY_LENGTH(&sessions));
 	ctx->print(ctx, "%s", "");
 
 	ctx->print(ctx, "Clients:");
@@ -101,19 +99,14 @@ cmd_server_info_exec(unused struct cmd *self, struct cmd_ctx *ctx)
 
 	ctx->print(ctx, "Sessions: [%zu/%zu]",
 	    sizeof (struct grid_cell), sizeof (struct grid_utf8));
-	for (i = 0; i < ARRAY_LENGTH(&sessions); i++) {
-		s = ARRAY_ITEM(&sessions, i);
-		if (s == NULL)
-			continue;
-
+	RB_FOREACH(s, sessions, &sessions) {
 		t = s->creation_time.tv_sec;
 		tim = ctime(&t);
 		*strchr(tim, '\n') = '\0';
 
 		ctx->print(ctx, "%2u: %s: %u windows (created %s) [%ux%u] "
-		    "[flags=0x%x, references=%u]", i, s->name,
-		    winlink_count(&s->windows), tim, s->sx, s->sy, s->flags,
-		    s->references);
+		    "[flags=0x%x]", s->idx, s->name,
+		    winlink_count(&s->windows), tim, s->sx, s->sy, s->flags);
 		RB_FOREACH(wl, winlinks, &s->windows) {
 			w = wl->window;
 			ctx->print(ctx, "%4u: %s [%ux%u] [flags=0x%x, "
diff --git a/cmd.c b/cmd.c
index a83fddfc..8ef91a54 100644
--- a/cmd.c
+++ b/cmd.c
@@ -1,4 +1,4 @@
-/* $Id: cmd.c,v 1.145 2010-12-06 21:48:56 nicm Exp $ */
+/* $Id: cmd.c,v 1.146 2010-12-22 15:36:44 tcunha Exp $ */
 
 /*
  * Copyright (c) 2007 Nicholas Marriott <nicm@users.sourceforge.net>
@@ -111,7 +111,8 @@ const struct cmd_entry *cmd_table[] = {
 	NULL
 };
 
-struct session	*cmd_choose_session(struct sessions *);
+struct session	*cmd_choose_session_list(struct sessionslist *);
+struct session	*cmd_choose_session(void);
 struct client	*cmd_choose_client(struct clients *);
 struct client	*cmd_lookup_client(const char *);
 struct session	*cmd_lookup_session(const char *, int *);
@@ -315,10 +316,9 @@ cmd_current_session(struct cmd_ctx *ctx)
 	struct msg_command_data	*data = ctx->msgdata;
 	struct client		*c = ctx->cmdclient;
 	struct session		*s;
-	struct sessions		 ss;
+	struct sessionslist	 ss;
 	struct winlink		*wl;
 	struct window_pane	*wp;
-	u_int			 i;
 	int			 found;
 
 	if (ctx->curclient != NULL && ctx->curclient->session != NULL)
@@ -331,9 +331,7 @@ cmd_current_session(struct cmd_ctx *ctx)
 	 */
 	if (c != NULL && c->tty.path != NULL) {
 		ARRAY_INIT(&ss);
-		for (i = 0; i < ARRAY_LENGTH(&sessions); i++) {
-			if ((s = ARRAY_ITEM(&sessions, i)) == NULL)
-				continue;
+		RB_FOREACH(s, sessions, &sessions) {
 			found = 0;
 			RB_FOREACH(wl, winlinks, &s->windows) {
 				TAILQ_FOREACH(wp, &wl->window->panes, entry) {
@@ -349,25 +347,43 @@ cmd_current_session(struct cmd_ctx *ctx)
 				ARRAY_ADD(&ss, s);
 		}
 
-		s = cmd_choose_session(&ss);
+		s = cmd_choose_session_list(&ss);
 		ARRAY_FREE(&ss);
 		if (s != NULL)
 			return (s);
 	}
 
 	/* Use the session from the TMUX environment variable. */
-	if (data != NULL &&
-	    data->pid == getpid() &&
-	    data->idx <= ARRAY_LENGTH(&sessions) &&
-	    (s = ARRAY_ITEM(&sessions, data->idx)) != NULL)
-		return (s);
+	if (data != NULL && data->pid == getpid()) {
+		s = session_find_by_index(data->idx);
+		if (s != NULL)
+			return (s);
+	}
 
-	return (cmd_choose_session(&sessions));
+	return (cmd_choose_session());
+}
+
+/* Find the most recently used session. */
+struct session *
+cmd_choose_session(void)
+{
+	struct session	*s, *sbest;
+	struct timeval	*tv = NULL;
+
+	sbest = NULL;
+	RB_FOREACH(s, sessions, &sessions) {
+		if (tv == NULL || timercmp(&s->activity_time, tv, >)) {
+			sbest = s;
+			tv = &s->activity_time;
+		}
+	}
+
+	return (sbest);
 }
 
 /* Find the most recently used session from a list. */
 struct session *
-cmd_choose_session(struct sessions *ss)
+cmd_choose_session_list(struct sessionslist *ss)
 {
 	struct session	*s, *sbest;
 	struct timeval	*tv = NULL;
@@ -515,7 +531,6 @@ struct session *
 cmd_lookup_session(const char *name, int *ambiguous)
 {
 	struct session	*s, *sfound;
-	u_int		 i;
 
 	*ambiguous = 0;
 
@@ -524,21 +539,15 @@ cmd_lookup_session(const char *name, int *ambiguous)
 	 * be unique so an exact match can't be ambigious and can just be
 	 * returned.
 	 */
-	for (i = 0; i < ARRAY_LENGTH(&sessions); i++) {
-		if ((s = ARRAY_ITEM(&sessions, i)) == NULL)
-			continue;
-		if (strcmp(name, s->name) == 0)
-			return (s);
-	}
+	if ((s = session_find(name)) != NULL)
+		return (s);
 
 	/*
 	 * Otherwise look for partial matches, returning early if it is found to
 	 * be ambiguous.
 	 */
 	sfound = NULL;
-	for (i = 0; i < ARRAY_LENGTH(&sessions); i++) {
-		if ((s = ARRAY_ITEM(&sessions, i)) == NULL)
-			continue;
+	RB_FOREACH(s, sessions, &sessions) {
 		if (strncmp(name, s->name, strlen(name)) == 0 ||
 		    fnmatch(name, s->name, 0) == 0) {
 			if (sfound != NULL) {
diff --git a/resize.c b/resize.c
index 06899ce2..6ac93b77 100644
--- a/resize.c
+++ b/resize.c
@@ -1,4 +1,4 @@
-/* $Id: resize.c,v 1.26 2010-12-06 21:57:56 nicm Exp $ */
+/* $Id: resize.c,v 1.27 2010-12-22 15:36:44 tcunha Exp $ */
 
 /*
  * Copyright (c) 2007 Nicholas Marriott <nicm@users.sourceforge.net>
@@ -52,11 +52,7 @@ recalculate_sizes(void)
 	u_int		 	 i, j, ssx, ssy, has, limit;
 	int		 	 flag;
 
-	for (i = 0; i < ARRAY_LENGTH(&sessions); i++) {
-		s = ARRAY_ITEM(&sessions, i);
-		if (s == NULL)
-			continue;
-
+	RB_FOREACH(s, sessions, &sessions) {
 		ssx = ssy = UINT_MAX;
 		for (j = 0; j < ARRAY_LENGTH(&clients); j++) {
 			c = ARRAY_ITEM(&clients, j);
@@ -98,9 +94,8 @@ recalculate_sizes(void)
 		flag = options_get_number(&w->options, "aggressive-resize");
 
 		ssx = ssy = UINT_MAX;
-		for (j = 0; j < ARRAY_LENGTH(&sessions); j++) {
-			s = ARRAY_ITEM(&sessions, j);
-			if (s == NULL || s->flags & SESSION_UNATTACHED)
+		RB_FOREACH(s, sessions, &sessions) {
+			if (s->flags & SESSION_UNATTACHED)
 				continue;
 			if (flag)
 				has = s->curw->window == w;
diff --git a/server-fn.c b/server-fn.c
index f29399d2..d83520d9 100644
--- a/server-fn.c
+++ b/server-fn.c
@@ -1,4 +1,4 @@
-/* $Id: server-fn.c,v 1.115 2010-12-22 15:31:00 tcunha Exp $ */
+/* $Id: server-fn.c,v 1.116 2010-12-22 15:36:44 tcunha Exp $ */
 
 /*
  * Copyright (c) 2007 Nicholas Marriott <nicm@users.sourceforge.net>
@@ -30,13 +30,10 @@ void		server_callback_identify(int, short, void *);
 void
 server_fill_environ(struct session *s, struct environ *env)
 {
-	char		 tmuxvar[MAXPATHLEN], *term;
-	u_int		 idx;
+	char	tmuxvar[MAXPATHLEN], *term;
 
-	if (session_index(s, &idx) != 0)
-		fatalx("session not found");
 	xsnprintf(tmuxvar, sizeof tmuxvar,
-	    "%s,%ld,%u", socket_path, (long) getpid(), idx);
+	    "%s,%ld,%u", socket_path, (long) getpid(), s->idx);
 	environ_set(env, "TMUX", tmuxvar);
 
 	term = options_get_string(&s->options, "default-terminal");
@@ -175,7 +172,6 @@ void
 server_status_window(struct window *w)
 {
 	struct session	*s;
-	u_int		 i;
 
 	/*
 	 * This is slightly different. We want to redraw the status line of any
@@ -183,9 +179,8 @@ server_status_window(struct window *w)
 	 * current window.
 	 */
 
-	for (i = 0; i < ARRAY_LENGTH(&sessions); i++) {
-		s = ARRAY_ITEM(&sessions, i);
-		if (s != NULL && session_has(s, w) != NULL)
+	RB_FOREACH(s, sessions, &sessions) {
+		if (session_has(s, w) != NULL)
 			server_status_session(s);
 	}
 }
@@ -246,11 +241,9 @@ server_kill_window(struct window *w)
 {
 	struct session	*s;
 	struct winlink	*wl;
-	u_int		 i;
 
-	for (i = 0; i < ARRAY_LENGTH(&sessions); i++) {
-		s = ARRAY_ITEM(&sessions, i);
-		if (s == NULL || session_has(s, w) == NULL)
+	RB_FOREACH(s, sessions, &sessions) {
+		if (session_has(s, w) == NULL)
 			continue;
 		while ((wl = winlink_find_by_window(&s->windows, w)) != NULL) {
 			if (session_detach(s, wl)) {
@@ -365,12 +358,10 @@ struct session *
 server_next_session(struct session *s)
 {
 	struct session *s_loop, *s_out;
-	u_int		i;
 
 	s_out = NULL;
-	for (i = 0; i < ARRAY_LENGTH(&sessions); i++) {
-		s_loop = ARRAY_ITEM(&sessions, i);
-		if (s_loop == NULL || s_loop == s)
+	RB_FOREACH(s_loop, sessions, &sessions) {
+		if (s_loop == s)
 			continue;
 		if (s_out == NULL ||
 		    timercmp(&s_loop->activity_time, &s_out->activity_time, <))
@@ -411,15 +402,13 @@ void
 server_check_unattached (void)
 {
 	struct session	*s;
-	u_int		 i;
 
 	/*
 	 * If any sessions are no longer attached and have destroy-unattached
 	 * set, collect them.
 	 */
-	for (i = 0; i < ARRAY_LENGTH(&sessions); i++) {
-		s = ARRAY_ITEM(&sessions, i);
-		if (s == NULL || !(s->flags & SESSION_UNATTACHED))
+	RB_FOREACH(s, sessions, &sessions) {
+		if (!(s->flags & SESSION_UNATTACHED))
 			continue;
 		if (options_get_number (&s->options, "destroy-unattached"))
 			session_destroy(s);
diff --git a/server-window.c b/server-window.c
index 7f43a91e..b5daac5a 100644
--- a/server-window.c
+++ b/server-window.c
@@ -1,4 +1,4 @@
-/* $Id: server-window.c,v 1.18 2010-12-06 22:52:21 nicm Exp $ */
+/* $Id: server-window.c,v 1.19 2010-12-22 15:36:44 tcunha Exp $ */
 
 /*
  * Copyright (c) 2009 Nicholas Marriott <nicm@users.sourceforge.net>
@@ -38,17 +38,14 @@ server_window_loop(void)
 	struct winlink		*wl;
 	struct window_pane	*wp;
 	struct session		*s;
-	u_int		 	 i, j;
+	u_int		 	 i;
 
 	for (i = 0; i < ARRAY_LENGTH(&windows); i++) {
 		w = ARRAY_ITEM(&windows, i);
 		if (w == NULL)
 			continue;
 
-		for (j = 0; j < ARRAY_LENGTH(&sessions); j++) {
-			s = ARRAY_ITEM(&sessions, j);
-			if (s == NULL)
-				continue;
+		RB_FOREACH(s, sessions, &sessions) {
 			wl = session_has(s, w);
 			if (wl == NULL)
 				continue;
diff --git a/server.c b/server.c
index f1f9dce0..44a43692 100644
--- a/server.c
+++ b/server.c
@@ -1,4 +1,4 @@
-/* $Id: server.c,v 1.248 2010-10-24 19:54:41 nicm Exp $ */
+/* $Id: server.c,v 1.249 2010-12-22 15:36:44 tcunha Exp $ */
 
 /*
  * Copyright (c) 2007 Nicholas Marriott <nicm@users.sourceforge.net>
@@ -146,8 +146,8 @@ server_start(void)
 	ARRAY_INIT(&windows);
 	ARRAY_INIT(&clients);
 	ARRAY_INIT(&dead_clients);
-	ARRAY_INIT(&sessions);
-	ARRAY_INIT(&dead_sessions);
+	RB_INIT(&sessions);
+	RB_INIT(&dead_sessions);
 	TAILQ_INIT(&session_groups);
 	mode_key_init_trees();
 	key_bindings_init();
@@ -175,8 +175,8 @@ server_start(void)
 	 * If there is a session already, put the current window and pane into
 	 * more mode.
 	 */
-	if (!ARRAY_EMPTY(&sessions) && !ARRAY_EMPTY(&cfg_causes)) {
-		wp = ARRAY_FIRST(&sessions)->curw->window->active;
+	if (!RB_EMPTY(&sessions) && !ARRAY_EMPTY(&cfg_causes)) {
+		wp = RB_MIN(sessions, &sessions)->curw->window->active;
 		window_pane_set_mode(wp, &window_copy_mode);
 		window_copy_init_for_output(wp);
 		for (i = 0; i < ARRAY_LENGTH(&cfg_causes); i++) {
@@ -224,10 +224,8 @@ server_should_shutdown(void)
 	u_int	i;
 
 	if (!options_get_number(&global_options, "exit-unattached")) {
-		for (i = 0; i < ARRAY_LENGTH(&sessions); i++) {
-			if (ARRAY_ITEM(&sessions, i) != NULL)
-				return (0);
-		}
+		if (!RB_EMPTY(&sessions))
+			return (0);
 	}
 	for (i = 0; i < ARRAY_LENGTH(&clients); i++) {
 		if (ARRAY_ITEM(&clients, i) != NULL)
@@ -241,7 +239,7 @@ void
 server_send_shutdown(void)
 {
 	struct client	*c;
-	struct session	*s;
+	struct session	*s, *next_s;
 	u_int		 i;
 
 	for (i = 0; i < ARRAY_LENGTH(&clients); i++) {
@@ -255,9 +253,11 @@ server_send_shutdown(void)
 		}
 	}
 
-	for (i = 0; i < ARRAY_LENGTH(&sessions); i++) {
-		if ((s = ARRAY_ITEM(&sessions, i)) != NULL)
-			session_destroy(s);
+	s = RB_MIN(sessions, &sessions);
+	while (s != NULL) {
+		next_s = RB_NEXT(sessions, &sessions, s);
+		session_destroy(s);
+		s = next_s;
 	}
 }
 
@@ -265,16 +265,19 @@ server_send_shutdown(void)
 void
 server_clean_dead(void)
 {
-	struct session	*s;
+	struct session	*s, *next_s;
 	struct client	*c;
 	u_int		 i;
 
-	for (i = 0; i < ARRAY_LENGTH(&dead_sessions); i++) {
-		s = ARRAY_ITEM(&dead_sessions, i);
-		if (s == NULL || s->references != 0)
-			continue;
-		ARRAY_SET(&dead_sessions, i, NULL);
-		xfree(s);
+	s = RB_MIN(sessions, &dead_sessions);
+	while (s != NULL) {
+		next_s = RB_NEXT(sessions, &dead_sessions, s);
+		if (s->references == 0) {
+			RB_REMOVE(sessions, &dead_sessions, s);
+			xfree(s->name);
+			xfree(s);
+		}
+		s = next_s;
 	}
 
 	for (i = 0; i < ARRAY_LENGTH(&dead_clients); i++) {
@@ -291,15 +294,13 @@ void
 server_update_socket(void)
 {
 	struct session	*s;
-	u_int		 i;
 	static int	 last = -1;
 	int		 n, mode;
 	struct stat      sb;
 
 	n = 0;
-	for (i = 0; i < ARRAY_LENGTH(&sessions); i++) {
-		s = ARRAY_ITEM(&sessions, i);
-		if (s != NULL && !(s->flags & SESSION_UNATTACHED)) {
+	RB_FOREACH(s, sessions, &sessions) {
+		if (!(s->flags & SESSION_UNATTACHED)) {
 			n++;
 			break;
 		}
@@ -486,15 +487,11 @@ void
 server_lock_server(void)
 {
 	struct session  *s;
-	u_int            i;
 	int		 timeout;
 	time_t           t;
 
 	t = time(NULL);
-	for (i = 0; i < ARRAY_LENGTH(&sessions); i++) {
-		if ((s = ARRAY_ITEM(&sessions, i)) == NULL)
-			continue;
-
+	RB_FOREACH(s, sessions, &sessions) {
 		if (s->flags & SESSION_UNATTACHED) {
 			if (gettimeofday(&s->activity_time, NULL) != 0)
 				fatal("gettimeofday failed");
@@ -515,15 +512,11 @@ void
 server_lock_sessions(void)
 {
 	struct session  *s;
-	u_int		 i;
 	int		 timeout;
 	time_t		 t;
 
 	t = time(NULL);
-	for (i = 0; i < ARRAY_LENGTH(&sessions); i++) {
-		if ((s = ARRAY_ITEM(&sessions, i)) == NULL)
-			continue;
-
+	RB_FOREACH(s, sessions, &sessions) {
 		if (s->flags & SESSION_UNATTACHED) {
 			if (gettimeofday(&s->activity_time, NULL) != 0)
 				fatal("gettimeofday failed");
diff --git a/session.c b/session.c
index 2badf8bc..25f0ef53 100644
--- a/session.c
+++ b/session.c
@@ -1,4 +1,4 @@
-/* $Id: session.c,v 1.82 2010-12-22 15:33:14 tcunha Exp $ */
+/* $Id: session.c,v 1.83 2010-12-22 15:36:44 tcunha Exp $ */
 
 /*
  * Copyright (c) 2007 Nicholas Marriott <nicm@users.sourceforge.net>
@@ -29,11 +29,20 @@
 /* Global session list. */
 struct sessions	sessions;
 struct sessions dead_sessions;
+u_int		next_session;
 struct session_groups session_groups;
 
 struct winlink *session_next_alert(struct winlink *);
 struct winlink *session_previous_alert(struct winlink *);
 
+RB_GENERATE(sessions, session, entry, session_cmp);
+
+int
+session_cmp(struct session *s1, struct session *s2)
+{
+	return (strcmp(s1->name, s2->name));
+}
+
 /*
  * Find if session is still alive. This is true if it is still on the global
  * sessions list.
@@ -41,24 +50,35 @@ struct winlink *session_previous_alert(struct winlink *);
 int
 session_alive(struct session *s)
 {
-	u_int	idx;
+	struct session *s_loop;
 
-	return (session_index(s, &idx) == 0);
+	RB_FOREACH(s_loop, sessions, &sessions) {
+		if (s_loop == s)
+			return (1);
+	}
+	return (0);
 }
 
 /* Find session by name. */
 struct session *
 session_find(const char *name)
 {
+	struct session	s;
+
+	s.name = (char *) name;
+	return (RB_FIND(sessions, &sessions, &s));
+}
+
+/* Find session by index. */
+struct session *
+session_find_by_index(u_int idx)
+{
 	struct session	*s;
-	u_int		 i;
 
-	for (i = 0; i < ARRAY_LENGTH(&sessions); i++) {
-		s = ARRAY_ITEM(&sessions, i);
-		if (s != NULL && strcmp(s->name, name) == 0)
+	RB_FOREACH(s, sessions, &sessions) {
+		if (s->idx == idx)
 			return (s);
 	}
-
 	return (NULL);
 }
 
@@ -69,7 +89,6 @@ session_create(const char *name, const char *cmd, const char *cwd,
     char **cause)
 {
 	struct session	*s;
-	u_int		 i;
 
 	s = xmalloc(sizeof *s);
 	s->references = 0;
@@ -101,19 +120,12 @@ session_create(const char *name, const char *cmd, const char *cwd,
 	s->sx = sx;
 	s->sy = sy;
 
-	for (i = 0; i < ARRAY_LENGTH(&sessions); i++) {
-		if (ARRAY_ITEM(&sessions, i) == NULL) {
-			ARRAY_SET(&sessions, i, s);
-			break;
-		}
-	}
-	if (i == ARRAY_LENGTH(&sessions))
-		ARRAY_ADD(&sessions, s);
-
+	s->idx = next_session++;
 	if (name != NULL)
 		s->name = xstrdup(name);
 	else
-		xasprintf(&s->name, "%u", i);
+		xasprintf(&s->name, "%u", s->idx);
+	RB_INSERT(sessions, &sessions, s);
 
 	if (cmd != NULL) {
 		if (session_new(s, NULL, cmd, cwd, idx, cause) == NULL) {
@@ -132,15 +144,9 @@ session_create(const char *name, const char *cmd, const char *cwd,
 void
 session_destroy(struct session *s)
 {
-	u_int	i;
-
 	log_debug("session %s destroyed", s->name);
 
-	if (session_index(s, &i) != 0)
-		fatalx("session not found");
-	ARRAY_SET(&sessions, i, NULL);
-	while (!ARRAY_EMPTY(&sessions) && ARRAY_LAST(&sessions) == NULL)
-		ARRAY_TRUNC(&sessions, 1);
+	RB_REMOVE(sessions, &sessions, s);
 
 	if (s->tio != NULL)
 		xfree(s->tio);
@@ -156,27 +162,8 @@ session_destroy(struct session *s)
 		winlink_remove(&s->windows, RB_ROOT(&s->windows));
 
 	xfree(s->cwd);
-	xfree(s->name);
 
-	for (i = 0; i < ARRAY_LENGTH(&dead_sessions); i++) {
-		if (ARRAY_ITEM(&dead_sessions, i) == NULL) {
-			ARRAY_SET(&dead_sessions, i, s);
-			break;
-		}
-	}
-	if (i == ARRAY_LENGTH(&dead_sessions))
-		ARRAY_ADD(&dead_sessions, s);
-}
-
-/* Find session index. */
-int
-session_index(struct session *s, u_int *i)
-{
-	for (*i = 0; *i < ARRAY_LENGTH(&sessions); (*i)++) {
-		if (s == ARRAY_ITEM(&sessions, *i))
-			return (0);
-	}
-	return (-1);
+	RB_INSERT(sessions, &dead_sessions, s);
 }
 
 /* Find the next usable session. */
@@ -184,19 +171,18 @@ struct session *
 session_next_session(struct session *s)
 {
 	struct session *s2;
-	u_int		i;
 
-	if (ARRAY_LENGTH(&sessions) == 0 || session_index(s, &i) != 0)
+	if (RB_EMPTY(&sessions) || !session_alive(s))
 		return (NULL);
 
+	s2 = s;
 	do {
-		if (i == ARRAY_LENGTH(&sessions) - 1)
-			i = 0;
-		else
-			i++;
-		s2 = ARRAY_ITEM(&sessions, i);
-	} while (s2 == NULL);
-
+		s2 = RB_NEXT(sessions, &sessions, s2);
+		if (s2 == NULL)
+			s2 = RB_MIN(sessions, &sessions);
+	} while (s2 != s);
+	if (s2 == s)
+		return (NULL);
 	return (s2);
 }
 
@@ -205,19 +191,18 @@ struct session *
 session_previous_session(struct session *s)
 {
 	struct session *s2;
-	u_int		i;
 
-	if (ARRAY_LENGTH(&sessions) == 0 || session_index(s, &i) != 0)
+	if (RB_EMPTY(&sessions) || !session_alive(s))
 		return (NULL);
 
+	s2 = s;
 	do {
-		if (i == 0)
-			i = ARRAY_LENGTH(&sessions) - 1;
-		else
-			i--;
-		s2 = ARRAY_ITEM(&sessions, i);
-	} while (s2 == NULL);
-
+		s2 = RB_PREV(sessions, &sessions, s2);
+		if (s2 == NULL)
+			s2 = RB_MAX(sessions, &sessions);
+	} while (s2 != s);
+	if (s2 == s)
+		return (NULL);
 	return (s2);
 }
 
diff --git a/tmux.h b/tmux.h
index 0e1caf60..0642401c 100644
--- a/tmux.h
+++ b/tmux.h
@@ -1,4 +1,4 @@
-/* $Id: tmux.h,v 1.590 2010-12-22 15:31:56 tcunha Exp $ */
+/* $Id: tmux.h,v 1.591 2010-12-22 15:36:44 tcunha Exp $ */
 
 /*
  * Copyright (c) 2007 Nicholas Marriott <nicm@users.sourceforge.net>
@@ -928,6 +928,8 @@ struct session_group {
 TAILQ_HEAD(session_groups, session_group);
 
 struct session {
+	u_int		 idx;
+
 	char		*name;
 	char		*cwd;
 
@@ -955,8 +957,10 @@ struct session {
 	int		 references;
 
 	TAILQ_ENTRY(session) gentry;
+	RB_ENTRY(session)    entry;
 };
-ARRAY_DECL(sessions, struct session *);
+RB_HEAD(sessions, session);
+ARRAY_DECL(sessionslist, struct session *);
 
 /* TTY information. */
 struct tty_key {
@@ -1965,13 +1969,15 @@ void clear_signals(int);
 extern struct sessions sessions;
 extern struct sessions dead_sessions;
 extern struct session_groups session_groups;
+int	session_cmp(struct session *, struct session *);
+RB_PROTOTYPE(sessions, session, entry, session_cmp);
 int		 session_alive(struct session *);
 struct session	*session_find(const char *);
+struct session	*session_find_by_index(u_int);
 struct session	*session_create(const char *, const char *, const char *,
 		     struct environ *, struct termios *, int, u_int, u_int,
 		     char **);
 void		 session_destroy(struct session *);
-int		 session_index(struct session *, u_int *);
 struct session	*session_next_session(struct session *);
 struct session	*session_previous_session(struct session *);
 struct winlink	*session_new(struct session *,