1 4 package com.tc.memorydatastore.server; 5 6 import com.tc.memorydatastore.message.TCByteArrayKeyValuePair; 7 import com.tc.util.Assert; 8 9 import java.util.ArrayList ; 10 import java.util.Arrays ; 11 import java.util.Collection ; 12 import java.util.HashMap ; 13 import java.util.Iterator ; 14 import java.util.Map ; 15 import java.util.Set ; 16 import java.util.TreeMap ; 17 18 public class MemoryDataStore { 19 private final static int MAX_TRIE_LEVEL = 8; 20 21 private final Map store = new HashMap (); 22 23 public MemoryDataStore() { 24 super(); 25 } 26 27 public synchronized void put(String dataStoreName, byte[] key, byte[] value) { 28 DataStore dataStore = getDataStore(dataStoreName); 29 dataStore.put(key, value); 30 } 31 32 public synchronized byte[] get(String dataStoreName, byte[] key) { 33 DataStore dataStore = getDataStore(dataStoreName); 34 return dataStore.get(key); 35 } 36 37 public synchronized Collection getAll(String dataStoreName, byte[] key) { 38 DataStore dataStore = getDataStore(dataStoreName); 39 40 return dataStore.getAll(key); 41 } 42 43 public synchronized byte[] remove(String dataStoreName, byte[] key) { 44 DataStore dataStore = getDataStore(dataStoreName); 45 return dataStore.remove(key); 46 } 47 48 public synchronized int removeAll(String dataStoreName, byte[] key) { 49 DataStore dataStore = getDataStore(dataStoreName); 50 return dataStore.removeAll(key); 51 } 52 53 private DataStore getDataStore(String dataStoreName) { 54 DataStore dataStore = (DataStore) this.store.get(dataStoreName); 55 if (dataStore == null) { 56 dataStore = new DataStore(); 57 this.store.put(dataStoreName, dataStore); 58 } 59 return dataStore; 60 } 61 62 68 69 private static class ByteArrayObjectWrapper implements Comparable { 70 private byte[] value; 71 72 public ByteArrayObjectWrapper(byte[] value) { 73 this.value = value; 74 } 75 76 public int hashCode() { 77 if (value == null) 78 return 0; 79 80 int result = 1; 81 for (int i = 0; i < value.length; i++) { 82 result = 31 * result + value[i]; 83 } 84 85 return result; 86 } 87 88 public boolean equals(Object obj) { 89 if (obj == null) { 90 return false; 91 } 92 if (!(obj instanceof ByteArrayObjectWrapper)) { 93 return false; 94 } 95 return Arrays.equals(this.value, ((ByteArrayObjectWrapper) obj).value); 96 } 97 98 public String toString() { 99 StringBuffer sb = new StringBuffer (); 100 for (int i = 0; i < value.length; i++) { 101 sb.append(value[i]); 102 sb.append(" "); 103 } 104 return sb.toString(); 105 } 106 107 public int compareTo(Object obj) { 108 if (obj == null) { 109 throw new NullPointerException (); 110 } 111 Assert.assertTrue(obj instanceof ByteArrayObjectWrapper); 112 113 ByteArrayObjectWrapper objWrapper = (ByteArrayObjectWrapper) obj; 114 115 byte[] b = objWrapper.value; 116 117 for (int i = 0; i < value.length; i++) { 118 if (i >= b.length) { 119 break; 120 } 121 if (value[i] == b[i]) { 122 continue; 123 } 124 if (value[i] < b[i]) { 125 return -1; 126 } 127 if (value[i] > b[i]) { 128 return 1; 129 } 130 } 131 132 if (value.length == b.length) { 133 return 0; 134 } 135 if (value.length > b.length) { 136 return 1; 137 } 138 return -1; 139 } 140 141 public boolean startsWith(ByteArrayObjectWrapper obj) { 142 byte[] b = obj.value; 143 if (value.length < b.length) { return false; } 144 145 for (int i = 0; i < b.length; i++) { 146 if (value[i] == b[i]) { 147 continue; 148 } else { 149 return false; 150 } 151 } 152 return true; 153 } 154 } 155 156 private static class DataStore { 157 private final TreeMap map = new TreeMap (); 158 159 public DataStore() { 160 super(); 161 } 162 163 public void put(byte[] key, byte[] value) { 164 if (key.length <= 0) { 165 return; 166 } 167 map.put(new ByteArrayObjectWrapper(key), value); 168 } 169 170 public byte[] get(byte[] key) { 171 if (key.length <= 0) { 172 return null; 173 } 174 175 return (byte[]) map.get(new ByteArrayObjectWrapper(key)); 176 } 177 178 public Collection getAll(byte[] key) { 179 if (key.length <= 0) { 180 return null; 181 } 182 183 ByteArrayObjectWrapper wrappedKey = new ByteArrayObjectWrapper(key); 185 Map subMap = map.tailMap(wrappedKey); 186 188 Collection returnValues = new ArrayList (); 189 190 Set entrySet = subMap.entrySet(); 191 for (Iterator i = entrySet.iterator(); i.hasNext();) { 192 Map.Entry entry = (Map.Entry ) i.next(); 193 ByteArrayObjectWrapper k = (ByteArrayObjectWrapper) entry.getKey(); 194 byte[] v = (byte[]) entry.getValue(); 195 if (k.startsWith(wrappedKey)) { 196 returnValues.add(new TCByteArrayKeyValuePair(k.value, v)); 197 } else { 198 break; 199 } 200 } 201 205 return returnValues; 206 } 207 208 public byte[] remove(byte[] key) { 209 if (key.length <= 0) { 210 return null; 211 } 212 213 return (byte[]) map.remove(new ByteArrayObjectWrapper(key)); 214 } 215 216 public int removeAll(byte[] key) { 217 if (key.length <= 0) { 218 return 0; 219 } 220 221 ByteArrayObjectWrapper wrappedKey = new ByteArrayObjectWrapper(key); 222 Map subMap = map.tailMap(wrappedKey); 223 225 int returnValue = 0; 226 Set entrySet = subMap.entrySet(); 227 for (Iterator i = entrySet.iterator(); i.hasNext();) { 228 Map.Entry entry = (Map.Entry ) i.next(); 229 ByteArrayObjectWrapper k = (ByteArrayObjectWrapper) entry.getKey(); 230 if (k.startsWith(wrappedKey)) { 231 i.remove(); 232 returnValue++; 233 } else { 234 break; 235 } 236 } 237 238 240 return returnValue; 241 } 242 } 243 244 private static class ByteTrie { 245 private final static int NUM_OF_ENTRIES = 256; 246 private final ByteTrieNode[] head = new ByteTrieNode[NUM_OF_ENTRIES]; 247 248 public ByteTrie() { 249 super(); 250 } 251 252 public void put(byte[] key, byte[] value) { 253 if (key.length <= 0) { 254 return; 255 } 256 257 ByteTrieNode node = getNode(key); 258 node.put(key, value); 259 } 260 261 public byte[] get(byte[] key) { 262 if (key.length <= 0) { 263 return null; 264 } 265 266 ByteTrieNode node = getNode(key); 267 return node.get(key); 268 } 269 270 public Collection getAll(byte[] key) { 271 if (key.length <= 0) { 272 return null; 273 } 274 275 ByteTrieNode node = getNode(key); 276 return node.getAll(); 277 } 278 279 public byte[] remove(byte[] key) { 280 if (key.length <= 0) { 281 return null; 282 } 283 284 ByteTrieNode node = getNode(key); 285 return node.remove(key); 286 } 287 288 public int removeAll(byte[] key) { 289 if (key.length <= 0) { 290 return 0; 291 } 292 293 ByteTrieNode node = getNode(key); 294 return node.removeAll(key); 295 } 296 297 public void dumpTrie() { 298 for (int i = 0; i < head.length; i++) { 299 if (head[i] != null) { 300 System.err.println("head[" + i + "]: " + head[i]); 301 head[i].dumpTrie(2); 302 } 303 } 304 } 305 306 private ByteTrieNode getNode(byte[] key) { 307 ByteTrieNode node = getNode(head, key[0]); 308 309 int level = (MAX_TRIE_LEVEL == -1 || key.length < MAX_TRIE_LEVEL) ? key.length : MAX_TRIE_LEVEL; 310 for (int i = 1; i < level; i++) { 311 node = getNode(node.next, key[i]); 312 } 313 return node; 314 } 315 316 private ByteTrieNode getNode(ByteTrieNode[] nodes, byte b) { 317 ByteTrieNode node = nodes[b - 1]; 318 if (node == null) { 319 node = new ByteTrieNode(); 320 nodes[b - 1] = node; 321 } 322 return node; 323 } 324 325 private static class ByteTrieNode { 326 private final ByteTrieNode[] next = new ByteTrieNode[NUM_OF_ENTRIES]; 327 private final Map dataEntries = new HashMap (); 328 329 public void put(byte[] key, byte[] value) { 330 dataEntries.put(new ByteArrayObjectWrapper(key), value); 331 } 332 333 public byte[] get(byte[] key) { 334 return (byte[]) dataEntries.get(new ByteArrayObjectWrapper(key)); 335 } 336 337 public Collection getAll() { 338 Collection returnValue = new ArrayList (); 339 Set entrySet = dataEntries.entrySet(); 340 for (Iterator i = entrySet.iterator(); i.hasNext();) { 341 Map.Entry entry = (Map.Entry ) i.next(); 342 ByteArrayObjectWrapper key = (ByteArrayObjectWrapper) entry.getKey(); 343 TCByteArrayKeyValuePair keyValuePair = new TCByteArrayKeyValuePair(key.value, (byte[]) entry.getValue()); 344 returnValue.add(keyValuePair); 345 } 346 for (int i = 0; i < next.length; i++) { 347 if (next[i] != null) { 348 returnValue.addAll(next[i].getAll()); 349 } 350 } 351 return returnValue; 352 } 353 354 public byte[] remove(byte[] key) { 355 return (byte[]) dataEntries.remove(new ByteArrayObjectWrapper(key)); 356 } 357 358 public int removeAll(byte[] key) { 359 int numOfRemove = getNumOfChilds(); 360 dataEntries.clear(); 361 for (int i = 0; i < next.length; i++) { 362 next[i] = null; 363 } 364 return numOfRemove; 365 } 366 367 public void dumpTrie(int numOfSpaces) { 368 printSpace(numOfSpaces); 369 System.err.println("Size of data: " + dataEntries.size()); 370 Set keySet = dataEntries.keySet(); 371 for (Iterator i = keySet.iterator(); i.hasNext();) { 372 Object key = i.next(); 373 printSpace(numOfSpaces); 374 System.err.println("key: " + key); 375 } 376 377 for (int i = 0; i < next.length; i++) { 378 if (next[i] != null) { 379 printSpace(numOfSpaces); 380 System.err.println("next[" + i + "]: " + next[i]); 381 next[i].dumpTrie(numOfSpaces + 2); 382 } 383 } 384 } 385 386 private int getNumOfChilds() { 387 int numOfChilds = 0; 388 for (int i = 0; i < next.length; i++) { 389 if (next[i] != null) { 390 numOfChilds += next[i].getNumOfChilds(); 391 } 392 } 393 return dataEntries.size() + numOfChilds; 394 } 395 396 private void printSpace(int numOfSpaces) { 397 for (int i = 0; i < numOfSpaces; i++) { 398 System.err.print(' '); 399 } 400 } 401 } 402 403 } 404 405 } 406 | Popular Tags |