From 00a37f7479fc780669afd3ad82d938a1096952d0 Mon Sep 17 00:00:00 2001
From: sabetts <sabetts>
Date: Sat, 22 Feb 2003 11:16:55 +0000
Subject: * src/actions.c (cmd_number): use list delete entry macro
 (cmd_number): likewise (cmd_escape): use list looping macro (cmd_escape):
 likewise (cmd_defpadding): likewise (cmd_defborder): likewise

* src/data.h: include linkedlist.h
(struct rp_window_frame): use struct list_head instead of next,
prev pointers.
(struct rp_window): likewise
(struct screen_info): rename rp_window_frame_sentinel to
rp_window_frames and change it's type to list_head.

* src/events.c (mapping_notify): use list looping macro
(mapping_notify): likewise

* src/list.c: rename rp_unmapped_window_sentinel to
rp_unmapped_window and rp_mapped_window_sentinel to
rp_mapped_window. Use LIST_HEAD to create them. externs updated.
(add_to_window_list): use list add entry macro.
(find_window_in_list): list head is of type list_head. Prototype
and callers updated.
(find_window_in_list): use list looping macro
(init_window_list): remove function
(find_window_number): use list looping macro
(find_window_name): likewise
(find_window_prev): use list previous entry macro
(find_window_next): use list next entry macro
(find_window_other): use list looping macro
(append_to_list): remove function
(insert_into_list): use list looping macro
(insert_into_list): use list add entry macro
(remove_from_list): remove function
(get_window_list): use list looping macro

* src/main.c (main): do not call init_window_list()

* src/manage.c (unmanage): use list delete macro
(map_window): likewise
(withdraw_window): use list moving macro to move entry to
another list.
(hide_others): use list looping macro

* src/split.c (num_frames): use list looping macro
(frames_screen): likewise
(maximize_all_windows_in_frame): likewise
(delete_frame_from_list): remove function
(create_initial_frame): remove list init code. Add current frame
to screen's frame list.
(init_frame_list): use list init macro
(find_last_frame): use list looping macro
(find_windows_frame): likewise
(find_frame_next): use list next entry macro
(find_frame_prev): use list previous entry macro
(find_window_for_frame): use list looping macro
(split_frame): use list add entry macro
(remove_all_splits): use list looping macro
(resize_frame_vertically): likewise
(resize_frame_horizontally): likewise
(total_frame_area): likewise
(frame_overlaps): likewise
(remove_frame): likewise
(find_frame_up): likewise
(find_frame_down): likewise
(find_frame_left): likewise
(find_frame_right): likewise
---
 ChangeLog        |  70 +++++++++++++
 src/actions.c    |  24 ++---
 src/data.h       |  12 ++-
 src/events.c     |  10 +-
 src/linkedlist.h | 295 +++++++++++++++++++++++++++++++++++++++++++++++++++++++
 src/list.c       | 144 +++++----------------------
 src/list.h       |   9 +-
 src/main.c       |   1 -
 src/manage.c     |  14 +--
 src/split.c      | 177 +++++++++------------------------
 10 files changed, 456 insertions(+), 300 deletions(-)
 create mode 100644 src/linkedlist.h

diff --git a/ChangeLog b/ChangeLog
index 11325a9..57706d2 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,73 @@
+2003-02-22  Shawn Betts  <sabetts@sfu.ca>
+
+	* src/actions.c (cmd_number): use list delete entry macro
+	(cmd_number): likewise
+	(cmd_escape): use list looping macro
+	(cmd_escape): likewise
+	(cmd_defpadding): likewise
+	(cmd_defborder): likewise
+
+	* src/data.h: include linkedlist.h
+	(struct rp_window_frame): use struct list_head instead of next,
+	prev pointers.
+	(struct rp_window): likewise
+	(struct screen_info): rename rp_window_frame_sentinel to
+	rp_window_frames and change it's type to list_head.
+
+	* src/events.c (mapping_notify): use list looping macro
+	(mapping_notify): likewise
+
+	* src/list.c: rename rp_unmapped_window_sentinel to
+	rp_unmapped_window and rp_mapped_window_sentinel to
+	rp_mapped_window. Use LIST_HEAD to create them. externs updated.
+	(add_to_window_list): use list add entry macro.
+	(find_window_in_list): list head is of type list_head. Prototype
+	and callers updated.
+	(find_window_in_list): use list looping macro
+	(init_window_list): remove function
+	(find_window_number): use list looping macro
+	(find_window_name): likewise
+	(find_window_prev): use list previous entry macro
+	(find_window_next): use list next entry macro
+	(find_window_other): use list looping macro
+	(append_to_list): remove function
+	(insert_into_list): use list looping macro
+	(insert_into_list): use list add entry macro
+	(remove_from_list): remove function
+	(get_window_list): use list looping macro
+
+	* src/main.c (main): do not call init_window_list()
+
+	* src/manage.c (unmanage): use list delete macro
+	(map_window): likewise
+	(withdraw_window): use list moving macro to move entry to
+	another list.
+	(hide_others): use list looping macro
+
+	* src/split.c (num_frames): use list looping macro
+	(frames_screen): likewise
+	(maximize_all_windows_in_frame): likewise
+	(delete_frame_from_list): remove function
+	(create_initial_frame): remove list init code. Add current frame
+	to screen's frame list.
+	(init_frame_list): use list init macro
+	(find_last_frame): use list looping macro
+	(find_windows_frame): likewise
+	(find_frame_next): use list next entry macro
+	(find_frame_prev): use list previous entry macro
+	(find_window_for_frame): use list looping macro
+	(split_frame): use list add entry macro
+	(remove_all_splits): use list looping macro
+	(resize_frame_vertically): likewise
+	(resize_frame_horizontally): likewise
+	(total_frame_area): likewise
+	(frame_overlaps): likewise
+	(remove_frame): likewise
+	(find_frame_up): likewise
+	(find_frame_down): likewise
+	(find_frame_left): likewise
+	(find_frame_right): likewise
+
 2003-02-10  Shawn Betts  <sabetts@sfu.ca>
 
 	* src/split.h (num_frames): new prototype
diff --git a/src/actions.c b/src/actions.c
index 17a1db2..6bec5d1 100644
--- a/src/actions.c
+++ b/src/actions.c
@@ -1135,8 +1135,8 @@ cmd_number (int interactive, void *data)
 	  other_win->number = old_number;
 
 	  /* Resort the the window in the list */
-	  remove_from_list (other_win);
-	  insert_into_list (other_win, rp_mapped_window_sentinel);
+	  list_del (&other_win->node);
+	  insert_into_list (other_win, &rp_mapped_window);
 	}
       else
 	{
@@ -1147,8 +1147,8 @@ cmd_number (int interactive, void *data)
       add_window_number (new_number);
 
       /* resort the the window in the list */
-      remove_from_list (win);
-      insert_into_list (win, rp_mapped_window_sentinel);
+      list_del (&win->node);
+      insert_into_list (win, &rp_mapped_window);
 
       /* Update the window list. */
       update_window_names (win->scr);
@@ -1232,9 +1232,7 @@ cmd_escape (int interactive, void *data)
 	}
 
       /* Remove the grab on the current prefix key */
-      for (cur = rp_mapped_window_sentinel->next; 
-	   cur != rp_mapped_window_sentinel; 
-	   cur = cur->next)
+      list_for_each_entry (cur, &rp_mapped_window, node)
 	{
 	  ungrab_prefix_key (cur->w);
 	}
@@ -1243,9 +1241,7 @@ cmd_escape (int interactive, void *data)
       prefix_key.state = key->state;
 
       /* Add the grab for the new prefix key */
-      for (cur = rp_mapped_window_sentinel->next; 
-	   cur != rp_mapped_window_sentinel; 
-	   cur = cur->next)
+      list_for_each_entry (cur,&rp_mapped_window,node)
 	{
 	  grab_prefix_key (cur->w);
 	}
@@ -1994,9 +1990,7 @@ cmd_defpadding (int interactive, void *data)
 
   /* Resize the frames to make sure they are not too big and not too
      small. */
-  for (frame = current_screen()->rp_window_frame_sentinel->next; 
-       frame != current_screen()->rp_window_frame_sentinel;
-       frame = frame->next)
+  list_for_each_entry (frame,&(current_screen()->rp_window_frames),node)
     {
       int bk_pos, bk_len;
 
@@ -2061,9 +2055,7 @@ cmd_defborder (int interactive, void *data)
   defaults.window_border_width = tmp;
 
   /* Update all the visible windows. */
-  for (win = rp_mapped_window_sentinel->next; 
-       win != rp_mapped_window_sentinel; 
-       win = win->next)
+  list_for_each_entry (win,&rp_mapped_window,node)
     {
       if (win->frame)
 	maximize (win);
diff --git a/src/data.h b/src/data.h
index c4b236b..d3b2e9e 100644
--- a/src/data.h
+++ b/src/data.h
@@ -22,6 +22,8 @@
 #ifndef _RATPOISON_DATA_H
 #define _RATPOISON_DATA_H
 
+#include "linkedlist.h"
+
 #include <X11/X.h>
 #include <X11/Xlib.h>
 #include <X11/Xutil.h>
@@ -44,7 +46,7 @@ struct rp_window_frame
   /* For determining the last frame. */
   int last_access;
 
-  rp_window_frame *prev, *next;
+  struct list_head node;
 };
 
 struct rp_window
@@ -87,7 +89,7 @@ struct rp_window
      mapped into. */
   rp_window_frame *frame;
 
-  rp_window *next, *prev;  
+  struct list_head node;
 };
 
 struct screen_info
@@ -105,7 +107,7 @@ struct screen_info
 
   /* A list of frames that may or may not contain windows. There should
      always be one in the list. */
-  rp_window_frame *rp_window_frame_sentinel;
+  struct list_head rp_window_frames;
 
   /* Pointer to the currently focused frame. One for each screen so
      when you switch screens the focus doesn't get frobbed. */
@@ -194,11 +196,11 @@ extern struct rp_key prefix_key;
 
 /* A list of mapped windows. These windows show up in the window
    list and have a number assigned to them. */
-extern rp_window *rp_mapped_window_sentinel;
+extern struct list_head rp_mapped_window;
 
 /* A list of unmapped windows. These windows do not have a number
    assigned to them and are not visible/active. */
-extern rp_window *rp_unmapped_window_sentinel;
+extern struct list_head rp_unmapped_window;
 
 extern int rp_current_screen;
 extern screen_info *screens;
diff --git a/src/events.c b/src/events.c
index 54270c3..3699a80 100644
--- a/src/events.c
+++ b/src/events.c
@@ -107,7 +107,7 @@ unmap_notify (XEvent *ev)
     return;
 
   /* FIXME: Should we only look in the mapped window list? */
-  win = find_window_in_list (ev->xunmap.window, rp_mapped_window_sentinel);
+  win = find_window_in_list (ev->xunmap.window, &rp_mapped_window);
 
   if (win == NULL)
     return;
@@ -653,9 +653,7 @@ mapping_notify (XMappingEvent *ev)
   rp_window *cur;
 
   /* Remove the grab on the current prefix key */
-  for (cur = rp_mapped_window_sentinel->next; 
-       cur != rp_mapped_window_sentinel; 
-       cur = cur->next)
+  list_for_each_entry (cur,&rp_mapped_window,node)
     {
       ungrab_prefix_key (cur->w);
     }
@@ -671,9 +669,7 @@ mapping_notify (XMappingEvent *ev)
     }
 
   /* Add the grab on the current prefix key */
-  for (cur = rp_mapped_window_sentinel->next; 
-       cur != rp_mapped_window_sentinel; 
-       cur = cur->next)
+  list_for_each_entry (cur, &rp_mapped_window,node)
     {
       grab_prefix_key (cur->w);
     }
diff --git a/src/linkedlist.h b/src/linkedlist.h
new file mode 100644
index 0000000..4f07927
--- /dev/null
+++ b/src/linkedlist.h
@@ -0,0 +1,295 @@
+/*
+ * Burrowed from the Linux kernel.
+ */
+
+#ifndef _RATPOISON_LINKLIST_H
+#define _RATPOISON_LINKLIST_H
+
+static inline void prefetch(const void *x) {;}
+
+/*
+ * Simple doubly linked list implementation.
+ *
+ * Some of the internal functions ("__xxx") are useful when
+ * manipulating whole lists rather than single entries, as
+ * sometimes we already know the next/prev entries and we can
+ * generate better code by using them directly rather than
+ * using the generic single-entry routines.
+ */
+
+struct list_head {
+	struct list_head *next, *prev;
+};
+
+#define LIST_HEAD_INIT(name) { &(name), &(name) }
+
+#define LIST_HEAD(name) \
+	struct list_head name = LIST_HEAD_INIT(name)
+
+#define INIT_LIST_HEAD(ptr) do { \
+	(ptr)->next = (ptr); (ptr)->prev = (ptr); \
+} while (0)
+
+/*
+ * Insert a new entry between two known consecutive entries. 
+ *
+ * This is only for internal list manipulation where we know
+ * the prev/next entries already!
+ */
+static inline void __list_add(struct list_head *new,
+			      struct list_head *prev,
+			      struct list_head *next)
+{
+	next->prev = new;
+	new->next = next;
+	new->prev = prev;
+	prev->next = new;
+}
+
+/**
+ * list_add - add a new entry
+ * @new: new entry to be added
+ * @head: list head to add it after
+ *
+ * Insert a new entry after the specified head.
+ * This is good for implementing stacks.
+ */
+static inline void list_add(struct list_head *new, struct list_head *head)
+{
+	__list_add(new, head, head->next);
+}
+
+/**
+ * list_add_tail - add a new entry
+ * @new: new entry to be added
+ * @head: list head to add it before
+ *
+ * Insert a new entry before the specified head.
+ * This is useful for implementing queues.
+ */
+static inline void list_add_tail(struct list_head *new, struct list_head *head)
+{
+	__list_add(new, head->prev, head);
+}
+
+/*
+ * Delete a list entry by making the prev/next entries
+ * point to each other.
+ *
+ * This is only for internal list manipulation where we know
+ * the prev/next entries already!
+ */
+static inline void __list_del(struct list_head * prev, struct list_head * next)
+{
+	next->prev = prev;
+	prev->next = next;
+}
+
+/**
+ * list_del - deletes entry from list.
+ * @entry: the element to delete from the list.
+ * Note: list_empty on entry does not return true after this, the entry is
+ * in an undefined state.
+ */
+static inline void list_del(struct list_head *entry)
+{
+	__list_del(entry->prev, entry->next);
+}
+
+/**
+ * list_del_init - deletes entry from list and reinitialize it.
+ * @entry: the element to delete from the list.
+ */
+static inline void list_del_init(struct list_head *entry)
+{
+	__list_del(entry->prev, entry->next);
+	INIT_LIST_HEAD(entry); 
+}
+
+/**
+ * list_move - delete from one list and add as another's head
+ * @list: the entry to move
+ * @head: the head that will precede our entry
+ */
+static inline void list_move(struct list_head *list, struct list_head *head)
+{
+        __list_del(list->prev, list->next);
+        list_add(list, head);
+}
+
+/**
+ * list_move_tail - delete from one list and add as another's tail
+ * @list: the entry to move
+ * @head: the head that will follow our entry
+ */
+static inline void list_move_tail(struct list_head *list,
+				  struct list_head *head)
+{
+        __list_del(list->prev, list->next);
+        list_add_tail(list, head);
+}
+
+/**
+ * list_empty - tests whether a list is empty
+ * @head: the list to test.
+ */
+static inline int list_empty(struct list_head *head)
+{
+	return head->next == head;
+}
+
+static inline void __list_splice(struct list_head *list,
+				 struct list_head *head)
+{
+	struct list_head *first = list->next;
+	struct list_head *last = list->prev;
+	struct list_head *at = head->next;
+
+	first->prev = head;
+	head->next = first;
+
+	last->next = at;
+	at->prev = last;
+}
+
+/**
+ * list_splice - join two lists
+ * @list: the new list to add.
+ * @head: the place to add it in the first list.
+ */
+static inline void list_splice(struct list_head *list, struct list_head *head)
+{
+	if (!list_empty(list))
+		__list_splice(list, head);
+}
+
+/**
+ * list_splice_init - join two lists and reinitialise the emptied list.
+ * @list: the new list to add.
+ * @head: the place to add it in the first list.
+ *
+ * The list at @list is reinitialised
+ */
+static inline void list_splice_init(struct list_head *list,
+				    struct list_head *head)
+{
+	if (!list_empty(list)) {
+		__list_splice(list, head);
+		INIT_LIST_HEAD(list);
+	}
+}
+
+/**
+ * container_of - cast a member of a structure out to the containing structure
+ *
+ * @ptr:        the pointer to the member.
+ * @type:       the type of the container struct this is embedded in.
+ * @member:     the name of the member within the struct.
+ *
+ */
+#define container_of(ptr, type, member) ({                      \
+        const typeof( ((type *)0)->member ) *__mptr = (ptr);    \
+        (type *)( (char *)__mptr - offsetof(type,member) );})
+
+/**
+ * list_entry - get the struct for this entry
+ * @ptr:	the &struct list_head pointer.
+ * @type:	the type of the struct this is embedded in.
+ * @member:	the name of the list_struct within the struct.
+ */
+#define list_entry(ptr, type, member) \
+	container_of(ptr, type, member)
+
+
+/**
+ * __list_for_each	-	iterate over a list
+ * @pos:	the &struct list_head to use as a loop counter.
+ * @head:	the head for your list.
+ *
+ * This variant differs from list_for_each() in that it's the
+ * simplest possible list iteration code, no prefetching is done.
+ * Use this for code that knows the list to be very short (empty
+ * or 1 entry) most of the time.
+ */
+#define list_for_each(pos, head) \
+	for (pos = (head)->next; pos != (head); pos = pos->next)
+
+/**
+ * list_for_each_prev	-	iterate over a list backwards
+ * @pos:	the &struct list_head to use as a loop counter.
+ * @head:	the head for your list.
+ */
+#define list_for_each_prev(pos, head) \
+	for (pos = (head)->prev, prefetch(pos->prev); pos != (head); \
+        	pos = pos->prev, prefetch(pos->prev))
+        	
+/**
+ * list_for_each_safe	-	iterate over a list safe against removal of list entry
+ * @pos:	the &struct list_head to use as a loop counter.
+ * @n:		another &struct list_head to use as temporary storage
+ * @head:	the head for your list.
+ */
+#define list_for_each_safe(pos, n, head) \
+	for (pos = (head)->next, n = pos->next; pos != (head); \
+		pos = n, n = pos->next)
+
+#define list_for_each_safe_entry(item, pos, n, head, member) \
+	for (pos = (head)->next,  \
+             item = list_entry(pos, typeof(*item), member), \
+             n = pos->next  \
+		     ; \
+	     pos != (head) \
+		     ; \
+	     pos = n,  \
+	     item = list_entry(pos, typeof(*item), member), \
+             n = pos->next) \
+
+/**
+ * list_for_each_entry	-	iterate over list of given type
+ * @pos:	the type * to use as a loop counter.
+ * @head:	the head for your list.
+ * @member:	the name of the list_struct within the struct.
+ */
+#define list_for_each_entry(pos, head, member)				\
+	for (pos = list_entry((head)->next, typeof(*pos), member),	\
+		     prefetch(pos->member.next);			\
+	     &pos->member != (head); 					\
+	     pos = list_entry(pos->member.next, typeof(*pos), member),	\
+		     prefetch(pos->member.next))
+
+#define list_for_each_entry_safe(pos, n, head, member)			\
+	for (pos = list_entry((head)->next, typeof(*pos), member),	\
+		n = list_entry(pos->member.next, typeof(*pos), member);	\
+	     &pos->member != (head);					\
+	     pos = n,							\
+		n = list_entry(pos->member.next, typeof(*pos), member))
+
+#define list_direction_entry(pos, head, member, direction) \
+({ \
+	typeof(pos) ret = NULL;  \
+	struct list_head *a_head = head;  \
+	if (pos->member.direction == a_head) { \
+		if (a_head->direction != &pos->member) \
+			ret = list_entry(a_head->direction,  \
+					 typeof(*pos), member); \
+	} else { \
+		ret = list_entry(pos->member.direction,  \
+				 typeof(*pos), member); \
+	} \
+	ret; \
+})
+
+#define list_next_entry(pos, head, member) \
+        list_direction_entry(pos, head, member, next)
+
+#define list_prev_entry(pos, head, member) \
+        list_direction_entry(pos, head, member, prev)
+
+#define list_for_each_entry_prev(pos, head, member)			\
+	for (pos = list_entry((head)->prev, typeof(*pos), member),	\
+		     prefetch(pos->member.prev);			\
+	     &pos->member != (head); 					\
+	     pos = list_entry(pos->member.prev, typeof(*pos), member),	\
+		     prefetch(pos->member.prev))
+
+#endif
diff --git a/src/list.c b/src/list.c
index a2370d3..ff54d34 100644
--- a/src/list.c
+++ b/src/list.c
@@ -26,8 +26,8 @@
 
 #include "ratpoison.h"
 
-rp_window *rp_unmapped_window_sentinel;
-rp_window *rp_mapped_window_sentinel;
+LIST_HEAD(rp_unmapped_window);
+LIST_HEAD(rp_mapped_window);
 
 /* Get the mouse position relative to the root of the specified window */
 static void
@@ -116,7 +116,6 @@ add_to_window_list (screen_info *s, Window w)
   new_window->w = w;
   new_window->scr = s;
   new_window->last_access = 0;
-  new_window->prev = NULL;
   new_window->state = WithdrawnState;
   new_window->number = -1;	
   new_window->named = 0;
@@ -139,18 +138,18 @@ add_to_window_list (screen_info *s, Window w)
   new_window->res_class = NULL;
 
   /* Add the window to the end of the unmapped list. */
-  append_to_list (new_window, rp_unmapped_window_sentinel);
+  list_add_tail (&new_window->node, &rp_unmapped_window);
 
   return new_window;
 }
 
 /* Check to see if the window is in the list of windows. */
 rp_window *
-find_window_in_list (Window w, rp_window *sentinel)
+find_window_in_list (Window w, struct list_head *list)
 {
   rp_window *cur;
 
-  for (cur = sentinel->next; cur != sentinel; cur = cur->next)
+  list_for_each_entry (cur, list, node)
     {
       if (cur->w == w) return cur;
     }
@@ -164,11 +163,11 @@ find_window (Window w)
 {
   rp_window *win = NULL;
 
-  win = find_window_in_list (w, rp_mapped_window_sentinel);
+  win = find_window_in_list (w, &rp_mapped_window);
 
   if (!win) 
     {
-      win = find_window_in_list (w, rp_unmapped_window_sentinel);
+      win = find_window_in_list (w, &rp_unmapped_window);
     }
 
   return win;
@@ -180,27 +179,12 @@ set_current_window (rp_window *win)
   set_frames_window (current_screen()->rp_current_frame, win);
 }
 
-void
-init_window_list ()
-{
-  rp_mapped_window_sentinel = xmalloc (sizeof (rp_window));
-  rp_unmapped_window_sentinel = xmalloc (sizeof (rp_window));
-
-  rp_mapped_window_sentinel->next = rp_mapped_window_sentinel;
-  rp_mapped_window_sentinel->prev = rp_mapped_window_sentinel;
-
-  rp_unmapped_window_sentinel->next = rp_unmapped_window_sentinel;
-  rp_unmapped_window_sentinel->prev = rp_unmapped_window_sentinel;
-}
-
 rp_window *
 find_window_number (int n)
 {
   rp_window *cur;
 
-  for (cur = rp_mapped_window_sentinel->next; 
-       cur != rp_mapped_window_sentinel; 
-       cur = cur->next)
+  list_for_each_entry (cur,&rp_mapped_window,node)
     {
 /*       if (cur->state == STATE_UNMAPPED) continue; */
 
@@ -228,9 +212,7 @@ find_window_name (char *name)
 {
   rp_window *w;
 
-  for (w = rp_mapped_window_sentinel->next; 
-       w != rp_mapped_window_sentinel; 
-       w = w->next)
+  list_for_each_entry (w,&rp_mapped_window,node)
     {
 /*       if (w->state == STATE_UNMAPPED)  */
 /* 	continue; */
@@ -252,12 +234,10 @@ find_window_prev (rp_window *w)
 
   if (!w) return NULL;
 
-  for (cur = w->prev; 
-       cur != w;
-       cur = cur->prev)
+  for (cur = list_prev_entry (w, &rp_mapped_window, node); 
+       cur != w; 
+       cur = list_prev_entry (cur, &rp_mapped_window, node))
     {
-      if (cur == rp_mapped_window_sentinel) continue;
-
       if (!find_windows_frame (cur))
 	{
 	  return cur;
@@ -276,12 +256,10 @@ find_window_next (rp_window *w)
 
   if (!w) return NULL;
 
-  for (cur = w->next; 
-       cur != w;
-       cur = cur->next)
+  for (cur = list_next_entry (w, &rp_mapped_window, node); 
+       cur != w; 
+       cur = list_next_entry (cur, &rp_mapped_window, node))
     {
-      if (cur == rp_mapped_window_sentinel) continue;
-
       if (!find_windows_frame (cur))
 	{
 	  return cur;
@@ -298,9 +276,7 @@ find_window_other ()
   rp_window *most_recent = NULL;
   rp_window *cur;
 
-  for (cur = rp_mapped_window_sentinel->next; 
-       cur != rp_mapped_window_sentinel; 
-       cur = cur->next)
+  list_for_each_entry (cur, &rp_mapped_window, node)
     {
       if (cur->last_access >= last_access 
 	  && cur != current_window()
@@ -314,97 +290,23 @@ find_window_other ()
   return most_recent;
 }
 
-/* This somewhat CPU intensive (memcpy) swap function sorta defeats
-   the purpose of a linear linked list. */
-/* static void */
-/* swap_list_elements (rp_window *a, rp_window *b) */
-/* { */
-/*   rp_window tmp; */
-/*   rp_window *tmp_a_next, *tmp_a_prev; */
-/*   rp_window *tmp_b_next, *tmp_b_prev; */
-
-/*   if (a == NULL || b == NULL || a == b) return; */
-
-/*   tmp_a_next = a->next; */
-/*   tmp_a_prev = a->prev; */
-
-/*   tmp_b_next = b->next; */
-/*   tmp_b_prev = b->prev; */
-
-/*   memcpy (&tmp, a, sizeof (rp_window)); */
-/*   memcpy (a, b, sizeof (rp_window)); */
-/*   memcpy (b, &tmp, sizeof (rp_window)); */
-
-/*   a->next = tmp_a_next; */
-/*   a->prev = tmp_a_prev; */
-
-/*   b->next = tmp_b_next; */
-/*   b->prev = tmp_b_prev; */
-/* } */
-
-/* Can you say b-b-b-b-bubble sort? */
-/* void */
-/* sort_window_list_by_number () */
-/* { */
-/*   rp_window *i, *j, *smallest; */
-
-/*   for (i=rp_window_head; i; i=i->next) */
-/*     { */
-/*       if (i->state == STATE_UNMAPPED) continue; */
-
-/*       smallest = i; */
-/*       for (j=i->next; j; j=j->next) */
-/* 	{ */
-/* 	  if (j->state == STATE_UNMAPPED) continue; */
-
-/* 	  if (j->number < smallest->number) */
-/* 	    { */
-/* 	      smallest = j; */
-/* 	    } */
-/* 	} */
-
-/*       swap_list_elements (i, smallest); */
-/*     } */
-/* } */
-
-void
-append_to_list (rp_window *win, rp_window *sentinel)
-{
-  win->prev = sentinel->prev;
-  sentinel->prev->next = win;
-  sentinel->prev = win;
-  win->next = sentinel;
-}
-
 /* Assumes the list is sorted by increasing number. Inserts win into
    to Right place to keep the list sorted. */
 void
-insert_into_list (rp_window *win, rp_window *sentinel)
+insert_into_list (rp_window *win, struct list_head *list)
 {
   rp_window *cur;
 
-  for (cur = sentinel->next; cur != sentinel; cur = cur->next)
+  list_for_each_entry (cur, list, node)
     {
       if (cur->number > win->number)
 	{
-	  win->next = cur;
-	  win->prev = cur->prev;
-
-	  cur->prev->next = win;
-	  cur->prev = win;
-
+	  list_add_tail (&win->node, &cur->node);
 	  return;
 	}
     }
 
-  append_to_list (win, sentinel);
-}
-
-void
-remove_from_list (rp_window *win)
-{
-  win->next->prev = win->prev;
-  win->prev->next = win->next;
+  list_add_tail(&win->node, list);
 }
 
 static void
@@ -734,9 +636,7 @@ get_window_list (char *fmt, char *delim, struct sbuf *buffer,
   sbuf_clear (buffer);
   other_window = find_window_other ();
 
-  for (w = rp_mapped_window_sentinel->next; 
-       w != rp_mapped_window_sentinel; 
-       w = w->next)
+  list_for_each_entry (w,&rp_mapped_window,node)
     {
       PRINT_DEBUG ("%d-%s\n", w->number, window_name (w));
 
@@ -757,7 +657,7 @@ get_window_list (char *fmt, char *delim, struct sbuf *buffer,
 
       /* Only put the delimiter between the windows, and not after the the last
          window. */
-      if (delim && w->next != rp_mapped_window_sentinel)
+      if (delim && w->node.next != &rp_mapped_window)
 	sbuf_concat (buffer, delim);
 
       if (w == current_window())
diff --git a/src/list.h b/src/list.h
index 44515c8..bc3314f 100644
--- a/src/list.h
+++ b/src/list.h
@@ -26,11 +26,8 @@
 
 void free_window (rp_window *w);
 rp_window *add_to_window_list (screen_info *s, Window w);
-void init_window_list ();
-/* void next_window (); */
-/* void prev_window (); */
 void last_window ();
-rp_window *find_window_in_list (Window w, rp_window *sentinel);
+rp_window *find_window_in_list (Window w, struct list_head *list);
 rp_window *find_window (Window w);
 void maximize_current_window ();
 void give_window_focus (rp_window *win, rp_window *last_win);
@@ -58,9 +55,7 @@ rp_window *find_window_next_with_frame (rp_window *w);
 rp_window *find_window_number (int n);
 void sort_window_list_by_number ();
 
-void append_to_list (rp_window *win, rp_window *sentinel);
-void insert_into_list (rp_window *win, rp_window *sentinel);
-void remove_from_list (rp_window *win);
+void insert_into_list (rp_window *win, struct list_head *list);
 
 void print_window_information (rp_window *win);
 void get_window_list (char *fmt, char *delim, struct sbuf *buffer, 
diff --git a/src/main.c b/src/main.c
index 3cf7039..129f1a9 100644
--- a/src/main.c
+++ b/src/main.c
@@ -584,7 +584,6 @@ main (int argc, char *argv[])
       init_screen (&screens[i], i);
     }
 
-  init_window_list ();
   init_frame_lists ();
   update_modifier_map ();
   initialize_default_keybindings ();
diff --git a/src/manage.c b/src/manage.c
index 1d129fd..5306a1c 100644
--- a/src/manage.c
+++ b/src/manage.c
@@ -275,8 +275,7 @@ void
 unmanage (rp_window *w)
 {
   return_window_number (w->number);
-  remove_from_list (w);
-
+  list_del (&w->node);
   free_window (w);
 
 #ifdef AUTO_CLOSE
@@ -640,8 +639,8 @@ map_window (rp_window *win)
   grab_prefix_key (win->w);
 
   /* Put win in the mapped window list */
-  remove_from_list (win);
-  insert_into_list (win, rp_mapped_window_sentinel);
+  list_del (&win->node);
+  insert_into_list (win, &rp_mapped_window); 
 
   /* The window has never been accessed since it was brought back from
      the Withdrawn state. */
@@ -723,8 +722,7 @@ withdraw_window (rp_window *win)
   return_window_number (win->number);
   win->number = -1;
 
-  remove_from_list (win);
-  append_to_list (win, rp_unmapped_window_sentinel);
+  list_move_tail(&win->node, &rp_unmapped_window);
 
   ignore_badwindow++;
 
@@ -746,9 +744,7 @@ hide_others (rp_window *win)
   frame = find_windows_frame (win);
   if (frame == NULL) return;
 
-  for (cur = rp_mapped_window_sentinel->next; 
-       cur != rp_mapped_window_sentinel; 
-       cur = cur->next)
+  list_for_each_entry (cur, &rp_mapped_window, node)
     {
       if (find_windows_frame (cur) 
 	  || cur->state != NormalState 
diff --git a/src/split.c b/src/split.c
index 53b596b..68f6cfb 100644
--- a/src/split.c
+++ b/src/split.c
@@ -44,9 +44,7 @@ num_frames (screen_info *s)
  int count = 0;
  rp_window_frame *cur;
 
- for (cur = s->rp_window_frame_sentinel->next; 
-      cur != s->rp_window_frame_sentinel; 
-      cur = cur->next)
+ list_for_each_entry (cur, &s->rp_window_frames, node)
    {
      count++;
    }
@@ -74,9 +72,7 @@ frames_screen (rp_window_frame *frame)
   rp_window_frame *cur;
 
   for (i=0; i<num_screens; i++)
-    for (cur = screens[i].rp_window_frame_sentinel->next; 
-	 cur !=screens[i]. rp_window_frame_sentinel; 
-	 cur = cur->next)
+    list_for_each_entry (cur, &screens[i].rp_window_frames, node)
       {
 	if (frame == cur)
 	  return &screens[i];
@@ -92,9 +88,7 @@ maximize_all_windows_in_frame (rp_window_frame *frame)
 {
   rp_window *win;
 
-  for (win = rp_mapped_window_sentinel->next;
-       win != rp_mapped_window_sentinel;
-       win = win->next)
+  list_for_each_entry (win, &rp_mapped_window, node)
     {
       if (win->frame == frame)
 	{
@@ -103,13 +97,6 @@ maximize_all_windows_in_frame (rp_window_frame *frame)
     }
 }
 
-static void
-delete_frame_from_list (rp_window_frame *frame)
-{
-  frame->next->prev = frame->prev;
-  frame->prev->next = frame->next;
-}
-
 /* Make the frame occupy the entire screen */ 
 static void
 maximize_frame (rp_window_frame *frame)
@@ -129,15 +116,10 @@ create_initial_frame (screen_info *screen)
 {
   screen->rp_current_frame = xmalloc (sizeof (rp_window_frame));
 
-  update_last_access (screen->rp_current_frame);
-
-  screen->rp_window_frame_sentinel->next = screen->rp_current_frame;
-  screen->rp_window_frame_sentinel->prev = screen->rp_current_frame;
-  screen->rp_current_frame->next = screen->rp_window_frame_sentinel;
-  screen->rp_current_frame->prev = screen->rp_window_frame_sentinel;
+  list_add_tail (&screen->rp_current_frame->node, &screen->rp_window_frames);
 
+  update_last_access (screen->rp_current_frame);
   maximize_frame (screen->rp_current_frame);
-
   set_frames_window (screen->rp_current_frame, NULL);
 }
 
@@ -153,10 +135,7 @@ init_frame_lists ()
 void
 init_frame_list (screen_info *screen)
 {
-  screen->rp_window_frame_sentinel = xmalloc (sizeof (rp_window_frame));
-
-  screen->rp_window_frame_sentinel->next = screen->rp_window_frame_sentinel;
-  screen->rp_window_frame_sentinel->prev = screen->rp_window_frame_sentinel;
+  INIT_LIST_HEAD (&screen->rp_window_frames);
 
   create_initial_frame(screen);
 }
@@ -167,9 +146,7 @@ find_last_frame (screen_info *s)
   rp_window_frame *cur, *last = NULL;
   int last_access = -1;
 
-  for (cur = s->rp_window_frame_sentinel->next; 
-       cur != s->rp_window_frame_sentinel;
-       cur = cur->next)
+  list_for_each_entry (cur, &s->rp_window_frames, node)
     {
       if (cur != s->rp_current_frame
 	  && cur->last_access > last_access)
@@ -191,9 +168,7 @@ find_windows_frame (rp_window *win)
 
   s = win->scr;
 
-  for (cur = s->rp_window_frame_sentinel->next; 
-       cur != s->rp_window_frame_sentinel;
-       cur = cur->next)
+  list_for_each_entry (cur, &s->rp_window_frames, node)
     {
       if (cur->win == win) return cur;
     }
@@ -204,35 +179,15 @@ find_windows_frame (rp_window *win)
 rp_window_frame *
 find_frame_next (rp_window_frame *frame)
 {
-  rp_window_frame *cur;
-
   if (frame == NULL) return NULL;
-
-  cur = frame;
-  if (cur->next == frames_screen (frame)->rp_window_frame_sentinel)
-    {
-      cur = cur->next;
-      if (cur->next == frame) return NULL;
-    }
-
-  return cur->next;
+  return list_next_entry (frame, &frames_screen (frame)->rp_window_frames, node);
 }
 
 rp_window_frame *
 find_frame_prev (rp_window_frame *frame)
 {
-  rp_window_frame *cur;
-
   if (frame == NULL) return NULL;
-
-  cur = frame;
-  if (cur->prev == frames_screen (frame)->rp_window_frame_sentinel)
-    {
-      cur = cur->prev;
-      if (cur->prev == frame) return NULL;
-    }
-
-  return cur->prev;
+  return list_prev_entry (frame, &frames_screen (frame)->rp_window_frames, node);
 }
 
 rp_window *
@@ -269,9 +224,7 @@ find_window_for_frame (rp_window_frame *frame)
   rp_window *most_recent = NULL;
   rp_window *cur;
 
-  for (cur = rp_mapped_window_sentinel->next; 
-       cur != rp_mapped_window_sentinel; 
-       cur = cur->next)
+  list_for_each_entry (cur, &rp_mapped_window, node)
     {
       if (cur->scr == s
 	  && cur != current_window() 
@@ -305,11 +258,10 @@ split_frame (rp_window_frame *frame, int way, int pixels)
      frame. */
   update_last_access (new_frame);
 
-  /* append the new frame to the list */
-  new_frame->prev = s->rp_window_frame_sentinel->prev;
-  s->rp_window_frame_sentinel->prev->next = new_frame;
-  s->rp_window_frame_sentinel->prev = new_frame;
-  new_frame->next = s->rp_window_frame_sentinel;
+  /* TODO: don't put the new frame at the end of the list, put it
+     after the existing frame. Then cycling frames cycles in the order
+     they were created. */
+  list_add_tail (&new_frame->node, &s->rp_window_frames);
 
   set_frames_window (new_frame, NULL);
 
@@ -379,46 +331,31 @@ h_split_frame (rp_window_frame *frame, int pixels)
 void
 remove_all_splits ()
 {
+  struct list_head *tmp, *iter;
   screen_info *s = &screens[rp_current_screen];
-  rp_window *cur_window;
-  rp_window_frame *frame, *cur_frame;
-  rp_window *win;
+  rp_window_frame *frame = NULL;
+  rp_window *win = NULL;
 
-  cur_window = current_window();
-  cur_frame  = s->rp_current_frame;
-
-  while (s->rp_window_frame_sentinel->next != s->rp_window_frame_sentinel)
+  /* Hide all the windows not in the current frame. */
+  list_for_each_entry (win, &rp_mapped_window, node)
     {
-      frame = s->rp_window_frame_sentinel->next;
-      delete_frame_from_list (frame);
-      if (frame != s->rp_current_frame)
-	{
-	  for (win = rp_mapped_window_sentinel->next;
-	       win != rp_mapped_window_sentinel;
-	       win = win->next)
-	    {
-	      if (win->frame == frame)
-		hide_window (win);
-	    }
-	}
-      free (frame);
+      if (win->frame == frame)
+	hide_window (win);
     }
 
-  create_initial_frame (s);
-  
-  /* Maximize all the windows that were in the current frame. */
-  for (win = rp_mapped_window_sentinel->next;
-       win != rp_mapped_window_sentinel;
-       win = win->next)
+  /* Delete all the frames except the current one. */
+  list_for_each_safe_entry (frame, iter, tmp, &s->rp_window_frames, node)
     {
-      if (win->frame == cur_frame)
+      if (frame != s->rp_current_frame)
 	{
-	  set_frames_window (win->scr->rp_current_frame, win);
-	  maximize (win);
+	  list_del (&frame->node);
+	  free (frame);
 	}
     }
 
-  set_frames_window (s->rp_current_frame, cur_window);
+  /* Maximize the frame and the windows in the frame. */
+  maximize_frame (s->rp_current_frame);
+  maximize_all_windows_in_frame (s->rp_current_frame);
 }
 
 /* Shrink the size of the frame to fit it's current window. */
@@ -450,9 +387,7 @@ resize_frame_vertically (rp_window_frame *frame, int diff)
   orig_y = frame->y;
 
   /* Look for frames below that needs to be resized.  */
-  for (cur = s->rp_window_frame_sentinel->next;
-       cur != s->rp_window_frame_sentinel;
-       cur = cur->next)
+  list_for_each_entry (cur, &s->rp_window_frames, node)
     {
       if (cur->y == (frame->y + frame->height)
       	  && (cur->x + cur->width) > frame->x
@@ -477,9 +412,7 @@ resize_frame_vertically (rp_window_frame *frame, int diff)
   /* Found no frames below, look for some above.  */
   if (!found_adjacent_frames)
     {
-      for (cur = s->rp_window_frame_sentinel->next;
-	   cur != s->rp_window_frame_sentinel;
-	   cur = cur->next)
+      list_for_each_entry (cur, &s->rp_window_frames, node)
 	{
 	    if (cur->y == (frame->y - cur->height)
 		&& (cur->x + cur->width) > frame->x
@@ -513,9 +446,7 @@ resize_frame_vertically (rp_window_frame *frame, int diff)
       frame->height += diff;
 
       /* If we left any gaps, take care of them too.  */
-      for (cur = s->rp_window_frame_sentinel->next;
-	   cur != s->rp_window_frame_sentinel;
-	   cur = cur->next)
+      list_for_each_entry (cur, &s->rp_window_frames, node)
 	{
 	  if (cur->y == orig_y && cur->x >= min_bound
 	      && cur->x + cur->width <= max_bound
@@ -556,9 +487,7 @@ resize_frame_horizontally (rp_window_frame *frame, int diff)
   orig_x = frame->x;
 
   /* Look for frames on the right that needs to be resized.  */
-  for (cur = s->rp_window_frame_sentinel->next;
-       cur != s->rp_window_frame_sentinel;
-       cur = cur->next)
+  list_for_each_entry (cur, &s->rp_window_frames, node)
     {
       if (cur->x == (frame->x + frame->width)
       	  && (cur->y + cur->height) > frame->y
@@ -583,9 +512,7 @@ resize_frame_horizontally (rp_window_frame *frame, int diff)
   /* Found no frames to the right, look for some to the left.  */
   if (!found_adjacent_frames)
     {
-      for (cur = s->rp_window_frame_sentinel->next;
-	   cur != s->rp_window_frame_sentinel;
-	   cur = cur->next)
+      list_for_each_entry (cur, &s->rp_window_frames, node)
 	{
 	  if (cur->x == (frame->x - cur->width)
 	      && (cur->y + cur->height) > frame->y
@@ -619,9 +546,7 @@ resize_frame_horizontally (rp_window_frame *frame, int diff)
       frame->width += diff;
 
       /* If we left any gaps, take care of them too.  */
-      for (cur = s->rp_window_frame_sentinel->next;
-	   cur != s->rp_window_frame_sentinel;
-	   cur = cur->next)
+      list_for_each_entry (cur, &s->rp_window_frames, node)
 	{
 	  if (cur->x == orig_x && cur->y >= min_bound
 	      && cur->y + cur->height <= max_bound
@@ -677,9 +602,7 @@ total_frame_area (screen_info *s)
   int area = 0;
   rp_window_frame *cur;
 
-  for (cur = s->rp_window_frame_sentinel->next; 
-       cur != s->rp_window_frame_sentinel; 
-       cur = cur->next)
+  list_for_each_entry (cur, &s->rp_window_frames, node)
     {
       area += cur->width * cur->height;
     }
@@ -710,9 +633,7 @@ frame_overlaps (rp_window_frame *frame)
 
   s = frames_screen (frame);
 
-  for (cur = s->rp_window_frame_sentinel->next; 
-       cur != s->rp_window_frame_sentinel; 
-       cur = cur->next)
+  list_for_each_entry (cur, &s->rp_window_frames, node)
     {
       if (cur != frame && frames_overlap (cur, frame))
 	{
@@ -736,13 +657,11 @@ remove_frame (rp_window_frame *frame)
   area = total_frame_area(s);
   PRINT_DEBUG ("Total Area: %d\n", area);
 
-  delete_frame_from_list (frame);
+  list_del (&frame->node);
   hide_window (frame->win);
   hide_others (frame->win);
 
-  for (cur = s->rp_window_frame_sentinel->next; 
-       cur != s->rp_window_frame_sentinel; 
-       cur = cur->next)
+  list_for_each_entry (cur, &s->rp_window_frames, node)
     {
       rp_window_frame tmp_frame;
       int fits = 0;
@@ -926,9 +845,7 @@ find_frame_up (rp_window_frame *frame)
   screen_info *s = frames_screen (frame);
   rp_window_frame *cur;
 
-  for (cur = s->rp_window_frame_sentinel->next; 
-       cur != s->rp_window_frame_sentinel; 
-       cur = cur->next)
+  list_for_each_entry (cur, &s->rp_window_frames, node)
     {
       if (frame->y == cur->y + cur->height)
 	{
@@ -946,9 +863,7 @@ find_frame_down (rp_window_frame *frame)
   screen_info *s = frames_screen (frame);
   rp_window_frame *cur;
 
-  for (cur = s->rp_window_frame_sentinel->next; 
-       cur != s->rp_window_frame_sentinel; 
-       cur = cur->next)
+  list_for_each_entry (cur, &s->rp_window_frames, node)
     {
       if (frame->y + frame->height == cur->y)
 	{
@@ -966,9 +881,7 @@ find_frame_left (rp_window_frame *frame)
   screen_info *s = frames_screen (frame);
   rp_window_frame *cur;
 
-  for (cur = s->rp_window_frame_sentinel->next; 
-       cur != s->rp_window_frame_sentinel; 
-       cur = cur->next)
+  list_for_each_entry (cur, &s->rp_window_frames, node)
     {
       if (frame->x == cur->x + cur->width)
 	{
@@ -986,9 +899,7 @@ find_frame_right (rp_window_frame *frame)
   screen_info *s = frames_screen (frame);
   rp_window_frame *cur;
 
-  for (cur = s->rp_window_frame_sentinel->next; 
-       cur != s->rp_window_frame_sentinel; 
-       cur = cur->next)
+  list_for_each_entry (cur, &s->rp_window_frames, node)
     {
       if (frame->x + frame->width == cur->x)
 	{
-- 
cgit v1.2.3