Path: ...!feeds.phibee-telecom.net!2.eu.feeder.erje.net!feeder.erje.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Keith Thompson <Keith.S.Thompson+u@gmail.com>
Newsgroups: comp.lang.c
Subject: Re: Good hash for pointers
Date: Thu, 23 May 2024 15:51:29 -0700
Organization: None to speak of
Lines: 24
Message-ID: <875xv43zwu.fsf@nosuchdomain.example.com>
References: <v2n88p$1nlcc$1@dont-email.me> <v2nkbq$1pt1p$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain
Injection-Date: Fri, 24 May 2024 00:51:34 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="9bf1a2728fa7020763691602348055f5";
	logging-data="2075894"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19puqw5M5Newu+4rkRxT2RR"
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/27.2 (gnu/linux)
Cancel-Lock: sha1:EYkEbcHSa1T2BwiZV7e32P5lNY0=
	sha1:LuksnLf/ZGJ/o+giQb5dLEJGLzs=
Bytes: 1959

Richard Harnden <richard.nospam@gmail.invalid> writes:
> On 23/05/2024 12:11, Malcolm McLean wrote:
>> What is a good hash function for pointers to use in portable ANSI C?
>
> All your pointers from malloc are going to be unique.
> All of their low bits are going to be zero, because they need to align
> on some n-bit boundary.
> All of their high bit are going to be the same, because that's just
> how it works.
>
> So just take the middle:  hash = ((intptr_t) ptr) >> 4 & 0xffff;

I'd use uintptr_t, not intptr_t.  I prefer not to think about how
bitwise operations work on signed values unless I have to.

You're assuming a 16-bit hash.  I have no idea whether that suits
Malcolm's requirements.

Another approach might be to divide the pointer representation into
N-bit chunks and xor them together.

-- 
Keith Thompson (The_Other_Keith) Keith.S.Thompson+u@gmail.com
void Void(void) { Void(); } /* The recursive call of the void */