Combine HASHes with TREEs

We use a little generalized AVL trees as simplest ordered/lookup structure in most of our code. It has little worse insertion and deletion performance than R-B, but maximal depth is smaller and lookups faster. But for cases where O(logN) is too big we use hashes where each has table entry i pointer to AVL tree of items. If the constant has table size is (ul_hashtab_sizestep_null) used then there is no malloc required for insert/delete but tree node structure has to be available in inserted items (same as for actual R-B tree Linux implementation).

The tuning of hash table size then tunes between O(1) but big amount of abundant memory filled by unused NULLs and O(logN) for total collision case.

If and default ul_hashtab_sizestep_default_table is used, the implementation tries to tune table and rehash data when the hash table size is too small or big for given item count.

Use example/test code is in ul_hashtabchk.c file.

Solution is not perfect but should prevent DoS quite well. The reason behind my decision for this structure was our real-time/control systems/application orientation where worst case scenarios/limits/considerations are the mantra.

The code is part of uLUt uLan libraries available under GPL, LGPL and MPL.

http://ulan.sourceforge.net/