[From nobody Sun May 29 05:38:44 2016 Received: from zmta04.collab.prod.int.phx2.redhat.com (LHLO zmta04.collab.prod.int.phx2.redhat.com) (10.5.81.11) by zmail21.collab.prod.int.phx2.redhat.com with LMTP; Mon, 2 Nov 2015 17:11:07 -0500 (EST) Received: from int-mx14.intmail.prod.int.phx2.redhat.com (int-mx14.intmail.prod.int.phx2.redhat.com [10.5.11.27]) by zmta04.collab.prod.int.phx2.redhat.com (Postfix) with ESMTP id CEA8EDA0F3 for <thaller@mail.corp.redhat.com>; Mon, 2 Nov 2015 17:11:07 -0500 (EST) Received: from mx1.redhat.com (ext-mx07.extmail.prod.ext.phx2.redhat.com [10.5.110.31]) by int-mx14.intmail.prod.int.phx2.redhat.com (8.14.4/8.14.4) with ESMTP id tA2MB7Gt010834 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-GCM-SHA384 bits=256 verify=NO) for <thaller@redhat.com>; Mon, 2 Nov 2015 17:11:07 -0500 Received: from mail-pa0-f51.google.com (mail-pa0-f51.google.com [209.85.220.51]) by mx1.redhat.com (Postfix) with ESMTPS id BFBACC1C74FB for <thaller@redhat.com>; Mon, 2 Nov 2015 22:11:06 +0000 (UTC) Received: by padec8 with SMTP id ec8so51391490pad.1 for <thaller@redhat.com>; Mon, 02 Nov 2015 14:11:06 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=cumulusnetworks.com; s=google; h=from:to:cc:subject:date:message-id; bh=f0oMPJU4+07+B419xUbQmpPHqniUhBNK1Zh2s4YFrdM=; b=DJxFazT1F+fdbHa2YVWKl19BuMD3QiC3QosM5cdB6jmUwhAJUzSPPCIVQgKmo9WyTY JN3eKrazc1gv8DJyUOhjGlNT374vVesEztJbpG4rs8HlmsICfXWtwjxdd/fsbIIg44oI tyd7l8QLYJxAmZCSIWQrI2p4PwrbTdt02p7XM= X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:from:to:cc:subject:date:message-id; bh=f0oMPJU4+07+B419xUbQmpPHqniUhBNK1Zh2s4YFrdM=; b=myf3hUntGfgnWYIXxRmVc3no+HGsDp1Y2NZd+l5QYPaYmjr5ORjuj7mc4RMxImqPec sFyodIyWxDuoJHNMpq8WVTDrffSm1Ga068/vtBRHzKbFrASzVevdfV0omj5MT9W00JRJ q/d3FFI4JAImnFLXDzWMlDfUrGpHuG5+OVCSHONia+bwFAqCy+M0iwAri1W7eIJgIFfL BL9wJKCUWZCxCv0w4eFKKdhuGpfNFmu1iomOqLS5RFdGlxpE7/vczUU4tgyNhtBBlJ5G T0SUT/t1KIGmh1WeoQBzy/IkN+IB2ztG5MXSCC9e2CFmts88/HxROj0QTD/gg2fUBbKt pRxA== X-Gm-Message-State: ALoCoQmwq8I+j+ueMqgg65pVmLqaTLKR9Cqw8IT5YEDM3BIiNmjpT4tnQf6XRZfyvl96q/m1Ywu+ X-Received: by 10.68.68.132 with SMTP id w4mr26126289pbt.137.1446501937641; Mon, 02 Nov 2015 14:05:37 -0800 (PST) Received: from hydra-01.cumulusnetworks.com ([216.129.126.126]) by smtp.googlemail.com with ESMTPSA id bz1sm25892966pab.20.2015.11.02.14.05.36 (version=TLSv1.2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Mon, 02 Nov 2015 14:05:37 -0800 (PST) From: Roopa Prabhu <roopa@cumulusnetworks.com> X-Google-Original-From: Roopa Prabhu To: libnl@lists.infradead.org Cc: thaller@redhat.com, roopa@cumulusnetworks.com Subject: [PATCH 2/6] hashtable: convert hashtable bucket list to a circular doubly linked list Date: Mon, 2 Nov 2015 14:05:25 -0800 Message-Id: <1446501929-32003-3-git-send-email-roopa@cumulusnetworks.com> X-RedHat-Spam-Score: 2.099 ** (ANY_BOUNCE_MESSAGE, BAYES_50, BOUNCE_MESSAGE, DCC_REPUT_13_19, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DSN_NO_MIMEVERSION, RCVD_IN_DNSWL_LOW, RCVD_IN_MSPIKE_H2, URIBL_BLOCKED) 209.85.220.51 mail-pa0-f51.google.com 209.85.220.51 mail-pa0-f51.google.com <> X-Scanned-By: MIMEDefang 2.68 on 10.5.11.27 X-Scanned-By: MIMEDefang 2.78 on 10.5.110.31 Mime-Version: 1.0 Content-Transfer-Encoding: quoted-printable From: Roopa Prabhu <roopa@cumulusnetworks.com> This patch converts hashtable bucket list to a circular doubly linked list for O(1) enqueue/dequeue. This helps support: - a netlink object append that causes enqueue at tail and - support for non-exclusive (ie create only flag) netlink objects causes an enqueue at head Signed-off-by: Roopa Prabhu <roopa@cumulusnetworks.com> --- include/netlink/hashtable.h | 2 +- lib/hashtable.c | 111 ++++++++++++++++++++++++++-------------= ---- 2 files changed, 68 insertions(+), 45 deletions(-) diff --git a/include/netlink/hashtable.h b/include/netlink/hashtable.h index d9e6ee4..70d8c0f 100644 --- a/include/netlink/hashtable.h +++ b/include/netlink/hashtable.h @@ -20,7 +20,7 @@ typedef struct nl_hash_node { uint32_t key; uint32_t key_size; struct nl_object * obj; - struct nl_hash_node * next; + struct nl_list_head list; } nl_hash_node_t; =20 typedef struct nl_hash_table { diff --git a/lib/hashtable.c b/lib/hashtable.c index 8b15925..75e9fda 100644 --- a/lib/hashtable.c +++ b/lib/hashtable.c @@ -14,6 +14,19 @@ #include <netlink/hash.h> #include <netlink/hashtable.h> =20 +static nl_hash_node_t *nl_hash_table_list_head_alloc() +{ + nl_hash_node_t *head; + + head =3D calloc(1, sizeof(*head)); + if (!head) + return NULL; + + nl_init_list_head(&head->list); + + return head; +} + /** * @ingroup core_types * @defgroup hashtable Hashtable @@ -58,15 +71,15 @@ void nl_hash_table_free(nl_hash_table_t *ht) int i; =20 for(i =3D 0; i < ht->size; i++) { - nl_hash_node_t *node =3D ht->nodes[i]; - nl_hash_node_t *saved_node; - - while (node) { - saved_node =3D node; - node =3D node->next; - nl_object_put(saved_node->obj); - free(saved_node); - } + nl_hash_node_t *node, *head =3D ht->nodes[i], *tmp; + + if (!head) + continue; + + nl_list_for_each_entry_safe(node, tmp, &head->list, list) { + nl_list_del(&node->list); + free(node); + } } =20 free(ht->nodes); @@ -86,16 +99,17 @@ void nl_hash_table_free(nl_hash_table_t *ht) struct nl_object* nl_hash_table_lookup(nl_hash_table_t *ht, struct nl_object *obj) { - nl_hash_node_t *node; + nl_hash_node_t *node, *head; uint32_t key_hash; =20 nl_object_keygen(obj, &key_hash, ht->size); - node =3D ht->nodes[key_hash]; + head =3D ht->nodes[key_hash]; + if (!head) + return NULL; =20 - while (node) { - if (nl_object_identical(node->obj, obj)) + nl_list_for_each_entry(node, &head->list, list) { + if (nl_object_identical(node->obj, obj)) return node->obj; - node =3D node->next; } =20 return NULL; @@ -116,18 +130,27 @@ struct nl_object* nl_hash_table_lookup(nl_hash_table_= t *ht, */ int nl_hash_table_add(nl_hash_table_t *ht, struct nl_object *obj) { - nl_hash_node_t *node; + nl_hash_node_t *node, *head; uint32_t key_hash; =20 nl_object_keygen(obj, &key_hash, ht->size); - node =3D ht->nodes[key_hash]; - - while (node) { - if (nl_object_identical(node->obj, obj)) { - NL_DBG(2, "Warning: Add to hashtable found duplicate...\n"); - return -NLE_EXIST; - } - node =3D node->next; + head =3D ht->nodes[key_hash]; + if (head !=3D NULL) { + nl_list_for_each_entry(node, &head->list, list) { + if (nl_object_identical(node->obj, obj)) { + NL_DBG(2, "Warning: Add to hashtable found " + "duplicate...\n"); + return -NLE_EXIST; + } + } + } else { + /* Initialize head (This can also be done in hash table alloc + * function. Its done here so that we only allocate nodes + * when needed) + */ + ht->nodes[key_hash] =3D nl_hash_table_list_head_alloc(); + if (!ht->nodes[key_hash]) + return -NLE_NOMEM; } =20 NL_DBG (5, "adding cache entry of obj %p in table %p, with hash 0x%x\n", @@ -140,8 +163,13 @@ int nl_hash_table_add(nl_hash_table_t *ht, struct nl_o= bject *obj) node->obj =3D obj; node->key =3D key_hash; node->key_size =3D sizeof(uint32_t); - node->next =3D ht->nodes[key_hash]; - ht->nodes[key_hash] =3D node; + nl_init_list_head(&node->list); + + if ((obj->ce_msgflags & NLM_F_APPEND) || + (obj->ce_flags & NL_OBJ_DUMP)) + nl_list_add_tail(&node->list, &ht->nodes[key_hash]->list); + else + nl_list_add_head(&node->list, &ht->nodes[key_hash]->list); =20 return 0; } @@ -160,30 +188,25 @@ int nl_hash_table_add(nl_hash_table_t *ht, struct nl_= object *obj) */ int nl_hash_table_del(nl_hash_table_t *ht, struct nl_object *obj) { - nl_hash_node_t *node, *prev; + nl_hash_node_t *node, *head; uint32_t key_hash; =20 nl_object_keygen(obj, &key_hash, ht->size); - prev =3D node =3D ht->nodes[key_hash]; + head =3D ht->nodes[key_hash]; + if (!head) + return -NLE_OBJ_NOTFOUND; =20 - while (node) { + nl_list_for_each_entry(node, &head->list, list) { if (nl_object_identical(node->obj, obj)) { - nl_object_put(obj); - - NL_DBG (5, "deleting cache entry of obj %p in table %p, with" - " hash 0x%x\n", obj, ht, key_hash); - - if (node =3D=3D ht->nodes[key_hash]) - ht->nodes[key_hash] =3D node->next; - else - prev->next =3D node->next; - - free(node); - - return 0; - } - prev =3D node; - node =3D node->next; + nl_object_put(obj); + nl_list_del(&node->list); + free(node); + if (nl_list_empty(&head->list)) { + free(ht->nodes[key_hash]); + ht->nodes[key_hash] =3D NULL; + } + return 0; + } } =20 return -NLE_OBJ_NOTFOUND; --=20 1.7.10.4 ]