001: package org.jacorb.notification.util;
002:
003: /*
004: * JacORB - a free Java ORB
005: *
006: * Copyright (C) 1999-2004 Gerald Brose
007: *
008: * This library is free software; you can redistribute it and/or
009: * modify it under the terms of the GNU Library General Public
010: * License as published by the Free Software Foundation; either
011: * version 2 of the License, or (at your option) any later version.
012: *
013: * This library is distributed in the hope that it will be useful,
014: * but WITHOUT ANY WARRANTY; without even the implied warranty of
015: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
016: * Library General Public License for more details.
017: *
018: * You should have received a copy of the GNU Library General Public
019: * License along with this library; if not, write to the Free
020: * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
021: *
022: */
023:
024: import java.util.ArrayList;
025: import java.util.List;
026:
027: /**
028: * @author Alphonse Bendt
029: * @version $Id: DefaultWildcardMap.java,v 1.2 2005/08/21 13:38:40 alphonse.bendt Exp $
030: */
031:
032: public class DefaultWildcardMap implements WildcardMap {
033: public static final int DEFAULT_TOPLEVEL_SIZE = 4;
034:
035: private final EntryList topLevel_;
036:
037: ////////////////////////////////////////
038:
039: public DefaultWildcardMap(int topLevelSize) {
040: super ();
041:
042: topLevel_ = new EntryList(topLevelSize);
043: }
044:
045: public DefaultWildcardMap() {
046: this (DEFAULT_TOPLEVEL_SIZE);
047: }
048:
049: ////////////////////////////////////////
050:
051: public void clear() {
052: topLevel_.clear();
053: }
054:
055: public Object remove(Object key) {
056: char[] _key = key.toString().toCharArray();
057:
058: return topLevel_.remove(_key, 0, _key.length);
059: }
060:
061: public Object put(Object key, Object value) {
062: char[] _key = key.toString().toCharArray();
063:
064: return topLevel_.put(_key, 0, _key.length, value);
065: }
066:
067: public Object getNoExpansion(Object key) {
068: char[] _key = key.toString().toCharArray();
069:
070: return topLevel_.getSingle(_key, 0, _key.length);
071: }
072:
073: public Object[] getWithExpansion(Object key) {
074: char[] _key = key.toString().toCharArray();
075:
076: return topLevel_.getMultiple(_key, 0, _key.length);
077: }
078:
079: public String toString() {
080: return topLevel_.toString();
081: }
082: }
083:
084: /**
085: * the idea for this implementation is based on extensible hashing and trie's. an EntryList maps
086: * Strings to values. common prefixes of Strings are only stored once. <br>
087: * See section 4.1.10 and section 4.2.5 in my masters thesis available at
088: * http://www.jacorb.org/docs/DAbendt-web.pdf (in german) for a broader description of what has been
089: * implemented here.
090: */
091:
092: class EntryList {
093: private static final char WILDCARD_CHAR = '*';
094: private static final int DEFAULT_INITIAL_SIZE = 2;
095:
096: private PatternWrapper myPattern_;
097:
098: final char[] key_;
099:
100: private final int start_;
101:
102: int end_;
103:
104: private final int depth_;
105:
106: private int splitted = 0;
107:
108: private MapEntry myEntry_;
109:
110: private EntryList[] entries_;
111:
112: ////////////////////////////////////////
113: // Constructors
114:
115: EntryList(int size) {
116: this (null, 0, 0, 0, null, size);
117: }
118:
119: private EntryList(char[] key, int start, int end, int depth,
120: MapEntry value) {
121: this (key, start, end, depth, value, DEFAULT_INITIAL_SIZE);
122: }
123:
124: private EntryList(char[] key, int start, int end, int depth,
125: MapEntry entry, int size) {
126: myEntry_ = entry;
127: key_ = key;
128: end_ = end;
129: start_ = start;
130: depth_ = depth;
131: entries_ = new EntryList[size];
132: initPattern(key_, start_, end_);
133: }
134:
135: ////////////////////////////////////////
136:
137: /**
138: * check if this EntryList has an Entry associated
139: */
140: private boolean hasEntry() {
141: return myEntry_ != null;
142: }
143:
144: void clear() {
145: entries_ = new EntryList[DEFAULT_INITIAL_SIZE];
146: }
147:
148: Object put(char[] key, int start, int length, Object value) {
149: return put(new MapEntry(key, start, length, value));
150: }
151:
152: /**
153: * add an Entry to this List.
154: */
155: private Object put(MapEntry entry) {
156: char _first = entry.key_[0];
157:
158: ensureIndexIsAvailable(_first);
159:
160: int _idx = computeHashIndex(_first);
161:
162: if (entries_[_idx] == null) {
163: entries_[_idx] = new EntryList(entry.key_, 0,
164: entry.key_.length, 0, entry);
165: return null;
166: }
167:
168: return entries_[_idx].put(entry.key_, 0, entry.key_.length, 0,
169: entry, false);
170: }
171:
172: Object put(char[] key, int start, int stop, int depth,
173: MapEntry value, boolean addLeadingStar) {
174: int _insertKeyLength = stop - start;
175: int _myKeyLength = end_ - start_;
176:
177: int _prefixLength = findCommonPrefix(key, start, stop);
178:
179: if (_prefixLength == _insertKeyLength) {
180: if (endsWithStar()) {
181: splitEntryList(this , _prefixLength);
182: }
183:
184: Object _old = null;
185: // overwrite
186:
187: if (myEntry_ != null) {
188: _old = myEntry_.value_;
189: }
190:
191: myEntry_ = value;
192:
193: return _old;
194: } else if (_prefixLength < _myKeyLength) {
195: splitEntryList(this , _prefixLength);
196:
197: boolean _addStar = false;
198:
199: if (endsWithStar()) {
200: _addStar = true;
201: }
202:
203: put(key, start, stop, depth + _prefixLength, value,
204: _addStar);
205: } else
206: // (_prefixLength > _myKeyLength)
207: {
208: char _firstRemainingChar = key[start + _prefixLength];
209: ensureIndexIsAvailable(_firstRemainingChar);
210:
211: int idx = computeHashIndex(_firstRemainingChar);
212:
213: if (entries_[idx] == null) {
214: entries_[idx] = new EntryList(key, start
215: + _prefixLength, stop, depth_ + _prefixLength,
216: value);
217:
218: if (addLeadingStar) {
219: entries_[idx].addLeadingStar();
220: }
221: } else {
222: entries_[idx].put(key, start + _prefixLength, stop,
223: depth + _prefixLength, value, false);
224: }
225: }
226:
227: return null;
228: }
229:
230: Object getSingle(char[] key, int start, int stop) {
231: EntryList _entryList = lookup(key[start]);
232: int _position = start;
233:
234: while (_entryList != null) {
235: int _remainingKeyLength = stop - _position;
236:
237: int _devoured = _entryList.compare(key, start
238: + _entryList.depth_, start + _entryList.depth_
239: + _remainingKeyLength, false);
240:
241: if (_devoured == _remainingKeyLength) {
242: return _entryList.myEntry_.value_;
243: } else if (_devoured > 0) {
244: char _firstRemainingChar = key[start
245: + _entryList.depth_ + _devoured];
246: int _oldDepth = _entryList.depth_;
247:
248: _entryList = _entryList.lookup(_firstRemainingChar);
249:
250: if (_entryList != null) {
251: _position += _entryList.depth_ - _oldDepth;
252: }
253: }
254: }
255:
256: return null;
257: }
258:
259: /**
260: * check if the Key for this List ends with a star.
261: */
262: private boolean endsWithStar() {
263: return key_[end_ - 1] == WILDCARD_CHAR;
264: }
265:
266: /**
267: * lookup a key in this list. thereby perform Wildcard expansion.
268: */
269: Object[] getMultiple(char[] key, int start, int stop) {
270: final List _toBeProcessed = new ArrayList();
271:
272: final List _resultList = new ArrayList();
273:
274: Cursor _startCursor;
275:
276: // first try exact match
277:
278: EntryList _list = lookup(key[start]);
279:
280: if (_list != null) {
281: // add EntryList to nodes to be processed
282:
283: _toBeProcessed.add(new Cursor(start, _list));
284: }
285:
286: // next try '*'
287:
288: if ((_list = lookup(WILDCARD_CHAR)) != null) {
289: // add EntryList to nodes to be processed
290:
291: _startCursor = new Cursor(start, _list);
292:
293: _toBeProcessed.add(_startCursor);
294: }
295:
296: // process all found nodes
297:
298: while (!_toBeProcessed.isEmpty()) {
299: Cursor _currentCursor = (Cursor) _toBeProcessed.get(0);
300:
301: int _remainingKeyLength = stop - _currentCursor.cursor_;
302:
303: // try to match the search key to the part of key which is
304: // associated with the current node
305: int _devoured = _currentCursor.list_.compare(key, start
306: + _currentCursor.list_.depth_,
307: start + _currentCursor.list_.depth_
308: + _remainingKeyLength, true);
309:
310: if (_devoured >= _remainingKeyLength) {
311: // the whole key could be matched
312:
313: if (_currentCursor.list_.hasEntry()) {
314: // if the current node has a result add it to the
315: // result set.
316: _resultList
317: .add(_currentCursor.list_.myEntry_.value_);
318: }
319:
320: if ((_remainingKeyLength > 0)
321: && _currentCursor.list_.endsWithStar()) {
322: // current key ends with '*'
323: // this means the last compare matched everything
324: // nontheless there still might be outgoing edges
325: // which must be checked if we have some more chars in
326: // the key left.
327:
328: for (int x = 0; x < _currentCursor.list_.entries_.length; ++x) {
329: if (_currentCursor.list_.entries_[x] != null) {
330: _toBeProcessed.add(new Cursor(
331: _currentCursor.list_.depth_ + 1,
332: _currentCursor.list_.entries_[x]));
333: }
334: }
335: }
336:
337: if (_currentCursor.list_.lookup(WILDCARD_CHAR) != null) {
338: // if there is a outgoing '*' visit it
339: // because it might match the end of a key
340:
341: _currentCursor.list_ = _currentCursor.list_
342: .lookup(WILDCARD_CHAR);
343: _currentCursor.cursor_ += _devoured;
344: } else {
345: _toBeProcessed.remove(0);
346: }
347: } else if (_devoured > 0) {
348: // a part could be matched
349: char _firstRemainingChar = key[start
350: + _currentCursor.list_.depth_ + _devoured];
351:
352: int _oldDepth = _currentCursor.list_.depth_;
353:
354: // '*' always matches
355:
356: if (_currentCursor.list_.lookup(WILDCARD_CHAR) != null) {
357: EntryList _entryList = _currentCursor.list_
358: .lookup(WILDCARD_CHAR);
359:
360: _toBeProcessed.add(new Cursor(
361: _currentCursor.cursor_ + _entryList.depth_
362: - _oldDepth, _entryList));
363: }
364:
365: if ((_currentCursor.list_ = _currentCursor.list_
366: .lookup(_firstRemainingChar)) != null) {
367: // instead of removing the old and adding a new
368: // cursor we reuse the old cursor
369: _currentCursor.cursor_ += _currentCursor.list_.depth_
370: - _oldDepth;
371: } else {
372: _toBeProcessed.remove(0);
373: }
374: } else {
375: // no part of the search key could be matched
376: _toBeProcessed.remove(0);
377: }
378: }
379:
380: return _resultList.toArray();
381: }
382:
383: Object remove(char[] key, int start, int stop) {
384: return remove(this , key, start, stop);
385: }
386:
387: private static Object remove(EntryList l, char[] key, int start,
388: int stop) {
389: int _cursor = start;
390: EntryList _current = l;
391:
392: while (true) {
393: int _devoured = findCommonPrefix(key, _cursor, stop,
394: _current.key_, _current.start_, _current.end_);
395:
396: _cursor += _devoured;
397:
398: if (_cursor == stop) {
399: Object _old = null;
400:
401: if (_current.myEntry_ != null) {
402: _old = _current.myEntry_.value_;
403: _current.myEntry_ = null;
404: }
405:
406: return _old;
407: }
408:
409: char _firstNext = key[start + _devoured];
410: _current = _current.lookup(_firstNext);
411:
412: if (_current == null) {
413: return null;
414: }
415: }
416: }
417:
418: ////////////////////////////////////////
419: // private methods
420:
421: private static class Cursor {
422: int cursor_;
423:
424: EntryList list_;
425:
426: Cursor(int cursor, EntryList list) {
427: cursor_ = cursor;
428: list_ = list;
429: }
430:
431: public String toString() {
432: String _rest = new String(list_.key_, cursor_, list_.end_
433: - cursor_);
434:
435: return "Cursor: " + _rest;
436: }
437: }
438:
439: private void addLeadingStar() {
440: int _newLength = end_ - start_ + 1;
441:
442: char[] _newKey = new char[_newLength];
443: System.arraycopy(key_, start_, _newKey, 1, end_ - start_);
444: _newKey[0] = WILDCARD_CHAR;
445:
446: initPattern(_newKey, 0, _newLength);
447: }
448:
449: private void initPattern() {
450: initPattern(key_, start_, end_);
451: }
452:
453: private void initPattern(char[] key, int start, int stop) {
454: myPattern_ = null;
455:
456: int _starCount = countStarsInKey(key, start, stop);
457:
458: if (_starCount > 0) {
459: char[] _pattern = new char[stop - start + _starCount + 1];
460: _pattern[0] = '^'; // regexp to match begin of line
461: int x = 0;
462: int _offset = 1;
463:
464: while (x < (stop - start)) {
465: char _x = key[start + x];
466: _pattern[x + _offset] = _x;
467:
468: // replace '*' with '.*'
469: if (_pattern[x + _offset] == WILDCARD_CHAR) {
470: _pattern[x + _offset] = '.';
471: _pattern[x + _offset + 1] = WILDCARD_CHAR;
472: ++_offset;
473: }
474:
475: ++x;
476: }
477:
478: String _patternString = new String(_pattern, 0, stop
479: - start + _starCount + 1);
480: myPattern_ = PatternWrapper.init(_patternString);
481: }
482: }
483:
484: private char key() {
485: return key_[start_];
486: }
487:
488: private EntryList lookup(char key) {
489: int idx = computeHashIndex(key);
490:
491: if (entries_[idx] != null && entries_[idx].key() == key) {
492: return entries_[idx];
493: }
494:
495: return null;
496: }
497:
498: /**
499: * ensure that the index returned by computeHashIndex for a specified key is available. That
500: * means
501: * <ol>
502: * <li>The Index is empty
503: * <li>The Index contains an EntryList with the same Key as the specified one
504: * </ol>
505: */
506: private void ensureIndexIsAvailable(char key) {
507: int idx = computeHashIndex(key);
508:
509: while (true) {
510: // assert (idx < entries_.length);
511:
512: if (entries_[idx] == null || entries_[idx].key() == key) {
513: return;
514: }
515:
516: doubleCapacity();
517:
518: idx = computeHashIndex(key);
519: }
520: }
521:
522: /**
523: * double the capacity for our entries. copy entries from old list into the new one.
524: */
525: private void doubleCapacity() {
526: int _newSize = entries_.length * 2;
527:
528: EntryList[] _newList = new EntryList[_newSize];
529:
530: for (int x = 0; x < entries_.length; ++x) {
531: if (entries_[x] != null) {
532: int _arrayPos = computeHashIndex(entries_[x].key(),
533: _newSize);
534: _newList[_arrayPos] = entries_[x];
535: }
536: }
537:
538: entries_ = _newList;
539: }
540:
541: private int compare(char[] a, int start, int stop, boolean wildcard) {
542: if (wildcard && myPattern_ != null) {
543: return compareKeyToPattern(a, start, stop, myPattern_);
544: }
545:
546: return compareKeyToKey(a, start, stop, key_, start_, end_);
547: }
548:
549: private int findCommonPrefix(char[] key, int start, int stop) {
550: return findCommonPrefix(key, start, stop, key_, start_, end_);
551: }
552:
553: private void printToStringBuffer(StringBuffer sb, String offset) {
554: if (key_ != null) {
555: sb.append(" --");
556: sb.append(key());
557: sb.append("-->\n");
558: sb.append(offset);
559: sb.append("depth: ");
560: sb.append(depth_);
561: sb.append("\n");
562: sb.append(offset);
563: sb.append("key: ");
564: sb.append(new String(key_, start_, end_ - start_));
565: sb.append("\n");
566: }
567:
568: if (myEntry_ != null) {
569: sb.append(offset + myEntry_);
570: sb.append("\n");
571: }
572:
573: for (int x = 0; x < entries_.length; x++) {
574: sb.append(offset + x);
575: sb.append(":");
576:
577: if (entries_[x] == null) {
578: sb.append("empty");
579: } else {
580: entries_[x].printToStringBuffer(sb, offset + " ");
581: }
582:
583: sb.append("\n");
584: }
585: }
586:
587: public String toString() {
588: StringBuffer _b = new StringBuffer();
589: printToStringBuffer(_b, "");
590: return _b.toString();
591: }
592:
593: ////////////////////////////////////////
594: // static methods
595:
596: private static void splitEntryList(EntryList list, int offset) {
597: EntryList _ret = new EntryList(list.key_, list.start_ + offset,
598: list.end_, list.depth_ + offset, list.myEntry_,
599: list.entries_.length);
600:
601: System.arraycopy(list.entries_, 0, _ret.entries_, 0,
602: list.entries_.length);
603:
604: list.entries_ = new EntryList[DEFAULT_INITIAL_SIZE];
605:
606: char _key = list.key_[list.start_ + offset];
607:
608: int _idx = computeHashIndex(_key, list.entries_.length);
609:
610: list.entries_[_idx] = _ret;
611: list.myEntry_ = null;
612: list.splitted++;
613: list.end_ = list.start_ + offset;
614:
615: if (list.endsWithStar()) {
616: _ret.addLeadingStar();
617: }
618:
619: list.initPattern();
620: }
621:
622: private static int computeHashIndex(char c, int size) {
623: return c % size;
624: }
625:
626: private int computeHashIndex(char c) {
627: return computeHashIndex(c, entries_.length);
628: }
629:
630: static int compareKeyToKey(char[] firstKeyArray, int start1,
631: int stop1, char[] secondKeyArray, int start2, int stop2) {
632: int length1 = stop1 - start1;
633: int length2 = stop2 - start2;
634: int _guard = (length1 > length2) ? length2 : length1;
635:
636: int _ret = 0;
637:
638: while (_ret < _guard) {
639: if (firstKeyArray[start1 + _ret] != secondKeyArray[start2
640: + _ret]) {
641: return _ret;
642: }
643:
644: ++_ret;
645: }
646:
647: return _ret;
648: }
649:
650: private static int compareKeyToPattern(char[] string1, int start1,
651: int stop1, PatternWrapper p) {
652: String _other = new String(string1, start1, stop1 - start1);
653:
654: return p.match(_other);
655: }
656:
657: private static int findCommonPrefix(char[] key1, int start1,
658: int stop1, char[] key2, int start2, int stop2) {
659: int _x = 0;
660: int _length1 = stop1 - start1;
661: int _length2 = stop2 - start2;
662:
663: int _guard = (_length1 >= _length2) ? _length2 : _length1;
664:
665: while ((_x < _guard) && (key1[start1] == key2[start2])) {
666: ++start1;
667: ++start2;
668: ++_x;
669: }
670:
671: return _x;
672: }
673:
674: static int countStarsInKey(char[] key, int start, int end) {
675: int _starCount = 0;
676: int x = start;
677:
678: while (x < end) {
679: if (key[x] == WILDCARD_CHAR) {
680: ++_starCount;
681: }
682:
683: ++x;
684: }
685: return _starCount;
686: }
687:
688: /**
689: * This Class represents a Entry within a WildcardMap. Each Entry is identified by a key and has
690: * a value associated.
691: */
692: private static class MapEntry {
693: /**
694: * start index of key within key_ array
695: */
696: private final int start_;
697:
698: /**
699: * stop index of key within key_ array
700: */
701: private final int stop_;
702:
703: /**
704: * this array contains the key. start and stop index of the key are denoted by start_ and
705: * stop_
706: */
707: final char[] key_;
708:
709: /**
710: * value associated to this Entry
711: */
712: final Object value_;
713:
714: ////////////////////////////////////////
715:
716: /**
717: * Creates a new <code>WCEntry</code> instance.
718: *
719: * @param key
720: * a <code>char[]</code> value
721: * @param start
722: * an <code>int</code> value
723: * @param stop
724: * an <code>int</code> value
725: * @param value
726: * an <code>Object</code> value
727: */
728: MapEntry(char[] key, int start, int stop, Object value) {
729: key_ = key;
730: start_ = start;
731: stop_ = stop;
732: value_ = value;
733: }
734:
735: ////////////////////////////////////////
736:
737: public int hashCode() {
738: return key_[start_];
739:
740: }
741:
742: public boolean equals(Object o) {
743: try {
744: MapEntry _other = (MapEntry) o;
745:
746: return (EntryList.compareKeyToKey(key_, start_, stop_,
747: _other.key_, _other.start_, _other.stop_) > 0);
748: } catch (ClassCastException e) {
749: return super .equals(o);
750: } catch (NullPointerException e) {
751: return false;
752: }
753: }
754:
755: public String toString() {
756: StringBuffer _b = new StringBuffer();
757:
758: _b.append("['");
759: _b.append(new String(key_, start_, stop_ - start_));
760: _b.append("' => ");
761: _b.append(value_);
762: _b.append("]");
763:
764: return _b.toString();
765: }
766: }
767: }
|