summaryrefslogtreecommitdiff
path: root/Documentation/technical/http-protocol.txt
diff options
context:
space:
mode:
authorLibravatar Jeff King <peff@peff.net>2016-07-29 00:06:59 -0400
committerLibravatar Junio C Hamano <gitster@pobox.com>2016-07-29 11:05:07 -0700
commit002f206faf09d39abee80f916cabaf3ab342b74f (patch)
tree2621f24f5c391d9e38368f3067af7cd437ec52c3 /Documentation/technical/http-protocol.txt
parentsha1_file: drop free_pack_by_name (diff)
downloadtgif-002f206faf09d39abee80f916cabaf3ab342b74f.tar.xz
add generic most-recently-used list
There are a few places in Git that would benefit from a fast most-recently-used cache (e.g., the list of packs, which we search linearly but would like to order based on locality). This patch introduces a generic list that can be used to store arbitrary pointers in most-recently-used order. The implementation is just a doubly-linked list, where "marking" an item as used moves it to the front of the list. Insertion and marking are O(1), and iteration is O(n). There's no lookup support provided; if you need fast lookups, you are better off with a different data structure in the first place. There is also no deletion support. This would not be hard to do, but it's not necessary for handling pack structs, which are created and never removed. Signed-off-by: Jeff King <peff@peff.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
Diffstat (limited to 'Documentation/technical/http-protocol.txt')
0 files changed, 0 insertions, 0 deletions