Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #402780 > unrolled thread

AVL tree insertion - programming exercise

Started byTim Rentsch <tr.17687@z991.linuxsc.com>
First post2026-10-06 23:08 -0700
Last post2026-10-13 03:52 -0700
Articles 6 on this page of 106 — 20 participants

Back to article view | Back to comp.lang.c

Contents

  AVL tree insertion - programming exercise Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-06 23:08 -0700
    Re: AVL tree insertion - programming exercise fir <profesor.fir@gmail.com> - 2026-10-07 15:25 +0200
      Re: AVL tree insertion - programming exercise Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-07 12:13 -0700
        Re: AVL tree insertion - programming exercise fir <profesor.fir@gmail.com> - 2026-10-07 21:28 +0200
          Re: AVL tree insertion - programming exercise Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-08 05:31 -0700
            Re: AVL tree insertion - programming exercise fir <profesor.fir@gmail.com> - 2026-10-09 11:12 +0200
              Re: AVL tree insertion - programming exercise fir <profesor.fir@gmail.com> - 2026-10-09 11:12 +0200
        Re: AVL tree insertion - programming exercise BGB <cr88192@gmail.com> - 2026-10-07 20:10 -0500
          Re: AVL tree insertion - programming exercise Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-08 05:56 -0700
            Re: AVL tree insertion - programming exercise BGB <cr88192@gmail.com> - 2026-10-08 15:09 -0500
              Re: AVL tree insertion - programming exercise fir <profesor.fir@gmail.com> - 2026-10-08 22:56 +0200
                Re: AVL tree insertion - programming exercise BGB <cr88192@gmail.com> - 2026-10-08 17:29 -0500
                  Re: AVL tree insertion - programming exercise fir <profesor.fir@gmail.com> - 2026-10-09 09:56 +0200
              Re: AVL tree insertion - programming exercise Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-10-09 01:39 +0200
                Re: AVL tree insertion - programming exercise Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-09 00:03 -0700
              Re: AVL tree insertion - programming exercise Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-08 23:53 -0700
                Re: AVL tree insertion - programming exercise David Brown <david.brown@hesbynett.no> - 2026-10-09 10:34 +0200
                  Re: AVL tree insertion - programming exercise Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-10-09 12:27 +0200
                    Re: AVL tree insertion - programming exercise David Brown <david.brown@hesbynett.no> - 2026-10-09 12:59 +0200
                  Re: AVL tree insertion - programming exercise bart <bc@freeuk.com> - 2026-10-09 11:43 +0100
                    Re: AVL tree insertion - programming exercise David Brown <david.brown@hesbynett.no> - 2026-10-09 13:20 +0200
                      Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-09 12:38 +0000
                        Re: AVL tree insertion - programming exercise David Brown <david.brown@hesbynett.no> - 2026-10-09 16:05 +0200
                          Re: AVL tree insertion - programming exercise Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-10-09 17:54 +0200
                            Re: AVL tree insertion - programming exercise Johann 'Myrkraverk' Oskarsson <johann@myrkraverk.invalid> - 2026-10-10 10:38 +0800
                              Re: AVL tree insertion - programming exercise ram@zedat.fu-berlin.de (Stefan Ram) - 2026-10-10 03:12 +0000
                                Re: AVL tree insertion - programming exercise Lawrence D’Oliveiro <ldo@nz.invalid> - 2026-10-10 04:44 +0000
                                  Re: AVL tree insertion - programming exercise "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2026-10-10 14:12 -0700
                          Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-09 19:48 +0000
                            Re: AVL tree insertion - programming exercise scott@slp53.sl.home (Scott Lurndal) - 2026-10-09 23:18 +0000
                            Re: AVL tree insertion - programming exercise David Brown <david.brown@hesbynett.no> - 2026-10-10 15:27 +0200
                              Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-12 18:26 +0000
                                Re: AVL tree insertion - programming exercise David Brown <david.brown@hesbynett.no> - 2026-10-12 21:17 +0200
                        Re: AVL tree insertion - programming exercise Michael S <already5chosen@yahoo.com> - 2026-10-09 17:47 +0300
                          Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-09 16:48 +0000
                            Re: AVL tree insertion - programming exercise Michael S <already5chosen@yahoo.com> - 2026-10-10 19:08 +0300
                              Re: AVL tree insertion - programming exercise David Brown <david.brown@hesbynett.no> - 2026-10-10 18:29 +0200
                                Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-10 17:44 +0000
                                  Re: AVL tree insertion - programming exercise David Brown <david.brown@hesbynett.no> - 2026-10-10 23:22 +0200
                              Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-10 17:43 +0000
                              Re: AVL tree insertion - programming exercise Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-10-10 20:35 +0200
                                Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-10 19:36 +0000
                                  Re: AVL tree insertion - programming exercise Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-10-10 22:08 +0200
                                  Re: AVL tree insertion - programming exercise Michael S <already5chosen@yahoo.com> - 2026-10-10 23:21 +0300
                                    Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-10 20:55 +0000
                              Re: AVL tree insertion - programming exercise scott@slp53.sl.home (Scott Lurndal) - 2026-10-10 20:22 +0000
                                Re: AVL tree insertion - programming exercise Michael S <already5chosen@yahoo.com> - 2026-10-10 23:32 +0300
                                  Re: AVL tree insertion - programming exercise scott@slp53.sl.home (Scott Lurndal) - 2026-10-11 15:24 +0000
    Re: AVL tree insertion - programming exercise Bonita Montero <Bonita.Montero@gmail.com> - 2026-10-10 19:40 +0200
    Re: AVL tree insertion - programming exercise Andrey Tarasevich <noone@noone.net> - 2026-10-10 12:39 -0700
      Re: AVL tree insertion - programming exercise Michael S <already5chosen@yahoo.com> - 2026-10-10 23:00 +0300
      Re: AVL tree insertion - programming exercise Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-10-10 22:28 +0200
      Re: AVL tree insertion - programming exercise Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-10 19:02 -0700
    Re: AVL tree insertion - programming exercise "chine.bleu" <chine.bleu@yahoo.com> - 2026-10-13 01:38 -0700
      Re: AVL tree insertion - programming exercise David Brown <david.brown@hesbynett.no> - 2026-10-13 11:42 +0200
        Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-13 10:55 +0000
        Re: AVL tree insertion - programming exercise Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2026-10-13 04:29 -0700
          Re: AVL tree insertion - programming exercise David Brown <david.brown@hesbynett.no> - 2026-10-13 14:01 +0200
            Re: AVL tree insertion - programming exercise Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2026-10-13 05:09 -0700
            Re: AVL tree insertion - programming exercise antispam@fricas.org (Waldek Hebisch) - 2026-10-13 19:01 +0000
          Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-13 15:17 +0000
            Re: AVL tree insertion - programming exercise David Brown <david.brown@hesbynett.no> - 2026-10-13 17:39 +0200
            Re: AVL tree insertion - programming exercise Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-13 09:01 -0700
              Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-13 21:17 +0000
                Re: AVL tree insertion - programming exercise "chine.bleu" <chine.bleu@yahoo.com> - 2026-10-13 18:01 -0700
                Re: AVL tree insertion - programming exercise Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2026-10-13 21:13 -0700
                  Re: AVL tree insertion - programming exercise David Brown <david.brown@hesbynett.no> - 2026-10-14 09:43 +0200
                    Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-14 20:11 +0000
                    Re: AVL tree insertion - programming exercise Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2026-10-14 15:25 -0700
                      Re: AVL tree insertion - programming exercise David Brown <david.brown@hesbynett.no> - 2026-10-15 09:28 +0200
                  Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-14 14:13 +0000
                    Re: AVL tree insertion - programming exercise Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-10-14 18:03 +0200
                      Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-14 18:21 +0000
                    Re: AVL tree insertion - programming exercise Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2026-10-14 15:42 -0700
                      Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-15 14:25 +0000
                        Re: AVL tree insertion - programming exercise Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2026-10-15 15:54 -0700
                          Re: AVL tree insertion - programming exercise Kaz Kylheku <046-301-5902@kylheku.com> - 2026-10-15 23:51 +0000
                            Re: AVL tree insertion - programming exercise Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2026-10-15 18:14 -0700
                              Re: AVL tree insertion - programming exercise Kaz Kylheku <046-301-5902@kylheku.com> - 2026-10-16 20:26 +0000
                                Re: AVL tree insertion - programming exercise Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2026-10-16 15:27 -0700
                            Re: AVL tree insertion - programming exercise antispam@fricas.org (Waldek Hebisch) - 2026-10-18 08:42 +0000
                              Re: AVL tree insertion - programming exercise Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-10-18 13:11 +0200
                                Re: AVL tree insertion - programming exercise antispam@fricas.org (Waldek Hebisch) - 2026-10-18 15:12 +0000
                          Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-16 03:09 +0000
                            Re: AVL tree insertion - programming exercise Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2026-10-15 21:34 -0700
                              Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-16 11:27 +0000
                                Re: AVL tree insertion - programming exercise Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2026-10-16 11:27 -0700
                          Re: AVL tree insertion - programming exercise Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-17 08:21 -0700
                            Re: AVL tree insertion - programming exercise Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2026-10-17 10:48 -0700
                            Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-17 18:10 +0000
                  Re: AVL tree insertion - programming exercise Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-14 10:39 -0700
            Re: AVL tree insertion - programming exercise scott@slp53.sl.home (Scott Lurndal) - 2026-10-13 17:15 +0000
              Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-13 21:30 +0000
        Re: AVL tree insertion - programming exercise "chine.bleu" <chine.bleu@yahoo.com> - 2026-10-13 08:19 -0700
        Re: AVL tree insertion - programming exercise "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2026-10-13 13:16 -0700
          Re: AVL tree insertion - programming exercise Michael S <already5chosen@yahoo.com> - 2026-10-13 23:28 +0300
      Re: AVL tree insertion - programming exercise James Kuyper <jameskuyper@alumni.caltech.edu> - 2026-10-13 06:20 -0400
        Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-13 14:34 +0000
          Re: AVL tree insertion - programming exercise Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2026-10-13 20:45 -0700
            Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-14 14:25 +0000
            Re: AVL tree insertion - programming exercise Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-14 20:54 -0700
              Re: AVL tree insertion - programming exercise Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2026-10-14 22:47 -0700
                Re: AVL tree insertion - programming exercise Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-15 04:42 -0700
                Re: AVL tree insertion - programming exercise "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2026-10-15 14:07 -0700
                  Re: AVL tree insertion - programming exercise "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2026-10-17 20:28 -0700
      Re: AVL tree insertion - programming exercise Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-13 03:52 -0700

Page 6 of 6 — ← Prev page 1 2 3 4 5 [6]

#403174

FromTim Rentsch <tr.17687@z991.linuxsc.com>
Date2026-10-14 20:54 -0700
Message-ID<86se27r52l.fsf@linuxsc.com>
In reply to#403140
Keith Thompson <Keith.S.Thompson+u@gmail.com> writes:

> cross@spitfire.i.gajendra.net (Dan Cross) writes:
>
>> In article <11al0l0$eefv$1@dont-email.me>,
>> James Kuyper  <jameskuyper@alumni.caltech.edu> 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.  :)

[toc] | [prev] | [next] | [standalone]

#403176

FromKeith Thompson <Keith.S.Thompson+u@gmail.com>
Date2026-10-14 22:47 -0700
Message-ID<11appe9$24dl1$1@kst.eternal-september.org>
In reply to#403174
Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
> Keith Thompson <Keith.S.Thompson+u@gmail.com> writes:
>> cross@spitfire.i.gajendra.net (Dan Cross) writes:
>>> In article <11al0l0$eefv$1@dont-email.me>,
>>> James Kuyper  <jameskuyper@alumni.caltech.edu> 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.

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.

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

[toc] | [prev] | [next] | [standalone]

#403185

FromTim Rentsch <tr.17687@z991.linuxsc.com>
Date2026-10-15 04:42 -0700
Message-ID<86fqy7qjg2.fsf@linuxsc.com>
In reply to#403176
Keith Thompson <Keith.S.Thompson+u@gmail.com> writes:

> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>
>> Keith Thompson <Keith.S.Thompson+u@gmail.com> writes:
>>
>>> cross@spitfire.i.gajendra.net (Dan Cross) writes:
>>>
>>>> In article <11al0l0$eefv$1@dont-email.me>,
>>>> James Kuyper  <jameskuyper@alumni.caltech.edu> 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.

[toc] | [prev] | [next] | [standalone]

#403198

From"Chris M. Thomasson" <chris.m.thomasson.1@gmail.com>
Date2026-10-15 14:07 -0700
Message-ID<11arfb8$2ov0f$1@dont-email.me>
In reply to#403176
On 10/14/2026 10:47 PM, Keith Thompson wrote:
> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>> Keith Thompson <Keith.S.Thompson+u@gmail.com> writes:
>>> cross@spitfire.i.gajendra.net (Dan Cross) writes:
>>>> In article <11al0l0$eefv$1@dont-email.me>,
>>>> James Kuyper  <jameskuyper@alumni.caltech.edu> 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.
> 
> 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.
> 

Playing the the low order bits is common in some exotic lock-free 
algorihtms. BUT, its much better to over allocate using say malloc, then 
manually align the pointer it returns. Then we can say that pointer is 
aligned on say a 8192 boundary. We know it size if 8192. But we had to 
ask malloc for more memory to make sure we can align and have the right 
size data block. THEN! We can play with the aligned address and store 
whatever data we want. Just make sure to strip it out before we use the 
aligned and packed pointer.

[toc] | [prev] | [next] | [standalone]

#403250

From"Chris M. Thomasson" <chris.m.thomasson.1@gmail.com>
Date2026-10-17 20:28 -0700
Message-ID<11b1edl$q92a$1@dont-email.me>
In reply to#403198
On 10/15/2026 2:07 PM, Chris M. Thomasson wrote:
> On 10/14/2026 10:47 PM, Keith Thompson wrote:
>> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>>> Keith Thompson <Keith.S.Thompson+u@gmail.com> writes:
>>>> cross@spitfire.i.gajendra.net (Dan Cross) writes:
>>>>> In article <11al0l0$eefv$1@dont-email.me>,
>>>>> James Kuyper  <jameskuyper@alumni.caltech.edu> 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.
>>
>> 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.
>>
> 
> Playing the the low order bits is common in some exotic lock-free 
> algorihtms. BUT, its much better to over allocate using say malloc, then 
> manually align the pointer it returns. Then we can say that pointer is 
> aligned on say a 8192 boundary. We know it size if 8192. But we had to 
> ask malloc for more memory to make sure we can align and have the right 
> size data block. THEN! We can play with the aligned address and store 
> whatever data we want. Just make sure to strip it out before we use the 
> aligned and packed pointer.

If somebody uses packed pointers, be sure to have a strip function, say 
get back to the raw pointer. Or It might start playing the following music:

Lisa Lisa & Cult Jam - Head To Toe
https://youtu.be/51Iq8JmmfxY?list=RDMM51Iq8JmmfxY

[toc] | [prev] | [next] | [standalone]

#403092

FromTim Rentsch <tr.17687@z991.linuxsc.com>
Date2026-10-13 03:52 -0700
Message-ID<86bj8xj2jk.fsf@linuxsc.com>
In reply to#403084
"chine.bleu" <chine.bleu@yahoo.com> writes:

> Tim Rentsch wrote:
>
>> sons[2] array.  These links are basically pointers, but held
>> as uintptr_t so they can take one of the bits to mean "tall",
>> which means taller than the other subtree of the node.  The
>> tree structure should maintain an invariant that at most one
>
> Memory is cheap.  Do not encode tags into low bits of an address unless
> you really know what your doing.  As a precaution check the return
> address of malloc
>
>     p = malloc(m);
>     if ((uintptr_t)p)&1!=0) abort();

Yes, in general the interface described will fall down on some
systems.  But it's just an exercise.  Feel free to use code along
the lines of the following (disclaimer: not tested) to confirm
the suitability of the pointer values being used:

    Node *
    new_node( int key ){
        Node *r = malloc( sizeof *r );
        assert(  (uintptr_t)r %2 ==0  );
        *r = (Node){ .key = key };
        return  r;
    }

[toc] | [prev] | [standalone]

Page 6 of 6 — ← Prev page 1 2 3 4 5 [6]

Back to top | Article view | comp.lang.c

csiph-web