001: /*
002: * All content copyright (c) 2003-2006 Terracotta, Inc., except as may otherwise be noted in a separate copyright notice. All rights reserved.
003: */
004: package com.tc.memorydatastore.server;
005:
006: import com.tc.memorydatastore.message.TCByteArrayKeyValuePair;
007: import com.tc.util.Assert;
008:
009: import java.util.ArrayList;
010: import java.util.Arrays;
011: import java.util.Collection;
012: import java.util.HashMap;
013: import java.util.Iterator;
014: import java.util.Map;
015: import java.util.Set;
016: import java.util.TreeMap;
017:
018: public class MemoryDataStore {
019: private final static int MAX_TRIE_LEVEL = 8;
020:
021: private final Map store = new HashMap();
022:
023: public MemoryDataStore() {
024: super ();
025: }
026:
027: public synchronized void put(String dataStoreName, byte[] key,
028: byte[] value) {
029: DataStore dataStore = getDataStore(dataStoreName);
030: dataStore.put(key, value);
031: }
032:
033: public synchronized byte[] get(String dataStoreName, byte[] key) {
034: DataStore dataStore = getDataStore(dataStoreName);
035: return dataStore.get(key);
036: }
037:
038: public synchronized Collection getAll(String dataStoreName,
039: byte[] key) {
040: DataStore dataStore = getDataStore(dataStoreName);
041:
042: return dataStore.getAll(key);
043: }
044:
045: public synchronized byte[] remove(String dataStoreName, byte[] key) {
046: DataStore dataStore = getDataStore(dataStoreName);
047: return dataStore.remove(key);
048: }
049:
050: public synchronized int removeAll(String dataStoreName, byte[] key) {
051: DataStore dataStore = getDataStore(dataStoreName);
052: return dataStore.removeAll(key);
053: }
054:
055: private DataStore getDataStore(String dataStoreName) {
056: DataStore dataStore = (DataStore) this .store.get(dataStoreName);
057: if (dataStore == null) {
058: dataStore = new DataStore();
059: this .store.put(dataStoreName, dataStore);
060: }
061: return dataStore;
062: }
063:
064: /*
065: * private ByteTrie getDataStore(String dataStoreName) { ByteTrie dataStore =
066: * (ByteTrie) this.store.get(dataStoreName); if (dataStore == null) {
067: * dataStore = new ByteTrie(); this.store.put(dataStoreName, dataStore); }
068: * return dataStore; }
069: */
070:
071: private static class ByteArrayObjectWrapper implements Comparable {
072: private byte[] value;
073:
074: public ByteArrayObjectWrapper(byte[] value) {
075: this .value = value;
076: }
077:
078: public int hashCode() {
079: if (value == null)
080: return 0;
081:
082: int result = 1;
083: for (int i = 0; i < value.length; i++) {
084: result = 31 * result + value[i];
085: }
086:
087: return result;
088: }
089:
090: public boolean equals(Object obj) {
091: if (obj == null) {
092: return false;
093: }
094: if (!(obj instanceof ByteArrayObjectWrapper)) {
095: return false;
096: }
097: return Arrays.equals(this .value,
098: ((ByteArrayObjectWrapper) obj).value);
099: }
100:
101: public String toString() {
102: StringBuffer sb = new StringBuffer();
103: for (int i = 0; i < value.length; i++) {
104: sb.append(value[i]);
105: sb.append(" ");
106: }
107: return sb.toString();
108: }
109:
110: public int compareTo(Object obj) {
111: if (obj == null) {
112: throw new NullPointerException();
113: }
114: Assert.assertTrue(obj instanceof ByteArrayObjectWrapper);
115:
116: ByteArrayObjectWrapper objWrapper = (ByteArrayObjectWrapper) obj;
117:
118: byte[] b = objWrapper.value;
119:
120: for (int i = 0; i < value.length; i++) {
121: if (i >= b.length) {
122: break;
123: }
124: if (value[i] == b[i]) {
125: continue;
126: }
127: if (value[i] < b[i]) {
128: return -1;
129: }
130: if (value[i] > b[i]) {
131: return 1;
132: }
133: }
134:
135: if (value.length == b.length) {
136: return 0;
137: }
138: if (value.length > b.length) {
139: return 1;
140: }
141: return -1;
142: }
143:
144: public boolean startsWith(ByteArrayObjectWrapper obj) {
145: byte[] b = obj.value;
146: if (value.length < b.length) {
147: return false;
148: }
149:
150: for (int i = 0; i < b.length; i++) {
151: if (value[i] == b[i]) {
152: continue;
153: } else {
154: return false;
155: }
156: }
157: return true;
158: }
159: }
160:
161: private static class DataStore {
162: private final TreeMap map = new TreeMap();
163:
164: public DataStore() {
165: super ();
166: }
167:
168: public void put(byte[] key, byte[] value) {
169: if (key.length <= 0) {
170: return;
171: }
172: map.put(new ByteArrayObjectWrapper(key), value);
173: }
174:
175: public byte[] get(byte[] key) {
176: if (key.length <= 0) {
177: return null;
178: }
179:
180: return (byte[]) map.get(new ByteArrayObjectWrapper(key));
181: }
182:
183: public Collection getAll(byte[] key) {
184: if (key.length <= 0) {
185: //return null;
186: }
187:
188: //long startTime = System.currentTimeMillis();
189: ByteArrayObjectWrapper wrappedKey = new ByteArrayObjectWrapper(
190: key);
191: Map subMap = map.tailMap(wrappedKey);
192: //System.err.println("Num of potentials in getAll: " + subMap.size());
193:
194: Collection returnValues = new ArrayList();
195:
196: Set entrySet = subMap.entrySet();
197: for (Iterator i = entrySet.iterator(); i.hasNext();) {
198: Map.Entry entry = (Map.Entry) i.next();
199: ByteArrayObjectWrapper k = (ByteArrayObjectWrapper) entry
200: .getKey();
201: byte[] v = (byte[]) entry.getValue();
202: if (key.length == 0 || k.startsWith(wrappedKey)) {
203: returnValues.add(new TCByteArrayKeyValuePair(
204: k.value, v));
205: } else {
206: break;
207: }
208: }
209: //System.err.println("Num to returns in getAll: " + returnValues.size());
210: //long endTime = System.currentTimeMillis();
211: //System.err.println("Time spent in getAll: " + (endTime - startTime) + " ms");
212:
213: return returnValues;
214: }
215:
216: public byte[] remove(byte[] key) {
217: if (key.length <= 0) {
218: return null;
219: }
220:
221: return (byte[]) map.remove(new ByteArrayObjectWrapper(key));
222: }
223:
224: public int removeAll(byte[] key) {
225: if (key.length <= 0) {
226: return 0;
227: }
228:
229: ByteArrayObjectWrapper wrappedKey = new ByteArrayObjectWrapper(
230: key);
231: Map subMap = map.tailMap(wrappedKey);
232: //System.err.println("Num of potentials in getAll: " + subMap.size());
233:
234: int returnValue = 0;
235: Set entrySet = subMap.entrySet();
236: for (Iterator i = entrySet.iterator(); i.hasNext();) {
237: Map.Entry entry = (Map.Entry) i.next();
238: ByteArrayObjectWrapper k = (ByteArrayObjectWrapper) entry
239: .getKey();
240: if (k.startsWith(wrappedKey)) {
241: i.remove();
242: returnValue++;
243: } else {
244: break;
245: }
246: }
247:
248: //System.err.println("Num to remove: " + returnValue);
249:
250: return returnValue;
251: }
252: }
253:
254: private static class ByteTrie {
255: private final static int NUM_OF_ENTRIES = 256;
256: private final ByteTrieNode[] head = new ByteTrieNode[NUM_OF_ENTRIES];
257:
258: public ByteTrie() {
259: super ();
260: }
261:
262: public void put(byte[] key, byte[] value) {
263: if (key.length <= 0) {
264: return;
265: }
266:
267: ByteTrieNode node = getNode(key);
268: node.put(key, value);
269: }
270:
271: public byte[] get(byte[] key) {
272: if (key.length <= 0) {
273: return null;
274: }
275:
276: ByteTrieNode node = getNode(key);
277: return node.get(key);
278: }
279:
280: public Collection getAll(byte[] key) {
281: if (key.length <= 0) {
282: return null;
283: }
284:
285: ByteTrieNode node = getNode(key);
286: return node.getAll();
287: }
288:
289: public byte[] remove(byte[] key) {
290: if (key.length <= 0) {
291: return null;
292: }
293:
294: ByteTrieNode node = getNode(key);
295: return node.remove(key);
296: }
297:
298: public int removeAll(byte[] key) {
299: if (key.length <= 0) {
300: return 0;
301: }
302:
303: ByteTrieNode node = getNode(key);
304: return node.removeAll(key);
305: }
306:
307: public void dumpTrie() {
308: for (int i = 0; i < head.length; i++) {
309: if (head[i] != null) {
310: System.err.println("head[" + i + "]: " + head[i]);
311: head[i].dumpTrie(2);
312: }
313: }
314: }
315:
316: private ByteTrieNode getNode(byte[] key) {
317: ByteTrieNode node = getNode(head, key[0]);
318:
319: int level = (MAX_TRIE_LEVEL == -1 || key.length < MAX_TRIE_LEVEL) ? key.length
320: : MAX_TRIE_LEVEL;
321: for (int i = 1; i < level; i++) {
322: node = getNode(node.next, key[i]);
323: }
324: return node;
325: }
326:
327: private ByteTrieNode getNode(ByteTrieNode[] nodes, byte b) {
328: ByteTrieNode node = nodes[b - 1];
329: if (node == null) {
330: node = new ByteTrieNode();
331: nodes[b - 1] = node;
332: }
333: return node;
334: }
335:
336: private static class ByteTrieNode {
337: private final ByteTrieNode[] next = new ByteTrieNode[NUM_OF_ENTRIES];
338: private final Map dataEntries = new HashMap();
339:
340: public void put(byte[] key, byte[] value) {
341: dataEntries.put(new ByteArrayObjectWrapper(key), value);
342: }
343:
344: public byte[] get(byte[] key) {
345: return (byte[]) dataEntries
346: .get(new ByteArrayObjectWrapper(key));
347: }
348:
349: public Collection getAll() {
350: Collection returnValue = new ArrayList();
351: Set entrySet = dataEntries.entrySet();
352: for (Iterator i = entrySet.iterator(); i.hasNext();) {
353: Map.Entry entry = (Map.Entry) i.next();
354: ByteArrayObjectWrapper key = (ByteArrayObjectWrapper) entry
355: .getKey();
356: TCByteArrayKeyValuePair keyValuePair = new TCByteArrayKeyValuePair(
357: key.value, (byte[]) entry.getValue());
358: returnValue.add(keyValuePair);
359: }
360: for (int i = 0; i < next.length; i++) {
361: if (next[i] != null) {
362: returnValue.addAll(next[i].getAll());
363: }
364: }
365: return returnValue;
366: }
367:
368: public byte[] remove(byte[] key) {
369: return (byte[]) dataEntries
370: .remove(new ByteArrayObjectWrapper(key));
371: }
372:
373: public int removeAll(byte[] key) {
374: int numOfRemove = getNumOfChilds();
375: dataEntries.clear();
376: for (int i = 0; i < next.length; i++) {
377: next[i] = null;
378: }
379: return numOfRemove;
380: }
381:
382: public void dumpTrie(int numOfSpaces) {
383: printSpace(numOfSpaces);
384: System.err.println("Size of data: "
385: + dataEntries.size());
386: Set keySet = dataEntries.keySet();
387: for (Iterator i = keySet.iterator(); i.hasNext();) {
388: Object key = i.next();
389: printSpace(numOfSpaces);
390: System.err.println("key: " + key);
391: }
392:
393: for (int i = 0; i < next.length; i++) {
394: if (next[i] != null) {
395: printSpace(numOfSpaces);
396: System.err.println("next[" + i + "]: "
397: + next[i]);
398: next[i].dumpTrie(numOfSpaces + 2);
399: }
400: }
401: }
402:
403: private int getNumOfChilds() {
404: int numOfChilds = 0;
405: for (int i = 0; i < next.length; i++) {
406: if (next[i] != null) {
407: numOfChilds += next[i].getNumOfChilds();
408: }
409: }
410: return dataEntries.size() + numOfChilds;
411: }
412:
413: private void printSpace(int numOfSpaces) {
414: for (int i = 0; i < numOfSpaces; i++) {
415: System.err.print(' ');
416: }
417: }
418: }
419:
420: }
421:
422: }
|