From 5eccb3e6d7c27149a0092de48eb21baa495879cb Mon Sep 17 00:00:00 2001 From: Rob Austein Date: Thu, 25 May 2017 11:18:39 -0400 Subject: Checkpoint while refactoring. Almost certainly will not compile. --- ks.c | 275 ++----------------------------------------------------------------- 1 file changed, 8 insertions(+), 267 deletions(-) (limited to 'ks.c') 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)) -- cgit v1.2.3