1. 29 Jul, 2016 1 commit
    • Jeff King's avatar
      add generic most-recently-used list · 002f206f
      Jeff King authored
      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: default avatarJeff King <peff@peff.net>
      Signed-off-by: default avatarJunio C Hamano <gitster@pobox.com>