From patchwork Sat Jan 7 09:18:18 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Masahiro Yamada X-Patchwork-Id: 40322 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a5d:4e01:0:0:0:0:0 with SMTP id p1csp1224034wrt; Sat, 7 Jan 2023 01:19:57 -0800 (PST) X-Google-Smtp-Source: AMrXdXtz7yFHGzt2n8acb5flEvl6NvIgBJkbO1cAIVk4A4Np9iEu8JG921bb1BLWcRPLoWHPtleb X-Received: by 2002:a05:6a20:6699:b0:a7:e65:2b65 with SMTP id o25-20020a056a20669900b000a70e652b65mr65624797pzh.23.1673083197552; Sat, 07 Jan 2023 01:19:57 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1673083197; cv=none; d=google.com; s=arc-20160816; b=Jwq/FQDboikEyNygicOi9xcI0nUDjxeXglH8xtOuQ2C71PdEKz22HM50TnAynOnmWh E1Mof9ALmrzpsou1bex1Q+6kNFcuTm3huACVEqgygNnbzfACRRQ6fEizY5jNU3gA5hBs CdHCAnUWQDbyMWQ4s56Jlh+piEFvXqpi/k9lsJPMTV4AT9Spn66rg8jcaKl9apuYZfqM zgh/czqwY7ftVhaZTmdotq3L5WUqFhIi2816q4dkpMAC8rf0kbTyA6RC70m/ImpWYjNn 5eXDFjROuBy/FEAcG7GMUtCH2mqi+YR1UHEI6yQ9/6pFdgM69QFcQTRX38hcMdTuMeYc a5cg== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:content-transfer-encoding:mime-version :references:in-reply-to:message-id:date:subject:cc:to:from :dkim-signature; bh=c8QtFh55HKZ6z/B4W3R9DkJBELx4eHi8lzaai01M7Qs=; b=MsGJFaGQXgeXhCM277KZ7YnewJVpbjmEHJDdCkgY+xD7FNeP7RCTBjFel2gjcKDrYC b8tE4ooV6QeqGmm+mx05QjyO3j2eq0UGnbtvoVVVY41hi3DRLr1d2mYYG1eNVK0XhUc4 pXATsBZzrrVlzZb3UcaWfQZ8iYtv4bGetMWG1Y57/dXgSBwOyTIhxYm/htMcdB7vshNl msc/fi527ZSFUCkIZBV4SIT+xCZvX+uSMX2kEP5oR9guHysxbhS4JZ4wc7oCWIi28SVU Sh2I8hyFZTHQFydkZWJpembnbxwpsS79/SjUuNpZH+8n7lDtb762K2W5M3fDFhj1XXIV wLZQ== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@kernel.org header.s=k20201202 header.b=USGRmCPj; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=kernel.org Received: from out1.vger.email (out1.vger.email. [2620:137:e000::1:20]) by mx.google.com with ESMTP id e21-20020a637455000000b004795c10a6c6si3727632pgn.665.2023.01.07.01.19.45; Sat, 07 Jan 2023 01:19:57 -0800 (PST) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20; Authentication-Results: mx.google.com; dkim=pass header.i=@kernel.org header.s=k20201202 header.b=USGRmCPj; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=kernel.org Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S231770AbjAGJTW (ORCPT + 99 others); Sat, 7 Jan 2023 04:19:22 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:33272 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S231748AbjAGJSw (ORCPT ); Sat, 7 Jan 2023 04:18:52 -0500 Received: from dfw.source.kernel.org (dfw.source.kernel.org [139.178.84.217]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id E0A3387F21; Sat, 7 Jan 2023 01:18:46 -0800 (PST) Received: from smtp.kernel.org (relay.kernel.org [52.25.139.140]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by dfw.source.kernel.org (Postfix) with ESMTPS id CD2FD606A0; Sat, 7 Jan 2023 09:18:45 +0000 (UTC) Received: by smtp.kernel.org (Postfix) with ESMTPSA id 12214C433F2; Sat, 7 Jan 2023 09:18:41 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=k20201202; t=1673083125; bh=KHt1EK26ZGiCZ+hM8+UAROr2DkypHQCMEzGlrsxrzJs=; h=From:To:Cc:Subject:Date:In-Reply-To:References:From; b=USGRmCPjYNX6ogQJTnr+bdgvTdiqwjDgydRFPehzZrcxPQrTVeokqOwv+Avf4WktR vFW8sKGqXKrXZaGi++fWsdr7nsu84MdtzoXbGZKylLXPVT9HiDTLo44c86Q7q6zpz2 DpvYAaUDsYSV92YSHwQL095ySj2XQWIRlYhJAwB/tF8Z4uLSW4L3hbbCEVay8AYaao Dol9xUemVNxo70aRvkzGDds2LpbWIVOVH4+4cpHyK5wIq9DNO1MDdH1zsogel1m4IJ xzipdFimzMgUqb42WFYasicdrmUxqYOpwSDDh2JrWUxKUjIe/A9X4rC2+k7WXwXoYb eYSWNNye95KgA== From: Masahiro Yamada To: linux-kbuild@vger.kernel.org Cc: linux-kernel@vger.kernel.org, Miguel Ojeda , Alex Gaynor , Wedson Almeida Filho , Boqun Feng , Gary Guo , =?utf-8?q?Bj=C3=B6rn_Roy_Baron?= , rust-for-linux@vger.kernel.org, Masahiro Yamada , Nathan Chancellor , Nick Desaulniers , Nicolas Schier Subject: [PATCH v2 5/7] fixdep: refactor hash table lookup Date: Sat, 7 Jan 2023 18:18:18 +0900 Message-Id: <20230107091820.3382134-5-masahiroy@kernel.org> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20230107091820.3382134-1-masahiroy@kernel.org> References: <20230107091820.3382134-1-masahiroy@kernel.org> MIME-Version: 1.0 X-Spam-Status: No, score=-7.1 required=5.0 tests=BAYES_00,DKIMWL_WL_HIGH, DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,RCVD_IN_DNSWL_HI, SPF_HELO_NONE,SPF_PASS autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on lindbergh.monkeyblade.net Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1754354887043040537?= X-GMAIL-MSGID: =?utf-8?q?1754354887043040537?= Change the hash table code so it will be easier to add the second table. Signed-off-by: Masahiro Yamada Reviewed-by: Miguel Ojeda Tested-by: Miguel Ojeda --- (no changes since v1) scripts/basic/fixdep.c | 47 ++++++++++++++++++++++-------------------- 1 file changed, 25 insertions(+), 22 deletions(-) diff --git a/scripts/basic/fixdep.c b/scripts/basic/fixdep.c index f5a51770eb74..74f90a0deeb9 100644 --- a/scripts/basic/fixdep.c +++ b/scripts/basic/fixdep.c @@ -113,7 +113,7 @@ struct item { }; #define HASHSZ 256 -static struct item *hashtab[HASHSZ]; +static struct item *config_hashtab[HASHSZ]; static unsigned int strhash(const char *str, unsigned int sz) { @@ -125,25 +125,11 @@ static unsigned int strhash(const char *str, unsigned int sz) return hash; } -/* - * Lookup a value in the configuration string. - */ -static int is_defined_config(const char *name, int len, unsigned int hash) -{ - struct item *aux; - - for (aux = hashtab[hash % HASHSZ]; aux; aux = aux->next) { - if (aux->hash == hash && aux->len == len && - memcmp(aux->name, name, len) == 0) - return 1; - } - return 0; -} - /* * Add a new value to the configuration string. */ -static void define_config(const char *name, int len, unsigned int hash) +static void add_to_hashtable(const char *name, int len, unsigned int hash, + struct item *hashtab[]) { struct item *aux = malloc(sizeof(*aux) + len); @@ -158,17 +144,34 @@ static void define_config(const char *name, int len, unsigned int hash) hashtab[hash % HASHSZ] = aux; } +/* + * Lookup a string in the hash table. If found, just return true. + * If not, add it to the hashtable and return false. + */ +static bool in_hashtable(const char *name, int len, struct item *hashtab[]) +{ + struct item *aux; + unsigned int hash = strhash(name, len); + + for (aux = hashtab[hash % HASHSZ]; aux; aux = aux->next) { + if (aux->hash == hash && aux->len == len && + memcmp(aux->name, name, len) == 0) + return true; + } + + add_to_hashtable(name, len, hash, hashtab); + + return false; +} + /* * Record the use of a CONFIG_* word. */ static void use_config(const char *m, int slen) { - unsigned int hash = strhash(m, slen); - - if (is_defined_config(m, slen, hash)) - return; + if (in_hashtable(m, slen, config_hashtab)) + return; - define_config(m, slen, hash); /* Print out a dependency path from a symbol name. */ printf(" $(wildcard include/config/%.*s) \\\n", slen, m); }