Path: csiph.com!news.mixmin.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail From: Tim Rentsch Newsgroups: comp.lang.c Subject: Re: Good hash for pointers Date: Sat, 25 May 2024 02:49:00 -0700 Organization: A noiseless patient Spider Lines: 69 Message-ID: <86bk4ugr1v.fsf@linuxsc.com> References: <86v834i1o9.fsf@linuxsc.com> <86r0dshysc.fsf@linuxsc.com> <86ed9shtsj.fsf@linuxsc.com> <865xv3ic14.fsf@linuxsc.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Injection-Date: Sat, 25 May 2024 11:49:02 +0200 (CEST) Injection-Info: dont-email.me; posting-host="8137c08e2aeaf8da9fb9d9b9c4e0a9a5"; logging-data="2977519"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/YV4PAn9onu88uaYTSLeHZbxsXHkO/kuE=" User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux) Cancel-Lock: sha1:dtbs+XauHwNY8wS54Mdgsrqa1lI= sha1:5AFBUdDddFeno3VEI7sb+Ghuuyg= Xref: csiph.com comp.lang.c:385040 Malcolm McLean writes: > On 24/05/2024 14:18, Tim Rentsch wrote: > >> bart writes: >> >>> On 24/05/2024 02:39, Tim Rentsch wrote: >>> >>>> Malcolm McLean writes: >>>> >>>>> On 24/05/2024 00:52, Tim Rentsch wrote: >>>>> >>>>>> Malcolm McLean writes: >>>>>> >>>>>>> On 23/05/2024 23:49, Tim Rentsch wrote: >>>>>>> >>>>>>>> Malcolm McLean writes: >>>>>>>> >>>>>>>>> What is a good hash function for pointers to use in portable >>>>>>>>> ANSI C? >>>>>>>> >>>>>>>> I have a preliminary question. Do you really mean ANSI C, or >>>>>>>> is C99 acceptable? >>>>>>> >>>>>>> C89 is better. >>>>>>> But the pass has been sold. >>>>>> >>>>>> I'm not asking which you think is better. I'm asking about >>>>>> what your requirements are. >>>>> >>>>> C 89. >>>>> I don't want to pull in C99 types and so on just for a hash >>>>> function. >>>> >>>> In that case I think you are stuck with using a half-baked >>>> solution. The standard integer types available in C89 just >>>> aren't a good fit in a 64-bit world. >>> >>> I assume the C89 implementation is one that can target current 64 >>> bit machines. >>> >>> Then char, short, int, long long will almost certainly have widths >>> of 8, 16, 32 and 64 bits respectively. >> >> C89 doesn't have long long. >> >>> (I don't know if 'long long' was part of C89, but it sounds like >>> Malcolm just doesn't want to be bothered with stdint.h, and any >>> compiler used is like to support it. >> >> What he said was C89. He didn't mention stdint.h. I take >> him at his word. If what he wants is something different, >> he should say clearly what it is, and not make people guess >> about it. (To be clear this recommendation is intended for >> every questioner, not just Malcolm.) > > cJSON.c is C89. And these additions to the resource compiler were > inspired by a menntion of cJSON.c here. > > So a C89 hash for a pointer to an unsigned int would be ideal. However > it might be impossible to write one which is both efficient in terms > of machine instructions and a good hash function in that it > distributes the hashes evenly given an uneven distribution of > keys. And pointers returned from repeated calls to malloc() are going > to have an odd distribution of values. I suggest you look for a way to write and use a hash function that uses unsigned long long without that causing cJSON.c to need compiling by a post-C89 ruleset.