Skip to content
  • Nick Wellnhofer's avatar
    hash: Rewrite hash table code · 4a513d56
    Nick Wellnhofer authored
    This is a complete rewrite of the code in hash.c
    
    Move from a chained hash table implementation to open addressing with
    Robin Hood probing. This allows to increase the maximum fill factor and
    further reduce the growth factor, saving considerable amounts of memory
    without sacrificing performance.
    
    To make this work, hash values are now cached in the table entry
    also avoiding many key comparisons.
    
    Tables are created lazily with a smaller minimum size.
    
    Insertion functions now report an error if growing the table resulted in
    a memory allocation failure.
    
    Some string comparisons were optimized to call directly into libc
    instead of using the xmlstring API.
    
    The length of inserted keys is computed along with the hash improving
    allocation performance.
    
    Bounds checking was made more robust.
    
    In dictionary-based mode, unneeded interning of strings is avoided.
    4a513d56