1:
6:
7: package ;
8: import ;
9: import ;
10:
11:
63: public class ConcurrentSkipListMap<K,V> extends AbstractMap<K,V>
64: implements ConcurrentNavigableMap<K,V>,
65: Cloneable,
66: java.io.Serializable {
67:
292:
293: private static final long serialVersionUID = -8627078645895051609L;
294:
295:
299: private static final Random seedGenerator = new Random();
300:
301:
304: private static final Object BASE_HEADER = new Object();
305:
306:
309: private transient volatile HeadIndex<K,V> head;
310:
311:
316: private final Comparator<? super K> comparator;
317:
318:
322: private transient int randomSeed;
323:
324:
325: private transient KeySet keySet;
326:
327: private transient EntrySet entrySet;
328:
329: private transient Values values;
330:
331: private transient ConcurrentNavigableMap<K,V> descendingMap;
332:
333:
338: final void initialize() {
339: keySet = null;
340: entrySet = null;
341: values = null;
342: descendingMap = null;
343: randomSeed = seedGenerator.nextInt() | 0x0100;
344: head = new HeadIndex<K,V>(new Node<K,V>(null, BASE_HEADER, null),
345: null, null, 1);
346: }
347:
348:
349: private static final
350: AtomicReferenceFieldUpdater<ConcurrentSkipListMap, HeadIndex>
351: headUpdater = AtomicReferenceFieldUpdater.newUpdater
352: (ConcurrentSkipListMap.class, HeadIndex.class, "head");
353:
354:
357: private boolean casHead(HeadIndex<K,V> cmp, HeadIndex<K,V> val) {
358: return headUpdater.compareAndSet(this, cmp, val);
359: }
360:
361:
362:
363:
370: static final class Node<K,V> {
371: final K key;
372: volatile Object value;
373: volatile Node<K,V> next;
374:
375:
378: Node(K key, Object value, Node<K,V> next) {
379: this.key = key;
380: this.value = value;
381: this.next = next;
382: }
383:
384:
391: Node(Node<K,V> next) {
392: this.key = null;
393: this.value = this;
394: this.next = next;
395: }
396:
397:
398: static final AtomicReferenceFieldUpdater<Node, Node>
399: nextUpdater = AtomicReferenceFieldUpdater.newUpdater
400: (Node.class, Node.class, "next");
401:
402:
403: static final AtomicReferenceFieldUpdater<Node, Object>
404: valueUpdater = AtomicReferenceFieldUpdater.newUpdater
405: (Node.class, Object.class, "value");
406:
407:
410: boolean casValue(Object cmp, Object val) {
411: return valueUpdater.compareAndSet(this, cmp, val);
412: }
413:
414:
417: boolean casNext(Node<K,V> cmp, Node<K,V> val) {
418: return nextUpdater.compareAndSet(this, cmp, val);
419: }
420:
421:
430: boolean isMarker() {
431: return value == this;
432: }
433:
434:
438: boolean isBaseHeader() {
439: return value == BASE_HEADER;
440: }
441:
442:
447: boolean appendMarker(Node<K,V> f) {
448: return casNext(f, new Node<K,V>(f));
449: }
450:
451:
458: void helpDelete(Node<K,V> b, Node<K,V> f) {
459:
464: if (f == next && this == b.next) {
465: if (f == null || f.value != f)
466: appendMarker(f);
467: else
468: b.casNext(this, f.next);
469: }
470: }
471:
472:
478: V getValidValue() {
479: Object v = value;
480: if (v == this || v == BASE_HEADER)
481: return null;
482: return (V)v;
483: }
484:
485:
490: AbstractMap.SimpleImmutableEntry<K,V> createSnapshot() {
491: V v = getValidValue();
492: if (v == null)
493: return null;
494: return new AbstractMap.SimpleImmutableEntry<K,V>(key, v);
495: }
496: }
497:
498:
499:
500:
507: static class Index<K,V> {
508: final Node<K,V> node;
509: final Index<K,V> down;
510: volatile Index<K,V> right;
511:
512:
515: Index(Node<K,V> node, Index<K,V> down, Index<K,V> right) {
516: this.node = node;
517: this.down = down;
518: this.right = right;
519: }
520:
521:
522: static final AtomicReferenceFieldUpdater<Index, Index>
523: rightUpdater = AtomicReferenceFieldUpdater.newUpdater
524: (Index.class, Index.class, "right");
525:
526:
529: final boolean casRight(Index<K,V> cmp, Index<K,V> val) {
530: return rightUpdater.compareAndSet(this, cmp, val);
531: }
532:
533:
537: final boolean indexesDeletedNode() {
538: return node.value == null;
539: }
540:
541:
549: final boolean link(Index<K,V> succ, Index<K,V> newSucc) {
550: Node<K,V> n = node;
551: newSucc.right = succ;
552: return n.value != null && casRight(succ, newSucc);
553: }
554:
555:
562: final boolean unlink(Index<K,V> succ) {
563: return !indexesDeletedNode() && casRight(succ, succ.right);
564: }
565: }
566:
567:
568:
569:
572: static final class HeadIndex<K,V> extends Index<K,V> {
573: final int level;
574: HeadIndex(Node<K,V> node, Index<K,V> down, Index<K,V> right, int level) {
575: super(node, down, right);
576: this.level = level;
577: }
578: }
579:
580:
581:
582:
597: static final class ComparableUsingComparator<K> implements Comparable<K> {
598: final K actualKey;
599: final Comparator<? super K> cmp;
600: ComparableUsingComparator(K key, Comparator<? super K> cmp) {
601: this.actualKey = key;
602: this.cmp = cmp;
603: }
604: public int compareTo(K k2) {
605: return cmp.compare(actualKey, k2);
606: }
607: }
608:
609:
614: private Comparable<? super K> comparable(Object key) throws ClassCastException {
615: if (key == null)
616: throw new NullPointerException();
617: if (comparator != null)
618: return new ComparableUsingComparator<K>((K)key, comparator);
619: else
620: return (Comparable<? super K>)key;
621: }
622:
623:
627: int compare(K k1, K k2) throws ClassCastException {
628: Comparator<? super K> cmp = comparator;
629: if (cmp != null)
630: return cmp.compare(k1, k2);
631: else
632: return ((Comparable<? super K>)k1).compareTo(k2);
633: }
634:
635:
640: boolean inHalfOpenRange(K key, K least, K fence) {
641: if (key == null)
642: throw new NullPointerException();
643: return ((least == null || compare(key, least) >= 0) &&
644: (fence == null || compare(key, fence) < 0));
645: }
646:
647:
651: boolean inOpenRange(K key, K least, K fence) {
652: if (key == null)
653: throw new NullPointerException();
654: return ((least == null || compare(key, least) >= 0) &&
655: (fence == null || compare(key, fence) <= 0));
656: }
657:
658:
659:
660:
668: private Node<K,V> findPredecessor(Comparable<? super K> key) {
669: if (key == null)
670: throw new NullPointerException();
671: for (;;) {
672: Index<K,V> q = head;
673: Index<K,V> r = q.right;
674: for (;;) {
675: if (r != null) {
676: Node<K,V> n = r.node;
677: K k = n.key;
678: if (n.value == null) {
679: if (!q.unlink(r))
680: break;
681: r = q.right;
682: continue;
683: }
684: if (key.compareTo(k) > 0) {
685: q = r;
686: r = r.right;
687: continue;
688: }
689: }
690: Index<K,V> d = q.down;
691: if (d != null) {
692: q = d;
693: r = d.right;
694: } else
695: return q.node;
696: }
697: }
698: }
699:
700:
744: private Node<K,V> findNode(Comparable<? super K> key) {
745: for (;;) {
746: Node<K,V> b = findPredecessor(key);
747: Node<K,V> n = b.next;
748: for (;;) {
749: if (n == null)
750: return null;
751: Node<K,V> f = n.next;
752: if (n != b.next)
753: break;
754: Object v = n.value;
755: if (v == null) {
756: n.helpDelete(b, f);
757: break;
758: }
759: if (v == n || b.value == null)
760: break;
761: int c = key.compareTo(n.key);
762: if (c == 0)
763: return n;
764: if (c < 0)
765: return null;
766: b = n;
767: n = f;
768: }
769: }
770: }
771:
772:
784: private V doGet(Object okey) {
785: Comparable<? super K> key = comparable(okey);
786: Node<K,V> bound = null;
787: Index<K,V> q = head;
788: Index<K,V> r = q.right;
789: Node<K,V> n;
790: K k;
791: int c;
792: for (;;) {
793: Index<K,V> d;
794:
795: if (r != null && (n = r.node) != bound && (k = n.key) != null) {
796: if ((c = key.compareTo(k)) > 0) {
797: q = r;
798: r = r.right;
799: continue;
800: } else if (c == 0) {
801: Object v = n.value;
802: return (v != null)? (V)v : getUsingFindNode(key);
803: } else
804: bound = n;
805: }
806:
807:
808: if ((d = q.down) != null) {
809: q = d;
810: r = d.right;
811: } else
812: break;
813: }
814:
815:
816: for (n = q.node.next; n != null; n = n.next) {
817: if ((k = n.key) != null) {
818: if ((c = key.compareTo(k)) == 0) {
819: Object v = n.value;
820: return (v != null)? (V)v : getUsingFindNode(key);
821: } else if (c < 0)
822: break;
823: }
824: }
825: return null;
826: }
827:
828:
834: private V getUsingFindNode(Comparable<? super K> key) {
835:
840: for (;;) {
841: Node<K,V> n = findNode(key);
842: if (n == null)
843: return null;
844: Object v = n.value;
845: if (v != null)
846: return (V)v;
847: }
848: }
849:
850:
851:
852:
860: private V doPut(K kkey, V value, boolean onlyIfAbsent) {
861: Comparable<? super K> key = comparable(kkey);
862: for (;;) {
863: Node<K,V> b = findPredecessor(key);
864: Node<K,V> n = b.next;
865: for (;;) {
866: if (n != null) {
867: Node<K,V> f = n.next;
868: if (n != b.next)
869: break;
870: Object v = n.value;
871: if (v == null) {
872: n.helpDelete(b, f);
873: break;
874: }
875: if (v == n || b.value == null)
876: break;
877: int c = key.compareTo(n.key);
878: if (c > 0) {
879: b = n;
880: n = f;
881: continue;
882: }
883: if (c == 0) {
884: if (onlyIfAbsent || n.casValue(v, value))
885: return (V)v;
886: else
887: break;
888: }
889:
890: }
891:
892: Node<K,V> z = new Node<K,V>(kkey, value, n);
893: if (!b.casNext(n, z))
894: break;
895: int level = randomLevel();
896: if (level > 0)
897: insertIndex(z, level);
898: return null;
899: }
900: }
901: }
902:
903:
912: private int randomLevel() {
913: int x = randomSeed;
914: x ^= x << 13;
915: x ^= x >>> 17;
916: randomSeed = x ^= x << 5;
917: if ((x & 0x8001) != 0)
918: return 0;
919: int level = 1;
920: while (((x >>>= 1) & 1) != 0) ++level;
921: return level;
922: }
923:
924:
929: private void insertIndex(Node<K,V> z, int level) {
930: HeadIndex<K,V> h = head;
931: int max = h.level;
932:
933: if (level <= max) {
934: Index<K,V> idx = null;
935: for (int i = 1; i <= level; ++i)
936: idx = new Index<K,V>(z, idx, null);
937: addIndex(idx, h, level);
938:
939: } else {
940:
948: level = max + 1;
949: Index<K,V>[] idxs = (Index<K,V>[])new Index[level+1];
950: Index<K,V> idx = null;
951: for (int i = 1; i <= level; ++i)
952: idxs[i] = idx = new Index<K,V>(z, idx, null);
953:
954: HeadIndex<K,V> oldh;
955: int k;
956: for (;;) {
957: oldh = head;
958: int oldLevel = oldh.level;
959: if (level <= oldLevel) {
960: k = level;
961: break;
962: }
963: HeadIndex<K,V> newh = oldh;
964: Node<K,V> oldbase = oldh.node;
965: for (int j = oldLevel+1; j <= level; ++j)
966: newh = new HeadIndex<K,V>(oldbase, newh, idxs[j], j);
967: if (casHead(oldh, newh)) {
968: k = oldLevel;
969: break;
970: }
971: }
972: addIndex(idxs[k], oldh, k);
973: }
974: }
975:
976:
983: private void addIndex(Index<K,V> idx, HeadIndex<K,V> h, int indexLevel) {
984:
985: int insertionLevel = indexLevel;
986: Comparable<? super K> key = comparable(idx.node.key);
987: if (key == null) throw new NullPointerException();
988:
989:
990:
991: for (;;) {
992: int j = h.level;
993: Index<K,V> q = h;
994: Index<K,V> r = q.right;
995: Index<K,V> t = idx;
996: for (;;) {
997: if (r != null) {
998: Node<K,V> n = r.node;
999:
1000: int c = key.compareTo(n.key);
1001: if (n.value == null) {
1002: if (!q.unlink(r))
1003: break;
1004: r = q.right;
1005: continue;
1006: }
1007: if (c > 0) {
1008: q = r;
1009: r = r.right;
1010: continue;
1011: }
1012: }
1013:
1014: if (j == insertionLevel) {
1015:
1016: if (t.indexesDeletedNode()) {
1017: findNode(key);
1018: return;
1019: }
1020: if (!q.link(r, t))
1021: break;
1022: if (--insertionLevel == 0) {
1023:
1024: if (t.indexesDeletedNode())
1025: findNode(key);
1026: return;
1027: }
1028: }
1029:
1030: if (--j >= insertionLevel && j < indexLevel)
1031: t = t.down;
1032: q = q.down;
1033: r = q.right;
1034: }
1035: }
1036: }
1037:
1038:
1039:
1040:
1059: final V doRemove(Object okey, Object value) {
1060: Comparable<? super K> key = comparable(okey);
1061: for (;;) {
1062: Node<K,V> b = findPredecessor(key);
1063: Node<K,V> n = b.next;
1064: for (;;) {
1065: if (n == null)
1066: return null;
1067: Node<K,V> f = n.next;
1068: if (n != b.next)
1069: break;
1070: Object v = n.value;
1071: if (v == null) {
1072: n.helpDelete(b, f);
1073: break;
1074: }
1075: if (v == n || b.value == null)
1076: break;
1077: int c = key.compareTo(n.key);
1078: if (c < 0)
1079: return null;
1080: if (c > 0) {
1081: b = n;
1082: n = f;
1083: continue;
1084: }
1085: if (value != null && !value.equals(v))
1086: return null;
1087: if (!n.casValue(v, null))
1088: break;
1089: if (!n.appendMarker(f) || !b.casNext(n, f))
1090: findNode(key);
1091: else {
1092: findPredecessor(key);
1093: if (head.right == null)
1094: tryReduceLevel();
1095: }
1096: return (V)v;
1097: }
1098: }
1099: }
1100:
1101:
1121: private void tryReduceLevel() {
1122: HeadIndex<K,V> h = head;
1123: HeadIndex<K,V> d;
1124: HeadIndex<K,V> e;
1125: if (h.level > 3 &&
1126: (d = (HeadIndex<K,V>)h.down) != null &&
1127: (e = (HeadIndex<K,V>)d.down) != null &&
1128: e.right == null &&
1129: d.right == null &&
1130: h.right == null &&
1131: casHead(h, d) &&
1132: h.right != null)
1133: casHead(d, h);
1134: }
1135:
1136:
1137:
1138:
1142: Node<K,V> findFirst() {
1143: for (;;) {
1144: Node<K,V> b = head.node;
1145: Node<K,V> n = b.next;
1146: if (n == null)
1147: return null;
1148: if (n.value != null)
1149: return n;
1150: n.helpDelete(b, n.next);
1151: }
1152: }
1153:
1154:
1158: Map.Entry<K,V> doRemoveFirstEntry() {
1159: for (;;) {
1160: Node<K,V> b = head.node;
1161: Node<K,V> n = b.next;
1162: if (n == null)
1163: return null;
1164: Node<K,V> f = n.next;
1165: if (n != b.next)
1166: continue;
1167: Object v = n.value;
1168: if (v == null) {
1169: n.helpDelete(b, f);
1170: continue;
1171: }
1172: if (!n.casValue(v, null))
1173: continue;
1174: if (!n.appendMarker(f) || !b.casNext(n, f))
1175: findFirst();
1176: clearIndexToFirst();
1177: return new AbstractMap.SimpleImmutableEntry<K,V>(n.key, (V)v);
1178: }
1179: }
1180:
1181:
1184: private void clearIndexToFirst() {
1185: for (;;) {
1186: Index<K,V> q = head;
1187: for (;;) {
1188: Index<K,V> r = q.right;
1189: if (r != null && r.indexesDeletedNode() && !q.unlink(r))
1190: break;
1191: if ((q = q.down) == null) {
1192: if (head.right == null)
1193: tryReduceLevel();
1194: return;
1195: }
1196: }
1197: }
1198: }
1199:
1200:
1201:
1202:
1203:
1207: Node<K,V> findLast() {
1208:
1213: Index<K,V> q = head;
1214: for (;;) {
1215: Index<K,V> d, r;
1216: if ((r = q.right) != null) {
1217: if (r.indexesDeletedNode()) {
1218: q.unlink(r);
1219: q = head;
1220: }
1221: else
1222: q = r;
1223: } else if ((d = q.down) != null) {
1224: q = d;
1225: } else {
1226: Node<K,V> b = q.node;
1227: Node<K,V> n = b.next;
1228: for (;;) {
1229: if (n == null)
1230: return (b.isBaseHeader())? null : b;
1231: Node<K,V> f = n.next;
1232: if (n != b.next)
1233: break;
1234: Object v = n.value;
1235: if (v == null) {
1236: n.helpDelete(b, f);
1237: break;
1238: }
1239: if (v == n || b.value == null)
1240: break;
1241: b = n;
1242: n = f;
1243: }
1244: q = head;
1245: }
1246: }
1247: }
1248:
1249:
1256: private Node<K,V> findPredecessorOfLast() {
1257: for (;;) {
1258: Index<K,V> q = head;
1259: for (;;) {
1260: Index<K,V> d, r;
1261: if ((r = q.right) != null) {
1262: if (r.indexesDeletedNode()) {
1263: q.unlink(r);
1264: break;
1265: }
1266:
1267: if (r.node.next != null) {
1268: q = r;
1269: continue;
1270: }
1271: }
1272: if ((d = q.down) != null)
1273: q = d;
1274: else
1275: return q.node;
1276: }
1277: }
1278: }
1279:
1280:
1285: Map.Entry<K,V> doRemoveLastEntry() {
1286: for (;;) {
1287: Node<K,V> b = findPredecessorOfLast();
1288: Node<K,V> n = b.next;
1289: if (n == null) {
1290: if (b.isBaseHeader())
1291: return null;
1292: else
1293: continue;
1294: }
1295: for (;;) {
1296: Node<K,V> f = n.next;
1297: if (n != b.next)
1298: break;
1299: Object v = n.value;
1300: if (v == null) {
1301: n.helpDelete(b, f);
1302: break;
1303: }
1304: if (v == n || b.value == null)
1305: break;
1306: if (f != null) {
1307: b = n;
1308: n = f;
1309: continue;
1310: }
1311: if (!n.casValue(v, null))
1312: break;
1313: K key = n.key;
1314: Comparable<? super K> ck = comparable(key);
1315: if (!n.appendMarker(f) || !b.casNext(n, f))
1316: findNode(ck);
1317: else {
1318: findPredecessor(ck);
1319: if (head.right == null)
1320: tryReduceLevel();
1321: }
1322: return new AbstractMap.SimpleImmutableEntry<K,V>(key, (V)v);
1323: }
1324: }
1325: }
1326:
1327:
1328:
1329:
1330:
1331: private static final int EQ = 1;
1332: private static final int LT = 2;
1333: private static final int GT = 0;
1334:
1335:
1341: Node<K,V> findNear(K kkey, int rel) {
1342: Comparable<? super K> key = comparable(kkey);
1343: for (;;) {
1344: Node<K,V> b = findPredecessor(key);
1345: Node<K,V> n = b.next;
1346: for (;;) {
1347: if (n == null)
1348: return ((rel & LT) == 0 || b.isBaseHeader())? null : b;
1349: Node<K,V> f = n.next;
1350: if (n != b.next)
1351: break;
1352: Object v = n.value;
1353: if (v == null) {
1354: n.helpDelete(b, f);
1355: break;
1356: }
1357: if (v == n || b.value == null)
1358: break;
1359: int c = key.compareTo(n.key);
1360: if ((c == 0 && (rel & EQ) != 0) ||
1361: (c < 0 && (rel & LT) == 0))
1362: return n;
1363: if ( c <= 0 && (rel & LT) != 0)
1364: return (b.isBaseHeader())? null : b;
1365: b = n;
1366: n = f;
1367: }
1368: }
1369: }
1370:
1371:
1377: AbstractMap.SimpleImmutableEntry<K,V> getNear(K key, int rel) {
1378: for (;;) {
1379: Node<K,V> n = findNear(key, rel);
1380: if (n == null)
1381: return null;
1382: AbstractMap.SimpleImmutableEntry<K,V> e = n.createSnapshot();
1383: if (e != null)
1384: return e;
1385: }
1386: }
1387:
1388:
1389:
1390:
1391:
1395: public ConcurrentSkipListMap() {
1396: this.comparator = null;
1397: initialize();
1398: }
1399:
1400:
1408: public ConcurrentSkipListMap(Comparator<? super K> comparator) {
1409: this.comparator = comparator;
1410: initialize();
1411: }
1412:
1413:
1424: public ConcurrentSkipListMap(Map<? extends K, ? extends V> m) {
1425: this.comparator = null;
1426: initialize();
1427: putAll(m);
1428: }
1429:
1430:
1439: public ConcurrentSkipListMap(SortedMap<K, ? extends V> m) {
1440: this.comparator = m.comparator();
1441: initialize();
1442: buildFromSorted(m);
1443: }
1444:
1445:
1451: public ConcurrentSkipListMap<K,V> clone() {
1452: ConcurrentSkipListMap<K,V> clone = null;
1453: try {
1454: clone = (ConcurrentSkipListMap<K,V>) super.clone();
1455: } catch (CloneNotSupportedException e) {
1456: throw new InternalError();
1457: }
1458:
1459: clone.initialize();
1460: clone.buildFromSorted(this);
1461: return clone;
1462: }
1463:
1464:
1469: private void buildFromSorted(SortedMap<K, ? extends V> map) {
1470: if (map == null)
1471: throw new NullPointerException();
1472:
1473: HeadIndex<K,V> h = head;
1474: Node<K,V> basepred = h.node;
1475:
1476:
1477:
1478: ArrayList<Index<K,V>> preds = new ArrayList<Index<K,V>>();
1479:
1480:
1481: for (int i = 0; i <= h.level; ++i)
1482: preds.add(null);
1483: Index<K,V> q = h;
1484: for (int i = h.level; i > 0; --i) {
1485: preds.set(i, q);
1486: q = q.down;
1487: }
1488:
1489: Iterator<? extends Map.Entry<? extends K, ? extends V>> it =
1490: map.entrySet().iterator();
1491: while (it.hasNext()) {
1492: Map.Entry<? extends K, ? extends V> e = it.next();
1493: int j = randomLevel();
1494: if (j > h.level) j = h.level + 1;
1495: K k = e.getKey();
1496: V v = e.getValue();
1497: if (k == null || v == null)
1498: throw new NullPointerException();
1499: Node<K,V> z = new Node<K,V>(k, v, null);
1500: basepred.next = z;
1501: basepred = z;
1502: if (j > 0) {
1503: Index<K,V> idx = null;
1504: for (int i = 1; i <= j; ++i) {
1505: idx = new Index<K,V>(z, idx, null);
1506: if (i > h.level)
1507: h = new HeadIndex<K,V>(h.node, h, idx, i);
1508:
1509: if (i < preds.size()) {
1510: preds.get(i).right = idx;
1511: preds.set(i, idx);
1512: } else
1513: preds.add(idx);
1514: }
1515: }
1516: }
1517: head = h;
1518: }
1519:
1520:
1521:
1522:
1531: private void writeObject(java.io.ObjectOutputStream s)
1532: throws java.io.IOException {
1533:
1534: s.defaultWriteObject();
1535:
1536:
1537: for (Node<K,V> n = findFirst(); n != null; n = n.next) {
1538: V v = n.getValidValue();
1539: if (v != null) {
1540: s.writeObject(n.key);
1541: s.writeObject(v);
1542: }
1543: }
1544: s.writeObject(null);
1545: }
1546:
1547:
1550: private void readObject(final java.io.ObjectInputStream s)
1551: throws java.io.IOException, ClassNotFoundException {
1552:
1553: s.defaultReadObject();
1554:
1555: initialize();
1556:
1557:
1564:
1565: HeadIndex<K,V> h = head;
1566: Node<K,V> basepred = h.node;
1567: ArrayList<Index<K,V>> preds = new ArrayList<Index<K,V>>();
1568: for (int i = 0; i <= h.level; ++i)
1569: preds.add(null);
1570: Index<K,V> q = h;
1571: for (int i = h.level; i > 0; --i) {
1572: preds.set(i, q);
1573: q = q.down;
1574: }
1575:
1576: for (;;) {
1577: Object k = s.readObject();
1578: if (k == null)
1579: break;
1580: Object v = s.readObject();
1581: if (v == null)
1582: throw new NullPointerException();
1583: K key = (K) k;
1584: V val = (V) v;
1585: int j = randomLevel();
1586: if (j > h.level) j = h.level + 1;
1587: Node<K,V> z = new Node<K,V>(key, val, null);
1588: basepred.next = z;
1589: basepred = z;
1590: if (j > 0) {
1591: Index<K,V> idx = null;
1592: for (int i = 1; i <= j; ++i) {
1593: idx = new Index<K,V>(z, idx, null);
1594: if (i > h.level)
1595: h = new HeadIndex<K,V>(h.node, h, idx, i);
1596:
1597: if (i < preds.size()) {
1598: preds.get(i).right = idx;
1599: preds.set(i, idx);
1600: } else
1601: preds.add(idx);
1602: }
1603: }
1604: }
1605: head = h;
1606: }
1607:
1608:
1609:
1610:
1620: public boolean containsKey(Object key) {
1621: return doGet(key) != null;
1622: }
1623:
1624:
1638: public V get(Object key) {
1639: return doGet(key);
1640: }
1641:
1642:
1655: public V put(K key, V value) {
1656: if (value == null)
1657: throw new NullPointerException();
1658: return doPut(key, value, false);
1659: }
1660:
1661:
1671: public V remove(Object key) {
1672: return doRemove(key, null);
1673: }
1674:
1675:
1685: public boolean containsValue(Object value) {
1686: if (value == null)
1687: throw new NullPointerException();
1688: for (Node<K,V> n = findFirst(); n != null; n = n.next) {
1689: V v = n.getValidValue();
1690: if (v != null && value.equals(v))
1691: return true;
1692: }
1693: return false;
1694: }
1695:
1696:
1712: public int size() {
1713: long count = 0;
1714: for (Node<K,V> n = findFirst(); n != null; n = n.next) {
1715: if (n.getValidValue() != null)
1716: ++count;
1717: }
1718: return (count >= Integer.MAX_VALUE)? Integer.MAX_VALUE : (int)count;
1719: }
1720:
1721:
1725: public boolean isEmpty() {
1726: return findFirst() == null;
1727: }
1728:
1729:
1732: public void clear() {
1733: initialize();
1734: }
1735:
1736:
1737:
1738:
1746:
1747:
1768: public NavigableSet<K> keySet() {
1769: KeySet ks = keySet;
1770: return (ks != null) ? ks : (keySet = new KeySet(this));
1771: }
1772:
1773: public NavigableSet<K> navigableKeySet() {
1774: KeySet ks = keySet;
1775: return (ks != null) ? ks : (keySet = new KeySet(this));
1776: }
1777:
1778:
1796: public Collection<V> values() {
1797: Values vs = values;
1798: return (vs != null) ? vs : (values = new Values(this));
1799: }
1800:
1801:
1825: public Set<Map.Entry<K,V>> entrySet() {
1826: EntrySet es = entrySet;
1827: return (es != null) ? es : (entrySet = new EntrySet(this));
1828: }
1829:
1830: public ConcurrentNavigableMap<K,V> descendingMap() {
1831: ConcurrentNavigableMap<K,V> dm = descendingMap;
1832: return (dm != null) ? dm : (descendingMap = new SubMap<K,V>
1833: (this, null, false, null, false, true));
1834: }
1835:
1836: public NavigableSet<K> descendingKeySet() {
1837: return descendingMap().navigableKeySet();
1838: }
1839:
1840:
1841:
1842:
1854: public boolean equals(Object o) {
1855: if (o == this)
1856: return true;
1857: if (!(o instanceof Map))
1858: return false;
1859: Map<?,?> m = (Map<?,?>) o;
1860: try {
1861: for (Map.Entry<K,V> e : this.entrySet())
1862: if (! e.getValue().equals(m.get(e.getKey())))
1863: return false;
1864: for (Map.Entry<?,?> e : m.entrySet()) {
1865: Object k = e.getKey();
1866: Object v = e.getValue();
1867: if (k == null || v == null || !v.equals(get(k)))
1868: return false;
1869: }
1870: return true;
1871: } catch (ClassCastException unused) {
1872: return false;
1873: } catch (NullPointerException unused) {
1874: return false;
1875: }
1876: }
1877:
1878:
1879:
1880:
1889: public V putIfAbsent(K key, V value) {
1890: if (value == null)
1891: throw new NullPointerException();
1892: return doPut(key, value, true);
1893: }
1894:
1895:
1902: public boolean remove(Object key, Object value) {
1903: if (key == null)
1904: throw new NullPointerException();
1905: if (value == null)
1906: return false;
1907: return doRemove(key, value) != null;
1908: }
1909:
1910:
1917: public boolean replace(K key, V oldValue, V newValue) {
1918: if (oldValue == null || newValue == null)
1919: throw new NullPointerException();
1920: Comparable<? super K> k = comparable(key);
1921: for (;;) {
1922: Node<K,V> n = findNode(k);
1923: if (n == null)
1924: return false;
1925: Object v = n.value;
1926: if (v != null) {
1927: if (!oldValue.equals(v))
1928: return false;
1929: if (n.casValue(v, newValue))
1930: return true;
1931: }
1932: }
1933: }
1934:
1935:
1944: public V replace(K key, V value) {
1945: if (value == null)
1946: throw new NullPointerException();
1947: Comparable<? super K> k = comparable(key);
1948: for (;;) {
1949: Node<K,V> n = findNode(k);
1950: if (n == null)
1951: return null;
1952: Object v = n.value;
1953: if (v != null && n.casValue(v, value))
1954: return (V)v;
1955: }
1956: }
1957:
1958:
1959:
1960: public Comparator<? super K> comparator() {
1961: return comparator;
1962: }
1963:
1964:
1967: public K firstKey() {
1968: Node<K,V> n = findFirst();
1969: if (n == null)
1970: throw new NoSuchElementException();
1971: return n.key;
1972: }
1973:
1974:
1977: public K lastKey() {
1978: Node<K,V> n = findLast();
1979: if (n == null)
1980: throw new NoSuchElementException();
1981: return n.key;
1982: }
1983:
1984:
1989: public ConcurrentNavigableMap<K,V> subMap(K fromKey,
1990: boolean fromInclusive,
1991: K toKey,
1992: boolean toInclusive) {
1993: if (fromKey == null || toKey == null)
1994: throw new NullPointerException();
1995: return new SubMap<K,V>
1996: (this, fromKey, fromInclusive, toKey, toInclusive, false);
1997: }
1998:
1999:
2004: public ConcurrentNavigableMap<K,V> headMap(K toKey,
2005: boolean inclusive) {
2006: if (toKey == null)
2007: throw new NullPointerException();
2008: return new SubMap<K,V>
2009: (this, null, false, toKey, inclusive, false);
2010: }
2011:
2012:
2017: public ConcurrentNavigableMap<K,V> tailMap(K fromKey,
2018: boolean inclusive) {
2019: if (fromKey == null)
2020: throw new NullPointerException();
2021: return new SubMap<K,V>
2022: (this, fromKey, inclusive, null, false, false);
2023: }
2024:
2025:
2030: public ConcurrentNavigableMap<K,V> subMap(K fromKey, K toKey) {
2031: return subMap(fromKey, true, toKey, false);
2032: }
2033:
2034:
2039: public ConcurrentNavigableMap<K,V> headMap(K toKey) {
2040: return headMap(toKey, false);
2041: }
2042:
2043:
2048: public ConcurrentNavigableMap<K,V> tailMap(K fromKey) {
2049: return tailMap(fromKey, true);
2050: }
2051:
2052:
2053:
2054:
2063: public Map.Entry<K,V> lowerEntry(K key) {
2064: return getNear(key, LT);
2065: }
2066:
2067:
2071: public K lowerKey(K key) {
2072: Node<K,V> n = findNear(key, LT);
2073: return (n == null)? null : n.key;
2074: }
2075:
2076:
2086: public Map.Entry<K,V> floorEntry(K key) {
2087: return getNear(key, LT|EQ);
2088: }
2089:
2090:
2095: public K floorKey(K key) {
2096: Node<K,V> n = findNear(key, LT|EQ);
2097: return (n == null)? null : n.key;
2098: }
2099:
2100:
2109: public Map.Entry<K,V> ceilingEntry(K key) {
2110: return getNear(key, GT|EQ);
2111: }
2112:
2113:
2117: public K ceilingKey(K key) {
2118: Node<K,V> n = findNear(key, GT|EQ);
2119: return (n == null)? null : n.key;
2120: }
2121:
2122:
2132: public Map.Entry<K,V> higherEntry(K key) {
2133: return getNear(key, GT);
2134: }
2135:
2136:
2141: public K higherKey(K key) {
2142: Node<K,V> n = findNear(key, GT);
2143: return (n == null)? null : n.key;
2144: }
2145:
2146:
2152: public Map.Entry<K,V> firstEntry() {
2153: for (;;) {
2154: Node<K,V> n = findFirst();
2155: if (n == null)
2156: return null;
2157: AbstractMap.SimpleImmutableEntry<K,V> e = n.createSnapshot();
2158: if (e != null)
2159: return e;
2160: }
2161: }
2162:
2163:
2169: public Map.Entry<K,V> lastEntry() {
2170: for (;;) {
2171: Node<K,V> n = findLast();
2172: if (n == null)
2173: return null;
2174: AbstractMap.SimpleImmutableEntry<K,V> e = n.createSnapshot();
2175: if (e != null)
2176: return e;
2177: }
2178: }
2179:
2180:
2186: public Map.Entry<K,V> pollFirstEntry() {
2187: return doRemoveFirstEntry();
2188: }
2189:
2190:
2196: public Map.Entry<K,V> pollLastEntry() {
2197: return doRemoveLastEntry();
2198: }
2199:
2200:
2201:
2202:
2203:
2206: abstract class Iter<T> implements Iterator<T> {
2207:
2208: Node<K,V> lastReturned;
2209:
2210: Node<K,V> next;
2211:
2212: V nextValue;
2213:
2214:
2215: Iter() {
2216: for (;;) {
2217: next = findFirst();
2218: if (next == null)
2219: break;
2220: Object x = next.value;
2221: if (x != null && x != next) {
2222: nextValue = (V) x;
2223: break;
2224: }
2225: }
2226: }
2227:
2228: public final boolean hasNext() {
2229: return next != null;
2230: }
2231:
2232:
2233: final void advance() {
2234: if ((lastReturned = next) == null)
2235: throw new NoSuchElementException();
2236: for (;;) {
2237: next = next.next;
2238: if (next == null)
2239: break;
2240: Object x = next.value;
2241: if (x != null && x != next) {
2242: nextValue = (V) x;
2243: break;
2244: }
2245: }
2246: }
2247:
2248: public void remove() {
2249: Node<K,V> l = lastReturned;
2250: if (l == null)
2251: throw new IllegalStateException();
2252:
2253:
2254: ConcurrentSkipListMap.this.remove(l.key);
2255: lastReturned = null;
2256: }
2257:
2258: }
2259:
2260: final class ValueIterator extends Iter<V> {
2261: public V next() {
2262: V v = nextValue;
2263: advance();
2264: return v;
2265: }
2266: }
2267:
2268: final class KeyIterator extends Iter<K> {
2269: public K next() {
2270: Node<K,V> n = next;
2271: advance();
2272: return n.key;
2273: }
2274: }
2275:
2276: final class EntryIterator extends Iter<Map.Entry<K,V>> {
2277: public Map.Entry<K,V> next() {
2278: Node<K,V> n = next;
2279: V v = nextValue;
2280: advance();
2281: return new AbstractMap.SimpleImmutableEntry<K,V>(n.key, v);
2282: }
2283: }
2284:
2285:
2286:
2287: Iterator<K> keyIterator() {
2288: return new KeyIterator();
2289: }
2290:
2291: Iterator<V> valueIterator() {
2292: return new ValueIterator();
2293: }
2294:
2295: Iterator<Map.Entry<K,V>> entryIterator() {
2296: return new EntryIterator();
2297: }
2298:
2299:
2300:
2301:
2306:
2307: static final <E> List<E> toList(Collection<E> c) {
2308:
2309: List<E> list = new ArrayList<E>();
2310: for (E e : c)
2311: list.add(e);
2312: return list;
2313: }
2314:
2315: static final class KeySet<E> extends AbstractSet<E> implements NavigableSet<E> {
2316: private final ConcurrentNavigableMap<E,Object> m;
2317: KeySet(ConcurrentNavigableMap<E,Object> map) { m = map; }
2318: public int size() { return m.size(); }
2319: public boolean isEmpty() { return m.isEmpty(); }
2320: public boolean contains(Object o) { return m.containsKey(o); }
2321: public boolean remove(Object o) { return m.remove(o) != null; }
2322: public void clear() { m.clear(); }
2323: public E lower(E e) { return m.lowerKey(e); }
2324: public E floor(E e) { return m.floorKey(e); }
2325: public E ceiling(E e) { return m.ceilingKey(e); }
2326: public E higher(E e) { return m.higherKey(e); }
2327: public Comparator<? super E> comparator() { return m.comparator(); }
2328: public E first() { return m.firstKey(); }
2329: public E last() { return m.lastKey(); }
2330: public E pollFirst() {
2331: Map.Entry<E,Object> e = m.pollFirstEntry();
2332: return e == null? null : e.getKey();
2333: }
2334: public E pollLast() {
2335: Map.Entry<E,Object> e = m.pollLastEntry();
2336: return e == null? null : e.getKey();
2337: }
2338: public Iterator<E> iterator() {
2339: if (m instanceof ConcurrentSkipListMap)
2340: return ((ConcurrentSkipListMap<E,Object>)m).keyIterator();
2341: else
2342: return ((ConcurrentSkipListMap.SubMap<E,Object>)m).keyIterator();
2343: }
2344: public boolean equals(Object o) {
2345: if (o == this)
2346: return true;
2347: if (!(o instanceof Set))
2348: return false;
2349: Collection<?> c = (Collection<?>) o;
2350: try {
2351: return containsAll(c) && c.containsAll(this);
2352: } catch (ClassCastException unused) {
2353: return false;
2354: } catch (NullPointerException unused) {
2355: return false;
2356: }
2357: }
2358: public Object[] toArray() { return toList(this).toArray(); }
2359: public <T> T[] toArray(T[] a) { return toList(this).toArray(a); }
2360: public Iterator<E> descendingIterator() {
2361: return descendingSet().iterator();
2362: }
2363: public NavigableSet<E> subSet(E fromElement,
2364: boolean fromInclusive,
2365: E toElement,
2366: boolean toInclusive) {
2367: return new ConcurrentSkipListSet<E>
2368: (m.subMap(fromElement, fromInclusive,
2369: toElement, toInclusive));
2370: }
2371: public NavigableSet<E> headSet(E toElement, boolean inclusive) {
2372: return new ConcurrentSkipListSet<E>(m.headMap(toElement, inclusive));
2373: }
2374: public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
2375: return new ConcurrentSkipListSet<E>(m.tailMap(fromElement, inclusive));
2376: }
2377: public NavigableSet<E> subSet(E fromElement, E toElement) {
2378: return subSet(fromElement, true, toElement, false);
2379: }
2380: public NavigableSet<E> headSet(E toElement) {
2381: return headSet(toElement, false);
2382: }
2383: public NavigableSet<E> tailSet(E fromElement) {
2384: return tailSet(fromElement, true);
2385: }
2386: public NavigableSet<E> descendingSet() {
2387: return new ConcurrentSkipListSet(m.descendingMap());
2388: }
2389: }
2390:
2391: static final class Values<E> extends AbstractCollection<E> {
2392: private final ConcurrentNavigableMap<Object, E> m;
2393: Values(ConcurrentNavigableMap<Object, E> map) {
2394: m = map;
2395: }
2396: public Iterator<E> iterator() {
2397: if (m instanceof ConcurrentSkipListMap)
2398: return ((ConcurrentSkipListMap<Object,E>)m).valueIterator();
2399: else
2400: return ((SubMap<Object,E>)m).valueIterator();
2401: }
2402: public boolean isEmpty() {
2403: return m.isEmpty();
2404: }
2405: public int size() {
2406: return m.size();
2407: }
2408: public boolean contains(Object o) {
2409: return m.containsValue(o);
2410: }
2411: public void clear() {
2412: m.clear();
2413: }
2414: public Object[] toArray() { return toList(this).toArray(); }
2415: public <T> T[] toArray(T[] a) { return toList(this).toArray(a); }
2416: }
2417:
2418: static final class EntrySet<K1,V1> extends AbstractSet<Map.Entry<K1,V1>> {
2419: private final ConcurrentNavigableMap<K1, V1> m;
2420: EntrySet(ConcurrentNavigableMap<K1, V1> map) {
2421: m = map;
2422: }
2423:
2424: public Iterator<Map.Entry<K1,V1>> iterator() {
2425: if (m instanceof ConcurrentSkipListMap)
2426: return ((ConcurrentSkipListMap<K1,V1>)m).entryIterator();
2427: else
2428: return ((SubMap<K1,V1>)m).entryIterator();
2429: }
2430:
2431: public boolean contains(Object o) {
2432: if (!(o instanceof Map.Entry))
2433: return false;
2434: Map.Entry<K1,V1> e = (Map.Entry<K1,V1>)o;
2435: V1 v = m.get(e.getKey());
2436: return v != null && v.equals(e.getValue());
2437: }
2438: public boolean remove(Object o) {
2439: if (!(o instanceof Map.Entry))
2440: return false;
2441: Map.Entry<K1,V1> e = (Map.Entry<K1,V1>)o;
2442: return m.remove(e.getKey(),
2443: e.getValue());
2444: }
2445: public boolean isEmpty() {
2446: return m.isEmpty();
2447: }
2448: public int size() {
2449: return m.size();
2450: }
2451: public void clear() {
2452: m.clear();
2453: }
2454: public boolean equals(Object o) {
2455: if (o == this)
2456: return true;
2457: if (!(o instanceof Set))
2458: return false;
2459: Collection<?> c = (Collection<?>) o;
2460: try {
2461: return containsAll(c) && c.containsAll(this);
2462: } catch (ClassCastException unused) {
2463: return false;
2464: } catch (NullPointerException unused) {
2465: return false;
2466: }
2467: }
2468: public Object[] toArray() { return toList(this).toArray(); }
2469: public <T> T[] toArray(T[] a) { return toList(this).toArray(a); }
2470: }
2471:
2472:
2484: static final class SubMap<K,V> extends AbstractMap<K,V>
2485: implements ConcurrentNavigableMap<K,V>, Cloneable,
2486: java.io.Serializable {
2487: private static final long serialVersionUID = -7647078645895051609L;
2488:
2489:
2490: private final ConcurrentSkipListMap<K,V> m;
2491:
2492: private final K lo;
2493:
2494: private final K hi;
2495:
2496: private final boolean loInclusive;
2497:
2498: private final boolean hiInclusive;
2499:
2500: private final boolean isDescending;
2501:
2502:
2503: private transient KeySet<K> keySetView;
2504: private transient Set<Map.Entry<K,V>> entrySetView;
2505: private transient Collection<V> valuesView;
2506:
2507:
2510: SubMap(ConcurrentSkipListMap<K,V> map,
2511: K fromKey, boolean fromInclusive,
2512: K toKey, boolean toInclusive,
2513: boolean isDescending) {
2514: if (fromKey != null && toKey != null &&
2515: map.compare(fromKey, toKey) > 0)
2516: throw new IllegalArgumentException("inconsistent range");
2517: this.m = map;
2518: this.lo = fromKey;
2519: this.hi = toKey;
2520: this.loInclusive = fromInclusive;
2521: this.hiInclusive = toInclusive;
2522: this.isDescending = isDescending;
2523: }
2524:
2525:
2526:
2527: private boolean tooLow(K key) {
2528: if (lo != null) {
2529: int c = m.compare(key, lo);
2530: if (c < 0 || (c == 0 && !loInclusive))
2531: return true;
2532: }
2533: return false;
2534: }
2535:
2536: private boolean tooHigh(K key) {
2537: if (hi != null) {
2538: int c = m.compare(key, hi);
2539: if (c > 0 || (c == 0 && !hiInclusive))
2540: return true;
2541: }
2542: return false;
2543: }
2544:
2545: private boolean inBounds(K key) {
2546: return !tooLow(key) && !tooHigh(key);
2547: }
2548:
2549: private void checkKeyBounds(K key) throws IllegalArgumentException {
2550: if (key == null)
2551: throw new NullPointerException();
2552: if (!inBounds(key))
2553: throw new IllegalArgumentException("key out of range");
2554: }
2555:
2556:
2559: private boolean isBeforeEnd(ConcurrentSkipListMap.Node<K,V> n) {
2560: if (n == null)
2561: return false;
2562: if (hi == null)
2563: return true;
2564: K k = n.key;
2565: if (k == null)
2566: return true;
2567: int c = m.compare(k, hi);
2568: if (c > 0 || (c == 0 && !hiInclusive))
2569: return false;
2570: return true;
2571: }
2572:
2573:
2577: private ConcurrentSkipListMap.Node<K,V> loNode() {
2578: if (lo == null)
2579: return m.findFirst();
2580: else if (loInclusive)
2581: return m.findNear(lo, m.GT|m.EQ);
2582: else
2583: return m.findNear(lo, m.GT);
2584: }
2585:
2586:
2590: private ConcurrentSkipListMap.Node<K,V> hiNode() {
2591: if (hi == null)
2592: return m.findLast();
2593: else if (hiInclusive)
2594: return m.findNear(hi, m.LT|m.EQ);
2595: else
2596: return m.findNear(hi, m.LT);
2597: }
2598:
2599:
2602: private K lowestKey() {
2603: ConcurrentSkipListMap.Node<K,V> n = loNode();
2604: if (isBeforeEnd(n))
2605: return n.key;
2606: else
2607: throw new NoSuchElementException();
2608: }
2609:
2610:
2613: private K highestKey() {
2614: ConcurrentSkipListMap.Node<K,V> n = hiNode();
2615: if (n != null) {
2616: K last = n.key;
2617: if (inBounds(last))
2618: return last;
2619: }
2620: throw new NoSuchElementException();
2621: }
2622:
2623: private Map.Entry<K,V> lowestEntry() {
2624: for (;;) {
2625: ConcurrentSkipListMap.Node<K,V> n = loNode();
2626: if (!isBeforeEnd(n))
2627: return null;
2628: Map.Entry<K,V> e = n.createSnapshot();
2629: if (e != null)
2630: return e;
2631: }
2632: }
2633:
2634: private Map.Entry<K,V> highestEntry() {
2635: for (;;) {
2636: ConcurrentSkipListMap.Node<K,V> n = hiNode();
2637: if (n == null || !inBounds(n.key))
2638: return null;
2639: Map.Entry<K,V> e = n.createSnapshot();
2640: if (e != null)
2641: return e;
2642: }
2643: }
2644:
2645: private Map.Entry<K,V> removeLowest() {
2646: for (;;) {
2647: Node<K,V> n = loNode();
2648: if (n == null)
2649: return null;
2650: K k = n.key;
2651: if (!inBounds(k))
2652: return null;
2653: V v = m.doRemove(k, null);
2654: if (v != null)
2655: return new AbstractMap.SimpleImmutableEntry<K,V>(k, v);
2656: }
2657: }
2658:
2659: private Map.Entry<K,V> removeHighest() {
2660: for (;;) {
2661: Node<K,V> n = hiNode();
2662: if (n == null)
2663: return null;
2664: K k = n.key;
2665: if (!inBounds(k))
2666: return null;
2667: V v = m.doRemove(k, null);
2668: if (v != null)
2669: return new AbstractMap.SimpleImmutableEntry<K,V>(k, v);
2670: }
2671: }
2672:
2673:
2676: private Map.Entry<K,V> getNearEntry(K key, int rel) {
2677: if (isDescending) {
2678: if ((rel & m.LT) == 0)
2679: rel |= m.LT;
2680: else
2681: rel &= ~m.LT;
2682: }
2683: if (tooLow(key))
2684: return ((rel & m.LT) != 0)? null : lowestEntry();
2685: if (tooHigh(key))
2686: return ((rel & m.LT) != 0)? highestEntry() : null;
2687: for (;;) {
2688: Node<K,V> n = m.findNear(key, rel);
2689: if (n == null || !inBounds(n.key))
2690: return null;
2691: K k = n.key;
2692: V v = n.getValidValue();
2693: if (v != null)
2694: return new AbstractMap.SimpleImmutableEntry<K,V>(k, v);
2695: }
2696: }
2697:
2698:
2699: private K getNearKey(K key, int rel) {
2700: if (isDescending) {
2701: if ((rel & m.LT) == 0)
2702: rel |= m.LT;
2703: else
2704: rel &= ~m.LT;
2705: }
2706: if (tooLow(key)) {
2707: if ((rel & m.LT) == 0) {
2708: ConcurrentSkipListMap.Node<K,V> n = loNode();
2709: if (isBeforeEnd(n))
2710: return n.key;
2711: }
2712: return null;
2713: }
2714: if (tooHigh(key)) {
2715: if ((rel & m.LT) != 0) {
2716: ConcurrentSkipListMap.Node<K,V> n = hiNode();
2717: if (n != null) {
2718: K last = n.key;
2719: if (inBounds(last))
2720: return last;
2721: }
2722: }
2723: return null;
2724: }
2725: for (;;) {
2726: Node<K,V> n = m.findNear(key, rel);
2727: if (n == null || !inBounds(n.key))
2728: return null;
2729: K k = n.key;
2730: V v = n.getValidValue();
2731: if (v != null)
2732: return k;
2733: }
2734: }
2735:
2736:
2737:
2738: public boolean containsKey(Object key) {
2739: if (key == null) throw new NullPointerException();
2740: K k = (K)key;
2741: return inBounds(k) && m.containsKey(k);
2742: }
2743:
2744: public V get(Object key) {
2745: if (key == null) throw new NullPointerException();
2746: K k = (K)key;
2747: return ((!inBounds(k)) ? null : m.get(k));
2748: }
2749:
2750: public V put(K key, V value) {
2751: checkKeyBounds(key);
2752: return m.put(key, value);
2753: }
2754:
2755: public V remove(Object key) {
2756: K k = (K)key;
2757: return (!inBounds(k))? null : m.remove(k);
2758: }
2759:
2760: public int size() {
2761: long count = 0;
2762: for (ConcurrentSkipListMap.Node<K,V> n = loNode();
2763: isBeforeEnd(n);
2764: n = n.next) {
2765: if (n.getValidValue() != null)
2766: ++count;
2767: }
2768: return count >= Integer.MAX_VALUE? Integer.MAX_VALUE : (int)count;
2769: }
2770:
2771: public boolean isEmpty() {
2772: return !isBeforeEnd(loNode());
2773: }
2774:
2775: public boolean containsValue(Object value) {
2776: if (value == null)
2777: throw new NullPointerException();
2778: for (ConcurrentSkipListMap.Node<K,V> n = loNode();
2779: isBeforeEnd(n);
2780: n = n.next) {
2781: V v = n.getValidValue();
2782: if (v != null && value.equals(v))
2783: return true;
2784: }
2785: return false;
2786: }
2787:
2788: public void clear() {
2789: for (ConcurrentSkipListMap.Node<K,V> n = loNode();
2790: isBeforeEnd(n);
2791: n = n.next) {
2792: if (n.getValidValue() != null)
2793: m.remove(n.key);
2794: }
2795: }
2796:
2797:
2798:
2799: public V putIfAbsent(K key, V value) {
2800: checkKeyBounds(key);
2801: return m.putIfAbsent(key, value);
2802: }
2803:
2804: public boolean remove(Object key, Object value) {
2805: K k = (K)key;
2806: return inBounds(k) && m.remove(k, value);
2807: }
2808:
2809: public boolean replace(K key, V oldValue, V newValue) {
2810: checkKeyBounds(key);
2811: return m.replace(key, oldValue, newValue);
2812: }
2813:
2814: public V replace(K key, V value) {
2815: checkKeyBounds(key);
2816: return m.replace(key, value);
2817: }
2818:
2819:
2820:
2821: public Comparator<? super K> comparator() {
2822: Comparator<? super K> cmp = m.comparator();
2823: if (isDescending)
2824: return Collections.reverseOrder(cmp);
2825: else
2826: return cmp;
2827: }
2828:
2829:
2833: private SubMap<K,V> newSubMap(K fromKey,
2834: boolean fromInclusive,
2835: K toKey,
2836: boolean toInclusive) {
2837: if (isDescending) {
2838: K tk = fromKey;
2839: fromKey = toKey;
2840: toKey = tk;
2841: boolean ti = fromInclusive;
2842: fromInclusive = toInclusive;
2843: toInclusive = ti;
2844: }
2845: if (lo != null) {
2846: if (fromKey == null) {
2847: fromKey = lo;
2848: fromInclusive = loInclusive;
2849: }
2850: else {
2851: int c = m.compare(fromKey, lo);
2852: if (c < 0 || (c == 0 && !loInclusive && fromInclusive))
2853: throw new IllegalArgumentException("key out of range");
2854: }
2855: }
2856: if (hi != null) {
2857: if (toKey == null) {
2858: toKey = hi;
2859: toInclusive = hiInclusive;
2860: }
2861: else {
2862: int c = m.compare(toKey, hi);
2863: if (c > 0 || (c == 0 && !hiInclusive && toInclusive))
2864: throw new IllegalArgumentException("key out of range");
2865: }
2866: }
2867: return new SubMap<K,V>(m, fromKey, fromInclusive,
2868: toKey, toInclusive, isDescending);
2869: }
2870:
2871: public SubMap<K,V> subMap(K fromKey,
2872: boolean fromInclusive,
2873: K toKey,
2874: boolean toInclusive) {
2875: if (fromKey == null || toKey == null)
2876: throw new NullPointerException();
2877: return newSubMap(fromKey, fromInclusive, toKey, toInclusive);
2878: }
2879:
2880: public SubMap<K,V> headMap(K toKey,
2881: boolean inclusive) {
2882: if (toKey == null)
2883: throw new NullPointerException();
2884: return newSubMap(null, false, toKey, inclusive);
2885: }
2886:
2887: public SubMap<K,V> tailMap(K fromKey,
2888: boolean inclusive) {
2889: if (fromKey == null)
2890: throw new NullPointerException();
2891: return newSubMap(fromKey, inclusive, null, false);
2892: }
2893:
2894: public SubMap<K,V> subMap(K fromKey, K toKey) {
2895: return subMap(fromKey, true, toKey, false);
2896: }
2897:
2898: public SubMap<K,V> headMap(K toKey) {
2899: return headMap(toKey, false);
2900: }
2901:
2902: public SubMap<K,V> tailMap(K fromKey) {
2903: return tailMap(fromKey, true);
2904: }
2905:
2906: public SubMap<K,V> descendingMap() {
2907: return new SubMap<K,V>(m, lo, loInclusive,
2908: hi, hiInclusive, !isDescending);
2909: }
2910:
2911:
2912:
2913: public Map.Entry<K,V> ceilingEntry(K key) {
2914: return getNearEntry(key, (m.GT|m.EQ));
2915: }
2916:
2917: public K ceilingKey(K key) {
2918: return getNearKey(key, (m.GT|m.EQ));
2919: }
2920:
2921: public Map.Entry<K,V> lowerEntry(K key) {
2922: return getNearEntry(key, (m.LT));
2923: }
2924:
2925: public K lowerKey(K key) {
2926: return getNearKey(key, (m.LT));
2927: }
2928:
2929: public Map.Entry<K,V> floorEntry(K key) {
2930: return getNearEntry(key, (m.LT|m.EQ));
2931: }
2932:
2933: public K floorKey(K key) {
2934: return getNearKey(key, (m.LT|m.EQ));
2935: }
2936:
2937: public Map.Entry<K,V> higherEntry(K key) {
2938: return getNearEntry(key, (m.GT));
2939: }
2940:
2941: public K higherKey(K key) {
2942: return getNearKey(key, (m.GT));
2943: }
2944:
2945: public K firstKey() {
2946: return isDescending? highestKey() : lowestKey();
2947: }
2948:
2949: public K lastKey() {
2950: return isDescending? lowestKey() : highestKey();
2951: }
2952:
2953: public Map.Entry<K,V> firstEntry() {
2954: return isDescending? highestEntry() : lowestEntry();
2955: }
2956:
2957: public Map.Entry<K,V> lastEntry() {
2958: return isDescending? lowestEntry() : highestEntry();
2959: }
2960:
2961: public Map.Entry<K,V> pollFirstEntry() {
2962: return isDescending? removeHighest() : removeLowest();
2963: }
2964:
2965: public Map.Entry<K,V> pollLastEntry() {
2966: return isDescending? removeLowest() : removeHighest();
2967: }
2968:
2969:
2970:
2971: public NavigableSet<K> keySet() {
2972: KeySet<K> ks = keySetView;
2973: return (ks != null) ? ks : (keySetView = new KeySet(this));
2974: }
2975:
2976: public NavigableSet<K> navigableKeySet() {
2977: KeySet<K> ks = keySetView;
2978: return (ks != null) ? ks : (keySetView = new KeySet(this));
2979: }
2980:
2981: public Collection<V> values() {
2982: Collection<V> vs = valuesView;
2983: return (vs != null) ? vs : (valuesView = new Values(this));
2984: }
2985:
2986: public Set<Map.Entry<K,V>> entrySet() {
2987: Set<Map.Entry<K,V>> es = entrySetView;
2988: return (es != null) ? es : (entrySetView = new EntrySet(this));
2989: }
2990:
2991: public NavigableSet<K> descendingKeySet() {
2992: return descendingMap().navigableKeySet();
2993: }
2994:
2995: Iterator<K> keyIterator() {
2996: return new SubMapKeyIterator();
2997: }
2998:
2999: Iterator<V> valueIterator() {
3000: return new SubMapValueIterator();
3001: }
3002:
3003: Iterator<Map.Entry<K,V>> entryIterator() {
3004: return new SubMapEntryIterator();
3005: }
3006:
3007:
3010: abstract class SubMapIter<T> implements Iterator<T> {
3011:
3012: Node<K,V> lastReturned;
3013:
3014: Node<K,V> next;
3015:
3016: V nextValue;
3017:
3018: SubMapIter() {
3019: for (;;) {
3020: next = isDescending ? hiNode() : loNode();
3021: if (next == null)
3022: break;
3023: Object x = next.value;
3024: if (x != null && x != next) {
3025: if (! inBounds(next.key))
3026: next = null;
3027: else
3028: nextValue = (V) x;
3029: break;
3030: }
3031: }
3032: }
3033:
3034: public final boolean hasNext() {
3035: return next != null;
3036: }
3037:
3038: final void advance() {
3039: if ((lastReturned = next) == null)
3040: throw new NoSuchElementException();
3041: if (isDescending)
3042: descend();
3043: else
3044: ascend();
3045: }
3046:
3047: private void ascend() {
3048: for (;;) {
3049: next = next.next;
3050: if (next == null)
3051: break;
3052: Object x = next.value;
3053: if (x != null && x != next) {
3054: if (tooHigh(next.key))
3055: next = null;
3056: else
3057: nextValue = (V) x;
3058: break;
3059: }
3060: }
3061: }
3062:
3063: private void descend() {
3064: for (;;) {
3065: next = m.findNear(lastReturned.key, LT);
3066: if (next == null)
3067: break;
3068: Object x = next.value;
3069: if (x != null && x != next) {
3070: if (tooLow(next.key))
3071: next = null;
3072: else
3073: nextValue = (V) x;
3074: break;
3075: }
3076: }
3077: }
3078:
3079: public void remove() {
3080: Node<K,V> l = lastReturned;
3081: if (l == null)
3082: throw new IllegalStateException();
3083: m.remove(l.key);
3084: lastReturned = null;
3085: }
3086:
3087: }
3088:
3089: final class SubMapValueIterator extends SubMapIter<V> {
3090: public V next() {
3091: V v = nextValue;
3092: advance();
3093: return v;
3094: }
3095: }
3096:
3097: final class SubMapKeyIterator extends SubMapIter<K> {
3098: public K next() {
3099: Node<K,V> n = next;
3100: advance();
3101: return n.key;
3102: }
3103: }
3104:
3105: final class SubMapEntryIterator extends SubMapIter<Map.Entry<K,V>> {
3106: public Map.Entry<K,V> next() {
3107: Node<K,V> n = next;
3108: V v = nextValue;
3109: advance();
3110: return new AbstractMap.SimpleImmutableEntry<K,V>(n.key, v);
3111: }
3112: }
3113: }
3114: }