1 module bcaa; 2 pragma(LDC_no_moduleinfo); 3 4 import core.stdc.stdlib; 5 6 import dvector; 7 8 struct Bcaa(K, V, size_t tableSize = 16) { 9 struct Node { 10 K key; 11 V val; 12 Node* next; 13 } 14 15 private Node*[tableSize] htable; 16 17 private uint hashCode(K key) @nogc nothrow { 18 static if(is(K : int)){ 19 if(key<0) 20 return -cast(uint)(key % htable.length); 21 return cast(uint)(key % htable.length); 22 } else 23 static if(is(K == string)){ 24 uint hashval; 25 foreach (i, char c; key) 26 hashval = c + 31 * hashval; 27 return hashval % htable.length; 28 } else { 29 static assert(false, "Unsupported key type!"); 30 } 31 } 32 33 void set(K key, V val) @nogc nothrow { 34 uint pos = hashCode(key); 35 Node *list = htable[pos]; 36 Node *temp = list; 37 38 while(temp){ 39 if(temp.key == key){ 40 temp.val = val; 41 return; 42 } 43 temp = temp.next; 44 } 45 Node *newNode = cast(Node*)malloc(Node.sizeof); 46 newNode.key = key; 47 newNode.val = val; 48 newNode.next = list; 49 htable[pos] = newNode; 50 } 51 52 private Node* lookup(K key) @nogc nothrow { 53 immutable pos = hashCode(key); 54 Node* list = htable[pos]; 55 Node* temp = list; 56 while(temp){ 57 if(temp.key == key){ 58 return temp; 59 } 60 temp = temp.next; 61 } 62 return null; 63 } 64 65 V get(K key) @nogc nothrow { 66 const node = lookup(key); 67 if(node !is null) 68 return node.val; 69 return V.init; 70 } 71 72 V opIndex(K key) @nogc nothrow { 73 return get(key); 74 } 75 76 void opIndexAssign(V value, K key) @nogc nothrow { 77 set(key, value); 78 } 79 80 /// returning vector has to be cleaned-up with member free method of Dvector. 81 Dvector!K keys() @nogc nothrow { 82 Dvector!K ks; 83 84 foreach(i; 0..tableSize){ 85 auto node = htable[i]; 86 if(node is null) 87 continue; 88 Node* tmp = node; 89 while(tmp){ 90 ks.pushBack(tmp.key); 91 tmp = tmp.next; 92 } 93 } 94 95 return ks; 96 } 97 98 /// returning vector has to be cleaned-up with member free method of Dvector. 99 Dvector!V values() @nogc nothrow { 100 Dvector!V vals; 101 102 foreach(i; 0..tableSize){ 103 auto node = htable[i]; 104 if(node is null) 105 continue; 106 Node* tmp = node; 107 while(tmp){ 108 vals.pushBack(tmp.val); 109 tmp = tmp.next; 110 } 111 } 112 113 return vals; 114 } 115 116 // uses iteration 117 bool remove(K key) @nogc nothrow { 118 foreach(i; 0..tableSize){ 119 Node* current, previous; 120 previous = null; 121 for (current = htable[i]; 122 current != null; 123 previous = current, 124 current = current.next) { 125 126 if (current.key == key) { 127 if (previous == null) { 128 htable[i] = current.next; 129 } else { 130 previous.next = current.next; 131 } 132 core.stdc.stdlib.free(current); 133 current = null; 134 return true; 135 } 136 } 137 } 138 return false; 139 } 140 141 // uses recursion 142 bool remove2(K key) @nogc nothrow { 143 144 Node *recursiveDelete(Node *current, K key, bool* removed) @nogc nothrow { 145 if (current == null) 146 return null; 147 if (current.key == key) { 148 Node *tmpNext = current.next; 149 core.stdc.stdlib.free(current); 150 *removed = true; 151 return tmpNext; 152 } 153 current.next = recursiveDelete(current.next, key, removed); 154 return current; 155 } 156 157 bool removed = false; 158 159 foreach(i; 0..tableSize){ 160 htable[i] = recursiveDelete(htable[i], key, &removed); 161 if(removed) 162 return true; 163 } 164 return false; 165 } 166 167 void free() @nogc nothrow { 168 auto _keys = keys(); 169 foreach (key; _keys) 170 core.stdc.stdlib.free(lookup(key)); 171 _keys.free; 172 } 173 } 174 175 unittest { 176 import core.stdc.stdio; 177 178 Bcaa!(string, string) aa; 179 180 aa["Stevie"] = "Ray Vaughan"; 181 aa["Asım Can"] = "Gündüz"; 182 aa["Dan"] = "Patlansky"; 183 aa["İlter"] = "Kurcala"; 184 aa["Ferhat"] = "Kurtulmuş"; 185 186 assert(aa.remove("Ferhat") == true); 187 assert(aa["Ferhat"] == null); 188 assert(aa.remove("Foe") == false); 189 assert(aa["İlter"] =="Kurcala"); 190 191 printf("%s\n",aa["Stevie"].ptr); 192 printf("%s\n",aa["Asım Can"].ptr); 193 printf("%s\n",aa["Dan"].ptr); 194 195 auto _keys = aa.keys; 196 foreach(key; _keys) 197 printf("%s -> %s \n", key.ptr, aa[key].ptr); 198 _keys.free; 199 200 aa.free; 201 202 struct Guitar { 203 string brand; 204 } 205 206 Bcaa!(int, Guitar) guitars; 207 208 guitars[0] = Guitar("Fender"); 209 guitars[3] = Guitar("Gibson"); 210 guitars[356] = Guitar("Stagg"); 211 212 assert(guitars[3].brand == "Gibson"); 213 214 printf("%s \n", guitars[356].brand.ptr); 215 216 guitars.free; 217 }