directory-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Emmanuel Lecharny" <>
Subject [ApacheDS][AvlTree] review
Date Wed, 28 May 2008 15:20:08 GMT

this is a first feedback about the AVL tree implementation.

- I have added some missing Javadoc. As a rule of thumb, I think it's
better to commit code with javadoc instead of committing code, and
doing javadoc after, because it will lead to many missing javadoc.
(this is something everyone of us have to take care of, I don't think
that anyone is following this rule, including me ;)

- Three methods at least should not be declared public : setFirst(),
setlast() and setRoot(). They are used by the deserializer, which
belongs to the same package, so defining those methods without any
qualifier is the way to go (but please add a comment, like this :
   * Create a DN when deserializing it.
  /* No protection */ LdapDN( String upName, String normName, byte[] bytes )

- The getSize() method computes the AVL size by counting all its
elements. Not really efficient. Storing the AVL size in the root
element should be better. We can also add a field in the Node
structure containing the number of childen plus the node itself (so
the underlying tree size). To be evaluated.

- We could improve the way the tree is built by avoiding a linkedList
creation (this linked list is used to store the nodes which have been
visited while adding or removing a node). This list is already
implicitly present as the algorithm is recursive.

- I would suggest to rename the K to V, as we are not really storing
keys, but values. In our specific case, yes, we are storing keys, but
I do think that an efficient AVL tree implementation belongs to
commons-collection, so a more generic approach could be better.

- We have some formatter and templates in project/resources. Please
use them, so that the code format  follows our defined code standard

- I would like to see if we can spare some
serialization/deserialization while searching. Not sure this is
possible, but implementing a cache can help.

- Otherwise, I did some profiling on the server, and the AVLTree
implementation eat a very small part of the CPU (barely 0,75%), which
is a pretty good news !

More to come later, but atm, I would say that the current
implementation is pretty ok.

Thanks for the good work !

cordialement, regards,
Emmanuel L├ęcharny

View raw message