+static tdb_off_t COLD find_in_chain(struct tdb_context *tdb,
+ struct tdb_data key,
+ tdb_off_t chain,
+ struct hash_info *h,
+ struct tdb_used_record *rec,
+ struct traverse_info *tinfo)
+{
+ tdb_off_t off, next;
+ enum TDB_ERROR ecode;
+
+ /* In case nothing is free, we set these to zero. */
+ h->home_bucket = h->found_bucket = 0;
+
+ for (off = chain; off; off = next) {
+ unsigned int i;
+
+ h->group_start = off;
+ ecode = tdb_read_convert(tdb, off, h->group, sizeof(h->group));
+ if (ecode != TDB_SUCCESS) {
+ return TDB_ERR_TO_OFF(ecode);
+ }
+
+ for (i = 0; i < (1 << TDB_HASH_GROUP_BITS); i++) {
+ tdb_off_t recoff;
+ if (!h->group[i]) {
+ /* Remember this empty bucket. */
+ h->home_bucket = h->found_bucket = i;
+ continue;
+ }
+
+ /* We can insert extra bits via add_to_hash
+ * empty bucket logic. */
+ recoff = h->group[i] & TDB_OFF_MASK;
+ ecode = tdb_read_convert(tdb, recoff, rec,
+ sizeof(*rec));
+ if (ecode != TDB_SUCCESS) {
+ return TDB_ERR_TO_OFF(ecode);
+ }
+
+ ecode = TDB_OFF_TO_ERR(key_matches(tdb, rec, recoff,
+ &key));
+ if (ecode < 0) {
+ return TDB_ERR_TO_OFF(ecode);
+ }
+ if (ecode == (enum TDB_ERROR)1) {
+ h->home_bucket = h->found_bucket = i;
+
+ if (tinfo) {
+ tinfo->levels[tinfo->num_levels]
+ .hashtable = off;
+ tinfo->levels[tinfo->num_levels]
+ .total_buckets
+ = 1 << TDB_HASH_GROUP_BITS;
+ tinfo->levels[tinfo->num_levels].entry
+ = i;
+ tinfo->num_levels++;
+ }
+ return recoff;
+ }
+ }
+ next = tdb_read_off(tdb, off
+ + offsetof(struct tdb_chain, next));
+ if (TDB_OFF_IS_ERR(next)) {
+ return next;
+ }
+ if (next)
+ next += sizeof(struct tdb_used_record);
+ }
+ return 0;
+}
+