Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c > #402780 > unrolled thread
| Started by | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| First post | 2026-10-06 23:08 -0700 |
| Last post | 2026-10-13 03:52 -0700 |
| Articles | 4 on this page of 84 — 19 participants |
Back to article view | Back to comp.lang.c
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 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 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-13 03:52 -0700
Page 5 of 5 — ← Prev page 1 2 3 4 [5]
| From | cross@spitfire.i.gajendra.net (Dan Cross) |
|---|---|
| Date | 2026-10-13 14:34 +0000 |
| Message-ID | <11alfgs$t7q$1@reader2.panix.com> |
| In reply to | #403089 |
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(); - Dan C.
[toc] | [prev] | [next] | [standalone]
| From | Keith Thompson <Keith.S.Thompson+u@gmail.com> |
|---|---|
| Date | 2026-10-13 20:45 -0700 |
| Message-ID | <11amttk$14pou$2@kst.eternal-september.org> |
| In reply to | #403103 |
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.
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.
--
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]
| From | cross@spitfire.i.gajendra.net (Dan Cross) |
|---|---|
| Date | 2026-10-14 14:25 +0000 |
| Message-ID | <11ao3dn$8hr$1@reader2.panix.com> |
| In reply to | #403140 |
In article <11amttk$14pou$2@kst.eternal-september.org>, Keith Thompson <Keith.S.Thompson+u@gmail.com> wrote: >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. It was just meant to `abort` if `malloc` could not allocate for whatever reason, and was unrelated to this business of stealing low bits to cache other data. The assertion is that, if the program survives these tests, then `p` is suitable for use. Sorry, I should have been clear about that. >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. I think the point is that if one wants to repurpose the low bits of the integer representation of `p` for some purpose, then one ought to verify the base assumption that those bits are available. One need not do that on every malloc call, however. In the face of weird implementations and esoteric hardware, I don't know that one can have a more general test suitable for e.g. a `static_assert()`. - Dan C.
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2026-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 5 of 5 — ← Prev page 1 2 3 4 [5]
Back to top | Article view | comp.lang.c
csiph-web