[Date Prev][Date Next] [Chronological] [Thread] [Top]

Threaded AVL routines

I was digging into the AVL library to look for some other ways to speed up back-hdb subtree searches. It seemed that threading the nodes might help in hdb's IDL construction. Anyway, I've dusted off some old AVL routines I wrote and added them to liblutil/tavl.c. It's worth noting that this code uses iterative insert/delete functions, which are about 15% faster than the recursive code in avl.c. I haven't determined yet whether threading will actually be useful here, but it may be worthwhile to replace the insert/delete in avl.c with the iterative versions (with or without the threading support). The traversal code is probably only relevant for callers of avl_apply; there aren't many instances in the source tree so it may not be any big deal.

 -- Howard Chu
 Chief Architect, Symas Corp.  http://www.symas.com
 Director, Highland Sun        http://highlandsun.com/hyc
 OpenLDAP Core Team            http://www.openldap.org/project/