aboutsummaryrefslogtreecommitdiff
path: root/ks.c
diff options
context:
space:
mode:
Diffstat (limited to 'ks.c')
-rw-r--r--ks.c275
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))
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-16 19:20:45 +0000