Hardcoding arbitrary limits in portable code is stupid. ("No one will ever need more than 640K...") What may seem (im)practical to you today may be commonplace tomorrow. This code will be maintenance-free no matter what class of machine it's built on, forever. That's *excellent* programming.
There is no bug here, this ITS is closed.
Ulrich Windl wrote:
On 28 Jan 2009 at 13:06, Howard Chu wrote:
Ulrich.Windl@rz.uni-regensburg.de wrote:
Full_Name: Ulrich Windl Version: 2.4.11 OS: Linux URL: ftp://ftp.openldap.org/incoming/ Submission from: (NULL) (132.199.156.178)
Looking for a threaded AVL tree implementation that is supposed to work, I found libraries/liblutil/tavl.c in openLDAP. I'm no expert on threaded AVL trees, but there's thing that worries me: tavl_delete uses two stacks (pptr, pdir) with a size of 8 elements on the routine' stack. While locating the element to delete, it pushes the parent node onto the stack.
You're misreading the code. The stack is 8*sizeof(void *) which means 32 elements deep on a 32 bit machine, and 64 deep on a 64 bit machine. There is no possibility of overflow now or for several years to come.
OK! I was confused by the terrible programming style at that point: as the array elements are of the proper type (and not bytes), there is no need for a sizeof here: I see no reason why the depth of the tree to be allowed should depend on the length of a pointer, maning: If you want 32, why don't you write 32? So the worst case stack depth would be something like "log2(2^32/(sizeof(void *) * 5))" ("5" being 2 links + 2 threading marks + 1 data pointer), something near 32-5 == 27 (for 32-bit machines) and 64-6 == 58. Practically the latter could be safely reduced to a value around 42 IMHO.