bitcoinleveldb_lru/

lru_cache.rs

/*!
  | LRU cache implementation
  |
  | Cache entries have an "in_cache" boolean
  | indicating whether the cache has a reference on
  | the entry.  The only ways that this can become
  | false without the entry being passed to its
  | "deleter" are via Erase(), via Insert() when an
  | element with a duplicate key is inserted, or on
  | destruction of the cache.
  |
  | The cache keeps two linked lists of items in
  | the cache.  All items in the cache are in one
  | list or the other, and never both.  Items still
  | referenced by clients but erased from the cache
  | are in neither list.  The lists are:
  |
  | - in-use:  contains the items currently
  |   referenced by clients, in no particular
  |   order.  (This list is used for invariant
  |   checking.  If we removed the check, elements
  |   that would otherwise be on this list could be
  |   left as disconnected singleton lists.)
  |
  | - LRU:  contains the items not currently
  | referenced by clients, in LRU order Elements
  | are moved between these lists by the Ref() and
  | Unref() methods, when they detect an element in
  | the cache acquiring or losing its only external
  | reference.
  */

crate::ix!();

pub const NUM_SHARD_BITS: usize = 4;
pub const NUM_SHARDS:     usize = 1 << NUM_SHARD_BITS;

//-------------------------------------------[.cpp/bitcoin/src/leveldb/util/cache.cc]

/**
  | An entry is a variable length heap-allocated
  | structure. Entries are kept in a circular
  | doubly linked list ordered by access
  | time.
  |
  */
pub struct LRUHandle {

    value:      *mut c_void,

    deleter:    fn(_0: &Slice, value: *mut c_void) -> c_void,

    next_hash:  *mut LRUHandle,
    next:       *mut LRUHandle,
    prev:       *mut LRUHandle,

    /**
       TODO(opt): Only allow uint32_t?
      */
    charge:     usize,

    key_length: usize,

    /**
       Whether entry is in the cache.
      */
    in_cache:   bool,

    /**
       References, including cache reference, if
       present.
      */
    refs:       u32,

    /**
       Hash of key(); used for fast sharding and
       comparisons
      */
    hash:       u32,

    /**
       Beginning of key
      */
    key_data:   [u8; 1],
}

impl LRUHandle {

    pub fn key(&self) -> Slice {
        
        todo!();
        /*
            // next_ is only equal to this if the LRU handle is the list head of an
        // empty list. List heads never have meaningful keys.
        assert(next != this);

        return Slice(key_data, key_length);
        */
    }
}

/**
  | We provide our own simple hash table since it
  | removes a whole bunch of porting hacks and is
  | also faster than some of the built-in hash
  | table implementations in some of the
  | compiler/runtime combinations we have tested.
  | E.g., readrandom speeds up by ~5% over the g++
  | 4.4.3's builtin hashtable.
  */
pub struct HandleTable {

    /**
      | The table consists of an array of buckets
      | where each bucket is a linked list of
      | cache entries that hash into the bucket.
      |
      */
    length: u32,
    elems:  u32,
    list:   *mut *mut LRUHandle,
}

impl Default for HandleTable {
    
    fn default() -> Self {
        todo!();
        /*
        : length(0),
        : elems(0),
        : list(nullptr),

            Resize();
        */
    }
}

impl Drop for HandleTable {
    fn drop(&mut self) {
        todo!();
        /*
            delete[] list_;
        */
    }
}

impl HandleTable {

    pub fn lookup(&mut self, 
        key_:  &Slice,
        hash_: u32) -> *mut LRUHandle {
        
        todo!();
        /*
            return *FindPointer(key, hash);
        */
    }
    
    pub fn insert(&mut self, h: *mut LRUHandle) -> *mut LRUHandle {
        
        todo!();
        /*
            LRUHandle** ptr = FindPointer(h->key(), h->hash);
        LRUHandle* old = *ptr;
        h->next_hash = (old == nullptr ? nullptr : old->next_hash);
        *ptr = h;
        if (old == nullptr) {
          ++elems_;
          if (elems_ > length_) {
            // Since each cache entry is fairly large, we aim for a small
            // average linked list length (<= 1).
            Resize();
          }
        }
        return old;
        */
    }
    
    pub fn remove(&mut self, 
        key_:  &Slice,
        hash_: u32) -> *mut LRUHandle {
        
        todo!();
        /*
            LRUHandle** ptr = FindPointer(key, hash);
        LRUHandle* result = *ptr;
        if (result != nullptr) {
          *ptr = result->next_hash;
          --elems_;
        }
        return result;
        */
    }

    /**
      | Return a pointer to slot that points to
      | a cache entry that matches key/hash.  If
      | there is no such cache entry, return
      | a pointer to the trailing slot in the
      | corresponding linked list.
      */
    pub fn find_pointer(&mut self, 
        key_:  &Slice,
        hash_: u32) -> *mut *mut LRUHandle {
        
        todo!();
        /*
            LRUHandle** ptr = &list_[hash & (length_ - 1)];
        while (*ptr != nullptr && ((*ptr)->hash != hash || key != (*ptr)->key())) {
          ptr = &(*ptr)->next_hash;
        }
        return ptr;
        */
    }
    
    pub fn resize(&mut self)  {
        
        todo!();
        /*
            uint32_t new_length = 4;
        while (new_length < elems_) {
          new_length *= 2;
        }
        LRUHandle** new_list = new LRUHandle*[new_length];
        memset(new_list, 0, sizeof(new_list[0]) * new_length);
        uint32_t count = 0;
        for (uint32_t i = 0; i < length_; i++) {
          LRUHandle* h = list_[i];
          while (h != nullptr) {
            LRUHandle* next = h->next_hash;
            uint32_t hash = h->hash;
            LRUHandle** ptr = &new_list[hash & (new_length - 1)];
            h->next_hash = *ptr;
            *ptr = h;
            h = next;
            count++;
          }
        }
        assert(elems_ == count);
        delete[] list_;
        list_ = new_list;
        length_ = new_length;
        */
    }
}

/**
   A single shard of sharded cache.
  */
pub struct LRUCache {

    /**
       Initialized before use.
      */
    capacity: usize,

    /**
      | mutex_ protects the following state.
      |
      */
    mutex:    RefCell<Mutex<LRUCacheInner>>,
}

pub struct LRUCacheInner {
    usage:    usize,

    /**
      | Dummy head of LRU list.
      |
      | lru.prev is newest entry, lru.next is
      | oldest entry.
      |
      | Entries have refs==1 and in_cache==true.
      */
    lru:      LRUHandle,

    /**
      | Dummy head of in-use list. 
      |
      | Entries are in use by clients, and have
      | refs >= 2 and in_cache==true.
      |
      */
    in_use:   LRUHandle,

    table:    HandleTable,
}

impl Drop for LRUCache {
    fn drop(&mut self) {
        todo!();
        /*
            assert(in_use_.next == &in_use_);  // Error if caller has an unreleased handle
      for (LRUHandle* e = lru_.next; e != &lru_;) {
        LRUHandle* next = e->next;
        assert(e->in_cache);
        e->in_cache = false;
        assert(e->refs == 1);  // Invariant of lru_ list.
        Unref(e);
        e = next;
      }
        */
    }
}

impl LRUCache {

    /**
      | Separate from constructor so caller
      | can easily make an array of LRUCache
      |
      */
    pub fn set_capacity(&mut self, capacity: usize)  {
        
        todo!();
        /*
            capacity_ = capacity;
        */
    }

    pub fn total_charge(&self) -> usize {
        
        todo!();
        /*
            MutexLock l(&mutex_);
        return usage_;
        */
    }
    
    pub fn new() -> Self {
    
        todo!();
        /*
        : capacity(0),
        : usage(0),

            // Make empty circular linked lists.
      lru_.next = &lru_;
      lru_.prev = &lru_;
      in_use_.next = &in_use_;
      in_use_.prev = &in_use_;
        */
    }
    
    pub fn ref_(&mut self, e: *mut LRUHandle)  {
        
        todo!();
        /*
          if (e->refs == 1 && e->in_cache) {  // If on lru_ list, move to in_use_ list.
            LRU_Remove(e);
            LRU_Append(&in_use_, e);
          }
          e->refs++;
        */
    }
    
    pub fn unref(&mut self, e: *mut LRUHandle)  {
        
        todo!();
        /*
      assert(e->refs > 0);
      e->refs--;
      if (e->refs == 0) {  // Deallocate.
        assert(!e->in_cache);
        (*e->deleter)(e->key(), e->value);
        free(e);
      } else if (e->in_cache && e->refs == 1) {
        // No longer in use; move to lru_ list.
        LRU_Remove(e);
        LRU_Append(&lru_, e);
      }
        */
    }
    
    pub fn lru_remove(&mut self, e: *mut LRUHandle)  {
        
        todo!();
        /*
           e->next->prev = e->prev;
           e->prev->next = e->next;
           */
    }
    
    pub fn lru_append(&mut self, 
        list: *mut LRUHandle,
        e:    *mut LRUHandle)  {
        
        todo!();
        /*
        // Make "e" newest entry by inserting just before *list
        e->next = list;
        e->prev = list->prev;
        e->prev->next = e;
        e->next->prev = e;
        */
    }
    
    pub fn lookup(&mut self, 
        key_:  &Slice,
        hash_: u32) -> *mut CacheHandle {
        
        todo!();
        /*
          MutexLock l(&mutex_);
          LRUHandle* e = table_.Lookup(key, hash);
          if (e != nullptr) {
            Ref(e);
          }
          return reinterpret_cast<Cache::Handle*>(e);
        */
    }
    
    pub fn release(&mut self, handle: *mut CacheHandle)  {
        
        todo!();
        /*
           MutexLock l(&mutex_);
           Unref(reinterpret_cast<LRUHandle*>(handle));
           */
    }
    
    /**
      | Like Cache methods, but with an extra
      | "hash" parameter.
      |
      */
    pub fn insert(&mut self, 
        key_:     &Slice,
        hash_:    u32,
        value:   *mut c_void,
        charge:  usize,
        deleter: fn(key_: &Slice, value: *mut c_void) -> c_void) -> *mut CacheHandle {
        
        todo!();
        /*
            MutexLock l(&mutex_);

      LRUHandle* e =
          reinterpret_cast<LRUHandle*>(malloc(sizeof(LRUHandle) - 1 + key.size()));
      e->value = value;
      e->deleter = deleter;
      e->charge = charge;
      e->key_length = key.size();
      e->hash = hash;
      e->in_cache = false;
      e->refs = 1;  // for the returned handle.
      memcpy(e->key_data, key.data(), key.size());

      if (capacity_ > 0) {
        e->refs++;  // for the cache's reference.
        e->in_cache = true;
        LRU_Append(&in_use_, e);
        usage_ += charge;
        FinishErase(table_.Insert(e));
      } else {  // don't cache. (capacity_==0 is supported and turns off caching.)
        // next is read by key() in an assert, so it must be initialized
        e->next = nullptr;
      }
      while (usage_ > capacity_ && lru_.next != &lru_) {
        LRUHandle* old = lru_.next;
        assert(old->refs == 1);
        bool erased = FinishErase(table_.Remove(old->key(), old->hash));
        if (!erased) {  // to avoid unused variable when compiled NDEBUG
          assert(erased);
        }
      }

      return reinterpret_cast<Cache::Handle*>(e);
        */
    }

    /**
      | If e != nullptr, finish removing *e from
      | the cache; it has already been removed from
      | the hash table.  Return whether e !=
      | nullptr.
      */
    #[EXCLUSIVE_LOCKS_REQUIRED(mutex_)]
    pub fn finish_erase(&mut self, e: *mut LRUHandle) -> bool {
        
        todo!();
        /*
          if (e != nullptr) {
            assert(e->in_cache);
            LRU_Remove(e);
            e->in_cache = false;
            usage_ -= e->charge;
            Unref(e);
          }
          return e != nullptr;
        */
    }
    
    pub fn erase(&mut self, 
        key_:  &Slice,
        hash_: u32)  {
        
        todo!();
        /*
            MutexLock l(&mutex_);
      FinishErase(table_.Remove(key, hash));
        */
    }
    
    pub fn prune(&mut self)  {
        
        todo!();
        /*
            MutexLock l(&mutex_);
      while (lru_.next != &lru_) {
        LRUHandle* e = lru_.next;
        assert(e->refs == 1);
        bool erased = FinishErase(table_.Remove(e->key(), e->hash));
        if (!erased) {  // to avoid unused variable when compiled NDEBUG
          assert(erased);
        }
      }
        */
    }
}

pub struct ShardedLRUCache {
    base:     Cache,
    shard:    [LRUCache; NUM_SHARDS],
    id_mutex: parking_lot::RawMutex,
    last_id:  u64,
}

impl ShardedLRUCache {

    #[inline] pub fn hash_slice(s: &Slice) -> u32 {
        
        todo!();
        /*
            return Hash(s.data(), s.size(), 0);
        */
    }
    
    pub fn shard(hash_: u32) -> u32 {
        
        todo!();
        /*
            return hash >> (32 - kNumShardBits);
        */
    }
    
    pub fn new(capacity: usize) -> Self {
    
        todo!();
        /*
        : last_id(0),

        const size_t per_shard = (capacity + (kNumShards - 1)) / kNumShards;
        for (int s = 0; s < kNumShards; s++) {
          shard_[s].SetCapacity(per_shard);
        }
        */
    }
    
    pub fn insert(&mut self, 
        key_:     &Slice,
        value:   *mut c_void,
        charge:  usize,
        deleter: fn(key_: &Slice, value: *mut c_void) -> c_void) -> *mut CacheHandle {
        
        todo!();
        /*
        const uint32_t hash = HashSlice(key);
        return shard_[Shard(hash)].Insert(key, hash, value, charge, deleter);
        */
    }
    
    pub fn lookup(&mut self, key_: &Slice) -> *mut CacheHandle {
        
        todo!();
        /*
        const uint32_t hash = HashSlice(key);
        return shard_[Shard(hash)].Lookup(key, hash);
        */
    }
    
    pub fn release(&mut self, handle: *mut CacheHandle)  {
        
        todo!();
        /*
        LRUHandle* h = reinterpret_cast<LRUHandle*>(handle);
        shard_[Shard(h->hash)].Release(handle);
        */
    }
    
    pub fn erase(&mut self, key_: &Slice)  {
        
        todo!();
        /*
        const uint32_t hash = HashSlice(key);
        shard_[Shard(hash)].Erase(key, hash);
        */
    }
    
    pub fn value(&mut self, handle: *mut CacheHandle)  {
        
        todo!();
        /*
        return reinterpret_cast<LRUHandle*>(handle)->value;
        */
    }
    
    pub fn new_id(&mut self) -> u64 {
        
        todo!();
        /*
        MutexLock l(&id_mutex_);
        return ++(last_id_);
        */
    }
    
    pub fn prune(&mut self)  {
        
        todo!();
        /*
        for (int s = 0; s < kNumShards; s++) {
          shard_[s].Prune();
        }
        */
    }
    
    pub fn total_charge(&self) -> usize {
        
        todo!();
        /*
        size_t total = 0;
        for (int s = 0; s < kNumShards; s++) {
          total += shard_[s].TotalCharge();
        }
        return total;
        */
    }
}

pub fn new_lru_cache(capacity: usize) -> *mut Cache {
    
    todo!();
    /*
       return new ShardedLRUCache(capacity);
       */
}