From nobody Tue May 7 00:42:45 2024 Delivered-To: importer@patchew.org Received-SPF: pass (zoho.com: domain of redhat.com designates 209.132.183.28 as permitted sender) client-ip=209.132.183.28; envelope-from=libvir-list-bounces@redhat.com; helo=mx1.redhat.com; Authentication-Results: mx.zohomail.com; spf=pass (zoho.com: domain of redhat.com designates 209.132.183.28 as permitted sender) smtp.mailfrom=libvir-list-bounces@redhat.com; dmarc=pass(p=none dis=none) header.from=redhat.com ARC-Seal: i=1; a=rsa-sha256; t=1555423819; cv=none; d=zoho.com; s=zohoarc; b=Jb5qpFbXOd9ZtC31EEzVJ4LkJclknLrwtCIsd/LoUWWXfkAYpbWIa8yZd5Ta/8FYoRJYO+g10UtTcGRruJ7/EqyH+uCe1bdQeV3owkHc1qF02hZFCU8YOc3HSqt47KrZDLVn29dvrPw8ZLWLs4TlNwKPnxDd27H/fvyJTfa5RYE= ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=zoho.com; s=zohoarc; t=1555423819; h=Content-Type:Content-Transfer-Encoding:Date:From:List-Subscribe:List-Post:List-Id:List-Archive:List-Help:List-Unsubscribe:MIME-Version:Message-ID:Sender:Subject:To:ARC-Authentication-Results; bh=l39u/AcWZlK4HIHzAqeQgGwm970mM5GNTT/s4yIK7XM=; b=mp+o4AZHfG7m3rohoS/x+leCepX7UTaHTAgLTWOABXmqjfrFpPinbPBCj7ayYFHs+yJsuNgAVxxCQOY6h3vk0gs2WnpCUJ64od75lNOya5TPJm1pAowLy5SLEbGhB4jJL/ipcWtUf6u7GrejwOYk/BO16d1Ny8kcbZWy8eOcp8Q= ARC-Authentication-Results: i=1; mx.zoho.com; spf=pass (zoho.com: domain of redhat.com designates 209.132.183.28 as permitted sender) smtp.mailfrom=libvir-list-bounces@redhat.com; dmarc=pass header.from= (p=none dis=none) header.from= Return-Path: Received: from mx1.redhat.com (mx1.redhat.com [209.132.183.28]) by mx.zohomail.com with SMTPS id 1555423819651193.77498535119287; Tue, 16 Apr 2019 07:10:19 -0700 (PDT) Received: from smtp.corp.redhat.com (int-mx06.intmail.prod.int.phx2.redhat.com [10.5.11.16]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mx1.redhat.com (Postfix) with ESMTPS id 646E581E0F; Tue, 16 Apr 2019 14:10:09 +0000 (UTC) Received: from colo-mx.corp.redhat.com (colo-mx02.intmail.prod.int.phx2.redhat.com [10.5.11.21]) by smtp.corp.redhat.com (Postfix) with ESMTPS id 98C385C1B4; Tue, 16 Apr 2019 14:10:06 +0000 (UTC) Received: from lists01.pubmisc.prod.ext.phx2.redhat.com (lists01.pubmisc.prod.ext.phx2.redhat.com [10.5.19.33]) by colo-mx.corp.redhat.com (Postfix) with ESMTP id A675E3FB13; Tue, 16 Apr 2019 14:09:58 +0000 (UTC) Received: from smtp.corp.redhat.com (int-mx08.intmail.prod.int.phx2.redhat.com [10.5.11.23]) by lists01.pubmisc.prod.ext.phx2.redhat.com (8.13.8/8.13.8) with ESMTP id x3GE9ve4021833 for ; Tue, 16 Apr 2019 10:09:57 -0400 Received: by smtp.corp.redhat.com (Postfix) id C17EA19C7D; Tue, 16 Apr 2019 14:09:57 +0000 (UTC) Received: from angien.brq.redhat.com (unknown [10.43.2.229]) by smtp.corp.redhat.com (Postfix) with ESMTP id 47DA719C78 for ; Tue, 16 Apr 2019 14:09:54 +0000 (UTC) From: Peter Krempa To: libvir-list@redhat.com Date: Tue, 16 Apr 2019 16:09:54 +0200 Message-Id: <5c1695877daa8e48a6e44a63b66100e1cb59666d.1555423586.git.pkrempa@redhat.com> MIME-Version: 1.0 X-Scanned-By: MIMEDefang 2.84 on 10.5.11.23 X-loop: libvir-list@redhat.com Subject: [libvirt] [PATCH] util: hash: Append to hash buckets when adding new entries X-BeenThere: libvir-list@redhat.com X-Mailman-Version: 2.1.12 Precedence: junk List-Id: Development discussions about the libvirt library & tools List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Content-Transfer-Encoding: quoted-printable Sender: libvir-list-bounces@redhat.com Errors-To: libvir-list-bounces@redhat.com X-Scanned-By: MIMEDefang 2.79 on 10.5.11.16 X-Greylist: Sender IP whitelisted, not delayed by milter-greylist-4.5.16 (mx1.redhat.com [10.5.110.25]); Tue, 16 Apr 2019 14:10:18 +0000 (UTC) Content-Type: text/plain; charset="utf-8" In cases when the hash function for a name collides with other entry already in the hash we prepend to the bucket. This creates a 'stack effect' on the buckets if we then iterate through the hash. Normally this is not a problem, but in tests we want deterministic results. Since it does not matter where we add the entry and it's usually more probable that a different entry will be accessed next change it to append to the end of the bucket. Luckily we already iterate throught the bucket once thus we can easily find the last entry and just connect the new entry after it. Signed-off-by: Peter Krempa Reviewed-by: Daniel P. Berrang=C3=A9 --- src/util/virhash.c | 9 +++++++-- 1 file changed, 7 insertions(+), 2 deletions(-) diff --git a/src/util/virhash.c b/src/util/virhash.c index 4907c1124f..0e30106041 100644 --- a/src/util/virhash.c +++ b/src/util/virhash.c @@ -316,6 +316,7 @@ virHashAddOrUpdateEntry(virHashTablePtr table, const vo= id *name, { size_t key, len =3D 0; virHashEntryPtr entry; + virHashEntryPtr last =3D NULL; void *new_name; if ((table =3D=3D NULL) || (name =3D=3D NULL)) @@ -337,6 +338,7 @@ virHashAddOrUpdateEntry(virHashTablePtr table, const vo= id *name, return -1; } } + last =3D entry; len++; } @@ -347,8 +349,11 @@ virHashAddOrUpdateEntry(virHashTablePtr table, const v= oid *name, entry->name =3D new_name; entry->payload =3D userdata; - entry->next =3D table->table[key]; - table->table[key] =3D entry; + + if (last) + last->next =3D entry; + else + table->table[key] =3D entry; table->nbElems++; --=20 2.20.1 -- libvir-list mailing list libvir-list@redhat.com https://www.redhat.com/mailman/listinfo/libvir-list