Checkpoint while refactoring. Almost certainly will not compile.

1 files changed, 8 insertions, 267 deletions

diff --git a/ks.c b/ks.c
index a93cbe1..f0c71cc 100644
--- a/ks.c
+++ b/ks.c
@@ -40,277 +40,17 @@
 #include "ks.h"
 
 /*
- * Find a block in the index, return true (found) or false (not found).
- * "where" indicates the name's position, or the position of the first free block.
- *
- * NB: This does NOT return a block number, it returns an index into
- * ks->index[].
- */
-
-static int ks_find(const hal_ks_t * const ks,
-                   const hal_uuid_t * const uuid,
-                   const int * const hint,
-                   int *where)
-{
-  if (ks == NULL || ks->index == NULL || ks->names == NULL || uuid == NULL || where == NULL)
-    return 0;
-
-  if (hint != NULL && *hint >= 0 && *hint < ks->used &&
-      hal_uuid_cmp(uuid, &ks->names[ks->index[*hint]]) == 0) {
-    *where = *hint;
-    return 1;
-  }
-
-  int lo = -1;
-  int hi = ks->used;
-
-  for (;;) {
-    int m = (lo + hi) / 2;
-    if (hi == 0 || m == lo) {
-      *where = hi;
-      return 0;
-    }
-    const int cmp = hal_uuid_cmp(uuid, &ks->names[ks->index[m]]);
-    if (cmp < 0)
-      hi = m;
-    else if (cmp > 0)
-      lo = m;
-    else {
-      *where = m;
-      return 1;
-    }
-  }
-}
-
-/*
- * Heapsort the index.  We only need to do this on setup, for other
- * operations we're just inserting or deleting a single entry in an
- * already-ordered array, which is just a search problem.  If we were
- * really crunched for space, we could use an insertion sort here, but
- * heapsort is easy and works well with data already in place.
- */
-
-static inline void ks_heapsift(hal_ks_t *ks, int parent, const int end)
-{
-  if (ks == NULL || ks->index == NULL || ks->names == NULL || parent < 0 || end < parent)
-    return;
-  for (;;) {
-    const int left_child  = parent * 2 + 1;
-    const int right_child = parent * 2 + 2;
-    int biggest = parent;
-    if (left_child  <= end && hal_uuid_cmp(&ks->names[ks->index[biggest]],
-                                           &ks->names[ks->index[left_child]])  < 0)
-      biggest = left_child;
-    if (right_child <= end && hal_uuid_cmp(&ks->names[ks->index[biggest]],
-                                           &ks->names[ks->index[right_child]]) < 0)
-      biggest = right_child;
-    if (biggest == parent)
-      return;
-    const uint16_t tmp = ks->index[biggest];
-    ks->index[biggest] = ks->index[parent];
-    ks->index[parent]  = tmp;
-    parent = biggest;
-  }
-}
-
-static inline void ks_heapsort(hal_ks_t *ks)
-{
-  if (ks == NULL || ks->index == NULL || ks->names == NULL)
-    return;
-  if (ks->used < 2)
-    return;
-  for (int i = (ks->used - 2) / 2; i >= 0; i--)
-    ks_heapsift(ks, i, ks->used - 1);
-  for (int i = ks->used - 1; i > 0; i--) {
-    const uint16_t tmp = ks->index[i];
-    ks->index[i]       = ks->index[0];
-    ks->index[0]       = tmp;
-    ks_heapsift(ks, 0, i - 1);
-  }
-}
-
-/*
- * Perform a consistency check on the index.
+ * Type safe casts.
  */
 
-#define fsck(_ks) \
-  do { hal_error_t _err = hal_ks_index_fsck(_ks); if (_err != HAL_OK) return _err; } while (0)
-
-
-hal_error_t hal_ks_index_fsck(hal_ks_t *ks)
+static inline ks_block_type_t block_get_type(const ks_block_t * const block)
 {
-  if (ks == NULL || ks->index == NULL || ks->names == NULL ||
-      ks->size == 0 || ks->used > ks->size)
-    return HAL_ERROR_BAD_ARGUMENTS;
-
-  for (int i = 1; i < ks->used; i++)
-    if (hal_uuid_cmp(&ks->names[ks->index[i - 1]], &ks->names[ks->index[i]]) >= 0)
-      return HAL_ERROR_KS_INDEX_UUID_MISORDERED;
-
-  return HAL_OK;
+  return block == NULL ? HAL_KS_BLOCK_TYPE_UNKNOWN : (ks_block_type_t) block->header.block_type;
 }
 
-/*
- * Find a single block by name.
- */
-
-hal_error_t hal_ks_index_find(hal_ks_t *ks,
-                              const hal_uuid_t * const name,
-                              unsigned *blockno,
-                              int *hint)
+static inline ks_block_status_t block_get_status(const ks_block_t * const block)
 {
-  if (ks == NULL || ks->index == NULL || ks->names == NULL ||
-      ks->size == 0 || ks->used > ks->size || name == NULL)
-    return HAL_ERROR_BAD_ARGUMENTS;
-
-  int where;
-
-  fsck(ks);
-
-  int ok = ks_find(ks, name, hint, &where);
-
-  if (blockno != NULL)
-    *blockno = ks->index[where];
-
-  if (hint != NULL)
-    *hint = where;
-
-  return ok ? HAL_OK : HAL_ERROR_KEY_NOT_FOUND;
-}
-
-/*
- * Add a single block to the index.
- */
-
-hal_error_t hal_ks_index_add(hal_ks_t *ks,
-                             const hal_uuid_t * const name,
-                             unsigned *blockno,
-                             int *hint)
-{
-  if (ks == NULL || ks->index == NULL || ks->names == NULL ||
-      ks->size == 0 || ks->used > ks->size || name == NULL)
-    return HAL_ERROR_BAD_ARGUMENTS;
-
-  if (ks->used == ks->size)
-    return HAL_ERROR_NO_KEY_INDEX_SLOTS;
-
-  int where;
-
-  fsck(ks);
-
-  if (ks_find(ks, name, hint, &where))
-    return HAL_ERROR_KEY_NAME_IN_USE;
-
-  /*
-   * Grab first block on free list, which makes room to slide the
-   * index up by one slot so we can insert the new block number.
-   */
-
-  const size_t len = (ks->used - where) * sizeof(*ks->index);
-  const uint16_t b = ks->index[ks->used++];
-  memmove(&ks->index[where + 1], &ks->index[where], len);
-  ks->index[where] = b;
-  ks->names[b] = *name;
-
-  if (blockno != NULL)
-    *blockno = b;
-
-  if (hint != NULL)
-    *hint = where;
-
-  fsck(ks);
-
-  return HAL_OK;
-}
-
-/*
- * Delete a single block from the index.
- */
-
-hal_error_t hal_ks_index_delete(hal_ks_t *ks,
-                                const hal_uuid_t * const name,
-                                unsigned *blockno,
-                                int *hint)
-{
-  if (ks == NULL || ks->index == NULL || ks->names == NULL ||
-      ks->size == 0 || ks->used > ks->size || name == NULL)
-    return HAL_ERROR_BAD_ARGUMENTS;
-
-  int where;
-
-  fsck(ks);
-
-  if (ks->used == 0 || !ks_find(ks, name, hint, &where))
-    return HAL_ERROR_KEY_NOT_FOUND;
-
-  /*
-   * Free the block and stuff it at the end of the free list.
-   */
-
-  const size_t len = (ks->size - where - 1) * sizeof(*ks->index);
-  const uint16_t b = ks->index[where];
-  memmove(&ks->index[where], &ks->index[where + 1], len);
-  ks->index[ks->size - 1] = b;
-  ks->used--;
-  memset(&ks->names[b], 0, sizeof(ks->names[b]));
-
-  if (blockno != NULL)
-    *blockno = b;
-
-  if (hint != NULL)
-    *hint = where;
-
-  fsck(ks);
-
-  return HAL_OK;
-}
-
-/*
- * Replace a single block in the index.
- */
-
-hal_error_t hal_ks_index_replace(hal_ks_t *ks,
-                                 const hal_uuid_t * const name,
-                                 unsigned *blockno,
-                                 int *hint)
-{
-  if (ks == NULL || ks->index == NULL || ks->names == NULL ||
-      ks->size == 0 || ks->used > ks->size || name == NULL)
-    return HAL_ERROR_BAD_ARGUMENTS;
-
-  if (ks->used == ks->size)
-    return HAL_ERROR_NO_KEY_INDEX_SLOTS;
-
-  int where;
-
-  fsck(ks);
-
-  if (ks->used == 0 || !ks_find(ks, name, hint, &where))
-    return HAL_ERROR_KEY_NOT_FOUND;
-
-  /*
-   * Grab first block from free list, slide free list down, put old
-   * block at end of free list and replace old block with new block.
-   */
-
-  const size_t len = (ks->size - ks->used - 1) * sizeof(*ks->index);
-  const uint16_t b1 = ks->index[where];
-  const uint16_t b2 = ks->index[ks->used];
-  memmove(&ks->index[ks->used], &ks->index[ks->used + 1], len);
-  ks->index[ks->size - 1] = b1;
-  ks->index[where] = b2;
-  ks->names[b2] = *name;
-  memset(&ks->names[b1], 0, sizeof(ks->names[b1]));
-
-  if (blockno != NULL)
-    *blockno = b2;
-
-  if (hint != NULL)
-    *hint = where;
-
-  fsck(ks);
-
-  return HAL_OK;
+  return block == NULL ? HAL_KS_BLOCK_STATUS_UNKNOWN : (ks_block_status_t) block->header.block_status;
 }
 
 /*
@@ -641,7 +381,8 @@ hal_error_t hal_ks_init_common(hal_ks_t *ks, const hal_ks_driver_t * const drive
    * failure, we should never lose data.
    */
 
-  ks_heapsort(ks);
+  if ((err = hal_ks_index_heapsort(ks)) != HAL_OK)
+    return err;
 
   for (unsigned b_tomb = 0; b_tomb < ks->size; b_tomb++) {
 
@@ -666,7 +407,7 @@ hal_error_t hal_ks_init_common(hal_ks_t *ks, const hal_ks_driver_t * const drive
 
     const int matches_next = where + 1 < ks->used && !hal_uuid_cmp(&name, &ks->names[ks->index[where + 1]]);
     const int matches_prev = where - 1 >= 0       && !hal_uuid_cmp(&name, &ks->names[ks->index[where - 1]]);
-    
+
     if ((matches_prev && matches_next) ||
         (matches_prev && block_status[ks->index[b_tomb - 1]] != BLOCK_STATUS_LIVE) ||
         (matches_next && block_status[ks->index[b_tomb + 1]] != BLOCK_STATUS_LIVE))