move EvictingCacheMap to folly
authorRanjeeth Dasineni <ranjeeth@fb.com>
Thu, 7 Aug 2014 07:34:11 +0000 (00:34 -0700)
committerSara Golemon <sgolemon@fb.com>
Thu, 14 Aug 2014 18:49:04 +0000 (11:49 -0700)
commit3ff4b4f4ae7c4bc45c8b6890c4d3c6f09b729527
treedefec73d944b981eec90e42ab6d9710af07a49b9
parentbe419a8edc10bc8a6b21bac0efc7ac9a0d88107b
move EvictingCacheMap to folly

Summary:
adding @agartrell's implementation of EvictingCacheMap to folly. Its a general purpose
cache with LRU eviction. It maintains a doubly linked list threaded throught a hash map using
boost::intrusive. set, get and delete are all constant time operations.  It is not thread safe.

Configurability: It allows callers to specify a hasher for the keys, has callbacks for eviction
events and the number of evictions on reaching a capacity limit is configurable. resizing for
a higher capacity though could be suboptimal since index is not resized accordingly and you could
end up with a bad load factor.

Test Plan: unit tests

Reviewed By: tulloch@fb.com, njormrod@fb.com

Subscribers: tulloch, chrisbray, mhx, doug, agartrell

FB internal diff: D1483789
folly/EvictingCacheMap.h [new file with mode: 0644]
folly/test/EvictingCacheMapTest.cpp [new file with mode: 0644]