This project is mirrored from https://github.com/git/git. Updated .
  1. 07 Jul, 2014 3 commits
    • Karsten Blees's avatar
      hashmap: add string interning API · 7b64d42d
      Karsten Blees authored
      Interning short strings with high probability of duplicates can reduce the
      memory footprint and speed up comparisons.
      
      Add strintern() and memintern() APIs that use a hashmap to manage the pool
      of unique, interned strings.
      
      Note: strintern(getenv()) could be used to sanitize git's use of getenv(),
      in case we ever encounter a platform where a call to getenv() invalidates
      previous getenv() results (which is allowed by POSIX).
      Signed-off-by: default avatarKarsten Blees <blees@dcon.de>
      Signed-off-by: default avatarJunio C Hamano <gitster@pobox.com>
      7b64d42d
    • Karsten Blees's avatar
      hashmap: add simplified hashmap_get_from_hash() API · ab73a9d1
      Karsten Blees authored
      Hashmap entries are typically looked up by just a key. The hashmap_get()
      API expects an initialized entry structure instead, to support compound
      keys. This flexibility is currently only needed by find_dir_entry() in
      name-hash.c (and compat/win32/fscache.c in the msysgit fork). All other
      (currently five) call sites of hashmap_get() have to set up a near emtpy
      entry structure, resulting in duplicate code like this:
      
        struct hashmap_entry keyentry;
        hashmap_entry_init(&keyentry, hash(key));
        return hashmap_get(map, &keyentry, key);
      
      Add a hashmap_get_from_hash() API that allows hashmap lookups by just
      specifying the key and its hash code, i.e.:
      
        return hashmap_get_from_hash(map, hash(key), key);
      Signed-off-by: default avatarKarsten Blees <blees@dcon.de>
      Signed-off-by: default avatarJunio C Hamano <gitster@pobox.com>
      ab73a9d1
    • Karsten Blees's avatar
      hashmap: factor out getting a hash code from a SHA1 · 039dc71a
      Karsten Blees authored
      Copying the first bytes of a SHA1 is duplicated in six places,
      however, the implications (the actual value would depend on the
      endianness of the platform) is documented only once.
      
      Add a properly documented API for this.
      Signed-off-by: default avatarKarsten Blees <blees@dcon.de>
      Signed-off-by: default avatarJunio C Hamano <gitster@pobox.com>
      039dc71a
  2. 24 Feb, 2014 1 commit
  3. 18 Nov, 2013 1 commit
    • Karsten Blees's avatar
      add a hashtable implementation that supports O(1) removal · 6a364ced
      Karsten Blees authored
      The existing hashtable implementation (in hash.[ch]) uses open addressing
      (i.e. resolve hash collisions by distributing entries across the table).
      Thus, removal is difficult to implement with less than O(n) complexity.
      Resolving collisions of entries with identical hashes (e.g. via chaining)
      is left to the client code.
      
      Add a hashtable implementation that supports O(1) removal and is slightly
      easier to use due to builtin entry chaining.
      
      Supports all basic operations init, free, get, add, remove and iteration.
      
      Also includes ready-to-use hash functions based on the public domain FNV-1
      algorithm (http://www.isthe.com/chongo/tech/comp/fnv).
      
      The per-entry data structure (hashmap_entry) is piggybacked in front of
      the client's data structure to save memory. See test-hashmap.c for usage
      examples.
      
      The hashtable is resized by a factor of four when 80% full. With these
      settings, average memory consumption is about 2/3 of hash.[ch], and
      insertion is about twice as fast due to less frequent resizing.
      
      Lookups are also slightly faster, because entries are strictly confined to
      their bucket (i.e. no data of other buckets needs to be traversed).
      Signed-off-by: default avatarKarsten Blees <blees@dcon.de>
      Signed-off-by: default avatarJunio C Hamano <gitster@pobox.com>
      6a364ced