From patchwork Wed Nov 11 20:02:07 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 11898435 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-9.6 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_PATCH,MAILING_LIST_MULTI,SIGNED_OFF_BY, SPF_HELO_NONE,SPF_PASS autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 06523C388F9 for ; Wed, 11 Nov 2020 20:02:29 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 8BE682087D for ; Wed, 11 Nov 2020 20:02:28 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="mh20k604" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726273AbgKKUC1 (ORCPT ); Wed, 11 Nov 2020 15:02:27 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:57932 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1725860AbgKKUC0 (ORCPT ); Wed, 11 Nov 2020 15:02:26 -0500 Received: from mail-wr1-x443.google.com (mail-wr1-x443.google.com [IPv6:2a00:1450:4864:20::443]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 45B65C0613D4 for ; Wed, 11 Nov 2020 12:02:26 -0800 (PST) Received: by mail-wr1-x443.google.com with SMTP id k2so3754462wrx.2 for ; Wed, 11 Nov 2020 12:02:26 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=message-id:in-reply-to:references:from:date:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=oFAswi3o4d7CVNEpLSnDCYqFONh+d8GGqoJ1wyK3dI8=; b=mh20k6041XEz1CPGPKI6dihqw1vT5Da+orLgydqLmezat3bqCEPqEK9xurQrYmDUKA cjDFH/i9F3dUm+qWxZ6sG3ypik43VmMIA4oU3/eB/qWwpZorgv6DUni9A3p+GhmX64B0 z9W7LzvFAO0LZeN1OIlLDFLV0WkjD3fqHPpArxis94Fi3LtbKrXuaFVhzQTzjzRD7n1C UyOBuU1FRMz2GrGoWETdZb7pwdrlv02NzDSpl7Isivfk0uNbYMuer3jxRSGUXQPrE3Ki 9lnXqGrxgjLLevW5BdYuXXu1w0qO5GLK0lhnZDZ6t4hXTpe8njYO3KRRVZ3gZt+kTjW2 rUAg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:message-id:in-reply-to:references:from:date :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=oFAswi3o4d7CVNEpLSnDCYqFONh+d8GGqoJ1wyK3dI8=; b=cLxX2in8ZIghddFirwoZb++V+XiBh9Mi4WW1s0bGhTV7esijT+lPLS5b7MHbrvhrsK 2S2/TPKJ6Xpot8DU2MxvxlGrQGikxDIgKheJ0wphzldfq8fpT80+U2NLIyxomp5O7RMV UbA4FQpbUMCAowvk5IJi7Lmc8SbRJ2TTWHYZ9ttMYBye6/E65HtO8g2qU9OUAo6gbr4C Yytm+fXFIi7jXMRku3GmVoHVjjQ0z5h3apN3M7qaxF9wpQzDnT1mbowoiZ0PIolanuMT Af/4P5RYLHzV/rVXXvN0DV7URvecGNepZRn+Pe7iQ7vqVAFWZaeGTT3DWPNQPU+KA1TE yS7w== X-Gm-Message-State: AOAM530AZ9oBjwQHd53c9U0QmLeFTnQOWgF3fojC5UUjmkWWD4XVQiaJ pv9Kn+Kj/WDNZn0+wd3hmZOUTVGpaPI= X-Google-Smtp-Source: ABdhPJzjVpUCib3my4oxQ6BdiCUvBhnlRjS3OeV1pQThUSWge3Bu1bRXoIODeDqaaH2tNWQb222mtw== X-Received: by 2002:adf:e3cf:: with SMTP id k15mr15489088wrm.259.1605124944818; Wed, 11 Nov 2020 12:02:24 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id y11sm3473386wmj.36.2020.11.11.12.02.24 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 11 Nov 2020 12:02:24 -0800 (PST) Message-Id: In-Reply-To: References: Date: Wed, 11 Nov 2020 20:02:07 +0000 Subject: [PATCH v6 01/15] hashmap: add usage documentation explaining hashmap_free[_entries]() Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Jeff King , Elijah Newren , Phillip Wood , Elijah Newren , Elijah Newren Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Elijah Newren From: Elijah Newren The existence of hashmap_free() and hashmap_free_entries() confused me, and the docs weren't clear enough. We are dealing with a map table, entries in that table, and possibly also things each of those entries point to. I had to consult other source code examples and the implementation. Add a brief note to clarify the differences. This will become even more important once we introduce a new hashmap_partial_clear() function which will add the question of whether the table itself has been freed. Signed-off-by: Elijah Newren --- hashmap.h | 31 +++++++++++++++++++++++++++++-- 1 file changed, 29 insertions(+), 2 deletions(-) diff --git a/hashmap.h b/hashmap.h index b011b394fe..2994dc7a9c 100644 --- a/hashmap.h +++ b/hashmap.h @@ -236,13 +236,40 @@ void hashmap_init(struct hashmap *map, void hashmap_free_(struct hashmap *map, ssize_t offset); /* - * Frees a hashmap structure and allocated memory, leaves entries undisturbed + * Frees a hashmap structure and allocated memory for the table, but does not + * free the entries nor anything they point to. + * + * Usage note: + * + * Many callers will need to iterate over all entries and free the data each + * entry points to; in such a case, they can free the entry itself while at it. + * Thus, you might see: + * + * hashmap_for_each_entry(map, hashmap_iter, e, hashmap_entry_name) { + * free(e->somefield); + * free(e); + * } + * hashmap_free(map); + * + * instead of + * + * hashmap_for_each_entry(map, hashmap_iter, e, hashmap_entry_name) { + * free(e->somefield); + * } + * hashmap_free_entries(map, struct my_entry_struct, hashmap_entry_name); + * + * to avoid the implicit extra loop over the entries. However, if there are + * no special fields in your entry that need to be freed beyond the entry + * itself, it is probably simpler to avoid the explicit loop and just call + * hashmap_free_entries(). */ #define hashmap_free(map) hashmap_free_(map, -1) /* * Frees @map and all entries. @type is the struct type of the entry - * where @member is the hashmap_entry struct used to associate with @map + * where @member is the hashmap_entry struct used to associate with @map. + * + * See usage note above hashmap_free(). */ #define hashmap_free_entries(map, type, member) \ hashmap_free_(map, offsetof(type, member)); From patchwork Wed Nov 11 20:02:08 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 11898433 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-9.6 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_PATCH,MAILING_LIST_MULTI,SIGNED_OFF_BY, SPF_HELO_NONE,SPF_PASS autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 33D23C56201 for ; Wed, 11 Nov 2020 20:02:29 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id CD541208B8 for ; Wed, 11 Nov 2020 20:02:28 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="l6ZHDWrF" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727560AbgKKUC2 (ORCPT ); Wed, 11 Nov 2020 15:02:28 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:57934 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1725860AbgKKUC1 (ORCPT ); Wed, 11 Nov 2020 15:02:27 -0500 Received: from mail-wm1-x32c.google.com (mail-wm1-x32c.google.com [IPv6:2a00:1450:4864:20::32c]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 340FDC0613D4 for ; Wed, 11 Nov 2020 12:02:27 -0800 (PST) Received: by mail-wm1-x32c.google.com with SMTP id c16so3466157wmd.2 for ; Wed, 11 Nov 2020 12:02:27 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=message-id:in-reply-to:references:from:date:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=lfeFxSmzBLKnFekm6mzwPvSqu+S1DEbaBDz97hV1DAw=; b=l6ZHDWrFxrGFpRxHsXeCzOEi+kIeflZwY9RpTC3D5JWveFlxX60wPb5RQc5NYZp4pp FdvOul9LEsfoepWaho53/BXGz4kKvXi9PgHOsHRR/jDRL9klYFPVVikrcMLry6OOMV1g UqqpcjAGrZrETI5qYybkLq7lka9EO2N+fQNdAP82vln1tF+tbD8XvWvnjQl+OeCS/WJI mypDtXh3wou8hmXxAso4K+JAPX1gA/t+bKG44mxRUdkqLY+eSs8Kx1sD40SrpLXswuAj 4BJHl11T6x8RPBI/+rjmX9RGnGYQdzgn0tIw5htAufUoUq+o1b4cziNVUbsRC7JNZzQI VAow== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:message-id:in-reply-to:references:from:date :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=lfeFxSmzBLKnFekm6mzwPvSqu+S1DEbaBDz97hV1DAw=; b=bieC/NUi+aFgSgc7kf6f9viR357NiAZAAnkD6PBQIFNMvzNvAzqnFQIapIyb3rqJU5 xiKQCI803fA9fjNSEDDj4X6wzRXg4ZXeWvQRxBRUoqecussWI0rXft0Fu8l4RHcgfi3h tLaDOMJbSYCY3RIXF0IXGFMC0LsYjpopa8SNEYGVAcFOyocFhx4gYD9jd3DWCZTKlFM7 CqhFCgvcbZiITDfVbvlmV+p3CemEKDFIlydr/z4hpXoCqH1hB3eSQvmYVHq5kdXJhlH5 ZTfQy+oPHHir0e7qaILM36RMdvsZ+8n2wEfPJueUQZ1mDNUOqrDWaxcmjMXojcAt7M7a cKJA== X-Gm-Message-State: AOAM531Cshnv9Bbwlyvr8rhUsYqyuSUcJa1RGEz08SCcauxLTdDYeiW7 BQueXvWgNTYT0WHYeHV48f2mkHCoZf8= X-Google-Smtp-Source: ABdhPJzBJoYkjTEWZHRJBGKTOTTdls7qx3DaCXdczY+515hSGEaMLnka3UJ3Oevx4T1xyaAMh7AoPg== X-Received: by 2002:a1c:80d3:: with SMTP id b202mr5981202wmd.139.1605124945643; Wed, 11 Nov 2020 12:02:25 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id y20sm3673113wma.15.2020.11.11.12.02.25 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 11 Nov 2020 12:02:25 -0800 (PST) Message-Id: <591161fd781b7666ddaa45694eb20610cc359741.1605124942.git.gitgitgadget@gmail.com> In-Reply-To: References: Date: Wed, 11 Nov 2020 20:02:08 +0000 Subject: [PATCH v6 02/15] hashmap: adjust spacing to fix argument alignment Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Jeff King , Elijah Newren , Phillip Wood , Elijah Newren , Elijah Newren Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Elijah Newren From: Elijah Newren No actual code changes; just whitespace adjustments. Signed-off-by: Elijah Newren --- hashmap.c | 17 +++++++++-------- hashmap.h | 22 +++++++++++----------- 2 files changed, 20 insertions(+), 19 deletions(-) diff --git a/hashmap.c b/hashmap.c index 09813e1a46..e44d8a3e85 100644 --- a/hashmap.c +++ b/hashmap.c @@ -92,8 +92,9 @@ static void alloc_table(struct hashmap *map, unsigned int size) } static inline int entry_equals(const struct hashmap *map, - const struct hashmap_entry *e1, const struct hashmap_entry *e2, - const void *keydata) + const struct hashmap_entry *e1, + const struct hashmap_entry *e2, + const void *keydata) { return (e1 == e2) || (e1->hash == e2->hash && @@ -101,7 +102,7 @@ static inline int entry_equals(const struct hashmap *map, } static inline unsigned int bucket(const struct hashmap *map, - const struct hashmap_entry *key) + const struct hashmap_entry *key) { return key->hash & (map->tablesize - 1); } @@ -148,7 +149,7 @@ static int always_equal(const void *unused_cmp_data, } void hashmap_init(struct hashmap *map, hashmap_cmp_fn equals_function, - const void *cmpfn_data, size_t initial_size) + const void *cmpfn_data, size_t initial_size) { unsigned int size = HASHMAP_INITIAL_SIZE; @@ -199,7 +200,7 @@ struct hashmap_entry *hashmap_get(const struct hashmap *map, } struct hashmap_entry *hashmap_get_next(const struct hashmap *map, - const struct hashmap_entry *entry) + const struct hashmap_entry *entry) { struct hashmap_entry *e = entry->next; for (; e; e = e->next) @@ -225,8 +226,8 @@ void hashmap_add(struct hashmap *map, struct hashmap_entry *entry) } struct hashmap_entry *hashmap_remove(struct hashmap *map, - const struct hashmap_entry *key, - const void *keydata) + const struct hashmap_entry *key, + const void *keydata) { struct hashmap_entry *old; struct hashmap_entry **e = find_entry_ptr(map, key, keydata); @@ -249,7 +250,7 @@ struct hashmap_entry *hashmap_remove(struct hashmap *map, } struct hashmap_entry *hashmap_put(struct hashmap *map, - struct hashmap_entry *entry) + struct hashmap_entry *entry) { struct hashmap_entry *old = hashmap_remove(map, entry, NULL); hashmap_add(map, entry); diff --git a/hashmap.h b/hashmap.h index 2994dc7a9c..904f61d6e1 100644 --- a/hashmap.h +++ b/hashmap.h @@ -228,9 +228,9 @@ struct hashmap { * prevent expensive resizing. If 0, the table is dynamically resized. */ void hashmap_init(struct hashmap *map, - hashmap_cmp_fn equals_function, - const void *equals_function_data, - size_t initial_size); + hashmap_cmp_fn equals_function, + const void *equals_function_data, + size_t initial_size); /* internal function for freeing hashmap */ void hashmap_free_(struct hashmap *map, ssize_t offset); @@ -288,7 +288,7 @@ void hashmap_free_(struct hashmap *map, ssize_t offset); * and if it is on stack, you can just let it go out of scope). */ static inline void hashmap_entry_init(struct hashmap_entry *e, - unsigned int hash) + unsigned int hash) { e->hash = hash; e->next = NULL; @@ -330,8 +330,8 @@ static inline unsigned int hashmap_get_size(struct hashmap *map) * to `hashmap_cmp_fn` to decide whether the entry matches the key. */ struct hashmap_entry *hashmap_get(const struct hashmap *map, - const struct hashmap_entry *key, - const void *keydata); + const struct hashmap_entry *key, + const void *keydata); /* * Returns the hashmap entry for the specified hash code and key data, @@ -364,7 +364,7 @@ static inline struct hashmap_entry *hashmap_get_from_hash( * call to `hashmap_get` or `hashmap_get_next`. */ struct hashmap_entry *hashmap_get_next(const struct hashmap *map, - const struct hashmap_entry *entry); + const struct hashmap_entry *entry); /* * Adds a hashmap entry. This allows to add duplicate entries (i.e. @@ -384,7 +384,7 @@ void hashmap_add(struct hashmap *map, struct hashmap_entry *entry); * Returns the replaced entry, or NULL if not found (i.e. the entry was added). */ struct hashmap_entry *hashmap_put(struct hashmap *map, - struct hashmap_entry *entry); + struct hashmap_entry *entry); /* * Adds or replaces a hashmap entry contained within @keyvar, @@ -406,8 +406,8 @@ struct hashmap_entry *hashmap_put(struct hashmap *map, * Argument explanation is the same as in `hashmap_get`. */ struct hashmap_entry *hashmap_remove(struct hashmap *map, - const struct hashmap_entry *key, - const void *keydata); + const struct hashmap_entry *key, + const void *keydata); /* * Removes a hashmap entry contained within @keyvar, @@ -449,7 +449,7 @@ struct hashmap_entry *hashmap_iter_next(struct hashmap_iter *iter); /* Initializes the iterator and returns the first entry, if any. */ static inline struct hashmap_entry *hashmap_iter_first(struct hashmap *map, - struct hashmap_iter *iter) + struct hashmap_iter *iter) { hashmap_iter_init(map, iter); return hashmap_iter_next(iter); From patchwork Wed Nov 11 20:02:09 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 11898437 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-9.6 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_PATCH,MAILING_LIST_MULTI,SIGNED_OFF_BY, SPF_HELO_NONE,SPF_PASS autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id E2B93C5517A for ; Wed, 11 Nov 2020 20:02:30 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 901512087D for ; Wed, 11 Nov 2020 20:02:30 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="s57JhnuQ" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727690AbgKKUC3 (ORCPT ); Wed, 11 Nov 2020 15:02:29 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:57934 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1725860AbgKKUC2 (ORCPT ); Wed, 11 Nov 2020 15:02:28 -0500 Received: from mail-wr1-x444.google.com (mail-wr1-x444.google.com [IPv6:2a00:1450:4864:20::444]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id D0965C0613D4 for ; Wed, 11 Nov 2020 12:02:27 -0800 (PST) Received: by mail-wr1-x444.google.com with SMTP id k2so3754537wrx.2 for ; Wed, 11 Nov 2020 12:02:27 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=message-id:in-reply-to:references:from:date:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=IEPGTilWFeb/gYnUiQHEDPP0R8dCTuzsEUTPxGrkZm8=; b=s57JhnuQZ8XzkDarvLj4St4go/vw+RLWRNy6kmKB8zYl4HHaH3st2SxRZhe5BPZCrU k/FMHuF0bC0ZqB0vcjLGNWOTrwzZgySGKAH4nU9QW9OadlayOlsOVozG62rrEUkgeL3h aZKAK53ULjmQQl0KKUG8Wj7QkzYX+emt3OuYx/kcggM0EL/MbJkwbue1shk5T/JyVTsG 0GMvbCYxHwNdbN3WEwqDmwekzTW3NUSBYm8h4r78//L6yrmThN6osxYylqZoWYKK84kF z+mePJB7KtjAgV4w3hHisdS1oTKtDCpbeCJ374MTsnrIq6tQYNFjt8zyuXCVeyAznKRV Jz4g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:message-id:in-reply-to:references:from:date :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=IEPGTilWFeb/gYnUiQHEDPP0R8dCTuzsEUTPxGrkZm8=; b=Cp1j4lLWH8ARQZMGJVgvsw33yM1RU/CuuZmG9e1m3IYDYOXBzuB9gZgvsejBhsNCEk WCS07fpOa/QH4ss9U7+ovvnCOXOAq4ye+ll5OOMq+OfDE7PemIP+lPJyN+5EhBIbNNDC RBW/9HgO49u2E6eE04/UWXwj25WMFEg8CIxBWsEDZ0wyyuBzUf9R1nuqiCXzOK3pA3jN /L+ycXU6QBvmM4D3oklvBhjvZXRujy0KI8ZsMQ75Ru45EuQQdFaczr6jMAHVAWAJsE/6 4Nz6WEPL1qKss3zv65sPnuFkSbjznLnx+kKgOEa0gGAHJEFpUiebzZpOhcEmzHhyVFo5 RNMw== X-Gm-Message-State: AOAM533u484idfDMVyb1KfzvS1CYRaUd1EbcUUOwcSz5mAgHIUTSIeDs BVdmKZOkPc8Y5A8V4LYU9zAJ5q/2nCM= X-Google-Smtp-Source: ABdhPJw5D/m+hHm91s6f5d50t+B0yeaCSeCaNHyLfoAU9P/w0XSuyIBYnztSWReGowDcj2FVEMRfeg== X-Received: by 2002:a5d:51cd:: with SMTP id n13mr21657481wrv.87.1605124946473; Wed, 11 Nov 2020 12:02:26 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id j127sm4102448wma.31.2020.11.11.12.02.25 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 11 Nov 2020 12:02:26 -0800 (PST) Message-Id: In-Reply-To: References: Date: Wed, 11 Nov 2020 20:02:09 +0000 Subject: [PATCH v6 03/15] hashmap: allow re-use after hashmap_free() Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Jeff King , Elijah Newren , Phillip Wood , Elijah Newren , Elijah Newren Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Elijah Newren From: Elijah Newren Previously, once map->table had been freed, any calls to hashmap_put(), hashmap_get(), or hashmap_remove() would cause a NULL pointer dereference (since hashmap_free_() also zeros the memory; without that zeroing, calling these functions would cause a use-after-free problem). Modify these functions to check for a NULL table and automatically allocate as needed. Also add a HASHMAP_INIT(fn, data) macro for initializing hashmaps on the stack without calling hashmap_init(). Signed-off-by: Elijah Newren --- hashmap.c | 16 ++++++++++++++-- hashmap.h | 3 +++ 2 files changed, 17 insertions(+), 2 deletions(-) diff --git a/hashmap.c b/hashmap.c index e44d8a3e85..bb7c9979b8 100644 --- a/hashmap.c +++ b/hashmap.c @@ -114,6 +114,7 @@ int hashmap_bucket(const struct hashmap *map, unsigned int hash) static void rehash(struct hashmap *map, unsigned int newsize) { + /* map->table MUST NOT be NULL when this function is called */ unsigned int i, oldsize = map->tablesize; struct hashmap_entry **oldtable = map->table; @@ -134,6 +135,7 @@ static void rehash(struct hashmap *map, unsigned int newsize) static inline struct hashmap_entry **find_entry_ptr(const struct hashmap *map, const struct hashmap_entry *key, const void *keydata) { + /* map->table MUST NOT be NULL when this function is called */ struct hashmap_entry **e = &map->table[bucket(map, key)]; while (*e && !entry_equals(map, *e, key, keydata)) e = &(*e)->next; @@ -196,6 +198,8 @@ struct hashmap_entry *hashmap_get(const struct hashmap *map, const struct hashmap_entry *key, const void *keydata) { + if (!map->table) + return NULL; return *find_entry_ptr(map, key, keydata); } @@ -211,8 +215,12 @@ struct hashmap_entry *hashmap_get_next(const struct hashmap *map, void hashmap_add(struct hashmap *map, struct hashmap_entry *entry) { - unsigned int b = bucket(map, entry); + unsigned int b; + + if (!map->table) + alloc_table(map, HASHMAP_INITIAL_SIZE); + b = bucket(map, entry); /* add entry */ entry->next = map->table[b]; map->table[b] = entry; @@ -230,7 +238,11 @@ struct hashmap_entry *hashmap_remove(struct hashmap *map, const void *keydata) { struct hashmap_entry *old; - struct hashmap_entry **e = find_entry_ptr(map, key, keydata); + struct hashmap_entry **e; + + if (!map->table) + return NULL; + e = find_entry_ptr(map, key, keydata); if (!*e) return NULL; diff --git a/hashmap.h b/hashmap.h index 904f61d6e1..3b0f2bcade 100644 --- a/hashmap.h +++ b/hashmap.h @@ -210,6 +210,9 @@ struct hashmap { /* hashmap functions */ +#define HASHMAP_INIT(fn, data) { .cmpfn = fn, .cmpfn_data = data, \ + .do_count_items = 1 } + /* * Initializes a hashmap structure. * From patchwork Wed Nov 11 20:02:10 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 11898459 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-9.6 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_PATCH,MAILING_LIST_MULTI,SIGNED_OFF_BY, SPF_HELO_NONE,SPF_PASS autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 92AD8C5517A for ; Wed, 11 Nov 2020 20:02:42 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 3BCCB2087D for ; Wed, 11 Nov 2020 20:02:42 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="ZT4M+fRy" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727812AbgKKUCb (ORCPT ); Wed, 11 Nov 2020 15:02:31 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:57942 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727682AbgKKUC3 (ORCPT ); Wed, 11 Nov 2020 15:02:29 -0500 Received: from mail-wm1-x344.google.com (mail-wm1-x344.google.com [IPv6:2a00:1450:4864:20::344]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id D6230C0613D1 for ; Wed, 11 Nov 2020 12:02:28 -0800 (PST) Received: by mail-wm1-x344.google.com with SMTP id a3so3443797wmb.5 for ; Wed, 11 Nov 2020 12:02:28 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=message-id:in-reply-to:references:from:date:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=hz04PDbA9UEQiHo/9pZvZ4q4Euew0clND1poGrjjarc=; b=ZT4M+fRy6KORs+1LA+LzHUEBMYAazuWFOdNctJwVqW+SIhn44v9H71Vlscq+Kpz/gg FIUA4P5RCsZf9L09sWC7sVYajQjy3a+gAh0cP3R5o7kelMglP96Sd+YNO+JU2EEI4Xut nCl5x47y90uK0T+cGhgho9t/L6umvE7PAyd13zy675hW7DaT6NJTjLI7VAYE2DgUUOFj kY6zCC0gW6yiDLR0zDgqdQx5H6rbhGXFozDK++KLyJIo7h38Xt7r0SPD/rkiAq6DTkt2 y7AhiggWA8EGsWtoAayHtO8f7PMN6KelGiR8sUL5KTbmynz0kL7gZ+yB5jCWxCZyolCL 5oOA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:message-id:in-reply-to:references:from:date :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=hz04PDbA9UEQiHo/9pZvZ4q4Euew0clND1poGrjjarc=; b=Eiv3gvCPjk9m+0+ROXshd6MtuKCLz+xnU1jUgKci68o67hpGCdmtSlb5JRz2kYV2iH ZWbqkWJBor9py2gbGkSoJmznzWL3v7ELMeCfkeJ/EjS9iQir1y2sdMVrr/JUznvdgLpT zLxMfJFezE8cPs3DZgFgBAonbdtqezFPnN+4RgzEbpE0+DMm2rbYluv4QFculETrqKx0 FV0bhfGNADatTWmIyMCZb0c/sRA/tu3pwLDoebdSqZcAEjetlLifiwt32wN+mT0LjESo syIQQ6SLFvUlf0f/Q7KBNx/btjftd6x0aE5NOYoRnkF7ABf+Na6tQqoFAOGrYObciQoy awJw== X-Gm-Message-State: AOAM533NeOqio3X1azfX/iGWlDRZ+hDLh3TutUIbsf+wX6mO5a3MqOs7 yqr9B0penSC8+VIxkVVVpFSY66J+Cos= X-Google-Smtp-Source: ABdhPJwSNKPR9h6WEJ+LXPNjYIl7wCr1vje8xD0k0ei+VyNVnetGa84SjgSa9tmvj/FLxbhEWgYNrQ== X-Received: by 2002:a1c:2cd7:: with SMTP id s206mr5609855wms.182.1605124947413; Wed, 11 Nov 2020 12:02:27 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id t5sm3810676wmg.19.2020.11.11.12.02.26 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 11 Nov 2020 12:02:26 -0800 (PST) Message-Id: <61f1da3c51b521035ba728c025cd6a28397f8051.1605124942.git.gitgitgadget@gmail.com> In-Reply-To: References: Date: Wed, 11 Nov 2020 20:02:10 +0000 Subject: [PATCH v6 04/15] hashmap: introduce a new hashmap_partial_clear() Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Jeff King , Elijah Newren , Phillip Wood , Elijah Newren , Elijah Newren Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Elijah Newren From: Elijah Newren merge-ort is a heavy user of strmaps, which are built on hashmap.[ch]. clear_or_reinit_internal_opts() in merge-ort was taking about 12% of overall runtime in my testcase involving rebasing 35 patches of linux.git across a big rename. clear_or_reinit_internal_opts() was calling hashmap_free() followed by hashmap_init(), meaning that not only was it freeing all the memory associated with each of the strmaps just to immediately allocate a new array again, it was allocating a new array that was likely smaller than needed (thus resulting in later need to rehash things). The ending size of the map table on the previous commit was likely almost perfectly sized for the next commit we wanted to pick, and not dropping and reallocating the table immediately is a win. Add some new API to hashmap to clear a hashmap of entries without freeing map->table (and instead only zeroing it out like alloc_table() would do, along with zeroing the count of items in the table and the shrink_at field). Signed-off-by: Elijah Newren --- hashmap.c | 39 +++++++++++++++++++++++++++------------ hashmap.h | 13 ++++++++++++- 2 files changed, 39 insertions(+), 13 deletions(-) diff --git a/hashmap.c b/hashmap.c index bb7c9979b8..922ed07954 100644 --- a/hashmap.c +++ b/hashmap.c @@ -174,22 +174,37 @@ void hashmap_init(struct hashmap *map, hashmap_cmp_fn equals_function, map->do_count_items = 1; } +static void free_individual_entries(struct hashmap *map, ssize_t entry_offset) +{ + struct hashmap_iter iter; + struct hashmap_entry *e; + + hashmap_iter_init(map, &iter); + while ((e = hashmap_iter_next(&iter))) + /* + * like container_of, but using caller-calculated + * offset (caller being hashmap_free_entries) + */ + free((char *)e - entry_offset); +} + +void hashmap_partial_clear_(struct hashmap *map, ssize_t entry_offset) +{ + if (!map || !map->table) + return; + if (entry_offset >= 0) /* called by hashmap_clear_entries */ + free_individual_entries(map, entry_offset); + memset(map->table, 0, map->tablesize * sizeof(struct hashmap_entry *)); + map->shrink_at = 0; + map->private_size = 0; +} + void hashmap_free_(struct hashmap *map, ssize_t entry_offset) { if (!map || !map->table) return; - if (entry_offset >= 0) { /* called by hashmap_free_entries */ - struct hashmap_iter iter; - struct hashmap_entry *e; - - hashmap_iter_init(map, &iter); - while ((e = hashmap_iter_next(&iter))) - /* - * like container_of, but using caller-calculated - * offset (caller being hashmap_free_entries) - */ - free((char *)e - entry_offset); - } + if (entry_offset >= 0) /* called by hashmap_free_entries */ + free_individual_entries(map, entry_offset); free(map->table); memset(map, 0, sizeof(*map)); } diff --git a/hashmap.h b/hashmap.h index 3b0f2bcade..e9430d582a 100644 --- a/hashmap.h +++ b/hashmap.h @@ -235,7 +235,8 @@ void hashmap_init(struct hashmap *map, const void *equals_function_data, size_t initial_size); -/* internal function for freeing hashmap */ +/* internal functions for clearing or freeing hashmap */ +void hashmap_partial_clear_(struct hashmap *map, ssize_t offset); void hashmap_free_(struct hashmap *map, ssize_t offset); /* @@ -268,6 +269,16 @@ void hashmap_free_(struct hashmap *map, ssize_t offset); */ #define hashmap_free(map) hashmap_free_(map, -1) +/* + * Basically the same as calling hashmap_free() followed by hashmap_init(), + * but doesn't incur the overhead of deallocating and reallocating + * map->table; it leaves map->table allocated and the same size but zeroes + * it out so it's ready for use again as an empty map. As with + * hashmap_free(), you may need to free the entries yourself before calling + * this function. + */ +#define hashmap_partial_clear(map) hashmap_partial_clear_(map, -1) + /* * Frees @map and all entries. @type is the struct type of the entry * where @member is the hashmap_entry struct used to associate with @map. From patchwork Wed Nov 11 20:02:11 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 11898441 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-9.6 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_PATCH,MAILING_LIST_MULTI,SIGNED_OFF_BY, SPF_HELO_NONE,SPF_PASS,URIBL_BLOCKED autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id CDA8DC388F9 for ; Wed, 11 Nov 2020 20:02:33 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 65B132087D for ; Wed, 11 Nov 2020 20:02:33 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="ElYeSSyP" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727843AbgKKUCc (ORCPT ); Wed, 11 Nov 2020 15:02:32 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:57944 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727617AbgKKUCa (ORCPT ); Wed, 11 Nov 2020 15:02:30 -0500 Received: from mail-wr1-x443.google.com (mail-wr1-x443.google.com [IPv6:2a00:1450:4864:20::443]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 0BDD4C0613D1 for ; Wed, 11 Nov 2020 12:02:30 -0800 (PST) Received: by mail-wr1-x443.google.com with SMTP id d12so3688904wrr.13 for ; Wed, 11 Nov 2020 12:02:29 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=message-id:in-reply-to:references:from:date:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=eD1ODDn8YazYa2TxKvej2ageSWRW9od1dWKHaSlyndc=; b=ElYeSSyPfr3Y48QAOgOESeLh6VqSH+QckVyEonFzgFXUvw8TANgPp1BMcm357vaJW8 Z4RQ9StOTF3IndZEbbjKLUyaYoQ5YbK0soZ3pVeQqRDluJZJoK29poU1Vle3uaocSuIj ITmU8D86ogEXlleJMkNVE+pdW3cRhBN1wH6Pd5x2r8KYIxuNUgGbbamNQrrQyhPlJVk2 +IXosO1JmZygo7+gLdusppcTBXvL2mY/mR+ZTUMhpsWYFod6qulTU17o9qAjgpO9cyWD ZYVImkvq11f9oYdbM2P/6ia555JEMklFc7P4DZCov4bzZGD9S+RWu09yRTug3nsvBkj/ H0jw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:message-id:in-reply-to:references:from:date :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=eD1ODDn8YazYa2TxKvej2ageSWRW9od1dWKHaSlyndc=; b=hO9U03TcQ1kWUkxn85km9og8U8pEC+vvQmNBJ4hdVaLSpkq6yslOuhUFLWYwv//DNx 1owfFZgyUNpgiuIRrDcdKF/suZjPai9CqSEW0H/MqVp5DlhCBt37TNLsTexjuRZg4V3X GKzO7+D9g6kixAgQbQYR+YsXFwZmurcZSFLFaXTZlxb3btKZzNHHOpHwSwSnFj21ZD1O 8Sbnt5AbBMhQvrc8D/lX/LbJgaTOqinNQRRzfd/PMVzIXBWFo7RHRdePEmdqZ4TH9fyT F8CKdMBKfU1JPJDqiKg7Ko8/jCQyQOllOmLlCMeNIR3VHVecs0BJOVt56zIcRnJ6PBP+ DsdA== X-Gm-Message-State: AOAM533hs1ZmlInbKvw/4RS0/Ufb8dIE7sdrz8Twv/ANS//muOyWr1lo fu+rbiRifSklABDUGdXfHR6UcfqOMfk= X-Google-Smtp-Source: ABdhPJznfvAtEja8h1BsmBKS1Fruyjl4ztlNIZLceN5PJ1repXYAQ60f7bGqEWKzNBqIgscQo4Lq9A== X-Received: by 2002:adf:e6cf:: with SMTP id y15mr21926858wrm.403.1605124948280; Wed, 11 Nov 2020 12:02:28 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id m126sm3768386wmm.0.2020.11.11.12.02.27 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 11 Nov 2020 12:02:27 -0800 (PST) Message-Id: <861e8d65ae8065595d9d4ccff5f70155fec408c9.1605124942.git.gitgitgadget@gmail.com> In-Reply-To: References: Date: Wed, 11 Nov 2020 20:02:11 +0000 Subject: [PATCH v6 05/15] hashmap: provide deallocation function names Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Jeff King , Elijah Newren , Phillip Wood , Elijah Newren , Elijah Newren Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Elijah Newren From: Elijah Newren hashmap_free(), hashmap_free_entries(), and hashmap_free_() have existed for a while, but aren't necessarily the clearest names, especially with hashmap_partial_clear() being added to the mix and lazy-initialization now being supported. Peff suggested we adopt the following names[1]: - hashmap_clear() - remove all entries and de-allocate any hashmap-specific data, but be ready for reuse - hashmap_clear_and_free() - ditto, but free the entries themselves - hashmap_partial_clear() - remove all entries but don't deallocate table - hashmap_partial_clear_and_free() - ditto, but free the entries This patch provides the new names and converts all existing callers over to the new naming scheme. [1] https://lore.kernel.org/git/20201030125059.GA3277724@coredump.intra.peff.net/ Signed-off-by: Elijah Newren --- add-interactive.c | 2 +- blame.c | 2 +- bloom.c | 2 +- builtin/fetch.c | 6 +++--- builtin/shortlog.c | 2 +- config.c | 2 +- diff.c | 4 ++-- diffcore-rename.c | 2 +- dir.c | 8 ++++---- hashmap.c | 6 +++--- hashmap.h | 44 +++++++++++++++++++++++++---------------- merge-recursive.c | 6 +++--- name-hash.c | 4 ++-- object.c | 2 +- oidmap.c | 2 +- patch-ids.c | 2 +- range-diff.c | 2 +- ref-filter.c | 2 +- revision.c | 2 +- sequencer.c | 4 ++-- submodule-config.c | 4 ++-- t/helper/test-hashmap.c | 6 +++--- 22 files changed, 63 insertions(+), 53 deletions(-) diff --git a/add-interactive.c b/add-interactive.c index 555c4abf32..a14c0feaa2 100644 --- a/add-interactive.c +++ b/add-interactive.c @@ -557,7 +557,7 @@ static int get_modified_files(struct repository *r, if (ps) clear_pathspec(&rev.prune_data); } - hashmap_free_entries(&s.file_map, struct pathname_entry, ent); + hashmap_clear_and_free(&s.file_map, struct pathname_entry, ent); if (unmerged_count) *unmerged_count = s.unmerged_count; if (binary_count) diff --git a/blame.c b/blame.c index 686845b2b4..229beb6452 100644 --- a/blame.c +++ b/blame.c @@ -435,7 +435,7 @@ static void get_fingerprint(struct fingerprint *result, static void free_fingerprint(struct fingerprint *f) { - hashmap_free(&f->map); + hashmap_clear(&f->map); free(f->entries); } diff --git a/bloom.c b/bloom.c index 68c73200a5..719c313a1c 100644 --- a/bloom.c +++ b/bloom.c @@ -287,7 +287,7 @@ struct bloom_filter *get_or_compute_bloom_filter(struct repository *r, } cleanup: - hashmap_free_entries(&pathmap, struct pathmap_hash_entry, entry); + hashmap_clear_and_free(&pathmap, struct pathmap_hash_entry, entry); } else { for (i = 0; i < diff_queued_diff.nr; i++) diff_free_filepair(diff_queued_diff.queue[i]); diff --git a/builtin/fetch.c b/builtin/fetch.c index f9c3c49f14..ecf8537605 100644 --- a/builtin/fetch.c +++ b/builtin/fetch.c @@ -393,7 +393,7 @@ static void find_non_local_tags(const struct ref *refs, item = refname_hash_add(&remote_refs, ref->name, &ref->old_oid); string_list_insert(&remote_refs_list, ref->name); } - hashmap_free_entries(&existing_refs, struct refname_hash_entry, ent); + hashmap_clear_and_free(&existing_refs, struct refname_hash_entry, ent); /* * We may have a final lightweight tag that needs to be @@ -428,7 +428,7 @@ static void find_non_local_tags(const struct ref *refs, **tail = rm; *tail = &rm->next; } - hashmap_free_entries(&remote_refs, struct refname_hash_entry, ent); + hashmap_clear_and_free(&remote_refs, struct refname_hash_entry, ent); string_list_clear(&remote_refs_list, 0); oidset_clear(&fetch_oids); } @@ -573,7 +573,7 @@ static struct ref *get_ref_map(struct remote *remote, } } if (existing_refs_populated) - hashmap_free_entries(&existing_refs, struct refname_hash_entry, ent); + hashmap_clear_and_free(&existing_refs, struct refname_hash_entry, ent); return ref_map; } diff --git a/builtin/shortlog.c b/builtin/shortlog.c index 0a5c4968f6..83f0a739b4 100644 --- a/builtin/shortlog.c +++ b/builtin/shortlog.c @@ -220,7 +220,7 @@ static void strset_clear(struct strset *ss) { if (!ss->map.table) return; - hashmap_free_entries(&ss->map, struct strset_item, ent); + hashmap_clear_and_free(&ss->map, struct strset_item, ent); } static void insert_records_from_trailers(struct shortlog *log, diff --git a/config.c b/config.c index 2bdff4457b..8f324ed3a6 100644 --- a/config.c +++ b/config.c @@ -1963,7 +1963,7 @@ void git_configset_clear(struct config_set *cs) free(entry->key); string_list_clear(&entry->value_list, 1); } - hashmap_free_entries(&cs->config_hash, struct config_set_element, ent); + hashmap_clear_and_free(&cs->config_hash, struct config_set_element, ent); cs->hash_initialized = 0; free(cs->list.items); cs->list.nr = 0; diff --git a/diff.c b/diff.c index 2bb2f8f57e..8e0e59f5cf 100644 --- a/diff.c +++ b/diff.c @@ -6289,9 +6289,9 @@ static void diff_flush_patch_all_file_pairs(struct diff_options *o) if (o->color_moved == COLOR_MOVED_ZEBRA_DIM) dim_moved_lines(o); - hashmap_free_entries(&add_lines, struct moved_entry, + hashmap_clear_and_free(&add_lines, struct moved_entry, ent); - hashmap_free_entries(&del_lines, struct moved_entry, + hashmap_clear_and_free(&del_lines, struct moved_entry, ent); } diff --git a/diffcore-rename.c b/diffcore-rename.c index 99e63e90f8..d367a6d244 100644 --- a/diffcore-rename.c +++ b/diffcore-rename.c @@ -407,7 +407,7 @@ static int find_exact_renames(struct diff_options *options) renames += find_identical_files(&file_table, i, options); /* Free the hash data structure and entries */ - hashmap_free_entries(&file_table, struct file_similarity, entry); + hashmap_clear_and_free(&file_table, struct file_similarity, entry); return renames; } diff --git a/dir.c b/dir.c index 78387110e6..161dce121e 100644 --- a/dir.c +++ b/dir.c @@ -817,8 +817,8 @@ static void add_pattern_to_hashsets(struct pattern_list *pl, struct path_pattern clear_hashmaps: warning(_("disabling cone pattern matching")); - hashmap_free_entries(&pl->parent_hashmap, struct pattern_entry, ent); - hashmap_free_entries(&pl->recursive_hashmap, struct pattern_entry, ent); + hashmap_clear_and_free(&pl->parent_hashmap, struct pattern_entry, ent); + hashmap_clear_and_free(&pl->recursive_hashmap, struct pattern_entry, ent); pl->use_cone_patterns = 0; } @@ -921,8 +921,8 @@ void clear_pattern_list(struct pattern_list *pl) free(pl->patterns[i]); free(pl->patterns); free(pl->filebuf); - hashmap_free_entries(&pl->recursive_hashmap, struct pattern_entry, ent); - hashmap_free_entries(&pl->parent_hashmap, struct pattern_entry, ent); + hashmap_clear_and_free(&pl->recursive_hashmap, struct pattern_entry, ent); + hashmap_clear_and_free(&pl->parent_hashmap, struct pattern_entry, ent); memset(pl, 0, sizeof(*pl)); } diff --git a/hashmap.c b/hashmap.c index 922ed07954..5009471800 100644 --- a/hashmap.c +++ b/hashmap.c @@ -183,7 +183,7 @@ static void free_individual_entries(struct hashmap *map, ssize_t entry_offset) while ((e = hashmap_iter_next(&iter))) /* * like container_of, but using caller-calculated - * offset (caller being hashmap_free_entries) + * offset (caller being hashmap_clear_and_free) */ free((char *)e - entry_offset); } @@ -199,11 +199,11 @@ void hashmap_partial_clear_(struct hashmap *map, ssize_t entry_offset) map->private_size = 0; } -void hashmap_free_(struct hashmap *map, ssize_t entry_offset) +void hashmap_clear_(struct hashmap *map, ssize_t entry_offset) { if (!map || !map->table) return; - if (entry_offset >= 0) /* called by hashmap_free_entries */ + if (entry_offset >= 0) /* called by hashmap_clear_and_free */ free_individual_entries(map, entry_offset); free(map->table); memset(map, 0, sizeof(*map)); diff --git a/hashmap.h b/hashmap.h index e9430d582a..7251687d73 100644 --- a/hashmap.h +++ b/hashmap.h @@ -96,7 +96,7 @@ * } * * if (!strcmp("end", action)) { - * hashmap_free_entries(&map, struct long2string, ent); + * hashmap_clear_and_free(&map, struct long2string, ent); * break; * } * } @@ -237,7 +237,7 @@ void hashmap_init(struct hashmap *map, /* internal functions for clearing or freeing hashmap */ void hashmap_partial_clear_(struct hashmap *map, ssize_t offset); -void hashmap_free_(struct hashmap *map, ssize_t offset); +void hashmap_clear_(struct hashmap *map, ssize_t offset); /* * Frees a hashmap structure and allocated memory for the table, but does not @@ -253,40 +253,50 @@ void hashmap_free_(struct hashmap *map, ssize_t offset); * free(e->somefield); * free(e); * } - * hashmap_free(map); + * hashmap_clear(map); * * instead of * * hashmap_for_each_entry(map, hashmap_iter, e, hashmap_entry_name) { * free(e->somefield); * } - * hashmap_free_entries(map, struct my_entry_struct, hashmap_entry_name); + * hashmap_clear_and_free(map, struct my_entry_struct, hashmap_entry_name); * * to avoid the implicit extra loop over the entries. However, if there are * no special fields in your entry that need to be freed beyond the entry * itself, it is probably simpler to avoid the explicit loop and just call - * hashmap_free_entries(). + * hashmap_clear_and_free(). */ -#define hashmap_free(map) hashmap_free_(map, -1) +#define hashmap_clear(map) hashmap_clear_(map, -1) /* - * Basically the same as calling hashmap_free() followed by hashmap_init(), - * but doesn't incur the overhead of deallocating and reallocating - * map->table; it leaves map->table allocated and the same size but zeroes - * it out so it's ready for use again as an empty map. As with - * hashmap_free(), you may need to free the entries yourself before calling - * this function. + * Similar to hashmap_clear(), except that the table is no deallocated; it + * is merely zeroed out but left the same size as before. If the hashmap + * will be reused, this avoids the overhead of deallocating and + * reallocating map->table. As with hashmap_clear(), you may need to free + * the entries yourself before calling this function. */ #define hashmap_partial_clear(map) hashmap_partial_clear_(map, -1) /* - * Frees @map and all entries. @type is the struct type of the entry - * where @member is the hashmap_entry struct used to associate with @map. + * Similar to hashmap_clear() but also frees all entries. @type is the + * struct type of the entry where @member is the hashmap_entry struct used + * to associate with @map. * - * See usage note above hashmap_free(). + * See usage note above hashmap_clear(). */ -#define hashmap_free_entries(map, type, member) \ - hashmap_free_(map, offsetof(type, member)); +#define hashmap_clear_and_free(map, type, member) \ + hashmap_clear_(map, offsetof(type, member)) + +/* + * Similar to hashmap_partial_clear() but also frees all entries. @type is + * the struct type of the entry where @member is the hashmap_entry struct + * used to associate with @map. + * + * See usage note above hashmap_clear(). + */ +#define hashmap_partial_clear_and_free(map, type, member) \ + hashmap_partial_clear_(map, offsetof(type, member)) /* hashmap_entry functions */ diff --git a/merge-recursive.c b/merge-recursive.c index d0214335a7..f736a0f632 100644 --- a/merge-recursive.c +++ b/merge-recursive.c @@ -2651,7 +2651,7 @@ static struct string_list *get_renames(struct merge_options *opt, free(e->target_file); string_list_clear(&e->source_files, 0); } - hashmap_free_entries(&collisions, struct collision_entry, ent); + hashmap_clear_and_free(&collisions, struct collision_entry, ent); return renames; } @@ -2870,7 +2870,7 @@ static void initial_cleanup_rename(struct diff_queue_struct *pairs, strbuf_release(&e->new_dir); /* possible_new_dirs already cleared in get_directory_renames */ } - hashmap_free_entries(dir_renames, struct dir_rename_entry, ent); + hashmap_clear_and_free(dir_renames, struct dir_rename_entry, ent); free(dir_renames); free(pairs->queue); @@ -3497,7 +3497,7 @@ static int merge_trees_internal(struct merge_options *opt, string_list_clear(entries, 1); free(entries); - hashmap_free_entries(&opt->priv->current_file_dir_set, + hashmap_clear_and_free(&opt->priv->current_file_dir_set, struct path_hashmap_entry, e); if (clean < 0) { diff --git a/name-hash.c b/name-hash.c index fb526a3775..5d3c7b12c1 100644 --- a/name-hash.c +++ b/name-hash.c @@ -726,6 +726,6 @@ void free_name_hash(struct index_state *istate) return; istate->name_hash_initialized = 0; - hashmap_free(&istate->name_hash); - hashmap_free_entries(&istate->dir_hash, struct dir_entry, ent); + hashmap_clear(&istate->name_hash); + hashmap_clear_and_free(&istate->dir_hash, struct dir_entry, ent); } diff --git a/object.c b/object.c index 3257518656..b8406409d5 100644 --- a/object.c +++ b/object.c @@ -532,7 +532,7 @@ void raw_object_store_clear(struct raw_object_store *o) close_object_store(o); o->packed_git = NULL; - hashmap_free(&o->pack_map); + hashmap_clear(&o->pack_map); } void parsed_object_pool_clear(struct parsed_object_pool *o) diff --git a/oidmap.c b/oidmap.c index 423aa014a3..286a04a53c 100644 --- a/oidmap.c +++ b/oidmap.c @@ -27,7 +27,7 @@ void oidmap_free(struct oidmap *map, int free_entries) return; /* TODO: make oidmap itself not depend on struct layouts */ - hashmap_free_(&map->map, free_entries ? 0 : -1); + hashmap_clear_(&map->map, free_entries ? 0 : -1); } void *oidmap_get(const struct oidmap *map, const struct object_id *key) diff --git a/patch-ids.c b/patch-ids.c index 12aa6d494b..21973e4933 100644 --- a/patch-ids.c +++ b/patch-ids.c @@ -71,7 +71,7 @@ int init_patch_ids(struct repository *r, struct patch_ids *ids) int free_patch_ids(struct patch_ids *ids) { - hashmap_free_entries(&ids->patches, struct patch_id, ent); + hashmap_clear_and_free(&ids->patches, struct patch_id, ent); return 0; } diff --git a/range-diff.c b/range-diff.c index 24dc435e48..befeecae44 100644 --- a/range-diff.c +++ b/range-diff.c @@ -266,7 +266,7 @@ static void find_exact_matches(struct string_list *a, struct string_list *b) } } - hashmap_free(&map); + hashmap_clear(&map); } static void diffsize_consume(void *data, char *line, unsigned long len) diff --git a/ref-filter.c b/ref-filter.c index c62f6b4822..5e66b8cd76 100644 --- a/ref-filter.c +++ b/ref-filter.c @@ -2222,7 +2222,7 @@ void ref_array_clear(struct ref_array *array) used_atom_cnt = 0; if (ref_to_worktree_map.worktrees) { - hashmap_free_entries(&(ref_to_worktree_map.map), + hashmap_clear_and_free(&(ref_to_worktree_map.map), struct ref_to_worktree_entry, ent); free_worktrees(ref_to_worktree_map.worktrees); ref_to_worktree_map.worktrees = NULL; diff --git a/revision.c b/revision.c index aa62212040..f27649d45d 100644 --- a/revision.c +++ b/revision.c @@ -139,7 +139,7 @@ static void paths_and_oids_clear(struct hashmap *map) free(entry->path); } - hashmap_free_entries(map, struct path_and_oids_entry, ent); + hashmap_clear_and_free(map, struct path_and_oids_entry, ent); } static void paths_and_oids_insert(struct hashmap *map, diff --git a/sequencer.c b/sequencer.c index 00acb12496..23a09c3e7a 100644 --- a/sequencer.c +++ b/sequencer.c @@ -5058,7 +5058,7 @@ static int make_script_with_merges(struct pretty_print_context *pp, oidmap_free(&commit2todo, 1); oidmap_free(&state.commit2label, 1); - hashmap_free_entries(&state.labels, struct labels_entry, entry); + hashmap_clear_and_free(&state.labels, struct labels_entry, entry); strbuf_release(&state.buf); return 0; @@ -5577,7 +5577,7 @@ int todo_list_rearrange_squash(struct todo_list *todo_list) for (i = 0; i < todo_list->nr; i++) free(subjects[i]); free(subjects); - hashmap_free_entries(&subject2item, struct subject2item_entry, entry); + hashmap_clear_and_free(&subject2item, struct subject2item_entry, entry); clear_commit_todo_item(&commit_todo); diff --git a/submodule-config.c b/submodule-config.c index c569e22aa3..f502505566 100644 --- a/submodule-config.c +++ b/submodule-config.c @@ -103,8 +103,8 @@ static void submodule_cache_clear(struct submodule_cache *cache) ent /* member name */) free_one_config(entry); - hashmap_free_entries(&cache->for_path, struct submodule_entry, ent); - hashmap_free_entries(&cache->for_name, struct submodule_entry, ent); + hashmap_clear_and_free(&cache->for_path, struct submodule_entry, ent); + hashmap_clear_and_free(&cache->for_name, struct submodule_entry, ent); cache->initialized = 0; cache->gitmodules_read = 0; } diff --git a/t/helper/test-hashmap.c b/t/helper/test-hashmap.c index f38706216f..2475663b49 100644 --- a/t/helper/test-hashmap.c +++ b/t/helper/test-hashmap.c @@ -110,7 +110,7 @@ static void perf_hashmap(unsigned int method, unsigned int rounds) hashmap_add(&map, &entries[i]->ent); } - hashmap_free(&map); + hashmap_clear(&map); } } else { /* test map lookups */ @@ -130,7 +130,7 @@ static void perf_hashmap(unsigned int method, unsigned int rounds) } } - hashmap_free(&map); + hashmap_clear(&map); } } @@ -262,6 +262,6 @@ int cmd__hashmap(int argc, const char **argv) } strbuf_release(&line); - hashmap_free_entries(&map, struct test_entry, ent); + hashmap_clear_and_free(&map, struct test_entry, ent); return 0; } From patchwork Wed Nov 11 20:02:12 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 11898439 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-9.6 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_PATCH,MAILING_LIST_MULTI,SIGNED_OFF_BY, SPF_HELO_NONE,SPF_PASS autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 2B625C5517A for ; Wed, 11 Nov 2020 20:02:33 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id CF8D72087D for ; Wed, 11 Nov 2020 20:02:32 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="BF8QeAQO" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727835AbgKKUCb (ORCPT ); Wed, 11 Nov 2020 15:02:31 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:57950 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727768AbgKKUCa (ORCPT ); Wed, 11 Nov 2020 15:02:30 -0500 Received: from mail-wr1-x443.google.com (mail-wr1-x443.google.com [IPv6:2a00:1450:4864:20::443]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 74059C0613D4 for ; Wed, 11 Nov 2020 12:02:30 -0800 (PST) Received: by mail-wr1-x443.google.com with SMTP id s8so3704695wrw.10 for ; Wed, 11 Nov 2020 12:02:30 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=message-id:in-reply-to:references:from:date:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=oEYc2S4ksSfmtDUY2461bdvZotWwPmh9voOUaSelCBs=; b=BF8QeAQONFZfbbgj3G3+EqmsZvbFmYZOZ7zr2qWnxlR7mvCsOYx5hc2/216qH2HL7N ZvotK6cGgRqGgqJC6WdGVe68MqhHggLFiyHTzT7Cep+hoKpkGTIKP4oh1o3XeBajApTz 5G9n9hHsuVIpYOdPo77E6hqPk3eRrtLRC17U/0ogHoMNa4vik3XEZUHTQFuUttKSKh+Q uyTnM16IS7by07tqWlgINoiqyA6yvk4LOXI/5BzgTp6NLtA0Md1AJWvTzi87Fbf+yfd4 BeJNXYR0niUianX5q2mRsrXNAjjgZ/WMCDMBv69/cSriz3JbVIpCF+JmvZ7LHjQgIwfY 5TNA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:message-id:in-reply-to:references:from:date :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=oEYc2S4ksSfmtDUY2461bdvZotWwPmh9voOUaSelCBs=; b=sApOcSAE0dMeEbjJOvOdC8wRAiHv4dolfgdm5u0Sh0596GTRXWSL1pNupdMRmoMKpL 5abkvusLKV3F+kIvph9PnqZpg2QbtO4IKUJR4oai3kzpQBkd8IozIHUuP0qMb6IgSZo9 8iFQcy08cuuygiiqRpoP68VvZav6zYUwowuvUgp3yCgi3Lob+rBfMB1zLrL9dT+5otCx Ck87uvLCUpAa7B0zfyxuJ/PrGBQhTRzU53qxSSucLSCnObua6qi3GvdAGk7GSAWD60Ka JBrNvGyiKAxmqGkx9ORKjgjQhP4Jr3R1CZtcO3M/tl6uzFPUG/YNhCCzFLMvwnIWvAtD zbHQ== X-Gm-Message-State: AOAM531uc/PH1vzCeZW2Mmv/dC+819azI0UfZjZen3p2ndvzj/XMq3mN BAqQRXzBA2W46TvMwHSp5gnfIuCmpjo= X-Google-Smtp-Source: ABdhPJy13Ey/LekHz6PXnV5FG/jnMQPm7z0brJiDLHCfYgpHDN+XbRnZuBy+S6plG+fCvEPW85PEkg== X-Received: by 2002:adf:93e5:: with SMTP id 92mr32163662wrp.421.1605124948977; Wed, 11 Nov 2020 12:02:28 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id w1sm3546451wro.44.2020.11.11.12.02.28 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 11 Nov 2020 12:02:28 -0800 (PST) Message-Id: <448d3b219ffebbc0daa4ef033d78fd45693c5ccd.1605124942.git.gitgitgadget@gmail.com> In-Reply-To: References: Date: Wed, 11 Nov 2020 20:02:12 +0000 Subject: [PATCH v6 06/15] strmap: new utility functions Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Jeff King , Elijah Newren , Phillip Wood , Elijah Newren , Elijah Newren Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Elijah Newren From: Elijah Newren Add strmap as a new struct and associated utility functions, specifically for hashmaps that map strings to some value. The API is taken directly from Peff's proposal at https://lore.kernel.org/git/20180906191203.GA26184@sigill.intra.peff.net/ Note that similar string-list, I have a strdup_strings setting. However, unlike string-list, strmap_init() does not take a parameter for this setting and instead automatically sets it to 1; callers who want to control this detail need to instead call strmap_init_with_options(). (Future patches will add additional parameters to strmap_init_with_options()). Signed-off-by: Elijah Newren --- Makefile | 1 + strmap.c | 99 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ strmap.h | 65 +++++++++++++++++++++++++++++++++++++ 3 files changed, 165 insertions(+) create mode 100644 strmap.c create mode 100644 strmap.h diff --git a/Makefile b/Makefile index 95571ee3fc..777a34c01c 100644 --- a/Makefile +++ b/Makefile @@ -1000,6 +1000,7 @@ LIB_OBJS += stable-qsort.o LIB_OBJS += strbuf.o LIB_OBJS += streaming.o LIB_OBJS += string-list.o +LIB_OBJS += strmap.o LIB_OBJS += strvec.o LIB_OBJS += sub-process.o LIB_OBJS += submodule-config.o diff --git a/strmap.c b/strmap.c new file mode 100644 index 0000000000..53f284eb20 --- /dev/null +++ b/strmap.c @@ -0,0 +1,99 @@ +#include "git-compat-util.h" +#include "strmap.h" + +int cmp_strmap_entry(const void *hashmap_cmp_fn_data, + const struct hashmap_entry *entry1, + const struct hashmap_entry *entry2, + const void *keydata) +{ + const struct strmap_entry *e1, *e2; + + e1 = container_of(entry1, const struct strmap_entry, ent); + e2 = container_of(entry2, const struct strmap_entry, ent); + return strcmp(e1->key, e2->key); +} + +static struct strmap_entry *find_strmap_entry(struct strmap *map, + const char *str) +{ + struct strmap_entry entry; + hashmap_entry_init(&entry.ent, strhash(str)); + entry.key = str; + return hashmap_get_entry(&map->map, &entry, ent, NULL); +} + +void strmap_init(struct strmap *map) +{ + strmap_init_with_options(map, 1); +} + +void strmap_init_with_options(struct strmap *map, + int strdup_strings) +{ + hashmap_init(&map->map, cmp_strmap_entry, NULL, 0); + map->strdup_strings = strdup_strings; +} + +static void strmap_free_entries_(struct strmap *map, int free_values) +{ + struct hashmap_iter iter; + struct strmap_entry *e; + + if (!map) + return; + + /* + * We need to iterate over the hashmap entries and free + * e->key and e->value ourselves; hashmap has no API to + * take care of that for us. Since we're already iterating over + * the hashmap, though, might as well free e too and avoid the need + * to make some call into the hashmap API to do that. + */ + hashmap_for_each_entry(&map->map, &iter, e, ent) { + if (free_values) + free(e->value); + if (map->strdup_strings) + free((char*)e->key); + free(e); + } +} + +void strmap_clear(struct strmap *map, int free_values) +{ + strmap_free_entries_(map, free_values); + hashmap_clear(&map->map); +} + +void *strmap_put(struct strmap *map, const char *str, void *data) +{ + struct strmap_entry *entry = find_strmap_entry(map, str); + void *old = NULL; + + if (entry) { + old = entry->value; + entry->value = data; + } else { + const char *key = str; + + entry = xmalloc(sizeof(*entry)); + hashmap_entry_init(&entry->ent, strhash(str)); + + if (map->strdup_strings) + key = xstrdup(str); + entry->key = key; + entry->value = data; + hashmap_add(&map->map, &entry->ent); + } + return old; +} + +void *strmap_get(struct strmap *map, const char *str) +{ + struct strmap_entry *entry = find_strmap_entry(map, str); + return entry ? entry->value : NULL; +} + +int strmap_contains(struct strmap *map, const char *str) +{ + return find_strmap_entry(map, str) != NULL; +} diff --git a/strmap.h b/strmap.h new file mode 100644 index 0000000000..96888c23ad --- /dev/null +++ b/strmap.h @@ -0,0 +1,65 @@ +#ifndef STRMAP_H +#define STRMAP_H + +#include "hashmap.h" + +struct strmap { + struct hashmap map; + unsigned int strdup_strings:1; +}; + +struct strmap_entry { + struct hashmap_entry ent; + const char *key; + void *value; +}; + +int cmp_strmap_entry(const void *hashmap_cmp_fn_data, + const struct hashmap_entry *entry1, + const struct hashmap_entry *entry2, + const void *keydata); + +#define STRMAP_INIT { \ + .map = HASHMAP_INIT(cmp_strmap_entry, NULL), \ + .strdup_strings = 1, \ + } + +/* + * Initialize the members of the strmap. Any keys added to the strmap will + * be strdup'ed with their memory managed by the strmap. + */ +void strmap_init(struct strmap *map); + +/* + * Same as strmap_init, but for those who want to control the memory management + * carefully instead of using the default of strdup_strings=1. + */ +void strmap_init_with_options(struct strmap *map, + int strdup_strings); + +/* + * Remove all entries from the map, releasing any allocated resources. + */ +void strmap_clear(struct strmap *map, int free_values); + +/* + * Insert "str" into the map, pointing to "data". + * + * If an entry for "str" already exists, its data pointer is overwritten, and + * the original data pointer returned. Otherwise, returns NULL. + */ +void *strmap_put(struct strmap *map, const char *str, void *data); + +/* + * Return the data pointer mapped by "str", or NULL if the entry does not + * exist. + */ +void *strmap_get(struct strmap *map, const char *str); + +/* + * Return non-zero iff "str" is present in the map. This differs from + * strmap_get() in that it can distinguish entries with a NULL data pointer. + */ +int strmap_contains(struct strmap *map, const char *str); + +#endif /* STRMAP_H */ From patchwork Wed Nov 11 20:02:13 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 11898461 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-9.6 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_PATCH,MAILING_LIST_MULTI,SIGNED_OFF_BY, SPF_HELO_NONE,SPF_PASS autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 49459C5517A for ; Wed, 11 Nov 2020 20:02:47 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id E40FD2087D for ; Wed, 11 Nov 2020 20:02:46 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="C9zCYs3B" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727889AbgKKUCo (ORCPT ); Wed, 11 Nov 2020 15:02:44 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:57952 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727815AbgKKUCb (ORCPT ); Wed, 11 Nov 2020 15:02:31 -0500 Received: from mail-wm1-x343.google.com (mail-wm1-x343.google.com [IPv6:2a00:1450:4864:20::343]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 250AEC0613D1 for ; Wed, 11 Nov 2020 12:02:31 -0800 (PST) Received: by mail-wm1-x343.google.com with SMTP id h62so3464298wme.3 for ; Wed, 11 Nov 2020 12:02:31 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=message-id:in-reply-to:references:from:date:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=LohV9wz4XDfYNIAtf11Guo8xRjkzYRDWgPPI+0a6uSM=; b=C9zCYs3BpmEQ6Lq78RjYDWBcUQ3ILzbZxWnMbBX4EwHBhBffSJONMKrsXjhYlKkFFq Jk3x9Z3iQ+VUBmUoe87dkKtYhKSxxL5ukRGC7pSrattajdg5TaTOjI+Lw7k6eAFNFM95 18j95xR6hM7hngxEP+8HRTgSTyGiqZcvGYluDMwaopRoH9/DrtUVzeulif6tFrZLzFJf JyGbMeGUFssUoEjjj1NP6NVk1HUUGT+pPyB33zvNWCQwjNctSfP7UrK9XdPhDhKpSblF CONWWyKWThu4tTHfrhkMHa4KSzsjE5lbYdazEgwROfYAuHtmTITpEdXWc7W9Iq1IMDjk qJbw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:message-id:in-reply-to:references:from:date :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=LohV9wz4XDfYNIAtf11Guo8xRjkzYRDWgPPI+0a6uSM=; b=kH4xxbFqMDztbrKI7/J4XYELtxWB0QLJTujVlJd5+Zh/DPy+FVrwxsKipyHUiAo10F tfY0M/LK2w+GTrBfTK8Z7MFOLu9aEbkMFFpNZ0W3DXcvgeHUmfW0jXEKpBrSXHu0PeWb fRfG36AjpW9nPXQRKgw1OGCaF1dMKx/taXXXWST+uGMaNUK1WogyNrGcbpHOOq0tVMV7 JyAlJKT+ts/WfPHfoPPt2U8lro4yZ5XciB2414PYnQwcFL/qpM/9Vr1CgLg8hyS80UVR 5ptyWfYRwme1pkBW1hbmznLaOJORM+xA62UFRPjRmmzbmAoT0P4/q7kalnZ1SNGsR/PJ RieA== X-Gm-Message-State: AOAM533DlKZYkCTfqUdSDm6tyi04wjBuEgeENeKW++lCXk3VVW0P5IrH DaGcfIiYx5mJ+7j/rLZtDSPJeEXubtk= X-Google-Smtp-Source: ABdhPJzSY9sGpcQVS4doozlYAkEHL3dRVaBSPOUecl03pKxdKKws5/1Qi/TFyFIxVwLWr0S5xLx7jA== X-Received: by 2002:a1c:20c6:: with SMTP id g189mr6200783wmg.6.1605124949716; Wed, 11 Nov 2020 12:02:29 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id t11sm3695357wmf.35.2020.11.11.12.02.29 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 11 Nov 2020 12:02:29 -0800 (PST) Message-Id: <5e8004c728580589cdaf46d755f2c977feaffb34.1605124942.git.gitgitgadget@gmail.com> In-Reply-To: References: Date: Wed, 11 Nov 2020 20:02:13 +0000 Subject: [PATCH v6 07/15] strmap: add more utility functions Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Jeff King , Elijah Newren , Phillip Wood , Elijah Newren , Elijah Newren Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Elijah Newren From: Elijah Newren This adds a number of additional convienence functions I want/need: * strmap_get_size() * strmap_empty() * strmap_remove() * strmap_for_each_entry() * strmap_get_entry() I suspect the first four are self-explanatory. strmap_get_entry() is similar to strmap_get() except that instead of just returning the void* value that the string maps to, it returns the strmap_entry that contains both the string and the void* value (or NULL if the string isn't in the map). This is helpful because it avoids multiple lookups, e.g. in some cases a caller would need to call: * strmap_contains() to check that the map has an entry for the string * strmap_get() to get the void* value * * strmap_put() to update/overwrite the value If the void* pointer returned really is a pointer, then the last step is unnecessary, but if the void* pointer is just cast to an integer then strmap_put() will be needed. In contrast, one can call strmap_get_entry() and then: * check if the string was in the map by whether the pointer is NULL * access the value via entry->value * directly update entry->value meaning that we can replace two or three hash table lookups with one. Signed-off-by: Elijah Newren --- strmap.c | 20 ++++++++++++++++++++ strmap.h | 34 ++++++++++++++++++++++++++++++++++ 2 files changed, 54 insertions(+) diff --git a/strmap.c b/strmap.c index 53f284eb20..829f1bc095 100644 --- a/strmap.c +++ b/strmap.c @@ -87,6 +87,11 @@ void *strmap_put(struct strmap *map, const char *str, void *data) return old; } +struct strmap_entry *strmap_get_entry(struct strmap *map, const char *str) +{ + return find_strmap_entry(map, str); +} + void *strmap_get(struct strmap *map, const char *str) { struct strmap_entry *entry = find_strmap_entry(map, str); @@ -97,3 +102,18 @@ int strmap_contains(struct strmap *map, const char *str) { return find_strmap_entry(map, str) != NULL; } + +void strmap_remove(struct strmap *map, const char *str, int free_value) +{ + struct strmap_entry entry, *ret; + hashmap_entry_init(&entry.ent, strhash(str)); + entry.key = str; + ret = hashmap_remove_entry(&map->map, &entry, ent, NULL); + if (!ret) + return; + if (free_value) + free(ret->value); + if (map->strdup_strings) + free((char*)ret->key); + free(ret); +} diff --git a/strmap.h b/strmap.h index 96888c23ad..f74bc582e4 100644 --- a/strmap.h +++ b/strmap.h @@ -50,6 +50,12 @@ void strmap_clear(struct strmap *map, int free_values); */ void *strmap_put(struct strmap *map, const char *str, void *data); +/* + * Return the strmap_entry mapped by "str", or NULL if there is not such + * an item in map. + */ +struct strmap_entry *strmap_get_entry(struct strmap *map, const char *str); + /* * Return the data pointer mapped by "str", or NULL if the entry does not * exist. @@ -62,4 +68,32 @@ void *strmap_get(struct strmap *map, const char *str); */ int strmap_contains(struct strmap *map, const char *str); +/* + * Remove the given entry from the strmap. If the string isn't in the + * strmap, the map is not altered. + */ +void strmap_remove(struct strmap *map, const char *str, int free_value); + +/* + * Return how many entries the strmap has. + */ +static inline unsigned int strmap_get_size(struct strmap *map) +{ + return hashmap_get_size(&map->map); +} + +/* + * Return whether the strmap is empty. + */ +static inline int strmap_empty(struct strmap *map) +{ + return strmap_get_size(map) == 0; +} + +/* + * iterate through @map using @iter, @var is a pointer to a type strmap_entry + */ +#define strmap_for_each_entry(mystrmap, iter, var) \ + hashmap_for_each_entry(&(mystrmap)->map, iter, var, ent) + #endif /* STRMAP_H */ From patchwork Wed Nov 11 20:02:14 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 11898447 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-9.6 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_PATCH,MAILING_LIST_MULTI,SIGNED_OFF_BY, SPF_HELO_NONE,SPF_PASS autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id D45A5C56201 for ; Wed, 11 Nov 2020 20:02:37 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 830C12087D for ; Wed, 11 Nov 2020 20:02:37 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="DA+KpdV5" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727858AbgKKUCf (ORCPT ); Wed, 11 Nov 2020 15:02:35 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:57956 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727768AbgKKUCc (ORCPT ); Wed, 11 Nov 2020 15:02:32 -0500 Received: from mail-wm1-x341.google.com (mail-wm1-x341.google.com [IPv6:2a00:1450:4864:20::341]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id D3887C0613D1 for ; Wed, 11 Nov 2020 12:02:31 -0800 (PST) Received: by mail-wm1-x341.google.com with SMTP id w24so3493842wmi.0 for ; Wed, 11 Nov 2020 12:02:31 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=message-id:in-reply-to:references:from:date:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=egrP2YxGIqUqE7lI0Iu1Sp/CnRg8F1CK39E/Ny45G70=; b=DA+KpdV5LrwJnygi82b18MnbwvjVJRSvZ6FmYS87mtjX422t/zTvoB3MgLlqBHMl1s 90SFE/v7oQcUPlD7iQAOuF2nx8MpvLkZYHEeXxH5GbOrx6nyv3mxhTnaqOoOi0sAmTkG P5qsaPz5P8YurV6MODp+1HQJ+KohVDC2IRtDEr/2Q0C53ydqLBF8kKsjqtPM4ESaXikf vCJq/TOlvdw9oTiHkO3TYMHAjIIScIVQsX+6BrwREqkrpc2ivZtULe5c9wGTXbzsSV6j U0I3f1lYKhguHYNu5F5j+P9AYIfBnxjzi8F0PabEEMWeNeAm5hi6PPfsxkNUKuscvT9l dMHw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:message-id:in-reply-to:references:from:date :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=egrP2YxGIqUqE7lI0Iu1Sp/CnRg8F1CK39E/Ny45G70=; b=AxcchNQ3ZCT5jfa5YnCriJaQ5XN2WbPTMGQlFpCN8kW9TLLlJO/Irmji8W5iS/CH3m VmE9mwuhH+JgnOPEv2L3YQNLG7Ko3XdKPN/VuwL4Wx6fpwv+xnOAZ3soLYTMYPrPfpVc rrLfHzMEcUP6vBW9CKG1Ag6NSHI4RDBkN4g3JKrqjfgNqQLV/Q5pvI5u9iKWSQwFCNDl /tiyGS1rRalyljhIqQWWeO33XAY5FkpQZKuWrIQtGePR1t1v2NYlb6aj+cd3NQjav6io cBAjFsJbLYFydxSpimIwpElW0YcG+2M0ebiEQGSzbUHTKF0S2Tyw3IS9K1qYOW4MH/y6 pssQ== X-Gm-Message-State: AOAM530Fm7G5hJpKmN2LMCjhzJ8/q9ExAQi4FZ06XnstgxIcxLaqt78t o8hS3um0Phzggl2deAIox0lEK3AhBWM= X-Google-Smtp-Source: ABdhPJzUzq5qe0uF3foSS/Y6FSe9hRCMMMSvvUqzbt9Ql0Q15S/uJdD1Nkem3f5cCi/lnIN9wA5hoA== X-Received: by 2002:a1c:2041:: with SMTP id g62mr1471651wmg.118.1605124950503; Wed, 11 Nov 2020 12:02:30 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id w21sm3628672wmi.29.2020.11.11.12.02.29 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 11 Nov 2020 12:02:30 -0800 (PST) Message-Id: In-Reply-To: References: Date: Wed, 11 Nov 2020 20:02:14 +0000 Subject: [PATCH v6 08/15] strmap: enable faster clearing and reusing of strmaps Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Jeff King , Elijah Newren , Phillip Wood , Elijah Newren , Elijah Newren Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Elijah Newren From: Elijah Newren When strmaps are used heavily, such as is done by my new merge-ort algorithm, and strmaps need to be cleared but then re-used (because of e.g. picking multiple commits to cherry-pick, or due to a recursive merge having several different merges while recursing), free-ing and reallocating map->table repeatedly can add up in time, especially since it will likely be reallocated to a much smaller size but the previous merge provides a good guide to the right size to use for the next merge. Introduce strmap_partial_clear() to take advantage of this type of situation; it will act similar to strmap_clear() except that map->table's entries are zeroed instead of map->table being free'd. Making use of this function reduced the cost of clear_or_reinit_internal_opts() by about 20% in mert-ort, and dropped the overall runtime of my rebase testcase by just under 2%. Signed-off-by: Elijah Newren --- strmap.c | 6 ++++++ strmap.h | 6 ++++++ 2 files changed, 12 insertions(+) diff --git a/strmap.c b/strmap.c index 829f1bc095..c410c5241a 100644 --- a/strmap.c +++ b/strmap.c @@ -64,6 +64,12 @@ void strmap_clear(struct strmap *map, int free_values) hashmap_clear(&map->map); } +void strmap_partial_clear(struct strmap *map, int free_values) +{ + strmap_free_entries_(map, free_values); + hashmap_partial_clear(&map->map); +} + void *strmap_put(struct strmap *map, const char *str, void *data) { struct strmap_entry *entry = find_strmap_entry(map, str); diff --git a/strmap.h b/strmap.h index f74bc582e4..c14fcee148 100644 --- a/strmap.h +++ b/strmap.h @@ -42,6 +42,12 @@ void strmap_init_with_options(struct strmap *map, */ void strmap_clear(struct strmap *map, int free_values); +/* + * Similar to strmap_clear() but leaves map->map->table allocated and + * pre-sized so that subsequent uses won't need as many rehashings. + */ +void strmap_partial_clear(struct strmap *map, int free_values); + /* * Insert "str" into the map, pointing to "data". * From patchwork Wed Nov 11 20:02:15 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 11898443 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-9.6 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_PATCH,MAILING_LIST_MULTI,SIGNED_OFF_BY, SPF_HELO_NONE,SPF_PASS autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 1C9A2C5517A for ; Wed, 11 Nov 2020 20:02:37 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id B800F2087D for ; Wed, 11 Nov 2020 20:02:36 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="AueMMHlG" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727852AbgKKUCe (ORCPT ); Wed, 11 Nov 2020 15:02:34 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:57962 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727617AbgKKUCd (ORCPT ); Wed, 11 Nov 2020 15:02:33 -0500 Received: from mail-wr1-x442.google.com (mail-wr1-x442.google.com [IPv6:2a00:1450:4864:20::442]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 92DE3C0613D1 for ; Wed, 11 Nov 2020 12:02:32 -0800 (PST) Received: by mail-wr1-x442.google.com with SMTP id j7so3753157wrp.3 for ; Wed, 11 Nov 2020 12:02:32 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=message-id:in-reply-to:references:from:date:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=h5PnHyptBUWzu+AN7UGcuZ3DQJK/OQ/2tdMdIpZtNLg=; b=AueMMHlGLpkED7wAWBz8T6aE4W2w4Z9v9GO9c+WlENUv1UbG+sNF+8tvTOLOLRMQB0 unerycfegFCCfxiVjAHBXgDT3fHiJRokksrNrvRUgOY+I4puTzSC4v8VUpfcW6fcNmPL 20/TigoaXR+U1yUZ1pLFHTEMFHAYSjBybOMxQ6HL073fZj0njV5plHPw/V/S+EaIGE0m EIh3sdE2KA7oJT8pCq3bTnhJnWjTrWRch50dTn9lpv2WmKh/64S7nkSdi6IWlYTtdJb8 ovA2WetU0I0IKnaLB0qTpEkMs1LIspKp1XJek+UBnUgUa8pgp5irHYHsSeOHO6DnMJkd GVEA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:message-id:in-reply-to:references:from:date :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=h5PnHyptBUWzu+AN7UGcuZ3DQJK/OQ/2tdMdIpZtNLg=; b=FRKnAR0DTXhIq4HWkPN1Sk8Ie/NQByeUvOJHdZAx7buL0Lky1TXER8cAhC/RDw8S0v zGwx/ruunE2O9Df61Ni4M1oBE/QMh1vMt3xhtB/NluFlVyPd/O48ou6jPiMCAdee+ZsA tiiQdmZ7Q9a0mmk59j1jY8tQjYrVLb/tFohSQ8Y0AisJ26zEJ+O+suZlMU+l2Hn/Mved 0WKh7IKDyWydycsZZOXO3DyzRGAxsBEfBKRyYij5xviHNB5TZOQYy6owyEiG+gnuIMCl 3+gmxFXXlRIqCOFOR9KyJkHHuhX4X3dnl03tNTBvUpsm38zaWNPmMxe/ny3S/spKcI8P RPCQ== X-Gm-Message-State: AOAM532WJzxAwXqLV6khkfsQ89qNn/KFrKTVHguf1ZLfDqnqfi9Y0oUj fUhtxSqk1Kxt2ikyDAqOyskomjsGzyc= X-Google-Smtp-Source: ABdhPJx/4bJ8ZsOH2R8XEELrooVqKp6VmrvBymXqushzvEASjhXj6OfgWDmRKb4nn7VZMgjCVistcg== X-Received: by 2002:adf:c58f:: with SMTP id m15mr32757047wrg.144.1605124951204; Wed, 11 Nov 2020 12:02:31 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id h4sm3617919wrq.3.2020.11.11.12.02.30 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 11 Nov 2020 12:02:30 -0800 (PST) Message-Id: In-Reply-To: References: Date: Wed, 11 Nov 2020 20:02:15 +0000 Subject: [PATCH v6 09/15] strmap: add functions facilitating use as a string->int map Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Jeff King , Elijah Newren , Phillip Wood , Elijah Newren , Elijah Newren Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Elijah Newren From: Elijah Newren Although strmap could be used as a string->int map, one either had to allocate an int for every entry and then deallocate later, or one had to do a bunch of casting between (void*) and (intptr_t). Add some special functions that do the casting. Also, rename put->set for such wrapper functions since 'put' implied there may be some deallocation needed if the string was already found in the map, which isn't the case when we're storing an int value directly in the void* slot instead of using the void* slot as a pointer to data. Signed-off-by: Elijah Newren --- strmap.c | 11 +++++++ strmap.h | 94 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 105 insertions(+) diff --git a/strmap.c b/strmap.c index c410c5241a..0d10a884b5 100644 --- a/strmap.c +++ b/strmap.c @@ -123,3 +123,14 @@ void strmap_remove(struct strmap *map, const char *str, int free_value) free((char*)ret->key); free(ret); } + +void strintmap_incr(struct strintmap *map, const char *str, intptr_t amt) +{ + struct strmap_entry *entry = find_strmap_entry(&map->map, str); + if (entry) { + intptr_t *whence = (intptr_t*)&entry->value; + *whence += amt; + } + else + strintmap_set(map, str, map->default_value + amt); +} diff --git a/strmap.h b/strmap.h index c14fcee148..56a5cdb864 100644 --- a/strmap.h +++ b/strmap.h @@ -23,6 +23,10 @@ int cmp_strmap_entry(const void *hashmap_cmp_fn_data, .map = HASHMAP_INIT(cmp_strmap_entry, NULL), \ .strdup_strings = 1, \ } +#define STRINTMAP_INIT { \ + .map = STRMAP_INIT, \ + .default_value = 0, \ + } /* * Initialize the members of the strmap. Any keys added to the strmap will @@ -102,4 +106,94 @@ static inline int strmap_empty(struct strmap *map) #define strmap_for_each_entry(mystrmap, iter, var) \ hashmap_for_each_entry(&(mystrmap)->map, iter, var, ent) + +/* + * strintmap: + * A map of string -> int, typecasting the void* of strmap to an int. + * + * Primary differences: + * 1) Since the void* value is just an int in disguise, there is no value + * to free. (Thus one fewer argument to strintmap_clear) + * 2) strintmap_get() returns an int, or returns the default_value if the + * key is not found in the strintmap. + * 3) No strmap_put() equivalent; strintmap_set() and strintmap_incr() + * instead. + */ + +struct strintmap { + struct strmap map; + int default_value; +}; + +#define strintmap_for_each_entry(mystrmap, iter, var) \ + strmap_for_each_entry(&(mystrmap)->map, iter, var) + +static inline void strintmap_init(struct strintmap *map, int default_value) +{ + strmap_init(&map->map); + map->default_value = default_value; +} + +static inline void strintmap_init_with_options(struct strintmap *map, + int default_value, + int strdup_strings) +{ + strmap_init_with_options(&map->map, strdup_strings); + map->default_value = default_value; +} + +static inline void strintmap_clear(struct strintmap *map) +{ + strmap_clear(&map->map, 0); +} + +static inline void strintmap_partial_clear(struct strintmap *map) +{ + strmap_partial_clear(&map->map, 0); +} + +static inline int strintmap_contains(struct strintmap *map, const char *str) +{ + return strmap_contains(&map->map, str); +} + +static inline void strintmap_remove(struct strintmap *map, const char *str) +{ + return strmap_remove(&map->map, str, 0); +} + +static inline int strintmap_empty(struct strintmap *map) +{ + return strmap_empty(&map->map); +} + +static inline unsigned int strintmap_get_size(struct strintmap *map) +{ + return strmap_get_size(&map->map); +} + +/* + * Returns the value for str in the map. If str isn't found in the map, + * the map's default_value is returned. + */ +static inline int strintmap_get(struct strintmap *map, const char *str) +{ + struct strmap_entry *result = strmap_get_entry(&map->map, str); + if (!result) + return map->default_value; + return (intptr_t)result->value; +} + +static inline void strintmap_set(struct strintmap *map, const char *str, + intptr_t v) +{ + strmap_put(&map->map, str, (void *)v); +} + +/* + * Increment the value for str by amt. If str isn't in the map, add it and + * set its value to default_value + amt. + */ +void strintmap_incr(struct strintmap *map, const char *str, intptr_t amt); + #endif /* STRMAP_H */ From patchwork Wed Nov 11 20:02:16 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 11898455 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-9.6 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_PATCH,MAILING_LIST_MULTI,SIGNED_OFF_BY, SPF_HELO_NONE,SPF_PASS autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 78784C388F9 for ; Wed, 11 Nov 2020 20:02:38 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 26DA92087D for ; Wed, 11 Nov 2020 20:02:38 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="KwoQR5wT" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727866AbgKKUCg (ORCPT ); Wed, 11 Nov 2020 15:02:36 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:57964 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727720AbgKKUCd (ORCPT ); Wed, 11 Nov 2020 15:02:33 -0500 Received: from mail-wm1-x32b.google.com (mail-wm1-x32b.google.com [IPv6:2a00:1450:4864:20::32b]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 73218C0613D1 for ; Wed, 11 Nov 2020 12:02:33 -0800 (PST) Received: by mail-wm1-x32b.google.com with SMTP id a65so3478990wme.1 for ; Wed, 11 Nov 2020 12:02:33 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=message-id:in-reply-to:references:from:date:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=6fFXRL/2noA6OKsC3oWtGYm2yYHcHHD3f5FR5Ikh3Vs=; b=KwoQR5wTTE8D952HSVq5XmdxJ8BuJtUwb6dH8u/j2WuE2sEg8ofBWzPrWK3Y+VJyLd zOGUwKvdtAVhaX8BytzPgXAj4wk0dk4nxfINZfFAbi4lTCDm1D5sXXyVuZTLJZd84xD6 ridgycdddlNUqO21jQE+p8cq3dD4ldmtvjKgGirqsRzgpMor41yDFShMVcgvFVYRdrGa 9oDqNALJNjYAGIf7JM36IQSHJ9q2RgK0TM6CzbmCe36V+uakxQ4rHtzJN6h5esBuGVXq AUWDex6VAaOLq7ol00wAgvkTcyzhQ1aq/COZd4dFqjuka4suLoqTgXwJ8kloiD+dIP46 bqEQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:message-id:in-reply-to:references:from:date :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=6fFXRL/2noA6OKsC3oWtGYm2yYHcHHD3f5FR5Ikh3Vs=; b=PWDgejGl/rWg1fkghlU8yutb7ISojxElFCTbQAR8BiewULKYqe3uTyF9tUhxmX/uQD BAzfl09vGMb+9BUrvxk3uyLKVxPkp8lwHFgKY0DRHN+IC7nlsuDcRSRKbeA4COw4Bhz5 A91C8N3376XsLWFfK/6ZEr+UzrYK0p7nCWJTjc3lMcChmDmIzCMU1aG7V6sy4S73+J9p cxbi75PIVUj0mxrqSNIx712HuFW8qQeVZUDQma53kcGivqq7Df5SYbkxGnU7uU4V463B M0cLs4djqZYQ6ObMs6+7X8AfT92hVreNfoHHk+LHQBoXyy+PlzyA4AEvuI/xu+jnuWvj OZDQ== X-Gm-Message-State: AOAM532dE4kZDaR7r33g0sERVVFU7IqT+9hclIFdUY/jvNXFub0Pl5T3 YdrIfeFFteaMK8rfdizBenHRlqe+0LI= X-Google-Smtp-Source: ABdhPJyzbnQd3t+779xzcJ2ic7pmiYET1f4fRmWqwC1dJl4QKbjDxO8giOVaTu+kPZIdi0F6wSKC5Q== X-Received: by 2002:a1c:4346:: with SMTP id q67mr6018820wma.170.1605124952041; Wed, 11 Nov 2020 12:02:32 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id m21sm9965686wmi.3.2020.11.11.12.02.31 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 11 Nov 2020 12:02:31 -0800 (PST) Message-Id: <3bcceb8cdb1dfd571ac5e0b45f20b3aef8bf553b.1605124942.git.gitgitgadget@gmail.com> In-Reply-To: References: Date: Wed, 11 Nov 2020 20:02:16 +0000 Subject: [PATCH v6 10/15] strmap: split create_entry() out of strmap_put() Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Jeff King , Elijah Newren , Phillip Wood , Elijah Newren , Elijah Newren Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Elijah Newren From: Elijah Newren This will facilitate adding entries to a strmap subtype in ways that differ slightly from that of strmap_put(). Signed-off-by: Elijah Newren --- strmap.c | 37 +++++++++++++++++++++++-------------- 1 file changed, 23 insertions(+), 14 deletions(-) diff --git a/strmap.c b/strmap.c index 0d10a884b5..dc84c57c07 100644 --- a/strmap.c +++ b/strmap.c @@ -70,27 +70,36 @@ void strmap_partial_clear(struct strmap *map, int free_values) hashmap_partial_clear(&map->map); } +static struct strmap_entry *create_entry(struct strmap *map, + const char *str, + void *data) +{ + struct strmap_entry *entry; + const char *key = str; + + entry = xmalloc(sizeof(*entry)); + hashmap_entry_init(&entry->ent, strhash(str)); + + if (map->strdup_strings) + key = xstrdup(str); + entry->key = key; + entry->value = data; + return entry; +} + void *strmap_put(struct strmap *map, const char *str, void *data) { struct strmap_entry *entry = find_strmap_entry(map, str); - void *old = NULL; if (entry) { - old = entry->value; + void *old = entry->value; entry->value = data; - } else { - const char *key = str; - - entry = xmalloc(sizeof(*entry)); - hashmap_entry_init(&entry->ent, strhash(str)); - - if (map->strdup_strings) - key = xstrdup(str); - entry->key = key; - entry->value = data; - hashmap_add(&map->map, &entry->ent); + return old; } - return old; + + entry = create_entry(map, str, data); + hashmap_add(&map->map, &entry->ent); + return NULL; } struct strmap_entry *strmap_get_entry(struct strmap *map, const char *str) From patchwork Wed Nov 11 20:02:17 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 11898453 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-9.6 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_PATCH,MAILING_LIST_MULTI,SIGNED_OFF_BY, SPF_HELO_NONE,SPF_PASS autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id D060FC56202 for ; Wed, 11 Nov 2020 20:02:39 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 6C39F2087D for ; Wed, 11 Nov 2020 20:02:39 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="AqBFd1EY" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727876AbgKKUCi (ORCPT ); Wed, 11 Nov 2020 15:02:38 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:57966 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727863AbgKKUCf (ORCPT ); Wed, 11 Nov 2020 15:02:35 -0500 Received: from mail-wr1-x444.google.com (mail-wr1-x444.google.com [IPv6:2a00:1450:4864:20::444]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 379F7C0613D4 for ; Wed, 11 Nov 2020 12:02:34 -0800 (PST) Received: by mail-wr1-x444.google.com with SMTP id j7so3753225wrp.3 for ; Wed, 11 Nov 2020 12:02:34 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=message-id:in-reply-to:references:from:date:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=SRd5zzuJ5YWrv3J1rtWTYj322wIQAFH2zDfaZkFQEEQ=; b=AqBFd1EYmtCSrp5o3jZtl9XVO8TBExhqy4QbTmmBV02yk3d21i6WfmUUiBuxvxSp1N w+68tJvtoNxQwZLNpeZONXoh4qD4oCibz//G1+yGYncaEioefCAJ7uj82xVEfjVKWKjF 2bzWV1RJJTIQZq0N/MvlG3+aIpjLV2BLvshhmNeFPQryUfxaUGn6vxANeJCbeD8wk4lx BKOgIG2PxpxEqrOMdCerfKpIY5MtvWojkh9ie2bh8GQTv/umI/b3AikBHGZpSC1norx1 kgFUJI2pZ70inFpCG8HeyX8gxcY8x086oHmJ40wIf0AFgHAslh0Um3VnEEznWzPuR1Gx P7gg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:message-id:in-reply-to:references:from:date :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=SRd5zzuJ5YWrv3J1rtWTYj322wIQAFH2zDfaZkFQEEQ=; b=qhZM3jhdGqrqVzxflYNl0cR2Usd1/8bxHaqHzo1nL0jqmxL5f1yBht/dtAkqSSVEsw VgVQ+5/njf9668NLPVMVdkjMMPc8vENfyrulHDvj060F/s/VIqhM1DF4Px2xU6cJlJsl X6J80CrCQhZTKBozc4gOvy5O0+LKzdRx+PCi++EFkwWjR9Ru0niBfZLFu/AtfExR7ryY EmkrGeOb6Cj1OnI0+Bnjn1x416vY81c/FnVcdpXLk22LHQHB7YYUYFXyI5YBUTCPHXIn fnVM7/zaDvPvpfh9Ew2m/HiBWLaxOJxXlh3ZLDD1nFKYwNPsDt+/bffE9Nkc7tromu8Z cydQ== X-Gm-Message-State: AOAM532yliK592rQuRq+SmZIJAqdmbhs3gf2XVieFAXKz2OQPAcUCD3h HZneFIqwYdiLK05AV84ok5LIHUw/+Mk= X-Google-Smtp-Source: ABdhPJz8S8+PJfEMlpHyaHPCF6KEZDbV3hvS6y/sA5xUnNiyXt6JkHvZPMONJ4lM9++8UOBteKBexA== X-Received: by 2002:adf:9461:: with SMTP id 88mr30656682wrq.171.1605124952787; Wed, 11 Nov 2020 12:02:32 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id s12sm3780976wmc.6.2020.11.11.12.02.32 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 11 Nov 2020 12:02:32 -0800 (PST) Message-Id: In-Reply-To: References: Date: Wed, 11 Nov 2020 20:02:17 +0000 Subject: [PATCH v6 11/15] strmap: add a strset sub-type Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Jeff King , Elijah Newren , Phillip Wood , Elijah Newren , Elijah Newren Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Elijah Newren From: Elijah Newren Similar to adding strintmap for special-casing a string -> int mapping, add a strset type for cases where we really are only interested in using strmap for storing a set rather than a mapping. In this case, we'll always just store NULL for the value but the different struct type makes it clearer than code comments how a variable is intended to be used. The difference in usage also results in some differences in API: a few things that aren't necessary or meaningful are dropped (namely, the free_values argument to *_clear(), and the *_get() function), and strset_add() is chosen as the API instead of strset_put(). Signed-off-by: Elijah Newren --- strmap.c | 17 +++++++++++++++ strmap.h | 63 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 80 insertions(+) diff --git a/strmap.c b/strmap.c index dc84c57c07..3784865745 100644 --- a/strmap.c +++ b/strmap.c @@ -143,3 +143,20 @@ void strintmap_incr(struct strintmap *map, const char *str, intptr_t amt) else strintmap_set(map, str, map->default_value + amt); } + +int strset_add(struct strset *set, const char *str) +{ + /* + * Cannot use strmap_put() because it'll return NULL in both cases: + * - cannot find str: NULL means "not found" + * - does find str: NULL is the value associated with str + */ + struct strmap_entry *entry = find_strmap_entry(&set->map, str); + + if (entry) + return 0; + + entry = create_entry(&set->map, str, NULL); + hashmap_add(&set->map.map, &entry->ent); + return 1; +} diff --git a/strmap.h b/strmap.h index 56a5cdb864..c8c4d7c932 100644 --- a/strmap.h +++ b/strmap.h @@ -27,6 +27,7 @@ int cmp_strmap_entry(const void *hashmap_cmp_fn_data, .map = STRMAP_INIT, \ .default_value = 0, \ } +#define STRSET_INIT { .map = STRMAP_INIT } /* * Initialize the members of the strmap. Any keys added to the strmap will @@ -196,4 +197,66 @@ static inline void strintmap_set(struct strintmap *map, const char *str, */ void strintmap_incr(struct strintmap *map, const char *str, intptr_t amt); +/* + * strset: + * A set of strings. + * + * Primary differences with strmap: + * 1) The value is always NULL, and ignored. As there is no value to free, + * there is one fewer argument to strset_clear + * 2) No strset_get() because there is no value. + * 3) No strset_put(); use strset_add() instead. + */ + +struct strset { + struct strmap map; +}; + +#define strset_for_each_entry(mystrset, iter, var) \ + strmap_for_each_entry(&(mystrset)->map, iter, var) + +static inline void strset_init(struct strset *set) +{ + strmap_init(&set->map); +} + +static inline void strset_init_with_options(struct strset *set, + int strdup_strings) +{ + strmap_init_with_options(&set->map, strdup_strings); +} + +static inline void strset_clear(struct strset *set) +{ + strmap_clear(&set->map, 0); +} + +static inline void strset_partial_clear(struct strset *set) +{ + strmap_partial_clear(&set->map, 0); +} + +static inline int strset_contains(struct strset *set, const char *str) +{ + return strmap_contains(&set->map, str); +} + +static inline void strset_remove(struct strset *set, const char *str) +{ + return strmap_remove(&set->map, str, 0); +} + +static inline int strset_empty(struct strset *set) +{ + return strmap_empty(&set->map); +} + +static inline unsigned int strset_get_size(struct strset *set) +{ + return strmap_get_size(&set->map); +} + +/* Returns 1 if str is added to the set; returns 0 if str was already in set */ +int strset_add(struct strset *set, const char *str); + #endif /* STRMAP_H */ From patchwork Wed Nov 11 20:02:18 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 11898445 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-9.6 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_PATCH,MAILING_LIST_MULTI,SIGNED_OFF_BY, SPF_HELO_NONE,SPF_PASS autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 5B419C5517A for ; Wed, 11 Nov 2020 20:02:40 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id E73932087D for ; Wed, 11 Nov 2020 20:02:39 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="jrCiN4bC" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727878AbgKKUCj (ORCPT ); Wed, 11 Nov 2020 15:02:39 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:57972 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727861AbgKKUCf (ORCPT ); Wed, 11 Nov 2020 15:02:35 -0500 Received: from mail-wm1-x343.google.com (mail-wm1-x343.google.com [IPv6:2a00:1450:4864:20::343]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 13ADAC0613D1 for ; Wed, 11 Nov 2020 12:02:35 -0800 (PST) Received: by mail-wm1-x343.google.com with SMTP id p22so3368050wmg.3 for ; Wed, 11 Nov 2020 12:02:35 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=message-id:in-reply-to:references:from:date:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=GU/E3guLHF3z1WLOtDxPFbXkx6dKo4kaIDYqJPTUC/U=; b=jrCiN4bC30rYesflq0erThhFwXPj4loITRIGnAY4bmntmi7dHz26hGUJvZAHToafm9 UL74Ol/FSMoREKINUt+mbfVGV2GIpIYPW9b1OcFVN6/1wJtu8IMkeMR/QLBW7v5bDaZP vN8tF4dM00y6kWjxVBYBWGgbKds9TUMMHOX0U4b/e3FilWd/d++HzWwZi6eK8pv+7WNk RkJYGEbpKQh5AUDYqh8rr2wraHTDmhIduG3oOuJmjFRAY+HOvANg5nPENdw0mmrpEfOH PtdevIbHFtquqKaWNayzvwij9T9Z5Ij/0dYPKmuda44SFpk/jCFXRoSH+5rbCkBAgCO+ 12fA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:message-id:in-reply-to:references:from:date :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=GU/E3guLHF3z1WLOtDxPFbXkx6dKo4kaIDYqJPTUC/U=; b=CZ7CHFdUBR4JfwrVktVSAOGfyKm6ohgENqaG4KupnmMpsE23EUJ9u2oZvVVlGVRko6 chYAXTwdT8abROsm8iZl+ghvPOGGdKyWrlnLPXkcDPIYRjWs3dEaV9OpsIAvhi6rUCAy /4iRo/g3o6oOYQJ2AZQ1dVjHJ8UB6b+AuwAOBnW/7OKH+C2vNSwGwdfXvo9MT7Ilpp1T knwPy51vY4tAChnknnuN58S0zXsQf1W9idwoeSNy3L2Nu7QQJbrZH82yK8BGGtMUViCG v8L9ebZJPGCZMA3SPmvmbhpY48WutXKviUhZnEdqk9OJ29Zip59O1KgXY0pVR/nbKYr5 EF2g== X-Gm-Message-State: AOAM531GOGQ42lG+e9M2ZlxMRQ1TEelar+RocFtaW7kb9u5Ag1cOnnWI AQd+5UrCioIGDbeAd2GiPWOb9M2hcrM= X-Google-Smtp-Source: ABdhPJyl928VUYFDhWz670MdFmyeb4d4+C+Ylf0RJhIhqXAOErauNYhIuhUW3plt4HyCpwKQV9MAyA== X-Received: by 2002:a1c:df89:: with SMTP id w131mr5626797wmg.164.1605124953587; Wed, 11 Nov 2020 12:02:33 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id f5sm3890652wrg.32.2020.11.11.12.02.33 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 11 Nov 2020 12:02:33 -0800 (PST) Message-Id: <3926c4c97bd08aac93d3f521273db9d76b4d5cd3.1605124942.git.gitgitgadget@gmail.com> In-Reply-To: References: Date: Wed, 11 Nov 2020 20:02:18 +0000 Subject: [PATCH v6 12/15] strmap: enable allocations to come from a mem_pool Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Jeff King , Elijah Newren , Phillip Wood , Elijah Newren , Elijah Newren Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Elijah Newren From: Elijah Newren For heavy users of strmaps, allowing the keys and entries to be allocated from a memory pool can provide significant overhead savings. Add an option to strmap_init_with_options() to specify a memory pool. Signed-off-by: Elijah Newren --- strmap.c | 31 ++++++++++++++++++++++--------- strmap.h | 11 ++++++++--- 2 files changed, 30 insertions(+), 12 deletions(-) diff --git a/strmap.c b/strmap.c index 3784865745..139afb9d4b 100644 --- a/strmap.c +++ b/strmap.c @@ -1,5 +1,6 @@ #include "git-compat-util.h" #include "strmap.h" +#include "mem-pool.h" int cmp_strmap_entry(const void *hashmap_cmp_fn_data, const struct hashmap_entry *entry1, @@ -24,13 +25,15 @@ static struct strmap_entry *find_strmap_entry(struct strmap *map, void strmap_init(struct strmap *map) { - strmap_init_with_options(map, 1); + strmap_init_with_options(map, NULL, 1); } void strmap_init_with_options(struct strmap *map, + struct mem_pool *pool, int strdup_strings) { hashmap_init(&map->map, cmp_strmap_entry, NULL, 0); + map->pool = pool; map->strdup_strings = strdup_strings; } @@ -42,6 +45,10 @@ static void strmap_free_entries_(struct strmap *map, int free_values) if (!map) return; + if (!free_values && map->pool) + /* Memory other than util is owned by and freed with the pool */ + return; + /* * We need to iterate over the hashmap entries and free * e->key and e->value ourselves; hashmap has no API to @@ -52,9 +59,11 @@ static void strmap_free_entries_(struct strmap *map, int free_values) hashmap_for_each_entry(&map->map, &iter, e, ent) { if (free_values) free(e->value); - if (map->strdup_strings) - free((char*)e->key); - free(e); + if (!map->pool) { + if (map->strdup_strings) + free((char*)e->key); + free(e); + } } } @@ -77,11 +86,13 @@ static struct strmap_entry *create_entry(struct strmap *map, struct strmap_entry *entry; const char *key = str; - entry = xmalloc(sizeof(*entry)); + entry = map->pool ? mem_pool_alloc(map->pool, sizeof(*entry)) + : xmalloc(sizeof(*entry)); hashmap_entry_init(&entry->ent, strhash(str)); if (map->strdup_strings) - key = xstrdup(str); + key = map->pool ? mem_pool_strdup(map->pool, str) + : xstrdup(str); entry->key = key; entry->value = data; return entry; @@ -128,9 +139,11 @@ void strmap_remove(struct strmap *map, const char *str, int free_value) return; if (free_value) free(ret->value); - if (map->strdup_strings) - free((char*)ret->key); - free(ret); + if (!map->pool) { + if (map->strdup_strings) + free((char*)ret->key); + free(ret); + } } void strintmap_incr(struct strintmap *map, const char *str, intptr_t amt) diff --git a/strmap.h b/strmap.h index c8c4d7c932..8745b7ceb1 100644 --- a/strmap.h +++ b/strmap.h @@ -3,8 +3,10 @@ #include "hashmap.h" +struct mem_pool; struct strmap { struct hashmap map; + struct mem_pool *pool; unsigned int strdup_strings:1; }; @@ -37,9 +39,10 @@ void strmap_init(struct strmap *map); /* * Same as strmap_init, but for those who want to control the memory management - * carefully instead of using the default of strdup_strings=1. + * carefully instead of using the default of strdup_strings=1 and pool=NULL. */ void strmap_init_with_options(struct strmap *map, + struct mem_pool *pool, int strdup_strings); /* @@ -137,9 +140,10 @@ static inline void strintmap_init(struct strintmap *map, int default_value) static inline void strintmap_init_with_options(struct strintmap *map, int default_value, + struct mem_pool *pool, int strdup_strings) { - strmap_init_with_options(&map->map, strdup_strings); + strmap_init_with_options(&map->map, pool, strdup_strings); map->default_value = default_value; } @@ -221,9 +225,10 @@ static inline void strset_init(struct strset *set) } static inline void strset_init_with_options(struct strset *set, + struct mem_pool *pool, int strdup_strings) { - strmap_init_with_options(&set->map, strdup_strings); + strmap_init_with_options(&set->map, pool, strdup_strings); } static inline void strset_clear(struct strset *set) From patchwork Wed Nov 11 20:02:19 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 11898457 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-9.6 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_PATCH,MAILING_LIST_MULTI,SIGNED_OFF_BY, SPF_HELO_NONE,SPF_PASS autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 22ACFC388F9 for ; Wed, 11 Nov 2020 20:02:47 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id A52EC207F7 for ; Wed, 11 Nov 2020 20:02:44 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="PwBfcCui" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727884AbgKKUCn (ORCPT ); Wed, 11 Nov 2020 15:02:43 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:57980 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727842AbgKKUCg (ORCPT ); Wed, 11 Nov 2020 15:02:36 -0500 Received: from mail-wr1-x432.google.com (mail-wr1-x432.google.com [IPv6:2a00:1450:4864:20::432]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id DC980C0613D6 for ; Wed, 11 Nov 2020 12:02:35 -0800 (PST) Received: by mail-wr1-x432.google.com with SMTP id j7so3753289wrp.3 for ; Wed, 11 Nov 2020 12:02:35 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=message-id:in-reply-to:references:from:date:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=IO3ISdeushRI00Yi2X+meRNtIymPkMni8juDUTbuRMA=; b=PwBfcCuiLSCltiGcHy9u/9upmroKwyO0kF16EpHmKG5ZOyyWuWhFlgMiuW19/Oejfv QzkcnHeQX5XRf6ZtnVBk4zExaHaTs9gp0lc96CZE7bLjZGlAGNiil4amUIKg4/3jg5yn khuAuS/j2h9wQOVzRNVp6GzHuXf1ZR83hFn4r6zd4QEu3zJwg5vb3xDi6/UvuOuNrdaN Ut+570lMPwm7WARZBiYMWIIhEznShLyknpD4Dz/IyRnAt+yGGqzTzgFMClrYyUvYWwlO 6eynB2iDob1q1E+ZiWc+7BvsE/K7WhufkVZv8j7l52DfKrttoBt7CZlTvPyAMjbpVWNu l9hg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:message-id:in-reply-to:references:from:date :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=IO3ISdeushRI00Yi2X+meRNtIymPkMni8juDUTbuRMA=; b=J50Tjg8SaOq/nTtb58RPEQ+PcbJditHigJJ9jbzOhriilsTGuBKP+5Rue8kfBRlXR0 hRbLRQYa7iiXD5V6NOwBTL1C/CAZk+npfVE2h13dmm/k6RNwVo/b+wp0lwLcYIPgixi2 eazHW9gRyjxK9OoKqrbnk1hWHV6+uPR/H5RUarWjc5AZ+SqkOh7vFwrZpYskYjlz515m 9akM/gYe6iMQ45HUiiPpDBoVB11VPrU6SNbX+pIbrdyOF7JoWLB8uQB45JX5F6KwjN7v qQVB4y2ni8bO7WwDZGW/PURy3LPyUJTGDvAQ44T0smVO70uODSddovsrpxEsvwiJ+34p T27Q== X-Gm-Message-State: AOAM533OodQLmH6sKT8bgvdHV6YhBCP8Hr28DbjZbOwU9LneoyONs0HW 8d90unzc3kshZGaf0VBr+npBtICmwZw= X-Google-Smtp-Source: ABdhPJz8B6VlAacqOnEVKvGk599yccLfwCk4HEdELYv0QgTW0e+1ICpPM/9GYBoR+0BBHN3AGQeaBQ== X-Received: by 2002:adf:dc0f:: with SMTP id t15mr4474056wri.29.1605124954419; Wed, 11 Nov 2020 12:02:34 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id m20sm4349712wrg.81.2020.11.11.12.02.33 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 11 Nov 2020 12:02:34 -0800 (PST) Message-Id: <562595224b56ff8b3dc3b97baa713e47d18e2126.1605124942.git.gitgitgadget@gmail.com> In-Reply-To: References: Date: Wed, 11 Nov 2020 20:02:19 +0000 Subject: [PATCH v6 13/15] strmap: take advantage of FLEXPTR_ALLOC_STR when relevant Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Jeff King , Elijah Newren , Phillip Wood , Elijah Newren , Elijah Newren Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Elijah Newren From: Elijah Newren By default, we do not use a mempool and strdup_strings is true; in this case, we can avoid both an extra allocation and an extra free by just over-allocating for the strmap_entry leaving enough space at the end to copy the key. FLEXPTR_ALLOC_STR exists for exactly this purpose, so make use of it. Also, adjust the case when we are using a memory pool and strdup_strings is true to just do one allocation from the memory pool instead of two so that the strmap_clear() and strmap_remove() code can just avoid freeing the key in all cases. Signed-off-by: Elijah Newren --- strmap.c | 35 +++++++++++++++++++---------------- strmap.h | 1 + 2 files changed, 20 insertions(+), 16 deletions(-) diff --git a/strmap.c b/strmap.c index 139afb9d4b..4fb9f6100e 100644 --- a/strmap.c +++ b/strmap.c @@ -59,11 +59,8 @@ static void strmap_free_entries_(struct strmap *map, int free_values) hashmap_for_each_entry(&map->map, &iter, e, ent) { if (free_values) free(e->value); - if (!map->pool) { - if (map->strdup_strings) - free((char*)e->key); + if (!map->pool) free(e); - } } } @@ -84,16 +81,25 @@ static struct strmap_entry *create_entry(struct strmap *map, void *data) { struct strmap_entry *entry; - const char *key = str; - entry = map->pool ? mem_pool_alloc(map->pool, sizeof(*entry)) - : xmalloc(sizeof(*entry)); + if (map->strdup_strings) { + if (!map->pool) { + FLEXPTR_ALLOC_STR(entry, key, str); + } else { + size_t len = st_add(strlen(str), 1); /* include NUL */ + entry = mem_pool_alloc(map->pool, + st_add(sizeof(*entry), len)); + memcpy(entry + 1, str, len); + entry->key = (void *)(entry + 1); + } + } else if (!map->pool) { + entry = xmalloc(sizeof(*entry)); + } else { + entry = mem_pool_alloc(map->pool, sizeof(*entry)); + } hashmap_entry_init(&entry->ent, strhash(str)); - - if (map->strdup_strings) - key = map->pool ? mem_pool_strdup(map->pool, str) - : xstrdup(str); - entry->key = key; + if (!map->strdup_strings) + entry->key = str; entry->value = data; return entry; } @@ -139,11 +145,8 @@ void strmap_remove(struct strmap *map, const char *str, int free_value) return; if (free_value) free(ret->value); - if (!map->pool) { - if (map->strdup_strings) - free((char*)ret->key); + if (!map->pool) free(ret); - } } void strintmap_incr(struct strintmap *map, const char *str, intptr_t amt) diff --git a/strmap.h b/strmap.h index 8745b7ceb1..c4c104411b 100644 --- a/strmap.h +++ b/strmap.h @@ -14,6 +14,7 @@ struct strmap_entry { struct hashmap_entry ent; const char *key; void *value; + /* strmap_entry may be allocated extra space to store the key at end */ }; int cmp_strmap_entry(const void *hashmap_cmp_fn_data, From patchwork Wed Nov 11 20:02:20 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 11898449 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-9.6 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_PATCH,MAILING_LIST_MULTI,SIGNED_OFF_BY, SPF_HELO_NONE,SPF_PASS,URIBL_BLOCKED autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id F243DC388F9 for ; Wed, 11 Nov 2020 20:02:42 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 97BC2208B8 for ; Wed, 11 Nov 2020 20:02:42 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="BPBPnf3t" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727681AbgKKUCl (ORCPT ); Wed, 11 Nov 2020 15:02:41 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:57982 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727868AbgKKUCh (ORCPT ); Wed, 11 Nov 2020 15:02:37 -0500 Received: from mail-wr1-x441.google.com (mail-wr1-x441.google.com [IPv6:2a00:1450:4864:20::441]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id CD153C0613D1 for ; Wed, 11 Nov 2020 12:02:36 -0800 (PST) Received: by mail-wr1-x441.google.com with SMTP id s8so3704962wrw.10 for ; Wed, 11 Nov 2020 12:02:36 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=message-id:in-reply-to:references:from:date:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=OA4wQ/JUZvjUd14KqKKplav5D5ohsMHFqJIjlPS/lz8=; b=BPBPnf3tu5ousPEXSm2MpDo6yb7SdkVY+JdpuuTVZwjmTubo30gA4ScWxugKr2utzA r7YNx57AoWFUkB0jEV/wKAOCXo8u6FD2YgpiPCj3Lw5+scarzTDCtOKniIGVgRPgeGzT UIxLGynXGJmsBkUyEBupZznN4qPcs7y2o1wxAg4te1EcfFmbOjS1dYNS6JHA/tz0K0SF ftBs0kkeauxMfXVrG4GxEYoFT/u21CmoWfU+XgWsh1VWhsRoDxAz+6mdCQE9Fte2ONYj q+aNwMvRYI7lmY82mS/LcyZnsPNs/yIGeGxv9JLyKSYNyi1YCnOFkz0iAxKELkH8vQhb t8Zg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:message-id:in-reply-to:references:from:date :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=OA4wQ/JUZvjUd14KqKKplav5D5ohsMHFqJIjlPS/lz8=; b=pmUXEuSg0Fl0ORHg5dz7vd3SIflXcHOqccJlNYeM/1yl7Uxb1lGGKMRkyeUYwfGGJn fHUMYu/FORn/KDS8poHQe982Cv0fvpmoVmCOCQS2Y3NOA8bSmsYQqxCmhF+FrcR+YYVA ojiqOjD7KgM2HNAR3Lj7+F70AXjKvRDHMUHD0lVyZSOq//Iy9UQPwtFqC7Ap+yKBJ+oe Jwb+nf60yBRkltBCSesL09Fg0Nih0s0irFvTeCvP76dUngcIq/8TnjUhFZB2TjUG4M0R lyFtCHYmWR5xz8nTq/sS4pSzh+2L9ozenrLgw9YbzH4yQ3ErC3/3q4Nu2mmjWe2R1tqS hUrA== X-Gm-Message-State: AOAM5306eHyvj/tGHChVoyP7SwYe20hkklFApsN4nq6wStt9AXRh04pt jJwCr50rO6v/eZZmUHqJ4sC2lCb5qtY= X-Google-Smtp-Source: ABdhPJymOEU44GGtRAJbIlvbP/70vFOQCwXLabbePN5jzbe6cR7AmcG7agvp2ozIv6EHWq/WarRR8g== X-Received: by 2002:adf:f6cd:: with SMTP id y13mr12017820wrp.363.1605124955378; Wed, 11 Nov 2020 12:02:35 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id p12sm3621748wrw.28.2020.11.11.12.02.34 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 11 Nov 2020 12:02:34 -0800 (PST) Message-Id: <058e7a6b76047a6e3196ff13cafc2d6ea3b772df.1605124942.git.gitgitgadget@gmail.com> In-Reply-To: References: Date: Wed, 11 Nov 2020 20:02:20 +0000 Subject: [PATCH v6 14/15] Use new HASHMAP_INIT macro to simplify hashmap initialization Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Jeff King , Elijah Newren , Phillip Wood , Elijah Newren , Elijah Newren Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Elijah Newren From: Elijah Newren Now that hashamp has lazy initialization and a HASHMAP_INIT macro, hashmaps allocated on the stack can be initialized without a call to hashmap_init() and in some cases makes the code a bit shorter. Convert some callsites over to take advantage of this. Signed-off-by: Elijah Newren --- attr.c | 26 ++++++++------------------ bloom.c | 3 +-- builtin/difftool.c | 9 ++++----- range-diff.c | 4 +--- revision.c | 9 +-------- t/helper/test-hashmap.c | 3 +-- 6 files changed, 16 insertions(+), 38 deletions(-) diff --git a/attr.c b/attr.c index a826b2ef1f..4ef85d668b 100644 --- a/attr.c +++ b/attr.c @@ -52,13 +52,6 @@ static inline void hashmap_unlock(struct attr_hashmap *map) pthread_mutex_unlock(&map->mutex); } -/* - * The global dictionary of all interned attributes. This - * is a singleton object which is shared between threads. - * Access to this dictionary must be surrounded with a mutex. - */ -static struct attr_hashmap g_attr_hashmap; - /* The container for objects stored in "struct attr_hashmap" */ struct attr_hash_entry { struct hashmap_entry ent; @@ -80,11 +73,14 @@ static int attr_hash_entry_cmp(const void *unused_cmp_data, return (a->keylen != b->keylen) || strncmp(a->key, b->key, a->keylen); } -/* Initialize an 'attr_hashmap' object */ -static void attr_hashmap_init(struct attr_hashmap *map) -{ - hashmap_init(&map->map, attr_hash_entry_cmp, NULL, 0); -} +/* + * The global dictionary of all interned attributes. This + * is a singleton object which is shared between threads. + * Access to this dictionary must be surrounded with a mutex. + */ +static struct attr_hashmap g_attr_hashmap = { + HASHMAP_INIT(attr_hash_entry_cmp, NULL) +}; /* * Retrieve the 'value' stored in a hashmap given the provided 'key'. @@ -96,9 +92,6 @@ static void *attr_hashmap_get(struct attr_hashmap *map, struct attr_hash_entry k; struct attr_hash_entry *e; - if (!map->map.tablesize) - attr_hashmap_init(map); - hashmap_entry_init(&k.ent, memhash(key, keylen)); k.key = key; k.keylen = keylen; @@ -114,9 +107,6 @@ static void attr_hashmap_add(struct attr_hashmap *map, { struct attr_hash_entry *e; - if (!map->map.tablesize) - attr_hashmap_init(map); - e = xmalloc(sizeof(struct attr_hash_entry)); hashmap_entry_init(&e->ent, memhash(key, keylen)); e->key = key; diff --git a/bloom.c b/bloom.c index 719c313a1c..b176f28f53 100644 --- a/bloom.c +++ b/bloom.c @@ -229,10 +229,9 @@ struct bloom_filter *get_or_compute_bloom_filter(struct repository *r, diffcore_std(&diffopt); if (diff_queued_diff.nr <= settings->max_changed_paths) { - struct hashmap pathmap; + struct hashmap pathmap = HASHMAP_INIT(pathmap_cmp, NULL); struct pathmap_hash_entry *e; struct hashmap_iter iter; - hashmap_init(&pathmap, pathmap_cmp, NULL, 0); for (i = 0; i < diff_queued_diff.nr; i++) { const char *path = diff_queued_diff.queue[i]->two->path; diff --git a/builtin/difftool.c b/builtin/difftool.c index 7ac432b881..6e18e623fd 100644 --- a/builtin/difftool.c +++ b/builtin/difftool.c @@ -342,7 +342,10 @@ static int run_dir_diff(const char *extcmd, int symlinks, const char *prefix, const char *workdir, *tmp; int ret = 0, i; FILE *fp; - struct hashmap working_tree_dups, submodules, symlinks2; + struct hashmap working_tree_dups = HASHMAP_INIT(working_tree_entry_cmp, + NULL); + struct hashmap submodules = HASHMAP_INIT(pair_cmp, NULL); + struct hashmap symlinks2 = HASHMAP_INIT(pair_cmp, NULL); struct hashmap_iter iter; struct pair_entry *entry; struct index_state wtindex; @@ -383,10 +386,6 @@ static int run_dir_diff(const char *extcmd, int symlinks, const char *prefix, rdir_len = rdir.len; wtdir_len = wtdir.len; - hashmap_init(&working_tree_dups, working_tree_entry_cmp, NULL, 0); - hashmap_init(&submodules, pair_cmp, NULL, 0); - hashmap_init(&symlinks2, pair_cmp, NULL, 0); - child.no_stdin = 1; child.git_cmd = 1; child.use_shell = 0; diff --git a/range-diff.c b/range-diff.c index befeecae44..b9950f10c8 100644 --- a/range-diff.c +++ b/range-diff.c @@ -232,11 +232,9 @@ static int patch_util_cmp(const void *dummy, const struct patch_util *a, static void find_exact_matches(struct string_list *a, struct string_list *b) { - struct hashmap map; + struct hashmap map = HASHMAP_INIT((hashmap_cmp_fn)patch_util_cmp, NULL); int i; - hashmap_init(&map, (hashmap_cmp_fn)patch_util_cmp, NULL, 0); - /* First, add the patches of a to a hash map */ for (i = 0; i < a->nr; i++) { struct patch_util *util = a->items[i].util; diff --git a/revision.c b/revision.c index f27649d45d..c6e169e3eb 100644 --- a/revision.c +++ b/revision.c @@ -124,11 +124,6 @@ static int path_and_oids_cmp(const void *hashmap_cmp_fn_data, return strcmp(e1->path, e2->path); } -static void paths_and_oids_init(struct hashmap *map) -{ - hashmap_init(map, path_and_oids_cmp, NULL, 0); -} - static void paths_and_oids_clear(struct hashmap *map) { struct hashmap_iter iter; @@ -213,7 +208,7 @@ void mark_trees_uninteresting_sparse(struct repository *r, struct oidset *trees) { unsigned has_interesting = 0, has_uninteresting = 0; - struct hashmap map; + struct hashmap map = HASHMAP_INIT(path_and_oids_cmp, NULL); struct hashmap_iter map_iter; struct path_and_oids_entry *entry; struct object_id *oid; @@ -237,8 +232,6 @@ void mark_trees_uninteresting_sparse(struct repository *r, if (!has_uninteresting || !has_interesting) return; - paths_and_oids_init(&map); - oidset_iter_init(trees, &iter); while ((oid = oidset_iter_next(&iter))) { struct tree *tree = lookup_tree(r, oid); diff --git a/t/helper/test-hashmap.c b/t/helper/test-hashmap.c index 2475663b49..36ff07bd4b 100644 --- a/t/helper/test-hashmap.c +++ b/t/helper/test-hashmap.c @@ -151,12 +151,11 @@ static void perf_hashmap(unsigned int method, unsigned int rounds) int cmd__hashmap(int argc, const char **argv) { struct strbuf line = STRBUF_INIT; - struct hashmap map; int icase; + struct hashmap map = HASHMAP_INIT(test_entry_cmp, &icase); /* init hash map */ icase = argc > 1 && !strcmp("ignorecase", argv[1]); - hashmap_init(&map, test_entry_cmp, &icase, 0); /* process commands from stdin */ while (strbuf_getline(&line, stdin) != EOF) { From patchwork Wed Nov 11 20:02:21 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 11898451 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-9.6 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_PATCH,MAILING_LIST_MULTI,SIGNED_OFF_BY, SPF_HELO_NONE,SPF_PASS autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id A1892C56201 for ; Wed, 11 Nov 2020 20:02:43 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 4C9CD2087D for ; Wed, 11 Nov 2020 20:02:43 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="tYEpKMRw" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727883AbgKKUCm (ORCPT ); Wed, 11 Nov 2020 15:02:42 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:57984 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727720AbgKKUCh (ORCPT ); Wed, 11 Nov 2020 15:02:37 -0500 Received: from mail-wr1-x444.google.com (mail-wr1-x444.google.com [IPv6:2a00:1450:4864:20::444]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 79033C0613D4 for ; Wed, 11 Nov 2020 12:02:37 -0800 (PST) Received: by mail-wr1-x444.google.com with SMTP id 33so3730248wrl.7 for ; Wed, 11 Nov 2020 12:02:37 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=message-id:in-reply-to:references:from:date:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=/m8cQExWBEWxoRtNoB5eAbuRwvA8C0BdwF9qLyUY+84=; b=tYEpKMRwB6wxX1ouX14vuvy5Fv92lx/0aurwHid8iy0xybFEQrDEcP+4FWswzuX16F 3j2dXVzD6Q1a3Jh31Zx5b0R66j6gp8UpMOyAGAhs9ihKJfjSu/qpROGVrXUGA09rE7Lp CK6qh4g+Y7/hA0woZ5nbH1tO+qU8410QDwIRlIdwL9VFKlzC7S3c3Ec8W0RiwEYMetEz 7ky9weX4Je09PgiZCH1Kz4HiE7P36UmvR7j5270oKLvQd3ztk+32okln8JODte3hUS0k JHayMc/rNNyeYU/TsK6e0z1k4tjnr7LtgJW4TW4raCdTznJ5uceMLUcbpVlLyc6/S4iV hKaA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:message-id:in-reply-to:references:from:date :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=/m8cQExWBEWxoRtNoB5eAbuRwvA8C0BdwF9qLyUY+84=; b=JM9D3CHNb5lDvEpH4110iyY/eaSEZfWBgEs5Aij53pu+d4Z178mACpftBsPKVp/+58 wfAopAy0uq9SGDjhRONCzO6sUkSAcZMELOR2gUFiF1SIPBjh6vUmYFi1vlfqswk1D7m1 auAxLx2vtmqoZJFrky9lQZD7bRQ4wfLtxl6zyp/a8+7Qab9qX4Q3KPWSWH9ek3d8jZu5 Scl7NB5pY8+kgyMnEzSKJF7FwsGohpmfgtxobbEvi+qd/685lM6XPQwFQbw2AAMOLu6x LHqKEdkXvEyofDyqfrwgJK0wGg040RWuUS0NnJiILAt2c/zsl+RbV8phBXurvN+QWpSJ m9Fg== X-Gm-Message-State: AOAM5328zy26LAhe8QWpUhYYJzgU3pGQ0TWCgXJ4E4TOGEVHB3epHUm+ zB83Yqu1p4zWSql49eJsXlLQCCUZfbM= X-Google-Smtp-Source: ABdhPJx7Xz7l1fAFLNe/hwE5ZxCO/pkNEs7Cmx6joZ8lboiQc+KbL9pO4meaZJSXCqM6oEIHYMMOtA== X-Received: by 2002:adf:c58f:: with SMTP id m15mr32757466wrg.144.1605124956134; Wed, 11 Nov 2020 12:02:36 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id t13sm3827880wru.67.2020.11.11.12.02.35 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 11 Nov 2020 12:02:35 -0800 (PST) Message-Id: <9b494c26c18e5a5b4f2561e30546d3bf3e82ef11.1605124942.git.gitgitgadget@gmail.com> In-Reply-To: References: Date: Wed, 11 Nov 2020 20:02:21 +0000 Subject: [PATCH v6 15/15] shortlog: use strset from strmap.h Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Jeff King , Elijah Newren , Phillip Wood , Elijah Newren , Elijah Newren Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Elijah Newren From: Elijah Newren Signed-off-by: Elijah Newren --- builtin/shortlog.c | 61 +++------------------------------------------- 1 file changed, 4 insertions(+), 57 deletions(-) diff --git a/builtin/shortlog.c b/builtin/shortlog.c index 83f0a739b4..c52e4ccd19 100644 --- a/builtin/shortlog.c +++ b/builtin/shortlog.c @@ -10,6 +10,7 @@ #include "shortlog.h" #include "parse-options.h" #include "trailer.h" +#include "strmap.h" static char const * const shortlog_usage[] = { N_("git shortlog [] [] [[--] ...]"), @@ -169,60 +170,6 @@ static void read_from_stdin(struct shortlog *log) strbuf_release(&oneline); } -struct strset_item { - struct hashmap_entry ent; - char value[FLEX_ARRAY]; -}; - -struct strset { - struct hashmap map; -}; - -#define STRSET_INIT { { NULL } } - -static int strset_item_hashcmp(const void *hash_data, - const struct hashmap_entry *entry, - const struct hashmap_entry *entry_or_key, - const void *keydata) -{ - const struct strset_item *a, *b; - - a = container_of(entry, const struct strset_item, ent); - if (keydata) - return strcmp(a->value, keydata); - - b = container_of(entry_or_key, const struct strset_item, ent); - return strcmp(a->value, b->value); -} - -/* - * Adds "str" to the set if it was not already present; returns true if it was - * already there. - */ -static int strset_check_and_add(struct strset *ss, const char *str) -{ - unsigned int hash = strhash(str); - struct strset_item *item; - - if (!ss->map.table) - hashmap_init(&ss->map, strset_item_hashcmp, NULL, 0); - - if (hashmap_get_from_hash(&ss->map, hash, str)) - return 1; - - FLEX_ALLOC_STR(item, value, str); - hashmap_entry_init(&item->ent, hash); - hashmap_add(&ss->map, &item->ent); - return 0; -} - -static void strset_clear(struct strset *ss) -{ - if (!ss->map.table) - return; - hashmap_clear_and_free(&ss->map, struct strset_item, ent); -} - static void insert_records_from_trailers(struct shortlog *log, struct strset *dups, struct commit *commit, @@ -253,7 +200,7 @@ static void insert_records_from_trailers(struct shortlog *log, if (!parse_ident(log, &ident, value)) value = ident.buf; - if (strset_check_and_add(dups, value)) + if (!strset_add(dups, value)) continue; insert_one_record(log, value, oneline); } @@ -291,7 +238,7 @@ void shortlog_add_commit(struct shortlog *log, struct commit *commit) log->email ? "%aN <%aE>" : "%aN", &ident, &ctx); if (!HAS_MULTI_BITS(log->groups) || - !strset_check_and_add(&dups, ident.buf)) + strset_add(&dups, ident.buf)) insert_one_record(log, ident.buf, oneline_str); } if (log->groups & SHORTLOG_GROUP_COMMITTER) { @@ -300,7 +247,7 @@ void shortlog_add_commit(struct shortlog *log, struct commit *commit) log->email ? "%cN <%cE>" : "%cN", &ident, &ctx); if (!HAS_MULTI_BITS(log->groups) || - !strset_check_and_add(&dups, ident.buf)) + strset_add(&dups, ident.buf)) insert_one_record(log, ident.buf, oneline_str); } if (log->groups & SHORTLOG_GROUP_TRAILER) {