Path: csiph.com!eternal-september.org!feeder.eternal-september.org!nntp.eternal-september.org!.POSTED!not-for-mail From: Tim Rentsch Newsgroups: comp.lang.c Subject: Re: AVL tree insertion - programming exercise Date: Thu, 15 Oct 2026 04:42:05 -0700 Organization: A noiseless patient Spider Lines: 99 Message-ID: <86fqy7qjg2.fsf@linuxsc.com> References: <86ece2kppv.fsf@linuxsc.com> <11akqm4$c6h9$1@dont-email.me> <11al0l0$eefv$1@dont-email.me> <11alfgs$t7q$1@reader2.panix.com> <11amttk$14pou$2@kst.eternal-september.org> <86se27r52l.fsf@linuxsc.com> <11appe9$24dl1$1@kst.eternal-september.org> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Injection-Date: Thu, 15 Oct 2026 11:42:10 +0000 (UTC) Injection-Info: dont-email.me; logging-data="2486706"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/s1WF8pkEb1z4LCYu8Np9D5rqqMS8509E="; posting-host="8e248dd53a94b2a901695ff9f1057f0e" User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux) Cancel-Lock: sha1:BgsxxTQlgjErCYCkQ63Xal8cvzs= sha1:kgZtXfPk2Jp7JD+iagNemI+L+LM= sha256:kBBaw7TECvnh3+j+5w/xQY3sPbT386kkvGYXhb7Dnbw= sha1:8W1Dhv1Ly40w7BQR+fspAIC/vi8= sha256:zXe+8vT/g8mx68zvM6i1IlGZ5mlwLloAVws7WN8Dqok= Xref: csiph.com comp.lang.c:403185 Keith Thompson writes: > Tim Rentsch writes: > >> Keith Thompson writes: >> >>> cross@spitfire.i.gajendra.net (Dan Cross) writes: >>> >>>> In article <11al0l0$eefv$1@dont-email.me>, >>>> James Kuyper wrote: >>>> >>>>> On 13/10/2026 10:38, chine.bleu wrote: >>>>> ...> As a precaution check the return >>>>> >>>>>> address of malloc >>>>>> >>>>>> p = malloc(m); >>>>>> if ((uintptr_t)p)&1!=0) abort(); >>>>> >>>>> Just to be pedantic, the standard doesn't guarantee that the >>>>> expression you use will test what you want to test. Since there >>>>> is a guarantee that malloc() returns a universally aligned memory, >>>>> I think it's actually more likely that the test will fail than >>>>> that malloc() will fail, though both probabilities are quite >>>>> negligible, so it's hard to be sure. >>>> >>>> The syntax and precedence errors aside, the test is clearly >>>> meant to ensure that the low bit in the return from `malloc` is >>>> clear, so that it can be repurposed for other things. It should >>>> likely be: >>>> >>>> p = malloc(m); >>>> if (p == NULL || ((uintptr_t)p & 1) != 0) abort(); >>> >>> I'm not sure the NULL test adds anything useful. The low-order bits >>> of a null pointer are very likely to be 0 on any real-world system. >> >> Surely we would like to protect against a null pointer being used >> to access a non-existent object. >> >>> Also, the test only looks at the low-order bits of the result of >>> the current malloc() call. If you have an exotic system where >>> an aligned pointer can have a low-order bit set to 1, it might >>> *sometimes* be set to 0. >> >> As long as the bit in question /is/ zero it doesn't matter if it >> might have been one. The bit will always be cleared before using >> the pointer as a pointer, so the pointer value in use will match >> the pointer value originally returned. >> >> Thus we might write a safe allocation function as follows: >> >> void * >> safe_new( size_t n ){ >> void *p = 0; >> >> while( !p || (uintptr_t)p %2 != 0 ){ >> free( p ), p = malloc( n++ ); >> } >> >> return p; >> } >> >> Of course it might not succeed in some cases, but it will be >> quite obvious if it doesn't. :) > > I might be missing the point of "chine.bleu"'s suggestion. I was > assuming that the point was to check whether it's possible *in > general* to play with the low-order bits of malloc'ed pointers. I took the tests with the abort() calls to be simply protection against an unsuitable pointer being returned. Nothing more complicated than that. The point I was making is different. It doesn't matter if the bit in question is always zero as long as it is zero a fair amount of the time. Also it doesn't have to be a low order bit, or any pre-chosen bit, as long as some particular bit is zero often enough. We can imagine doing a lot of malloc() calls at program startup and tallying how often a zero appears at each bit position, and using one of the bit positions with a high count. Simply do enough malloc() calls until the value returned has a zero bit at the selected bit position. The code above looks at a fixed low order bit, but it could just as well look at a bit whose position was chosen at run time during program startup. > On most systems, you can probably make that assumption based on > what you know about the system's memory model. But it can't be > checked reliably at run time. > > If I wanted my program to play with low-order bits of pointers, and > refuse to run if the system doesn't support that, I might write a > program that does a *lot* of malloc() calls and invoke it during > configuration, refusing to proceed with the build if it reports that > malloc() can return an "odd" pointer. Aborting during execution > feels sloppy. I understand what you're saying. It's mostly orthogonal to what I was saying.