[email protected] 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. > So from my knowledge this means that for a perfectly filled balanced tree, the > stack will overflow when the tree consists of 2^8 (2^0 + 2^1 + 2^2 + ... + > 2^7) > or more nodes, and you are locating a leaf node. Maybe even with fewer nodes. > As the algorithm also pushes an other element onto the stack, the problem > could > appear even before 128 nodes. -- -- Howard Chu CTO, Symas Corp. http://www.symas.com Director, Highland Sun http://highlandsun.com/hyc/ Chief Architect, OpenLDAP http://www.openldap.org/project/
