• Herbert Xu's avatar
    rhashtable: Add rhlist interface · ca26893f
    Herbert Xu authored
    The insecure_elasticity setting is an ugly wart brought out by
    users who need to insert duplicate objects (that is, distinct
    objects with identical keys) into the same table.
    
    In fact, those users have a much bigger problem.  Once those
    duplicate objects are inserted, they don't have an interface to
    find them (unless you count the walker interface which walks
    over the entire table).
    
    Some users have resorted to doing a manual walk over the hash
    table which is of course broken because they don't handle the
    potential existence of multiple hash tables.  The result is that
    they will break sporadically when they encounter a hash table
    resize/rehash.
    
    This patch provides a way out for those users, at the expense
    of an extra pointer per object.  Essentially each object is now
    a list of objects carrying the same key.  The hash table will
    only see the lists so nothing changes as far as rhashtable is
    concerned.
    
    To use this new interface, you need to insert a struct rhlist_head
    into your objects instead of struct rhash_head.  While the hash
    table is unchanged, for type-safety you'll need to use struct
    rhltable instead of struct rhashtable.  All the existing interfaces
    have been duplicated for rhlist, including the hash table walker.
    
    One missing feature is nulls marking because AFAIK the only potential
    user of it does not need duplicate objects.  Should anyone need
    this it shouldn't be too hard to add.
    Signed-off-by: default avatarHerbert Xu <herbert@gondor.apana.org.au>
    Acked-by: default avatarThomas Graf <tgraf@suug.ch>
    Signed-off-by: default avatarDavid S. Miller <davem@davemloft.net>
    ca26893f
rhashtable.h 36.2 KB