1 files changed, 106 insertions, 112 deletions

diff --git a/ks_index.c b/ks_index.c
index 806394a..ed22cfb 100644
--- a/ks_index.c
+++ b/ks_index.c
@@ -3,7 +3,7 @@
  * ----------
  * Keystore index API.  This is internal within libhal.
  *
- * Copyright (c) 2016, NORDUnet A/S All rights reserved.
+ * Copyright (c) 2016-2017, NORDUnet A/S All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions are
@@ -32,35 +32,37 @@
  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  */
 
+#include <stddef.h>
 #include <string.h>
-#include <assert.h>
 
 #include "hal.h"
 #include "hal_internal.h"
+#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
- * ksi->index[].
+ * ks->index[].
  */
 
-static int ks_find(const hal_ks_index_t * const ksi,
-		   const hal_uuid_t * const uuid,
+static int ks_find(const hal_ks_t * const ks,
+                   const hal_uuid_t * const uuid,
                    const int * const hint,
-		   int *where)
+                   int *where)
 {
-  assert(ksi != NULL && ksi->index != NULL && ksi->names != NULL && uuid != NULL && where != NULL);
+  if (ks == NULL || ks->index == NULL || ks->names == NULL || uuid == NULL || where == NULL)
+    return 0;
 
-  if (hint != NULL && *hint >= 0 && *hint < ksi->used &&
-      hal_uuid_cmp(uuid, &ksi->names[ksi->index[*hint]]) == 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 = ksi->used;
+  int hi = ks->used;
 
   for (;;) {
     int m = (lo + hi) / 2;
@@ -68,7 +70,7 @@ static int ks_find(const hal_ks_index_t * const ksi,
       *where = hi;
       return 0;
     }
-    const int cmp = hal_uuid_cmp(uuid, &ksi->names[ksi->index[m]]);
+    const int cmp = hal_uuid_cmp(uuid, &ks->names[ks->index[m]]);
     if (cmp < 0)
       hi = m;
     else if (cmp > 0)
@@ -88,82 +90,72 @@ static int ks_find(const hal_ks_index_t * const ksi,
  * heapsort is easy and works well with data already in place.
  */
 
-static inline void ks_heapsift(hal_ks_index_t *ksi, int parent, const int end)
+static inline hal_error_t ks_heapsift(hal_ks_t *ks, int parent, const int end)
 {
-  assert(ksi != NULL && ksi->index != NULL && ksi->names != NULL &&
-	 parent >= 0 && end >= parent);
+  if (ks == NULL || ks->index == NULL || ks->names == NULL || parent < 0 || end < parent)
+    return HAL_ERROR_IMPOSSIBLE;
+
   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(&ksi->names[ksi->index[biggest]],
-                                           &ksi->names[ksi->index[left_child]])  < 0)
+    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(&ksi->names[ksi->index[biggest]],
-                                           &ksi->names[ksi->index[right_child]]) < 0)
+    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  = ksi->index[biggest];
-    ksi->index[biggest] = ksi->index[parent];
-    ksi->index[parent] = tmp;
+      return HAL_OK;
+    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_index_t *ksi)
+hal_ks_error_t hal_ks_index_heapsort(hal_ks_t *ks)
 {
-  assert(ksi != NULL && ksi->index != NULL && ksi->names != NULL);
-  if (ksi->used < 2)
-    return;
-  for (int i = (ksi->used - 2) / 2; i >= 0; i--)
-    ks_heapsift(ksi, i, ksi->used - 1);
-  for (int i = ksi->used - 1; i > 0; i--) {
-    const uint16_t tmp = ksi->index[i];
-    ksi->index[i]      = ksi->index[0];
-    ksi->index[0]      = tmp;
-    ks_heapsift(ksi, 0, i - 1);
-  }
-}
-
-/*
- * Perform a consistency check on the index.
- */
+  if (ks == NULL || ks->index == NULL || ks->names == NULL)
+    return HAL_ERROR_IMPOSSIBLE;
 
-#define fsck(_ksi) \
-  do { hal_error_t _err = hal_ks_index_fsck(_ksi); if (_err != HAL_OK) return _err; } while (0)
+  if (ks->used < 2)
+    return HAL_OK;
 
+  hal_error_t err;
 
-hal_error_t hal_ks_index_fsck(hal_ks_index_t *ksi)
-{
-  if (ksi == NULL || ksi->index == NULL || ksi->names == NULL ||
-      ksi->size == 0 || ksi->used > ksi->size)
-    return HAL_ERROR_BAD_ARGUMENTS;
+  for (int i = (ks->used - 2) / 2; i >= 0; i--)
+    if ((err = ks_heapsift(ks, i, ks->used - 1)) != HAL_OK)
+      return err;
 
-  for (int i = 1; i < ksi->used; i++)
-    if (hal_uuid_cmp(&ksi->names[ksi->index[i - 1]], &ksi->names[ksi->index[i]]) >= 0)
-      return HAL_ERROR_KSI_INDEX_UUID_MISORDERED;
+  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;
+    if ((err = ks_heapsift(ks, 0, i - 1)) != HAL_OK)
+      return err;
+  }
 
   return HAL_OK;
 }
 
 /*
- * Set up the index. Only setup task we have at the moment is sorting the index.
+ * Perform a consistency check on the index.
  */
 
-hal_error_t hal_ks_index_setup(hal_ks_index_t *ksi)
+#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)
 {
-  if (ksi == NULL || ksi->index == NULL || ksi->names == NULL ||
-      ksi->size == 0 || ksi->used > ksi->size)
+  if (ks == NULL || ks->index == NULL || ks->names == NULL ||
+      ks->size == 0 || ks->used > ks->size)
     return HAL_ERROR_BAD_ARGUMENTS;
 
-  ks_heapsort(ksi);
-
-  /*
-   * One might think we should fsck here, but errors in the index
-   * at this point probably relate to errors in the supplied data,
-   * which only the driver knows how to clean up.
-   */
+  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;
 }
@@ -172,23 +164,23 @@ hal_error_t hal_ks_index_setup(hal_ks_index_t *ksi)
  * Find a single block by name.
  */
 
-hal_error_t hal_ks_index_find(hal_ks_index_t *ksi,
-			      const hal_uuid_t * const name,
-			      unsigned *blockno,
+hal_error_t hal_ks_index_find(hal_ks_t *ks,
+                              const hal_uuid_t * const name,
+                              unsigned *blockno,
                               int *hint)
 {
-  if (ksi == NULL || ksi->index == NULL || ksi->names == NULL ||
-      ksi->size == 0 || ksi->used > ksi->size || name == NULL)
+  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(ksi);
+  fsck(ks);
 
-  int ok = ks_find(ksi, name, hint, &where);
+  int ok = ks_find(ks, name, hint, &where);
 
   if (blockno != NULL)
-    *blockno = ksi->index[where];
+    *blockno = ks->index[where];
 
   if (hint != NULL)
     *hint = where;
@@ -200,23 +192,23 @@ hal_error_t hal_ks_index_find(hal_ks_index_t *ksi,
  * Add a single block to the index.
  */
 
-hal_error_t hal_ks_index_add(hal_ks_index_t *ksi,
-			     const hal_uuid_t * const name,
-			     unsigned *blockno,
+hal_error_t hal_ks_index_add(hal_ks_t *ks,
+                             const hal_uuid_t * const name,
+                             unsigned *blockno,
                              int *hint)
 {
-  if (ksi == NULL || ksi->index == NULL || ksi->names == NULL ||
-      ksi->size == 0 || ksi->used > ksi->size || name == NULL)
+  if (ks == NULL || ks->index == NULL || ks->names == NULL ||
+      ks->size == 0 || ks->used > ks->size || name == NULL)
     return HAL_ERROR_BAD_ARGUMENTS;
 
-  if (ksi->used == ksi->size)
+  if (ks->used == ks->size)
     return HAL_ERROR_NO_KEY_INDEX_SLOTS;
 
   int where;
 
-  fsck(ksi);
+  fsck(ks);
 
-  if (ks_find(ksi, name, hint, &where))
+  if (ks_find(ks, name, hint, &where))
     return HAL_ERROR_KEY_NAME_IN_USE;
 
   /*
@@ -224,11 +216,11 @@ hal_error_t hal_ks_index_add(hal_ks_index_t *ksi,
    * index up by one slot so we can insert the new block number.
    */
 
-  const size_t len = (ksi->used - where) * sizeof(*ksi->index);
-  const uint16_t b = ksi->index[ksi->used++];
-  memmove(&ksi->index[where + 1], &ksi->index[where], len);
-  ksi->index[where] = b;
-  ksi->names[b] = *name;
+  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;
@@ -236,7 +228,7 @@ hal_error_t hal_ks_index_add(hal_ks_index_t *ksi,
   if (hint != NULL)
     *hint = where;
 
-  fsck(ksi);
+  fsck(ks);
 
   return HAL_OK;
 }
@@ -245,32 +237,32 @@ hal_error_t hal_ks_index_add(hal_ks_index_t *ksi,
  * Delete a single block from the index.
  */
 
-hal_error_t hal_ks_index_delete(hal_ks_index_t *ksi,
-				const hal_uuid_t * const name,
-				unsigned *blockno,
+hal_error_t hal_ks_index_delete(hal_ks_t *ks,
+                                const hal_uuid_t * const name,
+                                unsigned *blockno,
                                 int *hint)
 {
-  if (ksi == NULL || ksi->index == NULL || ksi->names == NULL ||
-      ksi->size == 0 || ksi->used > ksi->size || name == NULL)
+  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(ksi);
+  fsck(ks);
 
-  if (ksi->used == 0 || !ks_find(ksi, name, hint, &where))
+  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 = (ksi->size - where - 1) * sizeof(*ksi->index);
-  const uint16_t b = ksi->index[where];
-  memmove(&ksi->index[where], &ksi->index[where + 1], len);
-  ksi->index[ksi->size - 1] = b;
-  ksi->used--;
-  memset(&ksi->names[b], 0, sizeof(ksi->names[b]));
+  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;
@@ -278,32 +270,34 @@ hal_error_t hal_ks_index_delete(hal_ks_index_t *ksi,
   if (hint != NULL)
     *hint = where;
 
-  fsck(ksi);
+  fsck(ks);
 
   return HAL_OK;
 }
 
 /*
- * Replace a single block in the index.
+ * Replace a single block with a new one, return new block number.
+ * Name of block does not change.  This is an optimization of a delete
+ * immediately followed by an add for the same name.
  */
 
-hal_error_t hal_ks_index_replace(hal_ks_index_t *ksi,
+hal_error_t hal_ks_index_replace(hal_ks_t *ks,
                                  const hal_uuid_t * const name,
                                  unsigned *blockno,
                                  int *hint)
 {
-  if (ksi == NULL || ksi->index == NULL || ksi->names == NULL ||
-      ksi->size == 0 || ksi->used > ksi->size || name == NULL)
+  if (ks == NULL || ks->index == NULL || ks->names == NULL ||
+      ks->size == 0 || ks->used > ks->size || name == NULL)
     return HAL_ERROR_BAD_ARGUMENTS;
 
-  if (ksi->used == ksi->size)
+  if (ks->used == ks->size)
     return HAL_ERROR_NO_KEY_INDEX_SLOTS;
 
   int where;
 
-  fsck(ksi);
+  fsck(ks);
 
-  if (ksi->used == 0 || !ks_find(ksi, name, hint, &where))
+  if (ks->used == 0 || !ks_find(ks, name, hint, &where))
     return HAL_ERROR_KEY_NOT_FOUND;
 
   /*
@@ -311,14 +305,14 @@ hal_error_t hal_ks_index_replace(hal_ks_index_t *ksi,
    * block at end of free list and replace old block with new block.
    */
 
-  const size_t len = (ksi->size - ksi->used - 1) * sizeof(*ksi->index);
-  const uint16_t b1 = ksi->index[where];
-  const uint16_t b2 = ksi->index[ksi->used];
-  memmove(&ksi->index[ksi->used], &ksi->index[ksi->used + 1], len);
-  ksi->index[ksi->size - 1] = b1;
-  ksi->index[where] = b2;
-  ksi->names[b2] = *name;
-  memset(&ksi->names[b1], 0, sizeof(ksi->names[b1]));
+  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;
@@ -326,7 +320,7 @@ hal_error_t hal_ks_index_replace(hal_ks_index_t *ksi,
   if (hint != NULL)
     *hint = where;
 
-  fsck(ksi);
+  fsck(ks);
 
   return HAL_OK;
 }