| 36 | } |
| 37 | |
| 38 | fn insert(&mut self, key: K, val: V) -> Option<V> { |
| 39 | if self.map.contains_key(&key) { |
| 40 | self.access(&key); |
| 41 | let entry = &mut self.entries[self.head.unwrap()]; |
| 42 | let old_val = entry.val.take(); |
| 43 | entry.val = Some(val); |
| 44 | old_val |
| 45 | } else { |
| 46 | self.ensure_room(); |
| 47 | |
| 48 | // 更新原始头指针 |
| 49 | let index = self.entries.len(); |
| 50 | self.head.map(|e| { self.entries[e].prev = Some(index); }); |
| 51 | |
| 52 | // 新的头结点 |
| 53 | self.entries.push(Entry { |
| 54 | key: key.clone(), |
| 55 | val: Some(val), |
| 56 | prev: None, |
| 57 | next: self.head, |
| 58 | }); |
| 59 | self.head = Some(index); |
| 60 | self.tail = self.tail.or(self.head); |
| 61 | self.map.insert(key, index); |
| 62 | |
| 63 | None |
| 64 | } |
| 65 | } |
| 66 | |
| 67 | fn remove(&mut self, key: &K) -> Option<V> { |
| 68 | self.map.remove(&key).map(|index| { |