path: root/builtin
diff options
authorJeff King <>2021-01-28 06:34:31 (GMT)
committerJunio C Hamano <>2021-01-28 19:26:20 (GMT)
commit680ff910b0329c8482f98ad9d3c49f4628c1bafa (patch)
treeb0c46d00dfd2290e335da846626182498257f4af /builtin
parent098c173f2bd6260faa8f21a3dc375e23bda6b554 (diff)
rerere: use strmap to store rerere directories
We store a struct for each directory we access under .git/rr-cache. The structs are kept in an array sorted by the binary hash associated with their name (and we do lookups with a binary search). This works OK, but there are a few small downsides: - the amount of code isn't huge, but it's more than we'd need using one of our other stock data structures - the insertion into a sorted array is quadratic (though in practice it's unlikely anybody has enough conflicts for this to matter) - it's intimately tied to the representation of an object hash. This isn't a big deal, as the conflict ids we generate use the same hash, but it produces a few awkward bits (e.g., we are the only user of hash_pos() that is not using object_id). Let's instead just treat the directory names as strings, and store them in a strmap. This is less code, and removes the use of hash_pos(). Insertion is now non-quadratic, though we probably use a bit more memory. Besides the hash table overhead, and storing hex bytes instead of a binary hash, we actually store each name twice. Other code expects to access the name of a rerere_dir struct from the struct itself, so we need a copy there. But strmap keeps its own copy of the name, as well. Using a bare hashmap instead of strmap means we could use the name for both, but at the cost of extra code (e.g., our own comparison function). Likewise, strmap has a feature to use a pointer to the in-struct name at the cost of a little extra code. I didn't do either here, as simple code seemed more important than squeezing out a few bytes of efficiency. Signed-off-by: Jeff King <> Signed-off-by: Junio C Hamano <>
Diffstat (limited to 'builtin')
0 files changed, 0 insertions, 0 deletions