From 255edd1b417480ab033c51165702c19fb5fff56f Mon Sep 17 00:00:00 2001 From: Volker Lendecke Date: Tue, 18 Mar 2014 07:46:38 +0100 Subject: tdb: Do a best fit search for dead records Hash chains are (or can be made) short enough that a full search for the best-fitting dead record is feasible. The freelist can become much longer, there we don't do the full search but accept records which are too large. Signed-off-by: Volker Lendecke Reviewed-by: Michael Adam Reviewed-by: Stefan Metzmacher --- lib/tdb/common/tdb.c | 20 +++++++++++++------- 1 file changed, 13 insertions(+), 7 deletions(-) diff --git a/lib/tdb/common/tdb.c b/lib/tdb/common/tdb.c index 634a5526d7..8242d2bb3f 100644 --- a/lib/tdb/common/tdb.c +++ b/lib/tdb/common/tdb.c @@ -449,6 +449,8 @@ static tdb_off_t tdb_find_dead(struct tdb_context *tdb, uint32_t hash, struct tdb_record *r, tdb_len_t length) { tdb_off_t rec_ptr; + tdb_off_t best_rec_ptr = 0; + struct tdb_record best = { .rec_len = UINT32_MAX }; /* read in the hash top */ if (tdb_ofs_read(tdb, TDB_HASH_TOP(hash), &rec_ptr) == -1) @@ -459,16 +461,20 @@ static tdb_off_t tdb_find_dead(struct tdb_context *tdb, uint32_t hash, if (tdb_rec_read(tdb, rec_ptr, r) == -1) return 0; - if (TDB_DEAD(r) && r->rec_len >= length) { - /* - * First fit for simple coding, TODO: change to best - * fit - */ - return rec_ptr; + if (TDB_DEAD(r) && (r->rec_len >= length) && + (r->rec_len < best.rec_len)) { + best_rec_ptr = rec_ptr; + best = *r; } rec_ptr = r->next; } - return 0; + + if (best.rec_len == UINT32_MAX) { + return 0; + } + + *r = best; + return best_rec_ptr; } static int _tdb_store(struct tdb_context *tdb, TDB_DATA key, -- cgit