| 50 | } |
| 51 | |
| 52 | fn insert(&mut self, key: K, val: V) -> Option<V> { |
| 53 | if self.map.contains_key(&key) { // 存在 key 就更新 |
| 54 | self.access(&key); |
| 55 | let entry = &mut self.entries[self.head.unwrap()]; |
| 56 | let old_val = entry.val.take(); |
| 57 | entry.val = Some(val); |
| 58 | old_val |
| 59 | } else { // 不存在就插入 |
| 60 | self.ensure_room(); |
| 61 | |
| 62 | // 更新原始头指针 |
| 63 | let index = self.entries.len(); |
| 64 | self.head.map(|e| { |
| 65 | self.entries[e].prev = Some(index); |
| 66 | }); |
| 67 | |
| 68 | // 新的头结点 |
| 69 | self.entries.push(Entry { |
| 70 | key: key.clone(), |
| 71 | val: Some(val), |
| 72 | prev: None, |
| 73 | next: self.head, |
| 74 | }); |
| 75 | self.head = Some(index); |
| 76 | self.tail = self.tail.or(self.head); |
| 77 | self.map.insert(key, index); |
| 78 | |
| 79 | None |
| 80 | } |
| 81 | } |
| 82 | |
| 83 | fn remove(&mut self, key: &K) -> Option<V> { |
| 84 | self.map.remove(&key).map(|index| { |