From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on dcvr.yhbt.net X-Spam-Level: X-Spam-ASN: AS3215 2.0.0.0/16 X-Spam-Status: No, score=-4.1 required=3.0 tests=AWL,BAYES_00, HEADER_FROM_DIFFERENT_DOMAINS,MAILING_LIST_MULTI,RCVD_IN_DNSWL_HI, SPF_PASS shortcircuit=no autolearn=ham autolearn_force=no version=3.4.2 Received: from lists.gnu.org (lists.gnu.org [IPv6:2001:4830:134:3::11]) (using TLSv1 with cipher AES256-SHA (256/256 bits)) (No client certificate requested) by dcvr.yhbt.net (Postfix) with ESMTPS id 4B0E11F97E for ; Tue, 27 Nov 2018 04:47:19 +0000 (UTC) Received: from localhost ([::1]:40011 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1gRVHJ-00076W-7B for normalperson@yhbt.net; Mon, 26 Nov 2018 23:47:17 -0500 Received: from eggs.gnu.org ([2001:4830:134:3::10]:43355) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1gRVHF-00076R-FN for bug-gnulib@gnu.org; Mon, 26 Nov 2018 23:47:14 -0500 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1gRVHC-0007Sk-BX for bug-gnulib@gnu.org; Mon, 26 Nov 2018 23:47:13 -0500 Received: from mail-ot1-f46.google.com ([209.85.210.46]:42760) by eggs.gnu.org with esmtps (TLS1.0:RSA_AES_128_CBC_SHA1:16) (Exim 4.71) (envelope-from ) id 1gRVHC-0007Sc-6m for bug-gnulib@gnu.org; Mon, 26 Nov 2018 23:47:10 -0500 Received: by mail-ot1-f46.google.com with SMTP id v23so13539630otk.9 for ; Mon, 26 Nov 2018 20:47:10 -0800 (PST) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:from:to:subject:message-id:references :mime-version:content-disposition:in-reply-to:user-agent; bh=WCZWDB6R2MTg5esG/J1mB5KW0C6YfNKjYhyVhGbbmpk=; b=iA1UyhoL3aZh0LwxmCwaS75euU+TbR0tCHNSMIxS1iVcbMVMyWtegptbtL/Q9dLbO2 jVYaQo04WJc4b/DJo3BlpEQKmYaNTVHcMpGkMTQhU5DZkhp1LsqSLMSugb8L/sCOcSz4 ujsrmw3v1d8xtxeJ/Of8Ikezr4kBVS0hcmfpyG13YEq63oPf2U2Vpmwr9ZN4LDqLpUBh o/cHzEbThtb+jJraobivBFLgkaIXlf2tM1m+7TsUxRY/+58Gv6QUoIc4M8f35MtKc0q4 H9g3Vtntdmsry5x4VLkB94zXJ8dPcxpFMD6wbf/oWZBxrZxRBME4Mgm1tr7SnGtrVGEW crxA== X-Gm-Message-State: AA+aEWa2Dr4lJk4b68eziGgFfGnzeaRXf7pOlYZxydsga5EFmFD6Bqye 8OlEWpVf0U9LM/dcRBB/JRnixgzr X-Google-Smtp-Source: AJdET5fcxLED5sWO5Ikqaekds5ZPdRtM5M5Y1AltO8NHwWqEguRHGOXoG+cnX1uE8hOO8nFrXVuv6g== X-Received: by 2002:a9d:4682:: with SMTP id z2mr16888863ote.104.1543294029099; Mon, 26 Nov 2018 20:47:09 -0800 (PST) Received: from sigabrt.benpfaff.org ([2600:1700:9920:6b60::48]) by smtp.gmail.com with ESMTPSA id t8sm2957484otp.69.2018.11.26.20.47.07 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Mon, 26 Nov 2018 20:47:08 -0800 (PST) Date: Mon, 26 Nov 2018 20:47:05 -0800 From: Ben Pfaff To: bug-gnulib@gnu.org Subject: Re: [RFC] Adding a real HashTable implementation to gnulib Message-ID: <20181127044705.GC18999@sigabrt.benpfaff.org> References: <20181126231616.tjfrkaxvv4tk3nak@tardis.localdomain> <20181126232255.GB18999@sigabrt.benpfaff.org> <20181127010217.sg5zk32snznppbp6@tardis.localdomain> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20181127010217.sg5zk32snznppbp6@tardis.localdomain> User-Agent: Mutt/1.5.23 (2014-03-12) X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] [fuzzy] X-Received-From: 209.85.210.46 X-BeenThere: bug-gnulib@gnu.org X-Mailman-Version: 2.1.21 Precedence: list List-Id: Gnulib discussion list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: bug-gnulib-bounces+normalperson=yhbt.net@gnu.org Sender: "bug-gnulib" Much as I like the PSPP hmaps, it probably makes sense for any hash table implementation in gnulib to match the existing code. On Tue, Nov 27, 2018 at 02:02:17AM +0100, Darshit Shah wrote: > Here are the links to the sources in the GNU Wget tree: > > http://git.savannah.gnu.org/cgit/wget.git/tree/src/hash.h > http://git.savannah.gnu.org/cgit/wget.git/tree/src/hash.c > > At first sight, the implementation in PSPP looks a lot more concise. > Also, it's usage of fewer preprocessor statements makes me already like it. > > However, it does seem that this implementation is not as general or, complete > as the existing hash table implementation in gnulib. The version available in > GNU Wget does implement all the same interfaces with very similar usage > characteristics. > > One of the things I noticed missing in the implementation in GNU PSPP is the > ability to grow the size of the table based on a certain threshold of > "fullness". > > * Ben Pfaff [181127 00:41]: > > On Tue, Nov 27, 2018 at 12:16:16AM +0100, Darshit Shah wrote: > > > I recently tried to use the hash table implementation in gnulib which resides > > > in the "hash" module. However, I quickly realised that the hash table in gnulib > > > seems to be what is otherwise popularly known as a hash set, i.e., it supports > > > storing and retrieving just values from the structure. > > > > > > On the other hand, a hash table is usually expected to have a key->value > > > mapping that is stored. > > > > > > Within GNU Wget, we have a fairly portable version of a hash table implemented > > > which I think would be a good addition for gnulib. What do you think? > > > > > > If I get a positive response here, I could extract that code and turn it into a > > > hash table module for gnulib. We should be able to reuse some part of the > > > existing code in "hash.c" for this purpose as well > > > > Can you point to the Wget hash table? > > > > I'm pretty fond of the hash table implementation we have in PSPP: > > http://git.savannah.gnu.org/cgit/pspp.git/tree/src/libpspp/hmap.h > > http://git.savannah.gnu.org/cgit/pspp.git/tree/src/libpspp/hmap.c > > > > > > -- > Thanking You, > Darshit Shah > PGP Fingerprint: 7845 120B 07CB D8D6 ECE5 FF2B 2A17 43ED A91A 35B6