From 42f4b6168254fa5ef886d95d96f4f0a94dc54cfa Mon Sep 17 00:00:00 2001
From: Petr Baudis <pasky@ucw.cz>
Date: Thu, 18 Sep 2008 05:29:29 +0200
Subject: [PATCH] board_group_rmlib(): Check major logic error - trigger
 refills appropriately

With the original code, refills would actually never trigger. Unfortunately,
this undoes quite a bit of the optimization gains for now.
---
 board.c | 78 ++++++++++++++++++++++++++++++++++-------------------------------
 board.h |  3 +++
 2 files changed, 44 insertions(+), 37 deletions(-)

diff --git a/board.c b/board.c
index 700b79f..d81a780 100644
--- a/board.c
+++ b/board.c
@@ -367,6 +367,37 @@ board_group_addlib(struct board *board, group_t group, coord_t coord, bool fresh
 }
 
 static void
+board_group_find_extra_libs(struct board *board, group_t group, struct group *gi, coord_t avoid)
+{
+	/* Add extra liberty from the board to our liberty list. */
+	bool watermark[board_size2(board)];
+	memset(watermark, 0, sizeof(watermark));
+
+	foreach_in_group(board, group) {
+		coord_t coord2 = c;
+		foreach_neighbor(board, coord2, {
+			if (likely(watermark[coord_raw(c)]))
+				continue;
+			watermark[coord_raw(c)] = true;
+			if (c != avoid && board_at(board, c) == S_NONE) {
+				bool next = false;
+				for (int i = 0; i < GROUP_KEEP_LIBS - 1; i++) {
+					if (gi->lib[i] == c) {
+						next = true;
+						break;
+					}
+				}
+				if (!next) {
+					gi->lib[gi->libs++] = c;
+					if (gi->libs >= GROUP_KEEP_LIBS)
+						return;
+				}
+			}
+		} );
+	} foreach_in_group_end;
+}
+
+static void
 board_group_rmlib(struct board *board, group_t group, coord_t coord)
 {
 	if (DEBUGL(7)) {
@@ -389,51 +420,24 @@ board_group_rmlib(struct board *board, group_t group, coord_t coord)
 		gi->lib[gi->libs] = 0;
 
 		check_libs_consistency(board, group);
-		if (gi->libs < GROUP_KEEP_LIBS - 1) {
-			if (gi->libs == 1)
-				board_capturable_add(board, group);
-			else if (gi->libs == 0)
-				board_capturable_rm(board, group);
-			return;
-		}
+
 		/* Postpone refilling lib[] until we need to. */
-		if (i > GROUP_REFILL_LIBS)
+		assert(GROUP_REFILL_LIBS > 1);
+		if (gi->libs > GROUP_REFILL_LIBS)
 			return;
-		goto find_extra_lib;
+		board_group_find_extra_libs(board, group, gi, coord);
+
+		if (gi->libs == 1)
+			board_capturable_add(board, group);
+		else if (gi->libs == 0)
+			board_capturable_rm(board, group);
+		return;
 	}
 
 	/* This is ok even if gi->libs < GROUP_KEEP_LIBS since we
 	 * can call this multiple times per coord. */
 	check_libs_consistency(board, group);
 	return;
-
-	/* Add extra liberty from the board to our liberty list. */
-find_extra_lib:;
-	bool watermark[board_size2(board)];
-	memset(watermark, 0, sizeof(watermark));
-
-	foreach_in_group(board, group) {
-		coord_t coord2 = c;
-		foreach_neighbor(board, coord2, {
-			if (likely(watermark[coord_raw(c)]))
-				continue;
-			watermark[coord_raw(c)] = true;
-			if (c != coord && board_at(board, c) == S_NONE) {
-				bool next = false;
-				for (int i = 0; i < GROUP_KEEP_LIBS - 1; i++) {
-					if (gi->lib[i] == c) {
-						next = true;
-						break;
-					}
-				}
-				if (!next) {
-					gi->lib[gi->libs++] = c;
-					if (gi->libs >= GROUP_KEEP_LIBS)
-						return;
-				}
-			}
-		} );
-	} foreach_in_group_end;
 }
 
 
diff --git a/board.h b/board.h
index a38484e..c1582d4 100644
--- a/board.h
+++ b/board.h
@@ -35,6 +35,9 @@ struct group {
 #define GROUP_KEEP_LIBS 4 // +1 can make noticeable speed difference
 #define GROUP_REFILL_LIBS 2 // refill lib[] when we go under this; this must be at least 2!
 	coord_t lib[GROUP_KEEP_LIBS];
+	/* libs is only LOWER BOUND for the number of real liberties!!!
+	 * It denotes only number of items in lib[], thus you can rely
+	 * on it to store real liberties only up to <= GROUP_REFILL_LIBS. */
 	int libs;
 };
 
-- 
2.11.4.GIT