switch to returning an array of actions instead of a linked list

- attempts to keep the same move ordering as the list method
- saves ~170msec on a depth 7 search for a given board configuration
- there is room to improve the pre-allocation size estimates, these
  bounds are not obviously tight and it may or may not be faster to
  have tighter bounds or even some form of estimation

1 files changed, 75 insertions, 90 deletions

diff --git a/include/actions.c b/include/actions.c
index 6303822..547024a 100644
--- a/include/actions.c
+++ b/include/actions.c
@@ -21,6 +21,7 @@
 #include <stdio.h>
 
 static uint8_t al_board_size;
+static uint32_t upper_bound_moves;
 
 // ===================================================================
 // Helper method declarations
@@ -30,14 +31,6 @@ static uint8_t al_board_size;
 
 #define CLR_STONE NUM_MASK
 
-static inline void list_append(action_list_t *list, const enum A_TYPE type,
-                               const int8_t loc, const uint8_t data0,
-                               const uint8_t data1);
-
-static inline void list_prepend(action_list_t *list, const enum A_TYPE type,
-                                const int8_t loc, const uint8_t data0,
-                                const uint8_t data1);
-
 static inline void inline_next_ply(tak_state_p state);
 
 static inline void inline_prev_ply(tak_state_p state);
@@ -51,56 +44,62 @@ static inline uint8_t check_no_overflow(tak_state_p state, const uint8_t loc,
 // Exported method implementations
 // ===================================================================
 
-int action_move_to_front(const action_t action, action_list_t *list) {
-  action_node_t *n = list->head;
-
-  // TODO: what if it's not in the list?
-
-  while (n) {
-    if (n->action == action) {
-      const action_t t = list->head->action;
-      list->head->action = action;
-      n->action = t;
-      return EXIT_SUCCESS;
-    }
-    n = n->next;
-  }
-
-  return EXIT_FAILURE;
-}
-
-void action_list_free(action_list_t *list) {
-  if (list) {
-    action_node_t *n = list->head, *nn;
-    while (n) {
-      nn = n->next;
-      free(n);
-      n = nn;
-    }
-    free(list);
-  }
-}
+inline void actions_free(action_t *actions) { free(actions); }
 
 // Keep track of move offsets
 int8_t move_deltas[4];
 
-void action_list_init(const uint8_t board_size) {
+void actions_init(const uint8_t board_size) {
   al_board_size = board_size;
   move_deltas[0] = +board_size;
   move_deltas[1] = -board_size;
   move_deltas[2] = -1;
   move_deltas[3] = +1;
+
+  const uint32_t five_cumulative_partitions = 7 + 5 + 3 + 2 + 1; // 18
+  const uint32_t six_cumulative_partitions =
+      11 + five_cumulative_partitions; // 29
+  if (board_size == 5) {
+    // 26 = 3*3 + 4*3 + 1
+
+    // which means central squares (4 dirs), sides (3 dirs), one corner (2 dirs)
+    upper_bound_moves = 4 * 3 * 3 + 3 * 4 * 3 + 2 * 1;
+    upper_bound_moves *= five_cumulative_partitions;
+  } else {
+    // 31 = 4*4 + 3*4 + 3
+
+    // which means central squares (4 dirs), three sides (3 dirs) and an extra
+    // three squares on the last side (1 dir)
+    upper_bound_moves = 4 * 4 * 4 + 3 * 3 * 4 + 3 * 3;
+    upper_bound_moves *= six_cumulative_partitions;
+  }
+  // In summary, using typedef uint32_t action_t
+  //  74 * 18 = 1332 for 5x5, ~5.2 Kb
+  // 109 * 29 = 3161 for 6x6, ~12.3 Kb
 }
 
-// We bias place over move by prepending place actions and appending
-// move actions to the generated list
-action_list_t *action_list_generate(tak_state_p state) {
-  action_list_t *list = malloc(sizeof(struct action_list_s));
+inline char action_in_list(action_t action, action_t *actions, const uint32_t num_actions) {
+  uint32_t idx;
+  for (idx = 0; idx < num_actions && actions[idx] != action; idx++);
+  return idx < num_actions;
+}
 
-  // TODO: trap errno
-  list->length = 0;
-  list->head = NULL;
+void action_move_to_front(action_t action, action_t *actions,
+                          const uint32_t num_actions) {
+  (void) num_actions; // yolo
+  uint32_t idx;
+  action_t prev = action, temp;
+  for (idx = 0; actions[idx] != action; idx++) {
+    temp = actions[idx];
+    actions[idx] = prev;
+    prev = temp;
+  }
+  actions[idx] = prev;
+}
 
+// We bias place over move by prepending place actions and appending
+// move actions to the generated list
+action_t *actions_generate(tak_state_p state, uint32_t *num_actions) {
   /*
    * The check for whether it's a black piece to be played is actually
    *     black = (ply < 2) ? (ply==1) : (ply & 1),
@@ -114,6 +113,22 @@ action_list_t *action_list_generate(tak_state_p state) {
                 cap = ((state->ply >= 2) && (material & 0x80)),
                 standing = ((state->ply >= 2) && flat);
 
+  // Count placement options
+  uint32_t placements = 0;
+  const uint32_t how_many = (flat ? 1 : 0) + (cap ? 1 : 0) + (standing ? 1 : 0);
+  for (int row = 0; row < state->board_size; row++) {
+    for (int col = 0; col < state->board_size; col++) {
+      const int l = THE_COORDS(al_board_size, col, row);
+      if (COUNT_AT(state, l) == 0)
+        placements += how_many;
+    }
+  }
+
+  // TODO: trap errno
+  action_t *actions =
+      malloc(sizeof(action_t) * (placements + upper_bound_moves));
+  uint32_t total = 0, move_idx = placements, place_idx = placements;
+
   // Step across the board
   for (int row = 0; row < state->board_size; row++) {
     for (int col = 0; col < state->board_size; col++) {
@@ -192,9 +207,10 @@ action_list_t *action_list_generate(tak_state_p state) {
                       can_and_must_crush || crushes[dir] != steps;
                   if (no_overflow && crush_check) {
                     // Store the move
-                    list_append(list, A_MOVE, loc,
-                                (can_and_must_crush << 7) | gaps,
+                    actions[move_idx++] =
+                        A_BUILD(A_MOVE, loc, (can_and_must_crush << 7) | gaps,
                                 (dir << 4) | num);
+                    total++;
                   }
                   /*
                    * With thanks to
@@ -214,16 +230,22 @@ action_list_t *action_list_generate(tak_state_p state) {
       else if (material) {
         // Empty square, generate placements
         if (flat) {
-          list_prepend(list, A_PLACE, loc, STONE_FLAT, 0);
-          if (standing)
-            list_prepend(list, A_PLACE, loc, STONE_STANDING, 0);
+          actions[--place_idx] = A_BUILD(A_PLACE, loc, STONE_FLAT, 0);
+          total++;
+          if (standing) {
+            actions[--place_idx] = A_BUILD(A_PLACE, loc, STONE_STANDING, 0);
+            total++;
+          }
+        }
+        if (cap) {
+          actions[--place_idx] = A_BUILD(A_PLACE, loc, STONE_CAPSTONE, 0);
+          total++;
         }
-        if (cap)
-          list_prepend(list, A_PLACE, loc, STONE_CAPSTONE, 0);
       }
     }
   }
-  return list;
+  *num_actions = total;
+  return actions;
 }
 
 void action_take(tak_state_p state, const action_t action) {
@@ -406,43 +428,6 @@ void action_to_ptn(const action_t action, char *out_ptn) {
 // Helper method implementations
 // ===================================================================
 
-static inline void list_append(action_list_t *list, const enum A_TYPE type,
-                               const int8_t loc, const uint8_t data0,
-                               const uint8_t data1) {
-  action_node_t *new = malloc(sizeof(action_node_t));
-  // TODO: trap errno
-
-  new->next = NULL;
-  new->action = A_BUILD(type, loc, data0, data1);
-
-  if (list->length) {
-    list->tail->next = new;
-    list->tail = new;
-  } else {
-    list->head = new;
-    list->tail = new;
-  }
-
-  list->length++;
-}
-
-static inline void list_prepend(action_list_t *list, const enum A_TYPE type,
-                                const int8_t loc, const uint8_t data0,
-                                const uint8_t data1) {
-  action_node_t *new = malloc(sizeof(action_list_t));
-  // TODO: trap errno
-
-  new->next = list->head;
-  list->head = new;
-  new->action = A_BUILD(type, loc, data0, data1);
-
-  if (list->length == 0) {
-    list->tail = new;
-  }
-
-  list->length++;
-}
-
 static inline void inline_next_ply(tak_state_p state) {
   state->ply++;
   if (state->ply == 2) {