ViewVC Help

View File | Revision Log | Show Annotations | Download File | Root Listing

root/jsr166/jsr166/src/main/java/util/concurrent/ConcurrentSkipListMap.java

Comparing jsr166/src/main/java/util/concurrent/ConcurrentSkipListMap.java (file contents):
Revision 1.9 by dl, Mon Apr 11 23:17:21 2005 UTC vs.
Revision 1.10 by jsr166, Tue Apr 26 20:42:51 2005 UTC

#	Line 299 | Line 299 | public class ConcurrentSkipListMap<K,V>
299		private transient volatile HeadIndex<K,V> head;
300
301		/**
302	<	* The Comparator used to maintain order in this Map, or null
302	>	* The comparator used to maintain order in this map, or null
303		* if using natural order.
304		* @serial
305		*/
#	Line 412 | Line 412 | public class ConcurrentSkipListMap<K,V>
412		}
413
414		/**
415	<	* Return true if this node is a marker. This method isn't
416	<	* actually called in an any current code checking for markers
415	>	* Returns true if this node is a marker. This method isn't
416	>	* actually called in any current code checking for markers
417		* because callers will have already read value field and need
418		* to use that read (not another done here) and so directly
419		* test if value points to node.
#	Line 425 | Line 425 | public class ConcurrentSkipListMap<K,V>
425		}
426
427		/**
428	<	* Return true if this node is the header of base-level list.
428	>	* Returns true if this node is the header of base-level list.
429		* @return true if this node is header node
430		*/
431		boolean isBaseHeader() {
#	Line 476 | Line 476 | public class ConcurrentSkipListMap<K,V>
476		}
477
478		/**
479	<	* Create and return a new SimpleImmutableEntry holding current
480	<	* mapping if this node holds a valid value, else null
479	>	* Creates and returns a new SimpleImmutableEntry holding current
480	>	* mapping if this node holds a valid value, else null.
481		* @return new entry or null
482		*/
483		AbstractMap.SimpleImmutableEntry<K,V> createSnapshot() {
#	Line 505 | Line 505 | public class ConcurrentSkipListMap<K,V>
505		volatile Index<K,V> right;
506
507		/**
508	<	* Creates index node with given values
508	>	* Creates index node with given values.
509		*/
510		Index(Node<K,V> node, Index<K,V> down, Index<K,V> right) {
511		this.node = node;
#	Line 616 | Line 616 | public class ConcurrentSkipListMap<K,V>
616		}
617
618		/**
619	<	* Compare using comparator or natural ordering. Used when the
619	>	* Compares using comparator or natural ordering. Used when the
620		* ComparableUsingComparator approach doesn't apply.
621		*/
622		int compare(K k1, K k2) throws ClassCastException {
#	Line 628 | Line 628 | public class ConcurrentSkipListMap<K,V>
628		}
629
630		/**
631	<	* Return true if given key greater than or equal to least and
631	>	* Returns true if given key greater than or equal to least and
632		* strictly less than fence, bypassing either test if least or
633		* fence are null. Needed mainly in submap operations.
634		*/
#	Line 640 | Line 640 | public class ConcurrentSkipListMap<K,V>
640		}
641
642		/**
643	<	* Return true if given key greater than or equal to least and less
643	>	* Returns true if given key greater than or equal to least and less
644		* or equal to fence. Needed mainly in submap operations.
645		*/
646		boolean inOpenRange(K key, K least, K fence) {
#	Line 653 | Line 653 | public class ConcurrentSkipListMap<K,V>
653		/* ---------------- Traversal -------------- */
654
655		/**
656	<	* Return a base-level node with key strictly less than given key,
656	>	* Returns a base-level node with key strictly less than given key,
657		* or the base-level header if there is no such node.  Also
658		* unlinks indexes to deleted nodes found along the way.  Callers
659		* rely on this side-effect of clearing indices to deleted nodes.
#	Line 686 | Line 686 | public class ConcurrentSkipListMap<K,V>
686		}
687
688		/**
689	<	* Return node holding key or null if no such, clearing out any
689	>	* Returns node holding key or null if no such, clearing out any
690		* deleted nodes seen along the way.  Repeatedly traverses at
691		* base-level looking for key starting at predecessor returned
692		* from findPredecessor, processing base-level deletions as
#	Line 810 | Line 810 | public class ConcurrentSkipListMap<K,V>
810		}
811
812		/**
813	<	* Perform map.get via findNode.  Used as a backup if doGet
813	>	* Performs map.get via findNode.  Used as a backup if doGet
814		* encounters an in-progress deletion.
815		* @param key the key
816		* @return the value, or null if absent
#	Line 885 | Line 885 | public class ConcurrentSkipListMap<K,V>
885		}
886
887		/**
888	<	* Return a random level for inserting a new node.
888	>	* Returns a random level for inserting a new node.
889		* Hardwired to k=1, p=0.5, max 31.
890		*
891		* This uses a cheap pseudo-random function that according to
#	Line 907 | Line 907 | public class ConcurrentSkipListMap<K,V>
907		}
908
909		/**
910	<	* Create and add index nodes for given node.
910	>	* Creates and adds index nodes for given node.
911		* @param z the node
912		* @param level the level of the index
913		*/
#	Line 959 | Line 959 | public class ConcurrentSkipListMap<K,V>
959		}
960
961		/**
962	<	* Add given index nodes from given level down to 1.
962	>	* Adds given index nodes from given level down to 1.
963		* @param idx the topmost index node being inserted
964		* @param h the value of head to use to insert. This must be
965		* snapshotted by callers to provide correct insertion level
#	Line 1141 | Line 1141 | public class ConcurrentSkipListMap<K,V>
1141		}
1142
1143		/**
1144	<	* Remove first entry; return either its key or a snapshot.
1144	>	* Removes first entry; returns either its key or a snapshot.
1145		* @param keyOnly if true return key, else return SimpleImmutableEntry
1146		* (This is a little ugly, but avoids code duplication.)
1147		* @return null if empty, first key if keyOnly true, else key,value entry
#	Line 1174 | Line 1174 | public class ConcurrentSkipListMap<K,V>
1174		}
1175
1176		/**
1177	<	* Clear out index nodes associated with deleted first entry.
1178	<	* Needed by doRemoveFirst
1177	>	* Clears out index nodes associated with deleted first entry.
1178	>	* Needed by doRemoveFirst.
1179		*/
1180		private void clearIndexToFirst() {
1181		for (;;) {
#	Line 1194 | Line 1194 | public class ConcurrentSkipListMap<K,V>
1194		}
1195
1196		/**
1197	<	* Remove first entry; return key or null if empty.
1197	>	* Removes first entry; returns key or null if empty.
1198		*/
1199		K pollFirstKey() {
1200		return (K)doRemoveFirst(true);
#	Line 1203 | Line 1203 | public class ConcurrentSkipListMap<K,V>
1203		/* ---------------- Finding and removing last element -------------- */
1204
1205		/**
1206	<	* Specialized version of find to get last valid node
1206	>	* Specialized version of find to get last valid node.
1207		* @return last node or null if empty
1208		*/
1209		Node<K,V> findLast() {
#	Line 1382 | Line 1382 | public class ConcurrentSkipListMap<K,V>
1382		}
1383
1384		/**
1385	<	* Return SimpleImmutableEntry for results of findNear.
1385	>	* Returns SimpleImmutableEntry for results of findNear.
1386		* @param kkey the key
1387		* @param rel the relation -- OR'ed combination of EQ, LT, GT
1388		* @return Entry fitting relation, or null if no such
#	Line 1399 | Line 1399 | public class ConcurrentSkipListMap<K,V>
1399		}
1400
1401		/**
1402	<	* Return ceiling, or first node if key is <tt>null</tt>
1402	>	* Returns ceiling, or first node if key is <tt>null</tt>.
1403		*/
1404		Node<K,V> findCeiling(K key) {
1405		return (key == null)? findFirst() : findNear(key, GT|EQ);
1406		}
1407
1408		/**
1409	<	* Return lower node, or last node if key is <tt>null</tt>
1409	>	* Returns lower node, or last node if key is <tt>null</tt>.
1410		*/
1411		Node<K,V> findLower(K key) {
1412		return (key == null)? findLast() : findNear(key, LT);
1413		}
1414
1415		/**
1416	<	* Return SimpleImmutableEntry or key for results of findNear
1416	>	* Returns SimpleImmutableEntry or key for results of findNear
1417		* after screening to ensure result is in given range. Needed by
1418		* submaps.
1419		* @param kkey the key
#	Line 1449 | Line 1449 | public class ConcurrentSkipListMap<K,V>
1449		}
1450
1451		/**
1452	<	* Find and remove least element of subrange.
1452	>	* Finds and removes least element of subrange.
1453		* @param least minimum allowed key value
1454		* @param fence key greater than maximum allowed key value
1455		* @param keyOnly if true return key, else return SimpleImmutableEntry
#	Line 1474 | Line 1474 | public class ConcurrentSkipListMap<K,V>
1474		}
1475
1476		/**
1477	<	* Find and remove greatest element of subrange.
1477	>	* Finds and removes greatest element of subrange.
1478		* @param least minimum allowed key value
1479		* @param fence key greater than maximum allowed key value
1480		* @param keyOnly if true return key, else return SimpleImmutableEntry
#	Line 1554 | Line 1554 | public class ConcurrentSkipListMap<K,V>
1554		* Returns a shallow copy of this <tt>Map</tt> instance. (The keys and
1555		* values themselves are not cloned.)
1556		*
1557	<	* @return a shallow copy of this Map.
1557	>	* @return a shallow copy of this map.
1558		*/
1559		public Object clone() {
1560		ConcurrentSkipListMap<K,V> clone = null;
#	Line 1628 | Line 1628 | public class ConcurrentSkipListMap<K,V>
1628		/* ---------------- Serialization -------------- */
1629
1630		/**
1631	<	* Save the state of the <tt>Map</tt> instance to a stream.
1631	>	* Save the state of this map to a stream.
1632		*
1633		* @serialData The key (Object) and value (Object) for each
1634	<	* key-value mapping represented by the Map, followed by
1634	>	* key-value mapping represented by the map, followed by
1635		* <tt>null</tt>. The key-value mappings are emitted in key-order
1636		* (as determined by the Comparator, or by the keys' natural
1637		* ordering if no Comparator).
#	Line 1653 | Line 1653 | public class ConcurrentSkipListMap<K,V>
1653		}
1654
1655		/**
1656	<	* Reconstitute the <tt>Map</tt> instance from a stream.
1656	>	* Reconstitute the map from a stream.
1657		*/
1658		private void readObject(final java.io.ObjectInputStream s)
1659		throws java.io.IOException, ClassNotFoundException {
#	Line 1782 | Line 1782 | public class ConcurrentSkipListMap<K,V>
1782		/**
1783		* Returns <tt>true</tt> if this map maps one or more keys to the
1784		* specified value.  This operation requires time linear in the
1785	<	* Map size.
1785	>	* map size.
1786		*
1787	<	* @param value value whose presence in this Map is to be tested.
1787	>	* @param value value whose presence in this map is to be tested.
1788		* @return  <tt>true</tt> if a mapping to <tt>value</tt> exists;
1789		*          <tt>false</tt> otherwise.
1790		* @throws  NullPointerException  if the value is <tt>null</tt>.

Diff Legend

–	Removed lines
+	Added lines
<	Changed lines
>	Changed lines