menu_items_swap bug [PATCH]

I was attempting to implement a queue feature this afternoon when I came across a bug in menu.c. The interface menu is represented by a doubly-linked list, and swapping two items is pretty tricky. In current usage, the two items are almost always adjacent, and the swap works fine in this case. In case the two items are not adjacent, though, the current code swaps the prev and next pointers in such a way that some data gets clobbered.

In fixing this bug, I introduced a generic swap function in common.h (see below), and I cleaned up the menu_items_swap function a little (to use the new swap function where appropriate).

I've tested the function as thoroughly as I can, and I've tried to stick to the style of the files I changed. Hope this makes it easy for you to apply the patch.

Index: menu.c
===================================================================
--- menu.c	(revision 1986)
+++ menu.c	(working copy)
@@ -776,8 +776,6 @@
 static void menu_items_swap (struct menu *menu, struct menu_item *mi1,
 		struct menu_item *mi2)
 {
-	int t;
-	
 	assert (menu != NULL);
 	assert (mi1 != NULL);
 	assert (mi2 != NULL);
@@ -785,43 +783,28 @@
 
 	/* if they are next to each other, change the pointers so that mi2
 	 * is the second one */
-	if (mi2->next == mi1) {
-		struct menu_item *i = mi1;
+	if (mi2->next == mi1)
+		swap(&mi1, &mi2, sizeof(mi1));
 
-		mi1 = mi2;
-		mi2 = i;
-	}
+	// safe even if mi1->next == mi2
+	if (mi2->next) mi2->next->prev = mi1;
+	if (mi1->prev) mi1->prev->next = mi2;
 
 	if (mi1->next == mi2) {
-		if (mi2->next)
-			mi2->next->prev = mi1;
-		if (mi1->prev)
-			mi1->prev->next = mi2;
-		
 		mi1->next = mi2->next;
 		mi2->prev = mi1->prev;
 		mi1->prev = mi2;
 		mi2->next = mi1;
+	} else {
+		// not safe if mi1->next == mi2
+		if (mi2->prev) mi2->prev->next = mi1;
+		if (mi1->next) mi1->next->prev = mi2;
+
+		swap(&mi1->prev, &mi2->prev, sizeof(mi1->prev));
+		swap(&mi1->next, &mi2->next, sizeof(mi1->next));
 	}
-	else {
-		if (mi2->next)
-			mi2->next->prev = mi1;
-		if (mi2->prev)
-			mi2->prev->next = mi1;
-		mi2->next = mi1->next;
-		mi2->prev = mi1->prev;
-		
-		if (mi1->next)
-			mi1->next->prev = mi2;
-		if (mi1->prev)
-			mi1->prev->next = mi2;
-		mi1->next = mi2->next;
-		mi1->prev = mi2->prev;
-	}
 
-	t = mi1->num;
-	mi1->num = mi2->num;
-	mi2->num = t;
+	swap(&mi1->num, &mi2->num, sizeof(mi1->num));
 
 	if (menu->top == mi1)
 		menu->top = mi2;
Index: common.c
===================================================================
--- common.c	(revision 1986)
+++ common.c	(working copy)
@@ -124,4 +124,16 @@
 	return fname;
 }
 
+static void swap_bytes(char *b1, char *b2) {
+	if (*b1 != *b2) {
+		*b1 ^= *b2;
+		*b2 ^= *b1;
+		*b1 ^= *b2;
+	}
+}
 
+void swap(void *a, void *b, size_t n) {
+	int i = 0;
+	for ( ; i 

In case this didn't come through with the original post:

Ben Newman
auratus@gmail.com
http://seraph.im

The patch looks OK, but can you give an example case where the current code fails?
--
Damian Pietras - MOC developer