git » libfilo » commit 2a08516

Make waiters list FIFO by making it semi-circular.

author Alberto Bertogli
2005-04-23 20:59:29 UTC
committer Alberto Bertogli
2005-04-23 20:59:29 UTC
parent 1f067800bb557e5694d219f790f97a7107b0c9c0
Make waiters list FIFO by making it semi-circular.
In order to make waiting more fail, make the waiter queue a FIFO, and handle
it as a semi-circular list, adding at the end.
libfilo.c +19 -9 
diff --git a/libfilo.c b/libfilo.c
index ad67b57..361f7e0 100644
--- a/libfilo.c
+++ b/libfilo.c
@@ -336,15 +336,16 @@ static void wait_on(filock_t *fl, off_t start, off_t end, int mode)
 
 	sem_init(&(wr.sem), 0, 0);
 
-	/* add to the list */
+	/* add to the semi-circular list */
 	if (fl->waiters == NULL) {
-		wr.next = wr.prev = NULL;
+		wr.next = NULL;
+		wr.prev = ≀
 		fl->waiters = ≀
 	} else {
-		wr.prev = NULL;
+		wr.next = NULL;
+		wr.prev = fl->waiters->prev;
+		fl->waiters->prev->next = ≀
 		fl->waiters->prev = ≀
-		wr.next = fl->waiters;
-		fl->waiters = ≀
 	}
 
 	fl_unlock(fl);
@@ -366,13 +367,22 @@ static void wake_up(filock_t *fl, off_t start, off_t end)
 			do_lock_tid(fl, wr->start, wr->end, wr->mode,
 					wr->owner);
 
-			/* remove from the list */
-			if (fl->waiters == wr)
+			/* remove from the semi-circular list */
+			if (fl->waiters == wr) {
+				/* head */
+				if (wr->next != NULL)
+					wr->next->prev = fl->waiters->prev;
 				fl->waiters = wr->next;
-			if (wr->prev != NULL)
+			} else if (fl->waiters->prev == wr) {
+				/* tail */
+				wr->prev->next = NULL;
+				fl->waiters->prev = wr->prev;
+			} else {
+				/* middle */
 				wr->prev->next = wr->next;
-			if (wr->next != NULL)
 				wr->next->prev = wr->prev;
+			}
+
 			/* it lives on wait_on()'s stack, there's no need to
 			 * free it */