1 /* 2 * 3 * Copyright 2018 gRPC authors. 4 * 5 * Licensed under the Apache License, Version 2.0 (the "License"); 6 * you may not use this file except in compliance with the License. 7 * You may obtain a copy of the License at 8 * 9 * http://www.apache.org/licenses/LICENSE-2.0 10 * 11 * Unless required by applicable law or agreed to in writing, software 12 * distributed under the License is distributed on an "AS IS" BASIS, 13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14 * See the License for the specific language governing permissions and 15 * limitations under the License. 16 * 17 */ 18 19 package grpc 20 21 import ( 22 "container/list" 23 ) 24 25 type linkedMapKVPair struct { 26 key string 27 value *stickyStoreEntry 28 } 29 30 // linkedMap is an implementation of a map that supports removing the oldest 31 // entry. 32 // 33 // linkedMap is NOT thread safe. 34 // 35 // It's for use of stickiness only! 36 type linkedMap struct { 37 m map[string]*list.Element 38 l *list.List // Head of the list is the oldest element. 39 } 40 41 // newLinkedMap returns a new LinkedMap. 42 func newLinkedMap() *linkedMap { 43 return &linkedMap{ 44 m: make(map[string]*list.Element), 45 l: list.New(), 46 } 47 } 48 49 // put adds entry (key, value) to the map. Existing key will be overridden. 50 func (m *linkedMap) put(key string, value *stickyStoreEntry) { 51 if oldE, ok := m.m[key]; ok { 52 // Remove existing entry. 53 m.l.Remove(oldE) 54 } 55 e := m.l.PushBack(&linkedMapKVPair{key: key, value: value}) 56 m.m[key] = e 57 } 58 59 // get returns the value of the given key. 60 func (m *linkedMap) get(key string) (*stickyStoreEntry, bool) { 61 e, ok := m.m[key] 62 if !ok { 63 return nil, false 64 } 65 m.l.MoveToBack(e) 66 return e.Value.(*linkedMapKVPair).value, true 67 } 68 69 // remove removes key from the map, and returns the value. The map is not 70 // modified if key is not in the map. 71 func (m *linkedMap) remove(key string) (*stickyStoreEntry, bool) { 72 e, ok := m.m[key] 73 if !ok { 74 return nil, false 75 } 76 delete(m.m, key) 77 m.l.Remove(e) 78 return e.Value.(*linkedMapKVPair).value, true 79 } 80 81 // len returns the len of the map. 82 func (m *linkedMap) len() int { 83 return len(m.m) 84 } 85 86 // clear removes all elements from the map. 87 func (m *linkedMap) clear() { 88 m.m = make(map[string]*list.Element) 89 m.l = list.New() 90 } 91 92 // removeOldest removes the oldest key from the map. 93 func (m *linkedMap) removeOldest() { 94 e := m.l.Front() 95 m.l.Remove(e) 96 delete(m.m, e.Value.(*linkedMapKVPair).key) 97 } 98
