1 /* 2 * P2PFaaS - A framework for FaaS Load Balancing 3 * Copyright (c) 2019 - 2022. Gabriele Proietti Mattia <pm.gabriele@outlook.com> 4 * 5 * This program is free software: you can redistribute it and/or modify 6 * it under the terms of the GNU General Public License as published by 7 * the Free Software Foundation, either version 3 of the License, or 8 * (at your option) any later version. 9 * 10 * This program is distributed in the hope that it will be useful, 11 * but WITHOUT ANY WARRANTY; without even the implied warranty of 12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 13 * GNU General Public License for more details. 14 * 15 * You should have received a copy of the GNU General Public License 16 * along with this program. If not, see <https://www.gnu.org/licenses/>. 17 */ 18 19 // Package hashtable creates a ValueHashtable data structure for the Item type 20 package hashtable 21 22 import ( 23 "fmt" 24 "sync" 25 26 "github.com/cheekybits/genny/generic" 27 ) 28 29 // Key the key of the dictionary 30 type Key generic.Type 31 32 // Value the content of the dictionary 33 type Value generic.Type 34 35 // ValueHashtable the set of Items 36 type ValueHashtable struct { 37 items map[int]Value 38 lock sync.RWMutex 39 } 40 41 // the hash() private function uses the famous Horner's method 42 // to generate a hash of a string with O(n) complexity 43 func hash(k Key) int { 44 key := fmt.Sprintf("%s", k) 45 h := 0 46 for i := 0; i < len(key); i++ { 47 h = 31*h + int(key[i]) 48 } 49 return h 50 } 51 52 // Put item with value v and key k into the hashtable 53 func (ht *ValueHashtable) Put(k Key, v Value) { 54 ht.lock.Lock() 55 defer ht.lock.Unlock() 56 i := hash(k) 57 if ht.items == nil { 58 ht.items = make(map[int]Value) 59 } 60 ht.items[i] = v 61 } 62 63 // Remove item with key k from hashtable 64 func (ht *ValueHashtable) Remove(k Key) { 65 ht.lock.Lock() 66 defer ht.lock.Unlock() 67 i := hash(k) 68 delete(ht.items, i) 69 } 70 71 // Get item with key k from the hashtable 72 func (ht *ValueHashtable) Get(k Key) Value { 73 ht.lock.RLock() 74 defer ht.lock.RUnlock() 75 i := hash(k) 76 return ht.items[i] 77 } 78 79 // Size returns the number of the hashtable elements 80 func (ht *ValueHashtable) Size() int { 81 ht.lock.RLock() 82 defer ht.lock.RUnlock() 83 return len(ht.items) 84 } 85