From 19e778232ea1c36f178fe5f8a8b365afaf2f54d9 Mon Sep 17 00:00:00 2001
From: Petr Baudis <pasky@ucw.cz>
Date: Fri, 15 Oct 2010 23:36:23 +0200
Subject: [PATCH] pattern3s: Add support for pattern table smaller than the
 hash range

This of course brings non-trivial overhead, but we also need to carry
atari status for each stone in the pattern.
---
 pattern3.c |  7 ++++++-
 pattern3.h | 30 +++++++++++++++++++++++-------
 2 files changed, 29 insertions(+), 8 deletions(-)

diff --git a/pattern3.c b/pattern3.c
index c90a949..19c322a 100644
--- a/pattern3.c
+++ b/pattern3.c
@@ -11,7 +11,12 @@
 static void
 pattern_record(struct pattern3s *p, char *str, hash3_t pat, int fixed_color)
 {
-	p->hash[pat] = fixed_color ? fixed_color : 3;
+	hash3_t hpat = pat;
+	while (p->hash[hpat & pattern3_hash_mask].pattern != pat
+	       && p->hash[hpat & pattern3_hash_mask].value != 0)
+		hpat++;
+	p->hash[hpat & pattern3_hash_mask].pattern = pat;
+	p->hash[hpat & pattern3_hash_mask].value = fixed_color ? fixed_color : 3;
 	//fprintf(stderr, "[%s] %04x %d\n", str, pat, fixed_color);
 }
 
diff --git a/pattern3.h b/pattern3.h
index 9384f5e..cdef9f0 100644
--- a/pattern3.h
+++ b/pattern3.h
@@ -11,15 +11,28 @@
 struct board;
 struct move;
 
-struct pattern3s {
-	/* Hashtable: 2*8 bits (ignore middle point, 2 bits per intersection) */
-	/* Value: 0: no pattern, 1: black pattern,
-	 * 2: white pattern, 3: both patterns */
-	char hash[65536];
-};
+/* hash3_t pattern: 8*2 bits
+ * (ignore middle point, 2 bits (color) per intersection) */
+/* Value bit 0: black pattern; bit 1: white pattern */
 
 /* XXX: See <board.h> for hash3_t typedef. */
 
+struct pattern2p {
+	hash3_t pattern;
+	char value;
+};
+
+struct pattern3s {
+	/* Right now, the hash is of just the right size, but this
+	 * is going to change very soon! */
+	/* In case of a collision, following hash entries are
+	 * used. value==0 indicated an unoccupied hash entry. */
+#define pattern3_hash_bits 16
+#define pattern3_hash_size (1 << pattern3_hash_bits)
+#define pattern3_hash_mask (pattern3_hash_size - 1)
+	struct pattern2p hash[pattern3_hash_size];
+};
+
 /* Source pattern encoding:
  * X: black;  O: white;  .: empty;  #: edge
  * x: !black; o: !white; ?: any
@@ -67,7 +80,10 @@ pattern3_move_here(struct pattern3s *p, struct board *b, struct move *m)
 #else
 	hash3_t pat = pattern3_hash(b, m->coord);
 #endif
-	return (p->hash[pat] & m->color);
+	while (p->hash[pat & pattern3_hash_mask].pattern != pat
+	       && p->hash[pat & pattern3_hash_mask].value != 0)
+		pat++;
+	return (p->hash[pat & pattern3_hash_mask].value & m->color);
 }
 
 static inline hash3_t
-- 
2.11.4.GIT