• David Howells's avatar
    Add a generic associative array implementation. · 3cb98950
    David Howells authored
    Add a generic associative array implementation that can be used as the
    container for keyrings, thereby massively increasing the capacity available
    whilst also speeding up searching in keyrings that contain a lot of keys.
    
    This may also be useful in FS-Cache for tracking cookies.
    
    Documentation is added into Documentation/associative_array.txt
    
    Some of the properties of the implementation are:
    
     (1) Objects are opaque pointers.  The implementation does not care where they
         point (if anywhere) or what they point to (if anything).
    
         [!] NOTE: Pointers to objects _must_ be zero in the two least significant
         	       bits.
    
     (2) Objects do not need to contain linkage blocks for use by the array.  This
         permits an object to be located in multiple arrays simultaneously.
         Rather, the array is made up of metadata blocks that point to objects.
    
     (3) Objects are labelled as being one of two types (the type is a bool value).
         This information is stored in the array, but has no consequence to the
         array itself or its algorithms.
    
     (4) Objects require index keys to locate them within the array.
    
     (5) Index keys must be unique.  Inserting an object with the same key as one
         already in the array will replace the old object.
    
     (6) Index keys can be of any length and can be of different lengths.
    
     (7) Index keys should encode the length early on, before any variation due to
         length is seen.
    
     (8) Index keys can include a hash to scatter objects throughout the array.
    
     (9) The array can iterated over.  The objects will not necessarily come out in
         key order.
    
    (10) The array can be iterated whilst it is being modified, provided the RCU
         readlock is being held by the iterator.  Note, however, under these
         circumstances, some objects may be seen more than once.  If this is a
         problem, the iterator should lock against modification.  Objects will not
         be missed, however, unless deleted.
    
    (11) Objects in the array can be looked up by means of their index key.
    
    (12) Objects can be looked up whilst the array is being modified, provided the
         RCU readlock is being held by the thread doing the look up.
    
    The implementation uses a tree of 16-pointer nodes internally that are indexed
    on each level by nibbles from the index key.  To improve memory efficiency,
    shortcuts can be emplaced to skip over what would otherwise be a series of
    single-occupancy nodes.  Further, nodes pack leaf object pointers into spare
    space in the node rather than making an extra branch until as such time an
    object needs to be added to a full node.
    Signed-off-by: default avatarDavid Howells <dhowells@redhat.com>
    3cb98950
assoc_array.txt 19.9 KB