diff options
| author | Volker Lendecke <vl@samba.org> | 2014-03-18 07:46:38 +0100 |
|---|---|---|
| committer | Michael Adam <obnox@samba.org> | 2014-03-18 13:42:10 +0100 |
| commit | 255edd1b417480ab033c51165702c19fb5fff56f (patch) | |
| tree | eb6de08e5a201ab4a785e8a833607103e944a2f1 | |
| parent | d1ce0110f0a1666df4d1eb81e76631a90e9e5a73 (diff) | |
| download | samba-255edd1b417480ab033c51165702c19fb5fff56f.tar.gz samba-255edd1b417480ab033c51165702c19fb5fff56f.tar.xz samba-255edd1b417480ab033c51165702c19fb5fff56f.zip | |
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 <vl@samba.org>
Reviewed-by: Michael Adam <obnox@samba.org>
Reviewed-by: Stefan Metzmacher <metze@samba.org>
| -rw-r--r-- | lib/tdb/common/tdb.c | 20 |
1 files 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, |