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 19package grpc 20 21import ( 22 "container/list" 23) 24 25type 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! 36type 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. 42func 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. 50func (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. 60func (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. 71func (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. 82func (m *linkedMap) len() int { 83 return len(m.m) 84} 85 86// clear removes all elements from the map. 87func (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. 93func (m *linkedMap) removeOldest() { 94 e := m.l.Front() 95 m.l.Remove(e) 96 delete(m.m, e.Value.(*linkedMapKVPair).key) 97} 98