From patchwork Fri Aug 21 18:52:25 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: John Passaro via GitGitGadget X-Patchwork-Id: 11730267 Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 1F216138C for ; Fri, 21 Aug 2020 18:52:48 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 0579620791 for ; Fri, 21 Aug 2020 18:52:48 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="U2TmCM2B" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726711AbgHUSwp (ORCPT ); Fri, 21 Aug 2020 14:52:45 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:56920 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726690AbgHUSwi (ORCPT ); Fri, 21 Aug 2020 14:52:38 -0400 Received: from mail-wm1-x335.google.com (mail-wm1-x335.google.com [IPv6:2a00:1450:4864:20::335]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 7613AC0613ED for ; Fri, 21 Aug 2020 11:52:38 -0700 (PDT) Received: by mail-wm1-x335.google.com with SMTP id k8so2788465wma.2 for ; Fri, 21 Aug 2020 11:52:38 -0700 (PDT) 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=jLC6+Dg0oFm7zIlpMUr3c3sbyDAR4md6X1v2GjWUA1E=; b=U2TmCM2Bp7wmjza/LW+7UYBlJqcjnKJTHtpCfaZTbHFlMqEnf0+eaZ5P2IS30P4ewD A/DsVSANiDd9EJe2tCDsUDeJ5/dp9B7+ndzoVZ8mZjxL/kpaCV6u/Cm+5FheIvEM1Qi2 zkUXOr0yYotsZBvtqj2Jk3hlm637dLxPwevC/C/cpt3RMwtIA1+ppIUTNCzmSCDNKS1L zL59a4wE0noFAVDL5E4a0e0swHi3q+1XK1Wlnd9zjRmBvg12rBKvyBpjP2+7loCeFGLN dgqbrYuRJyFpk3RbpYeBOJF4NRlKEl/ninlep/ipPrtwYXdqaI2pRv2pbATx4WCHRGpU Uqtw== 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=jLC6+Dg0oFm7zIlpMUr3c3sbyDAR4md6X1v2GjWUA1E=; b=fbgHnouCNAyoO7AQoO9apAau3gcT/bEKR+RsY7MDckdvk1GP/O/jh31HN4HSyhbhkQ KJTQwQj72Cxcs6SnXHs4ZdN8XrqzSewrc6FAa3xYvONvP1qL2KifF69zLFyxLlAomZ04 Ed56EkrJreDM0BYifpqjIcUuatlLr9iUY+AU+G3Cjri+K0ICbvlUcRWYTSUceWYV37IQ VR6oQwV4kT11RVwSUL+YdcFHJExFPkPGVIlkayRYk0EiFGo12Fp7l9vjN4XwvkuQB3ul W6CJzhXDAKA3xZn2cEFggg7qbz5g6xZP0rnhG4dZS4FRUZhDE+xaAk4xEUTyOeEgztoh hmmA== X-Gm-Message-State: AOAM530RWkIptdjk7u1EePsMUJCh6pFjNigy0EEl9hImk795Ao6fKbga /wF/dvOh64jIuuiwFo+Hsy3UV/94GUI= X-Google-Smtp-Source: ABdhPJydRprpYfDi/LO7eJIeFY5LxQWhYcN3XXxYKFOC93g2vabzvi+gZtLk9WZx9m6sr8et+95FJw== X-Received: by 2002:a1c:2501:: with SMTP id l1mr1561702wml.16.1598035951802; Fri, 21 Aug 2020 11:52:31 -0700 (PDT) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id p6sm6805851wmg.0.2020.08.21.11.52.31 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 21 Aug 2020 11:52:31 -0700 (PDT) Message-Id: In-Reply-To: References: From: "Elijah Newren via GitGitGadget" Date: Fri, 21 Aug 2020 18:52:25 +0000 Subject: [PATCH 1/5] hashmap: add usage documentation explaining hashmap_free[_entries]() Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Jeff King , Elijah Newren , Elijah Newren Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Elijah Newren The existence of hashmap_free() and hashmap_free_entries() confused me, and the docs weren't clear enough. I had to consult other source code examples and the implementation. Add a brief note to clarify, especially since hashmap_clear*() variants may be added in the future. Signed-off-by: Elijah Newren --- hashmap.h | 27 +++++++++++++++++++++++++-- 1 file changed, 25 insertions(+), 2 deletions(-) diff --git a/hashmap.h b/hashmap.h index ef220de4c6..a2f4adc1b3 100644 --- a/hashmap.h +++ b/hashmap.h @@ -236,13 +236,36 @@ 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 Fri Aug 21 18:52:26 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: John Passaro via GitGitGadget X-Patchwork-Id: 11730271 Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id D457A1392 for ; Fri, 21 Aug 2020 18:52:50 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id B64CA2076E for ; Fri, 21 Aug 2020 18:52:50 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="NUx+CKpV" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726730AbgHUSws (ORCPT ); Fri, 21 Aug 2020 14:52:48 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:56910 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726647AbgHUSwi (ORCPT ); Fri, 21 Aug 2020 14:52:38 -0400 Received: from mail-wm1-x336.google.com (mail-wm1-x336.google.com [IPv6:2a00:1450:4864:20::336]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id EED64C061575 for ; Fri, 21 Aug 2020 11:52:37 -0700 (PDT) Received: by mail-wm1-x336.google.com with SMTP id x5so2841949wmi.2 for ; Fri, 21 Aug 2020 11:52:37 -0700 (PDT) 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=XJYIWhbGYgy2LI4WVg5fpvlWd/v+EMmGDc4kl64UhnA=; b=NUx+CKpV2tcXqPS3+3fV7FZ9bUehIaNBr/fp5zm0KwtxQqNk+HCUhF5XspXoctXuwL FwMieVvfIenTGC1HmpvcG28svne4TV4eOTYimFUb1dmFdaCAog6uwHDa+2RSqJSyaBgd ZiSoYOAsh2XYQOktjaYavlB8lvsmIa0fWqOyNFjtMtl0o3pJP5sinXYb/ZDJ7qbKow6p acy7dywp7pURxSuSDTF6CoQEhXYZROVYdJhiaMx5b7lgvtCF6t7m36cBGeRnkIgLuklz uLYNA3MxlJj1AXQNrzUzeusbW9t09pkBhA+Xn51R61SHrtoxT3kW0kfRvKRsx/CI2jMK zP6Q== 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=XJYIWhbGYgy2LI4WVg5fpvlWd/v+EMmGDc4kl64UhnA=; b=fNceaS+pfKzkXK8rTKox9/Qjl9qA1G/wCfm6zijMVETmejYOI9TM9tOHPRIC3EsVir UWVl6V8tb8d1acX6PpiDGuUqqs7avM0hr4KwmruT9l1oF4N0h/ZvgVQRZJW3MQNulaLy mXq/wGN7sVnpfwBOQth+BxocsGpB1FKB3Zm0UHV/luX/5AoDqTORAAFJi50ZtgEJl/1x HuTSBVAsSZ+K8Ahk0LJ5Z4r2rjIidizhW2rk90R/8mIWcloccBnA1fGLpk/wi5k819of ZPSb2XJ9a01e895EJUL89NzRIRuFlSLcMEGWI9UNwTQGEky0U4ETpZuUJGWyUXnXWIFX mKAQ== X-Gm-Message-State: AOAM530kxr2SwTt3/bmxn75xsqfGAilP4/M0Q31W4taleFFr9ogbCfkj 5WbvE4I8FCxP4gXJbsuyw9k7xMdtOJc= X-Google-Smtp-Source: ABdhPJzKp1fP+BM5BqiMHHmwQZf35v3WU2xeG/TTl8PZzHd9GJ2fB0bH171nMMKyaaY5ZYzGFE85lQ== X-Received: by 2002:a1c:1f88:: with SMTP id f130mr4721903wmf.154.1598035952682; Fri, 21 Aug 2020 11:52:32 -0700 (PDT) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id k4sm6632994wrd.72.2020.08.21.11.52.32 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 21 Aug 2020 11:52:32 -0700 (PDT) Message-Id: In-Reply-To: References: From: "Elijah Newren via GitGitGadget" Date: Fri, 21 Aug 2020 18:52:26 +0000 Subject: [PATCH 2/5] strmap: new utility functions Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Jeff King , Elijah Newren , Elijah Newren Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org 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/ Peff only included the header, not the implementation, so it isn't clear what the structure was he was going to use for the hash entries. Instead of having my str_entry struct have three subfields (the hashmap_entry, the string, and the void* value), I made it only have two -- the hashmap_entry and a string_list_item, for two reasons: 1) a strmap is often the data structure we want where string_list has been used in the past. Using the same building block for individual entries in both makes it easier to adopt and reuse parts of the string_list API in strmap. 2) In some cases, after doing lots of other work, I want to be able to iterate over the items in my strmap in sorted order. hashmap obviously doesn't support that, but I wanted to be able to export the strmap to a string_list easily and then use its functions. (Note: I do not need the data structure to both be sorted and have efficient lookup at all times. If I did, I might use a B-tree instead, as suggested by brian in response to Peff in the thread noted above. In my case, most strmaps will never need sorting, but in one special case at the very end of a bunch of other work I want to iterate over the items in sorted order without doing any more lookups afterward.) Also, I removed the STRMAP_INIT macro, since it cannot be used to correctly initialize a strmap; the underlying hashmap needs a call to hashmap_init() to allocate the hash table first. Signed-off-by: Elijah Newren --- Makefile | 1 + strmap.c | 81 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ strmap.h | 47 ++++++++++++++++++++++++++++++++ 3 files changed, 129 insertions(+) create mode 100644 strmap.c create mode 100644 strmap.h diff --git a/Makefile b/Makefile index 65f8cfb236..0da15a9ee5 100644 --- a/Makefile +++ b/Makefile @@ -988,6 +988,7 @@ LIB_OBJS += strbuf.o LIB_OBJS += strvec.o LIB_OBJS += streaming.o LIB_OBJS += string-list.o +LIB_OBJS += strmap.o LIB_OBJS += sub-process.o LIB_OBJS += submodule-config.o LIB_OBJS += submodule.o diff --git a/strmap.c b/strmap.c new file mode 100644 index 0000000000..1c9fdb3b1e --- /dev/null +++ b/strmap.c @@ -0,0 +1,81 @@ +#include "git-compat-util.h" +#include "strmap.h" + +static int cmp_str_entry(const void *hashmap_cmp_fn_data, + const struct hashmap_entry *entry1, + const struct hashmap_entry *entry2, + const void *keydata) +{ + const struct str_entry *e1, *e2; + + e1 = container_of(entry1, const struct str_entry, ent); + e2 = container_of(entry2, const struct str_entry, ent); + return strcmp(e1->item.string, e2->item.string); +} + +static struct str_entry *find_str_entry(struct strmap *map, + const char *str) +{ + struct str_entry entry; + hashmap_entry_init(&entry.ent, strhash(str)); + entry.item.string = (char *)str; + return hashmap_get_entry(&map->map, &entry, ent, NULL); +} + +void strmap_init(struct strmap *map) +{ + hashmap_init(&map->map, cmp_str_entry, NULL, 0); +} + +void strmap_clear(struct strmap *map, int free_util) +{ + struct hashmap_iter iter; + struct str_entry *e; + + if (!map) + return; + + hashmap_for_each_entry(&map->map, &iter, e, ent /* member name */) { + free(e->item.string); + if (free_util) + free(e->item.util); + } + hashmap_free_entries(&map->map, struct str_entry, ent); + strmap_init(map); +} + +/* + * Insert "str" into the map, pointing to "data". A copy of "str" is made, so + * it does not need to persist after the this function is called. + * + * 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) +{ + struct str_entry *entry = find_str_entry(map, str); + void *old = NULL; + + if (entry) { + old = entry->item.util; + entry->item.util = data; + } else { + entry = xmalloc(sizeof(*entry)); + hashmap_entry_init(&entry->ent, strhash(str)); + entry->item.string = strdup(str); + entry->item.util = data; + hashmap_add(&map->map, &entry->ent); + } + return old; +} + +void *strmap_get(struct strmap *map, const char *str) +{ + struct str_entry *entry = find_str_entry(map, str); + return entry ? entry->item.util : NULL; +} + +int strmap_contains(struct strmap *map, const char *str) +{ + return find_str_entry(map, str) != NULL; +} diff --git a/strmap.h b/strmap.h new file mode 100644 index 0000000000..eb5807f6fa --- /dev/null +++ b/strmap.h @@ -0,0 +1,47 @@ +#ifndef STRMAP_H +#define STRMAP_H + +#include "hashmap.h" +#include "string-list.h" + +struct strmap { + struct hashmap map; +}; + +struct str_entry { + struct hashmap_entry ent; + struct string_list_item item; +}; + +/* + * Initialize an empty strmap + */ +void strmap_init(struct strmap *map); + +/* + * 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". A copy of "str" is made, so + * it does not need to persist after the this function is called. + * + * 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 Fri Aug 21 18:52:27 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: John Passaro via GitGitGadget X-Patchwork-Id: 11730265 Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 8BC4216B1 for ; Fri, 21 Aug 2020 18:52:44 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 6EBF82076E for ; Fri, 21 Aug 2020 18:52:44 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="MdayLfnt" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726706AbgHUSwn (ORCPT ); Fri, 21 Aug 2020 14:52:43 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:56904 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726645AbgHUSwg (ORCPT ); Fri, 21 Aug 2020 14:52:36 -0400 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 60462C061574 for ; Fri, 21 Aug 2020 11:52:35 -0700 (PDT) Received: by mail-wm1-x344.google.com with SMTP id p14so2854474wmg.1 for ; Fri, 21 Aug 2020 11:52:35 -0700 (PDT) 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=LPrFHbpoth+mxJptyUE+TeIv68nOfDNFxY+AnFxUX84=; b=MdayLfnt0A/nmXXAQbNwO7098Hnvs5wXMnYg9bBngmUDCCh4EQmgQ9ecO8GyGTKzOU YGv5aYIL9XlRTh0F2mRJvAw0eLXPUmCWl38Se1xXlOjSJNGuluF6XBf8haKybBpQF5ga fKUiKjb4nJUkvsYgmZi21UabcEr5RBZtFzVpsNPAUgdqJKVQFLe5cQYF36NVqI78WPa9 Zi1AjbqJOsCLTxaLYfE1JNyjrB3B9Vb4mc3GM5UmYIgzuEJ8+RTWWILfiYXcl4riYu32 xdpff0gO303zUln6g4Ep/XnPq5Sez6gTkQ9stEORa5L7ZZ7mPVL9/FGseP1INoVhop0i kA9g== 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=LPrFHbpoth+mxJptyUE+TeIv68nOfDNFxY+AnFxUX84=; b=UJMy3QQvHNLj8NHsocsne4wv591+kzNVngDSSwTZXfZ6kz2TMriDX/hO9h9MOw1K/+ GGv1o23Pr95DPRJ5IBfUq018ZdqwN+Sj0fR0dqT/HZFfgro0UAP+grjFt8BiYU8qqYYM mkKVDtaSfwrWV/EzFHmdBXDM6h2L5NjgSJV56ryI+/6P9UtZXJuf6Ny9GSgbZrRBpjN3 Nn85kIMYoNdIHOo3QdoChKh4s4ytyRu45+QNggG5x/P/u2+wNOSHhif2DxhasznSh3Jq RlUWYPsesW+HdkZaqM54jnBVWzXF+11Cnhj325EiTEDknx956HG47l7/yoW5xfkB/ype fr3g== X-Gm-Message-State: AOAM532+r52uWBOjlrfXE4bHwP69p445EA4E7dU9/6tPQJMU0g2Hllij Q76LULFGQvbcxlXJ3BWj+oxtOimg9dc= X-Google-Smtp-Source: ABdhPJwuVs8zrFgOTy736B7mV+24xoXE1xp/WAQqi3ghXs1k1CLZZ38VWo6IIwtkWrPWnQmQTj65Zg== X-Received: by 2002:a1c:61d5:: with SMTP id v204mr4630108wmb.102.1598035953478; Fri, 21 Aug 2020 11:52:33 -0700 (PDT) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id h13sm5769163wrx.17.2020.08.21.11.52.32 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 21 Aug 2020 11:52:33 -0700 (PDT) Message-Id: <5bda171d0c1562573800d4bcbfac4799f01d9c20.1598035949.git.gitgitgadget@gmail.com> In-Reply-To: References: From: "Elijah Newren via GitGitGadget" Date: Fri, 21 Aug 2020 18:52:27 +0000 Subject: [PATCH 3/5] strmap: add more utility functions Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Jeff King , Elijah Newren , Elijah Newren Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Elijah Newren This adds a number of additional convienence functions I want/need: * strmap_empty() * strmap_get_size() * strmap_remove() * strmap_for_each_entry() * strmap_free() * strmap_get_item() I suspect the first four are self-explanatory. strmap_free() differs from strmap_clear() in that the data structure is not reusable after it is called; strmap_clear() is not sufficient for the API because without strmap_free() we will leak memory. strmap_get_item() is similar to strmap_get() except that instead of just returning the void* value that the string maps to, it returns the string_list_item 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_item() and then: * check if the string was in the map by whether the pointer is NULL * access the value via item->util * directly update item->util meaning that we can replace two or three hash table lookups with one. Signed-off-by: Elijah Newren --- strmap.c | 35 ++++++++++++++++++++++++++++++----- strmap.h | 43 +++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 73 insertions(+), 5 deletions(-) diff --git a/strmap.c b/strmap.c index 1c9fdb3b1e..a4bfffcd8b 100644 --- a/strmap.c +++ b/strmap.c @@ -27,7 +27,7 @@ void strmap_init(struct strmap *map) hashmap_init(&map->map, cmp_str_entry, NULL, 0); } -void strmap_clear(struct strmap *map, int free_util) +void strmap_free(struct strmap *map, int free_util) { struct hashmap_iter iter; struct str_entry *e; @@ -35,12 +35,19 @@ void strmap_clear(struct strmap *map, int free_util) if (!map) return; - hashmap_for_each_entry(&map->map, &iter, e, ent /* member name */) { - free(e->item.string); - if (free_util) - free(e->item.util); + if (free_util) { + hashmap_for_each_entry(&map->map, &iter, e, ent) { + free(e->item.string); + if (free_util) + free(e->item.util); + } } hashmap_free_entries(&map->map, struct str_entry, ent); +} + +void strmap_clear(struct strmap *map, int free_util) +{ + strmap_free(map, free_util); strmap_init(map); } @@ -69,6 +76,13 @@ void *strmap_put(struct strmap *map, const char *str, void *data) return old; } +struct string_list_item *strmap_get_item(struct strmap *map, + const char *str) +{ + struct str_entry *entry = find_str_entry(map, str); + return entry ? &entry->item : NULL; +} + void *strmap_get(struct strmap *map, const char *str) { struct str_entry *entry = find_str_entry(map, str); @@ -79,3 +93,14 @@ int strmap_contains(struct strmap *map, const char *str) { return find_str_entry(map, str) != NULL; } + +void strmap_remove(struct strmap *map, const char *str, int free_util) +{ + struct str_entry entry, *ret; + hashmap_entry_init(&entry.ent, strhash(str)); + entry.item.string = (char *)str; + ret = hashmap_remove_entry(&map->map, &entry, ent, NULL); + if (ret && free_util) + free(ret->item.util); + free(ret); +} diff --git a/strmap.h b/strmap.h index eb5807f6fa..45d0a4f714 100644 --- a/strmap.h +++ b/strmap.h @@ -21,6 +21,11 @@ void strmap_init(struct strmap *map); /* * Remove all entries from the map, releasing any allocated resources. */ +void strmap_free(struct strmap *map, int free_values); + +/* + * Same as calling strmap_free() followed by strmap_init(). + */ void strmap_clear(struct strmap *map, int free_values); /* @@ -32,6 +37,12 @@ void strmap_clear(struct strmap *map, int free_values); */ void *strmap_put(struct strmap *map, const char *str, void *data); +/* + * Return the string_list_item mapped by "str", or NULL if there is not such + * an item in map. + */ +struct string_list_item *strmap_get_item(struct strmap *map, const char *str); + /* * Return the data pointer mapped by "str", or NULL if the entry does not * exist. @@ -44,4 +55,36 @@ 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 whether the strmap is empty. + */ +static inline int strmap_empty(struct strmap *map) +{ + return hashmap_get_size(&map->map) == 0; +} + +/* + * Return how many entries the strmap has. + */ +static inline unsigned int strmap_get_size(struct strmap *map) +{ + return hashmap_get_size(&map->map); +} + +/* + * iterate through @map using @iter, @var is a pointer to a type str_entry + */ +#define strmap_for_each_entry(mystrmap, iter, var) \ + for (var = hashmap_iter_first_entry_offset(&(mystrmap)->map, iter, \ + OFFSETOF_VAR(var, ent)); \ + var; \ + var = hashmap_iter_next_entry_offset(iter, \ + OFFSETOF_VAR(var, ent))) + #endif /* STRMAP_H */ From patchwork Fri Aug 21 18:52:28 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: John Passaro via GitGitGadget X-Patchwork-Id: 11730273 Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 69BD6138C for ; Fri, 21 Aug 2020 18:53:08 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 510E320791 for ; Fri, 21 Aug 2020 18:53:08 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="QqjzGzrq" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726734AbgHUSxH (ORCPT ); Fri, 21 Aug 2020 14:53:07 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:56986 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726578AbgHUSxG (ORCPT ); Fri, 21 Aug 2020 14:53:06 -0400 Received: from mail-wm1-x335.google.com (mail-wm1-x335.google.com [IPv6:2a00:1450:4864:20::335]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id B8CECC061573 for ; Fri, 21 Aug 2020 11:53:05 -0700 (PDT) Received: by mail-wm1-x335.google.com with SMTP id k8so2789613wma.2 for ; Fri, 21 Aug 2020 11:53:05 -0700 (PDT) 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=QT9k16JOKNndkpZDiEFnCKJW+UcvNcMp6F+vJeEQnSo=; b=QqjzGzrqhXcJ16cPqxL3DB9UQtMS4ATtWLq9UYfJ2BVJAwm5jV6ceTqHjF6WW4R2Nv O6CD+cV89mHRVWLjoJKcFsKbxwfDT+36MCgmXOgbE7IpFk4JL2J8AOx/hN+n0agASWy0 IrJS3+eLUZFzMY2vhE/Hf27ucTPj4Oj9k9QBFyfBz7OVar/Nk5qJRYesu3pIMCyhYuB1 wqrVzkhNvwsYCjCkGSdWGs2kS5GPiRMq0BHUJYN4qik1sfGVbXLyHFOMXwIM0LfdP6NT 4J1f2WnKWYjjvv5tlErKHyI6XGoBlHJsK/eYU/+DzAmdC24UGYuwrfjmJS/V8uaCTM3v eyGA== 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=QT9k16JOKNndkpZDiEFnCKJW+UcvNcMp6F+vJeEQnSo=; b=bCERP7jf5UYPfk/BUa2tRuQfLiUtOd0rSE9/KOijEv3smTyCqk+z/iBQs+Kss1ctVu 6gCmeExvvxLMP0+ELaVFIPorcv+7lWkeCeSwg5wCvQdybp6Tl4k5i/ye+glwoS+eF3Cb CYQMH+WGh9dgxdbEtVt1V8uLW9U6fie9iRPWrgoOd1aO4UcxS9Bg5q1ib8Yf2H3EXS3i 1ZEAZ3HnGYpuWhM/TwR8bIrhqpyPFkLvpWiaFKw5k8CNc7Va+gV8CfDTuFlE0uhabG1A RsmKYced6ZQ4Mvzd0tDK3iHVx+z6OGzePBX4I3E/PDFcwd/6auWz+ZwQGSv7HNaLQsdo 5TJw== X-Gm-Message-State: AOAM530qwDJZuiQt/Q9MvM8UjzvyeqlxL8Gkeww/tpblmEyoDWhYui4c wWei4AGO1TQzSqIlV0RCtRVksDCwRRU= X-Google-Smtp-Source: ABdhPJzSFV4t8yg53uX6y+uW171JtVVJre/sXlxS+UjSmLKRiGLhxRebsKT6yrVj1AMnOCr/8xM2CQ== X-Received: by 2002:a05:600c:2116:: with SMTP id u22mr5072590wml.35.1598035954295; Fri, 21 Aug 2020 11:52:34 -0700 (PDT) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id a3sm6942672wme.34.2020.08.21.11.52.33 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 21 Aug 2020 11:52:33 -0700 (PDT) Message-Id: In-Reply-To: References: From: "Elijah Newren via GitGitGadget" Date: Fri, 21 Aug 2020 18:52:28 +0000 Subject: [PATCH 4/5] strmap: add strdup_strings option Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Jeff King , Elijah Newren , Elijah Newren Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Elijah Newren Just as it is sometimes useful for string_list to duplicate and take ownership of memory management of the strings it contains, the same is sometimes true for strmaps as well. Add the same flag from string_list to strmap. Signed-off-by: Elijah Newren --- strmap.c | 23 ++++++++++++++++------- strmap.h | 9 +++++---- 2 files changed, 21 insertions(+), 11 deletions(-) diff --git a/strmap.c b/strmap.c index a4bfffcd8b..03eb6af45d 100644 --- a/strmap.c +++ b/strmap.c @@ -22,9 +22,10 @@ static struct str_entry *find_str_entry(struct strmap *map, return hashmap_get_entry(&map->map, &entry, ent, NULL); } -void strmap_init(struct strmap *map) +void strmap_init(struct strmap *map, int strdup_strings) { hashmap_init(&map->map, cmp_str_entry, NULL, 0); + map->strdup_strings = strdup_strings; } void strmap_free(struct strmap *map, int free_util) @@ -35,9 +36,10 @@ void strmap_free(struct strmap *map, int free_util) if (!map) return; - if (free_util) { + if (map->strdup_strings || free_util) { hashmap_for_each_entry(&map->map, &iter, e, ent) { - free(e->item.string); + if (map->strdup_strings) + free(e->item.string); if (free_util) free(e->item.util); } @@ -48,12 +50,11 @@ void strmap_free(struct strmap *map, int free_util) void strmap_clear(struct strmap *map, int free_util) { strmap_free(map, free_util); - strmap_init(map); + strmap_init(map, map->strdup_strings); } /* - * Insert "str" into the map, pointing to "data". A copy of "str" is made, so - * it does not need to persist after the this function is called. + * 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. @@ -69,7 +70,13 @@ void *strmap_put(struct strmap *map, const char *str, void *data) } else { entry = xmalloc(sizeof(*entry)); hashmap_entry_init(&entry->ent, strhash(str)); - entry->item.string = strdup(str); + /* + * We won't modify entry->item.string so it really should be + * const, but changing string_list_item to use a const char * + * is a bit too big of a change at this point. + */ + entry->item.string = + map->strdup_strings ? xstrdup(str) : (char *)str; entry->item.util = data; hashmap_add(&map->map, &entry->ent); } @@ -100,6 +107,8 @@ void strmap_remove(struct strmap *map, const char *str, int free_util) hashmap_entry_init(&entry.ent, strhash(str)); entry.item.string = (char *)str; ret = hashmap_remove_entry(&map->map, &entry, ent, NULL); + if (map->strdup_strings) + free(ret->item.string); if (ret && free_util) free(ret->item.util); free(ret); diff --git a/strmap.h b/strmap.h index 45d0a4f714..28a98c5a4b 100644 --- a/strmap.h +++ b/strmap.h @@ -6,6 +6,7 @@ struct strmap { struct hashmap map; + unsigned int strdup_strings:1; }; struct str_entry { @@ -14,9 +15,10 @@ struct str_entry { }; /* - * Initialize an empty strmap + * Initialize the members of the strmap, set `strdup_strings` + * member according to the value of the second parameter. */ -void strmap_init(struct strmap *map); +void strmap_init(struct strmap *map, int strdup_strings); /* * Remove all entries from the map, releasing any allocated resources. @@ -29,8 +31,7 @@ void strmap_free(struct strmap *map, int free_values); void strmap_clear(struct strmap *map, int free_values); /* - * Insert "str" into the map, pointing to "data". A copy of "str" is made, so - * it does not need to persist after the this function is called. + * 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. From patchwork Fri Aug 21 18:52:29 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: John Passaro via GitGitGadget X-Patchwork-Id: 11730269 Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 1B895138C for ; Fri, 21 Aug 2020 18:52:49 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 04EF220791 for ; Fri, 21 Aug 2020 18:52:49 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="abtj+B3z" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726727AbgHUSwr (ORCPT ); Fri, 21 Aug 2020 14:52:47 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:56918 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726682AbgHUSwi (ORCPT ); Fri, 21 Aug 2020 14:52:38 -0400 Received: from mail-wm1-x332.google.com (mail-wm1-x332.google.com [IPv6:2a00:1450:4864:20::332]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 621E3C061755 for ; Fri, 21 Aug 2020 11:52:38 -0700 (PDT) Received: by mail-wm1-x332.google.com with SMTP id t14so2780365wmi.3 for ; Fri, 21 Aug 2020 11:52:38 -0700 (PDT) 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=kkaPjl9wusTTa7slj9B8jUG/++0w8k/jaaFOQ+MQnzI=; b=abtj+B3zCJYtmdy85Gz6EfqDQM5AKolnrK5UcC8UNHkeeQdpt3ogXZUzGb1ASAfkb5 lpxJeWzfG1VLew80TlOxMhHWcjHGSZBX877QuFVmU2QgCKk1v93rsbz58R7YJa+gxp9L Dp4iBoXyuZ2uGGPbJKLiK879bmJS1SRQJHaPhHSaQzA4F1meK9I1abIMpq4/UfGUotvE iWd3mz7MqrP8huZRgtmFRrs3sx9CGzCaoD53MdPgCcX382iuLxYCLk2GNrEvHg6Y/l6M wfGybyjVbI9Hjkd5SeRUMXgd6gCOwk9Wj6EMShPEdW+uUFGmzDswRpTtVoWGCj+uXTRR Uhpg== 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=kkaPjl9wusTTa7slj9B8jUG/++0w8k/jaaFOQ+MQnzI=; b=Ve69cn16vm3/38OCd+ytDM1KJ5wxPmMZufPUzGPcipfkJTAhcnYRL6oFRKJUVBK3ZG ZMfIjFElOCXr0T1E/qqDX8utSxwpkn1Dd8mKriQzL15Z4PCqiH+ggM7QADtYVGwjIVAP OIofsAoCyDmw6kQO3orbNgUKPHrNnlIV1bBNIDBjZkVGOIqZl0o186JlAr0fxplcSvq1 IvQEuK8oHbrLEpzHc2EwRLKsr6I1tAGIW0EckmeIlozn8rbTulrWgpE6QNTH37fHJIa0 Y032b6HeO/WO41CC2CfNuFfdf7ttPR/WPr8Lo5xoCrsjSA8XXpIXZPHFgDB5BHd5j/IU FPgA== X-Gm-Message-State: AOAM531ok1Ag53TPKrkaGd3RzLHjvt4PtMPjGXZIpeEg07Oz5UCYx0nI MBlgye+ahF75KpeX7uz7vfGAA5W5PEI= X-Google-Smtp-Source: ABdhPJy/xz+w8SiMeXvTf2GiE6Wjys165l0Zw0sj/NSa1K4ZfB8HBiFBZSsKJz1oqGCiX9ywrGFo/A== X-Received: by 2002:a1c:a385:: with SMTP id m127mr5404727wme.189.1598035954970; Fri, 21 Aug 2020 11:52:34 -0700 (PDT) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id i7sm6378713wrs.25.2020.08.21.11.52.34 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 21 Aug 2020 11:52:34 -0700 (PDT) Message-Id: <418975b46039f63476852a868ca6221244b5d88e.1598035949.git.gitgitgadget@gmail.com> In-Reply-To: References: From: "Elijah Newren via GitGitGadget" Date: Fri, 21 Aug 2020 18:52:29 +0000 Subject: [PATCH 5/5] 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 , Elijah Newren Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org 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. A note on the name: strintmap looks and sounds pretty lame to me, but after trying to come up with something better and having no luck, I figured I'd just go with it for a while and then at some point some better and obvious name would strike me and I could replace it. Several months later, I still don't have a better name. Hopefully someone else has one. Signed-off-by: Elijah Newren --- strmap.c | 11 +++++++++++ strmap.h | 32 ++++++++++++++++++++++++++++++++ 2 files changed, 43 insertions(+) diff --git a/strmap.c b/strmap.c index 03eb6af45d..cbb99f4030 100644 --- a/strmap.c +++ b/strmap.c @@ -113,3 +113,14 @@ void strmap_remove(struct strmap *map, const char *str, int free_util) free(ret->item.util); free(ret); } + +void strintmap_incr(struct strmap *map, const char *str, intptr_t amt) +{ + struct str_entry *entry = find_str_entry(map, str); + if (entry) { + intptr_t *whence = (intptr_t*)&entry->item.util; + *whence += amt; + } + else + strintmap_set(map, str, amt); +} diff --git a/strmap.h b/strmap.h index 28a98c5a4b..5d9dd3ef58 100644 --- a/strmap.h +++ b/strmap.h @@ -88,4 +88,36 @@ static inline unsigned int strmap_get_size(struct strmap *map) var = hashmap_iter_next_entry_offset(iter, \ OFFSETOF_VAR(var, ent))) +/* + * Helper functions for using strmap as map of string -> int, using the void* + * field to store the int instead of allocating an int and having the void* + * member point to the allocated int. + */ + +static inline int strintmap_get(struct strmap *map, const char *str, + int default_value) +{ + struct string_list_item *result = strmap_get_item(map, str); + if (!result) + return default_value; + return (intptr_t)result->util; +} + +static inline void strintmap_set(struct strmap *map, const char *str, intptr_t v) +{ + strmap_put(map, str, (void *)v); +} + +void strintmap_incr(struct strmap *map, const char *str, intptr_t amt); + +static inline void strintmap_clear(struct strmap *map) +{ + strmap_clear(map, 0); +} + +static inline void strintmap_free(struct strmap *map) +{ + strmap_free(map, 0); +} + #endif /* STRMAP_H */ From patchwork Tue Oct 13 00:40:46 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 11834717 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 88C11C64E90 for ; Tue, 13 Oct 2020 02:42:20 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 4E8DD221FF for ; Tue, 13 Oct 2020 02:42:20 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="KSur9O4p" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727923AbgJMAlC (ORCPT ); Mon, 12 Oct 2020 20:41:02 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:49160 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727905AbgJMAk7 (ORCPT ); Mon, 12 Oct 2020 20:40:59 -0400 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 4738FC0613D6 for ; Mon, 12 Oct 2020 17:40:59 -0700 (PDT) Received: by mail-wr1-x444.google.com with SMTP id b8so8485860wrn.0 for ; Mon, 12 Oct 2020 17:40:59 -0700 (PDT) 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=KEnjSmKih4lWnAW0mb4Dt4TMKpeMKIrQtliv1GGUO54=; b=KSur9O4p3UwBeV8pAbSUv/PAKSU5Ax1cHnCjS7I9SfLJ/i0KpBUqfERzfpy4Q6/rG/ n5WtjjYDXGnKY76oQCzXqr0i5w2eDEGAAaY/Y3LuRMs8L1RM+fTij6NJGAV0ya2eXnrs BkBVq17PW4PI0X5Er2y1Hef7/+KY1OoeJ5lJye+R2q2AV+WrOkUyv3CXtabk5ifzQoMB JVp+hHNPKIbTl9zccSQlvLoSbiAe21niupyux8Qj/AxTQBYXMR/r6DdN3geaYrYedkrf cAc2lyWJWxk/upqmsADol9KjhC9TLfcbVYkMEMPgR4LK4MtIY21e/HQ8/X84gw6tCOjB iIqg== 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=KEnjSmKih4lWnAW0mb4Dt4TMKpeMKIrQtliv1GGUO54=; b=NM0BPqGw/Apm/yJC3RiLSKISlP2cwxNWQ/ribq2aULm2el/DeobWcvjh3aNC2H7kSB pyx22UnX9znnBtDvHpEbYMWQ0ridFGyMjm2uE2CdVuWP/AFiXsJ858pj/v57rUNu8Ow8 Gp6sx41VhZkyx0CqsSq6OkNn+9C6evh7RTOkNOZJii9t7lk9zUayuT1j+4McInY5JTTK YwX/+6Lp8IfIHPf3Valp1KBC0li1DQA703VrO6nove8TfEO0nONRCQ9Sb4Xj22JbQTW6 S4km0gOhNbYu/ihGwtNHT844sBDU4nHtPzSy/nLVyoZ+58bQ7IKNTBEguNbShxfcE+1b ApFQ== X-Gm-Message-State: AOAM533AFjfHg8V37Oq/+V5S2qIFwbqAanFn0JCXnxcIMxf9PAfcfdHf MnbsdA87/5yBCRy3VPmMtL5kVZoWeSk= X-Google-Smtp-Source: ABdhPJxIhPCJ+UIKhOLEViVANPtmsmcfYMGD+RlRUQH/7md5/2dzjCuYtAAOOhNSmB4ALzqHPoP7tw== X-Received: by 2002:adf:f7ca:: with SMTP id a10mr32236039wrq.321.1602549657786; Mon, 12 Oct 2020 17:40:57 -0700 (PDT) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id z15sm27838288wrq.24.2020.10.12.17.40.57 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 12 Oct 2020 17:40:57 -0700 (PDT) Message-Id: <61b5bf11103a7bd12de8fd066e128c469da3a0a4.1602549650.git.gitgitgadget@gmail.com> In-Reply-To: References: Date: Tue, 13 Oct 2020 00:40:46 +0000 Subject: [PATCH v2 06/10] strmap: add more utility functions Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Jeff King , 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_empty() * strmap_get_size() * 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 | 38 ++++++++++++++++++++++++++++++++++++++ 2 files changed, 58 insertions(+) diff --git a/strmap.c b/strmap.c index 4b48d64274..909b9fbedf 100644 --- a/strmap.c +++ b/strmap.c @@ -90,6 +90,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); @@ -100,3 +105,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_util) +{ + 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_util) + free(ret->value); + if (map->strdup_strings) + free((char*)ret->key); + free(ret); +} diff --git a/strmap.h b/strmap.h index 493d19cbc0..e49d020970 100644 --- a/strmap.h +++ b/strmap.h @@ -42,6 +42,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. @@ -54,4 +60,36 @@ 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 whether the strmap is empty. + */ +static inline int strmap_empty(struct strmap *map) +{ + return hashmap_get_size(&map->map) == 0; +} + +/* + * Return how many entries the strmap has. + */ +static inline unsigned int strmap_get_size(struct strmap *map) +{ + return hashmap_get_size(&map->map); +} + +/* + * iterate through @map using @iter, @var is a pointer to a type strmap_entry + */ +#define strmap_for_each_entry(mystrmap, iter, var) \ + for (var = hashmap_iter_first_entry_offset(&(mystrmap)->map, iter, \ + OFFSETOF_VAR(var, ent)); \ + var; \ + var = hashmap_iter_next_entry_offset(iter, \ + OFFSETOF_VAR(var, ent))) + #endif /* STRMAP_H */ From patchwork Tue Oct 13 00:40:47 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 11834713 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 4FAAFC71155 for ; Tue, 13 Oct 2020 02:42:20 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 2B38A221EB for ; Tue, 13 Oct 2020 02:42:20 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="fR9sa/Zk" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727926AbgJMAlC (ORCPT ); Mon, 12 Oct 2020 20:41:02 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:49162 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727912AbgJMAlA (ORCPT ); Mon, 12 Oct 2020 20:41:00 -0400 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 047AFC0613D0 for ; Mon, 12 Oct 2020 17:41:00 -0700 (PDT) Received: by mail-wm1-x344.google.com with SMTP id j136so19781160wmj.2 for ; Mon, 12 Oct 2020 17:40:59 -0700 (PDT) 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=Muujgt417JEkdvHe28Rt9c6zu2G+4ovZmfbKD5m49hc=; b=fR9sa/ZkqOpe0nba5BPZM01hiFgBmBj/u98L/Qa2emL+IXieVsy1xoG4QsX1e40X0w pxsRhlJN85H9FGdstLkPDPj51RMO+fPCJ56UHvYyA07O/l8uqdEWo/9ElSJpmqePDUfe o/+dMWvU5YBfoQHYKRafodMZxoE4iL2BZTOCnNmoL3HpWXLyk/NXR1mRWBow8oAPxQCA HrH5B0f2k/EhTcBZZ6QQbJ7+Qtr8cs7mbk36sxsK1mHe9MWDyGcvxl+qll3ZuBjHIZj/ /OhhYhE4Fn1kgJrFv2lYxR15m6WaaYAjyvbKQ5DwLyh7QGh18XXleJoDRnMyxuqangV1 SxGQ== 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=Muujgt417JEkdvHe28Rt9c6zu2G+4ovZmfbKD5m49hc=; b=ezZvtTlTYRfQiGOGhMoAREayCE/yfrYPfV/+XvIMC3DbQymVMWZIJR6UZlPqbe3pKy EXOuwfHwVRvih3bkHcDJQBI31CHCPYtOaPetcfhhrEItgTFyJ4ZEPU3ABlMKYDBlTEbj vtOk4Eukea/nyn3AYJJeVeuZfV3gz0esXRg47dmWV4/rWycZlonyMMG952Q61gcfOFyI k14qfRrJEgh7ajeqQoIfsoI88IXELkYDSPioipgKkob7OBs0N+lknKpWM3q5d7lJVhti mGsw0oTz335CAEEcUDNktUOYwZ1P7YYlEmhoaSPd280HSALYQlOcO8UJfZbAtWx8yRg2 nfAw== X-Gm-Message-State: AOAM530GEgWWsddLxjCwHmMZagunSDpnE6t9jKy6jjmH5PINWAsKinKz X5rry0daXr9bXHFV9oS2C/hT6kvGP+Q= X-Google-Smtp-Source: ABdhPJzthn+kBSvj9zbR6R1FQfeoK5XQPhz78WJLkDWnAXbaqDuoe2EQYjCImzlk8yYGfNRH0i4/ww== X-Received: by 2002:a05:600c:4147:: with SMTP id h7mr12508951wmm.45.1602549658618; Mon, 12 Oct 2020 17:40:58 -0700 (PDT) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id o4sm8313049wrv.8.2020.10.12.17.40.58 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 12 Oct 2020 17:40:58 -0700 (PDT) Message-Id: <2ebce0c5d82b87fa9c9ef5dcefc0ac2701654f3b.1602549650.git.gitgitgadget@gmail.com> In-Reply-To: References: Date: Tue, 13 Oct 2020 00:40:47 +0000 Subject: [PATCH v2 07/10] strmap: enable faster clearing and reusing of strmaps Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Jeff King , 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 reset_maps() 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 909b9fbedf..47cbf11ec7 100644 --- a/strmap.c +++ b/strmap.c @@ -64,6 +64,12 @@ void strmap_clear(struct strmap *map, int free_util) hashmap_free(&map->map); } +void strmap_partial_clear(struct strmap *map, int free_util) +{ + strmap_free_entries_(map, free_util); + 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 e49d020970..5bb7650d65 100644 --- a/strmap.h +++ b/strmap.h @@ -34,6 +34,12 @@ void strmap_ocd_init(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 Tue Oct 13 00:40:48 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 11834709 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 F3AE4C8300B for ; Tue, 13 Oct 2020 02:42:20 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id B632F221FF for ; Tue, 13 Oct 2020 02:42:20 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="hs8hJlmL" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727934AbgJMAlG (ORCPT ); Mon, 12 Oct 2020 20:41:06 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:49168 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727917AbgJMAlB (ORCPT ); Mon, 12 Oct 2020 20:41:01 -0400 Received: from mail-wr1-x42b.google.com (mail-wr1-x42b.google.com [IPv6:2a00:1450:4864:20::42b]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id C0354C0613D0 for ; Mon, 12 Oct 2020 17:41:00 -0700 (PDT) Received: by mail-wr1-x42b.google.com with SMTP id x7so13096889wrl.3 for ; Mon, 12 Oct 2020 17:41:00 -0700 (PDT) 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=fSoV1INTQ09lAoLPXCoEd4scIa7g6B+DTa5en96mUT8=; b=hs8hJlmLPTAhlp4YvWcmZrjKpI25Ts50lpuM1UDwC6kVw9y8dZNHyl6wEbA7auahDe 2T6L8MccgDqSGvg1w/K24Jic0U17FnXp+jLAaJ2Sdw8EBoWp9UQej26gNgzAUaHhgyjm c5bY0RpqnhB3FXkP0Cbc+/tA68LG/wBzNY5O0QOH4VyrfhZIkL2QKdgRwZYjlXn1kB1S mzm99eXTIWIDIVHdMj8kUo3DJ4pawTaAWnbWrGk0cROdMfyPGJTB1Sk3+sr4EJKZViyr gDgIBPYSzDAAa9qi1PP/pT66A7lvI8Ca0Zo8ScgbIGAAQzUy68oCz8WLN1pI6qs//qS2 f35w== 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=fSoV1INTQ09lAoLPXCoEd4scIa7g6B+DTa5en96mUT8=; b=W2Wo3sC6zUhYCaNN5dxCZc4opcuV1zUs9o0KUoJrJ3CPylkL7lcKsEk/SyjGME715I b6Sm1jKGAC2PoJGTm4Z7yyUoJrQR7O4MimPI+6STZlmaaOzF53HJtaGEhTp6upQf5/o9 bBkuLRgwEQcWdw7a2w5ptutYfifkUI6pBMPYQKJGCAFT4MMdZ1DAntdQeQ2XCWUb0bHh QH3Ize+15VGPB/LcoTPTzqgPjsUr5d73/AFisQ+Q5OhHHsPimJcZWctRQ2GKMl3HG7HA YOhjrySuurdrFEou+YLzRnNjZqopPqxy/E/Q1iTRh3sIF/wVOjhJSFM5vc1M7QlP6HvW /clw== X-Gm-Message-State: AOAM531NL5cmxTqpCn2I7azgMJ2eScB4wvEP581nopPv/dfYOy9GBmVR S0tvBLz9EgB3Y4xRnIubto01fV5XesQ= X-Google-Smtp-Source: ABdhPJxfvy5+yTGCBfPRqvi+HFu5hRSRUXHUWmHLWOduMQzqD4ooZrsPqQKGwevMWBIbgVgUc7d0PQ== X-Received: by 2002:adf:fcc3:: with SMTP id f3mr3112151wrs.336.1602549659326; Mon, 12 Oct 2020 17:40:59 -0700 (PDT) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id i10sm8501715wrq.27.2020.10.12.17.40.58 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 12 Oct 2020 17:40:58 -0700 (PDT) Message-Id: In-Reply-To: References: Date: Tue, 13 Oct 2020 00:40:48 +0000 Subject: [PATCH v2 08/10] 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 , 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. A note on the name: if anyone has a better name suggestion than strintmap, I'm happy to take it. It seems slightly unwieldy, but I have not been able to come up with a better name. Signed-off-by: Elijah Newren --- strmap.c | 11 ++++++++ strmap.h | 80 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 91 insertions(+) diff --git a/strmap.c b/strmap.c index 47cbf11ec7..d5003a79e3 100644 --- a/strmap.c +++ b/strmap.c @@ -126,3 +126,14 @@ void strmap_remove(struct strmap *map, const char *str, int free_util) 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, amt); +} diff --git a/strmap.h b/strmap.h index 5bb7650d65..fe15e74b78 100644 --- a/strmap.h +++ b/strmap.h @@ -98,4 +98,84 @@ static inline unsigned int strmap_get_size(struct strmap *map) var = hashmap_iter_next_entry_offset(iter, \ OFFSETOF_VAR(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; it also requires an extra parameter to + * be specified so it knows what value to return if the underlying strmap + * has not key matching the given string. + * 3) No strmap_put() equivalent; strintmap_set() and strintmap_incr() + * instead. + */ + +struct strintmap { + struct strmap map; +}; + +#define strintmap_for_each_entry(mystrmap, iter, var) \ + strmap_for_each_entry(&(mystrmap)->map, iter, var) + +static inline void strintmap_init(struct strintmap *map) +{ + strmap_init(&map->map); +} + +static inline void strintmap_ocd_init(struct strintmap *map, + int strdup_strings) +{ + strmap_ocd_init(&map->map, strdup_strings); +} + +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); +} + +static inline int strintmap_get(struct strintmap *map, const char *str, + int default_value) +{ + struct strmap_entry *result = strmap_get_entry(&map->map, str); + if (!result) + return 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); +} + +void strintmap_incr(struct strintmap *map, const char *str, intptr_t amt); + #endif /* STRMAP_H */ From patchwork Tue Oct 13 00:40:49 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 11834719 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 B9CEEC8300A for ; Tue, 13 Oct 2020 02:42:20 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 953AF221FC for ; Tue, 13 Oct 2020 02:42:20 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="Vz4k2Osd" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727928AbgJMAlF (ORCPT ); Mon, 12 Oct 2020 20:41:05 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:49170 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727922AbgJMAlB (ORCPT ); Mon, 12 Oct 2020 20:41:01 -0400 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 7EA0CC0613D1 for ; Mon, 12 Oct 2020 17:41:01 -0700 (PDT) Received: by mail-wm1-x343.google.com with SMTP id d3so19770759wma.4 for ; Mon, 12 Oct 2020 17:41:01 -0700 (PDT) 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=iWvAwS9aXbUqDr3/4BBwlTWRv2d1rnfnw12nVrdpWDc=; b=Vz4k2Osdng01RKivC067jphnQ4KKzvWqPDPLsOBKwIrw8tRhRTZO9f6Z/TaamcyXQ+ rTgocB6RXER5FzeLl5NxrgVUeyqL8pW2hwuOAJ6S0pN/dM8rxsNEjmEZMQXG8UoptxI1 Ha3CqdZQMxdnqpxsqarziXup98fMKdMFfP7QWjpdJQt5rYukeGOlYJ++1scn4H9FU5Dc pnHv2nTbp5jdJQdY8W/NIHaCA4ciQ7KK4AWDHRQ2C9AjBjaxj6BpSMxklvboIb5YlrI2 /7baJwsrHSE6Yutf9pZN4CTIPmuYlE6y6bizT2NjdRTjP3MleJCTmLbiNGOv0UhQ6n3s Y4hg== 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=iWvAwS9aXbUqDr3/4BBwlTWRv2d1rnfnw12nVrdpWDc=; b=Z5vpyWO1isbKttMTISBH9m7CcxtuWiNpXC87B6PCyWQxWUgfI4K1K1FwH3l5A5k7cc +R8pwmnoRgq5dFJBIskMyPfEJx3G9Q08xvvVExKqHFYgDey+oVQyj+yEEWwpUO+ZG7Qk Hv/SyfGbx7n5TivkhOHOSABjf1yjd8/v9HHOi8QQlUFbyWflKwwcli3rAdemR9nDBXZ+ XvSlUN9DVXlV0VtBFr7zcTJMohppjQoPAZJYGnlcLHuh/OAafVgfJGPIYy99XBVcfNr9 B+nVyLEVnlHRqhqfjXJHFlfSxgO7XKbiVB6jUlp+cskF6TBYR10OEoMR0UDwIlZyMNwG 0GQg== X-Gm-Message-State: AOAM5314bAvpTAf9ZqbNaN2lD4OHmDFXpODUAzS6st8PBx2qBhF/ct3c 5eNuApFFKrtqVxJ6aAP7DiUpzNxkneQ= X-Google-Smtp-Source: ABdhPJyu+Y4k5Wz+QmlbFViDY0hijdFvPrf3PQN19Kk7MBly6faG+mWwR7VyveWOkDtrfY27jGii0Q== X-Received: by 2002:a7b:c01a:: with SMTP id c26mr12945743wmb.35.1602549660080; Mon, 12 Oct 2020 17:41:00 -0700 (PDT) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id o6sm26860258wrm.69.2020.10.12.17.40.59 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 12 Oct 2020 17:40:59 -0700 (PDT) Message-Id: <490d3a42add2cc5f0d30db8f2351614294e00121.1602549650.git.gitgitgadget@gmail.com> In-Reply-To: References: Date: Tue, 13 Oct 2020 00:40:49 +0000 Subject: [PATCH v2 09/10] strmap: add a strset sub-type Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Jeff King , 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_util 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.h | 64 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 64 insertions(+) diff --git a/strmap.h b/strmap.h index fe15e74b78..2ad6696950 100644 --- a/strmap.h +++ b/strmap.h @@ -178,4 +178,68 @@ 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_ocd_init(struct strset *set, + int strdup_strings) +{ + strmap_ocd_init(&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); +} + +static inline void strset_add(struct strset *set, const char *str) +{ + strmap_put(&set->map, str, NULL); +} + #endif /* STRMAP_H */ From patchwork Tue Oct 13 00:40:50 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 11834715 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 AFCE5C83002 for ; Tue, 13 Oct 2020 02:42:20 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 71E77221EB for ; Tue, 13 Oct 2020 02:42:20 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="u2Ffy7ia" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727931AbgJMAlF (ORCPT ); Mon, 12 Oct 2020 20:41:05 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:49172 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727905AbgJMAlC (ORCPT ); Mon, 12 Oct 2020 20:41:02 -0400 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 3668EC0613D2 for ; Mon, 12 Oct 2020 17:41:02 -0700 (PDT) Received: by mail-wr1-x442.google.com with SMTP id h7so21729428wre.4 for ; Mon, 12 Oct 2020 17:41:02 -0700 (PDT) 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=xM8Wm7ZazBef0bIdplkeKJTFVK5duK9p8dSVJjU6cB4=; b=u2Ffy7iaD99fG4M8ze0qxDJhz4crFtTBDrMX0qc04V+sYNR1AB6iAcohxOizDryaaX lX6Hyj0fvjen6GmB8l1DEb8h/twVZ8wpyKmpttDPVWuuOJA7UZtFGQv3vtXJKiZMR0VQ zm3bIzSm6tP5JCZvitW78SgXwjIlFINA5t2Xy3AwDENe7j8aBD9X35ciK7bBjYdjanbv eYwcxSjHK2nUG/Ct3dLAgyyuWZM546rmu8dacF/q//vE2E/8mPSeXTUX+AUX9nVyfoVt OOReJoBOP5tZRjn2eN6K4mXR3jogrqjl5JzxYAuUPTchY3NDHtVarCatgXSv/E4UiVRD 4xkw== 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=xM8Wm7ZazBef0bIdplkeKJTFVK5duK9p8dSVJjU6cB4=; b=F7kWRQeaOZPEDpQBj1C9iTdBZnjUphyMgffCR+9iVj3oiaCmSvvLNMzSDz2UZuvsO0 /J+3+/FmVXsAw+8/wSOamfSRxQN8qQ0Q2Fy55ou0fGUJODN1FFUy2LzLjcjuPzL8aPnP TNZZoBDJ2vVfrKqcD4oakgkNcXhszWZ8R062Li0337mPoxW2P8MGVECYYw7lD9v/G7AY wQcPpksASG8INZQjYLwnQSFSOVhUSp2A7Thl+PaTsWldmTTtqYZ5WD8aNW0YoI35ER0a czYn6QNh3MpbqmV1q9ZWVQ4O/IwOdu/Bpuv03cdvSkjE672G+W646IztVhFHJv10g+/c mwRg== X-Gm-Message-State: AOAM5331ut8C7F+wUeAZ9J42J1d2rn2ms2Yhbs1qjdHeM0PkRp2gh4cj nBF+HarQitbMGuf3tZu5+auMNSrpZYY= X-Google-Smtp-Source: ABdhPJxF3LD0JQFAaABLDPo8jsLBWOD98yO+ULdtmwPZOlpaklXfjhxtq5iDDBODMrwAbVm9M8OW2g== X-Received: by 2002:adf:f74e:: with SMTP id z14mr32081251wrp.312.1602549660809; Mon, 12 Oct 2020 17:41:00 -0700 (PDT) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id c130sm25015201wma.17.2020.10.12.17.41.00 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 12 Oct 2020 17:41:00 -0700 (PDT) Message-Id: In-Reply-To: References: Date: Tue, 13 Oct 2020 00:40:50 +0000 Subject: [PATCH v2 10/10] 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 , 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_ocd_init() 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 d5003a79e3..83b9de961c 100644 --- a/strmap.c +++ b/strmap.c @@ -1,5 +1,6 @@ #include "git-compat-util.h" #include "strmap.h" +#include "mem-pool.h" static 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_ocd_init(map, 1); + strmap_ocd_init(map, NULL, 1); } void strmap_ocd_init(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_util) if (!map) return; + if (!free_util && 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_util) hashmap_for_each_entry(&map->map, &iter, e, ent) { if (free_util) 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); + } } } @@ -84,11 +93,13 @@ void *strmap_put(struct strmap *map, const char *str, void *data) */ 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; hashmap_add(&map->map, &entry->ent); @@ -122,9 +133,11 @@ void strmap_remove(struct strmap *map, const char *str, int free_util) return; if (free_util) 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 2ad6696950..b93b7c9fd6 100644 --- a/strmap.h +++ b/strmap.h @@ -3,8 +3,10 @@ #include "hashmap.h" +struct mempool; struct strmap { struct hashmap map; + struct mem_pool *pool; unsigned int strdup_strings:1; }; @@ -22,11 +24,12 @@ 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. * (OCD = Obsessive Compulsive Disorder, a joke that those who use this function * are obsessing over minor details.) */ void strmap_ocd_init(struct strmap *map, + struct mem_pool *pool, int strdup_strings); /* @@ -126,9 +129,10 @@ static inline void strintmap_init(struct strintmap *map) } static inline void strintmap_ocd_init(struct strintmap *map, + struct mem_pool *pool, int strdup_strings) { - strmap_ocd_init(&map->map, strdup_strings); + strmap_ocd_init(&map->map, pool, strdup_strings); } static inline void strintmap_clear(struct strintmap *map) @@ -202,9 +206,10 @@ static inline void strset_init(struct strset *set) } static inline void strset_ocd_init(struct strset *set, + struct mem_pool *pool, int strdup_strings) { - strmap_ocd_init(&set->map, strdup_strings); + strmap_ocd_init(&set->map, pool, strdup_strings); } static inline void strset_clear(struct strset *set)