I'm adding counters to the Attribute and Modification structures, a_numvals
and sm_numvals to track the number of values in each. I've added an
attr_valadd() routine that will add arrays of values to an attribute and
update the counter. This can eliminate most of the empty for loops we're using
to count these values at various points. But it means other code that
assembles Attributes manually needs to be updated. Fortunately most of these
are easy to spot now since they generally have to use attr_alloc(). I believe
I have them all.
This is the first stage in a larger transition, to using sorted arrays for
multivalued attributes. I haven't quite decided how the next steps will play
out just yet.
Note that we already do a sort on incoming attributes, but that code currently
has ORDER_PRESERVING defined so after duplicate checks are done we discard the
sort info. That preserves the existing/historical slapd behavior.
However, I'm pretty sure this is going to have to change. Using sorted arrays
will allow us to use binary search to find values, which will be a big win for
attributes with very many values. This will speed up test_filter, Compare, ACL
processing, etc. etc...
We can also implement this without any user-visible change, if we keep an
auxiliary ordering array, the way the current sorter does. But it seems to me
that that will be too much memory overhead. It also makes add/remove that much
-- Howard Chu
Chief Architect, Symas Corp. http://www.symas.com
Director, Highland Sun http://highlandsun.com/hyc/
Chief Architect, OpenLDAP http://www.openldap.org/project/