Jeff King <peff@xxxxxxxx> writes: > Subject: [PATCH] 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(). Nice. I didn't realize that this part is so well isolated that another table implementation can easily be dropped in (it was a long time since I stared at this part of the system, back when I was extending it to handle <preimage,postimage> pairs that share the same conflict IDs, which was quite tricky to get right). > This one might be controversial, or at least considered unnecessary > churn. Because the benefits I listed above are pretty negligible, and > really my ulterior motive is getting rid of the call to hash_pos(). No objection from me. Thanks.
