Repository: seung-lab/cloud-volume

Issue:
LRU Crash
The new LRU code is crashing on basil:

cv = CloudVolume('...')

img = cv.download_point((37902, 50771, 610), size=(256,256,256))
labels = fastremap.unique(img)
print(len(labels))

s = time.time()
x = cv.skeleton.reader.exists(labels, cv.skeleton.meta.skeleton_path)
print(time.time() - s)

```
Traceback (most recent call last):
  File "test2.py", line 17, in <module>
    x = cv.skeleton.reader.exists(labels, cv.skeleton.meta.skeleton_path)
  File "/Users/wms/cloud-volume/cloudvolume/datasource/precomputed/sharding.py", line 407, in exists
    minishard_number, path
  File "/Users/wms/cloud-volume/cloudvolume/datasource/precomputed/sharding.py", line 309, in get_minishard_index
    res = self.get_minishard_indices(filename, index, minishard_no, path)
  File "/Users/wms/cloud-volume/cloudvolume/datasource/precomputed/sharding.py", line 360, in get_minishard_indices
    self.minishard_index_cache[cache_key] = minishard_index
  File "/Users/wms/cloud-volume/cloudvolume/lru.py", line 221, in __setitem__
    (tkey, tval) = self.queue.delete_tail()
TypeError: cannot unpack non-iterable NoneType object
 92%|█████████████████████████████████████▌   | 457/499 [02:02<00:11,  3.73it/s]```

Discussion:
codecov-io: # [Codecov](https://codecov.io/gh/seung-lab/cloud-volume/pull/343?src=pr&el=h1) Report
> Merging [#343](https://codecov.io/gh/seung-lab/cloud-volume/pull/343?src=pr&el=desc) into [master](https://codecov.io/gh/seung-lab/cloud-volume/commit/c3556ac9116f474c76d0046263e4b57ec0af3388&el=desc) will **increase** coverage by `0.02%`.
> The diff coverage is `79.16%`.

[![Impacted file tree graph](https://codecov.io/gh/seung-lab/cloud-volume/pull/343/graphs/tree.svg?width=650&height=150&src=pr&token=7WwqdI3qkW)](https://codecov.io/gh/seung-lab/cloud-volume/pull/343?src=pr&el=tree)

```diff
@@            Coverage Diff             @@
##           master     #343      +/-   ##
==========================================
+ Coverage   79.14%   79.16%   +0.02%     
==========================================
  Files          75       75              
  Lines        9081     9121      +40     
==========================================
+ Hits         7187     7221      +34     
- Misses       1894     1900       +6     
```


| [Impacted Files](https://codecov.io/gh/seung-lab/cloud-volume/pull/343?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [cloudvolume/lru.py](https://codecov.io/gh/seung-lab/cloud-volume/pull/343/diff?src=pr&el=tree#diff-Y2xvdWR2b2x1bWUvbHJ1LnB5) | `69.31% <69.69%> (+1.01%)` | :arrow_up: |
| [test/test\_lru.py](https://codecov.io/gh/seung-lab/cloud-volume/pull/343/diff?src=pr&el=tree#diff-dGVzdC90ZXN0X2xydS5weQ==) | `100.00% <100.00%> (ø)` | |

------

[Continue to review full report at Codecov](https://codecov.io/gh/seung-lab/cloud-volume/pull/343?src=pr&el=continue).
> **Legend** - [Click here to learn more](https://docs.codecov.io/docs/codecov-delta)
> `Δ = absolute <relative> (impact)`, `ø = not affected`, `? = missing data`
> Powered by [Codecov](https://codecov.io/gh/seung-lab/cloud-volume/pull/343?src=pr&el=footer). Last update [c3556ac...ae01e39](https://codecov.io/gh/seung-lab/cloud-volume/pull/343?src=pr&el=lastupdated). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments).


Patch:
diff --git a/cloudvolume/lru.py b/cloudvolume/lru.py
index 161ccfb..df80ede 100644
--- a/cloudvolume/lru.py
+++ b/cloudvolume/lru.py
@@ -100,6 +100,11 @@ class DoublyLinkedList(object):
   def delete(self, node):
     nxt, prev = node.next, node.prev
 
+    if self.head == node:
+      self.head = nxt
+    if self.tail == node:
+      self.tail = prev
+
     if prev is not None:
       prev.next = nxt
 
@@ -133,11 +138,12 @@ class DoublyLinkedList(object):
       self.head = ListNode(val, None, None)
       self.tail = self.head
     elif self.head is None:
-      self.head = ListNode(val, self.tail, None)
+      self.head = ListNode(val, next=self.tail, prev=None)
       self.tail.prev = self.head
     else:
-      self.head = ListNode(val, self.head, None)
-      self.head.next.prev = self.head
+      prev_head = self.head
+      self.head = ListNode(val, next=prev_head, prev=None)
+      prev_head.prev = self.head
 
     self.size += 1
 
@@ -170,6 +176,15 @@ class LRU(object):
   def __len__(self):
     return self.queue.size
 
+  def keys(self):
+    return self.hash.keys()
+
+  def values(self):
+    return ( node.val for val in self.queue )
+
+  def items(self):
+    return ( (key, node.val) for key, node in self.hash.items() )
+
   def clear(self):
     self.queue = DoublyLinkedList()
     self.hash = {}
@@ -190,19 +205,26 @@ class LRU(object):
       (key,val) = self.queue.delete_tail()
       del self.hash[key]
 
-  def __contains__(self, key):
-    return key in self.hash
-
-  def __getitem__(self, key):
+  def delete(self, key):
     if key not in self.hash:
       raise KeyError("{} not in cache.".format(key))
 
+    node = self.hash[key]
+    self.queue.delete(node)
+    del self.hash[key]
+
+  def get(self, key, default=None):
+    if key not in self.hash:
+      if default is None:
+        raise KeyError("{} not in cache.".format(key))
+      return default
+
     node = self.hash[key]
     self.queue.promote_to_head(node)
 
     return node.val[1]
 
-  def __setitem__(self, key, val):
+  def set(self, key, val):
     if self.size == 0:
       return
 
@@ -218,7 +240,19 @@ class LRU(object):
 
     while len(self.queue) > self.size:
       (tkey,tval) = self.queue.delete_tail()
-      del self.hash[tkey]      
+      del self.hash[tkey]     
+
+  def __contains__(self, key):
+    return key in self.hash
+
+  def __getitem__(self, key):
+    return self.get(key)
+
+  def __setitem__(self, key, val):
+    return self.set(key, val)
+
+  def __delitem__(self, key):
+    return self.delete(key)
 
   def __str__(self):
     return str(self.queue)


Test patch:
diff --git a/test/test_lru.py b/test/test_lru.py
index b5601f8..7031452 100644
--- a/test/test_lru.py
+++ b/test/test_lru.py
@@ -1,5 +1,10 @@
+import pytest
+
 from cloudvolume.lru import LRU
 
+import time
+import random
+
 def test_lru():
   lru = LRU(5)
 
@@ -34,3 +39,25 @@ def test_lru():
   assert lru.queue.tolist() == [ 
     (0,0), (4,4), (3,3), (2,2), (1,1)
   ]
+
+def test_lru_chaos():
+  lru = LRU(10)
+
+  seed = time.time()
+  print("seed", seed)
+
+  random.seed(seed)
+  for i in range(150):
+    rand = random.randint(-5000, 5000)
+    lru[rand] = random.randint(-5000, 5000)
+
+    if rand % 17 == 0:
+      keys = lru.keys()
+      key = random.choice(list(keys))
+      lru[key]
+
+
+
+
+
+