464 * Algorithms" (CLR).
465 *
466 * TreeBins also require an additional locking mechanism. While
467 * list traversal is always possible by readers even during
468 * updates, tree traversal is not, mainly because of tree-rotations
469 * that may change the root node and/or its linkages. TreeBins
470 * include a simple read-write lock mechanism parasitic on the
471 * main bin-synchronization strategy: Structural adjustments
472 * associated with an insertion or removal are already bin-locked
473 * (and so cannot conflict with other writers) but must wait for
474 * ongoing readers to finish. Since there can be only one such
475 * waiter, we use a simple scheme using a single "waiter" field to
476 * block writers. However, readers need never block. If the root
477 * lock is held, they proceed along the slow traversal path (via
478 * next-pointers) until the lock becomes available or the list is
479 * exhausted, whichever comes first. These cases are not fast, but
480 * maximize aggregate expected throughput.
481 *
482 * Maintaining API and serialization compatibility with previous
483 * versions of this class introduces several oddities. Mainly: We
484 * leave untouched but unused constructor arguments refering to
485 * concurrencyLevel. We accept a loadFactor constructor argument,
486 * but apply it only to initial table capacity (which is the only
487 * time that we can guarantee to honor it.) We also declare an
488 * unused "Segment" class that is instantiated in minimal form
489 * only when serializing.
490 *
491 * Also, solely for compatibility with previous versions of this
492 * class, it extends AbstractMap, even though all of its methods
493 * are overridden, so it is just useless baggage.
494 *
495 * This file is organized to make things a little easier to follow
496 * while reading than they might otherwise: First the main static
497 * declarations and utilities, then fields, then main public
498 * methods (with a few factorings of multiple public methods into
499 * internal ones), then sizing methods, trees, traversers, and
500 * bulk operations.
501 */
502
503 /* ---------------- Constants -------------- */
504
|
464 * Algorithms" (CLR).
465 *
466 * TreeBins also require an additional locking mechanism. While
467 * list traversal is always possible by readers even during
468 * updates, tree traversal is not, mainly because of tree-rotations
469 * that may change the root node and/or its linkages. TreeBins
470 * include a simple read-write lock mechanism parasitic on the
471 * main bin-synchronization strategy: Structural adjustments
472 * associated with an insertion or removal are already bin-locked
473 * (and so cannot conflict with other writers) but must wait for
474 * ongoing readers to finish. Since there can be only one such
475 * waiter, we use a simple scheme using a single "waiter" field to
476 * block writers. However, readers need never block. If the root
477 * lock is held, they proceed along the slow traversal path (via
478 * next-pointers) until the lock becomes available or the list is
479 * exhausted, whichever comes first. These cases are not fast, but
480 * maximize aggregate expected throughput.
481 *
482 * Maintaining API and serialization compatibility with previous
483 * versions of this class introduces several oddities. Mainly: We
484 * leave untouched but unused constructor arguments referring to
485 * concurrencyLevel. We accept a loadFactor constructor argument,
486 * but apply it only to initial table capacity (which is the only
487 * time that we can guarantee to honor it.) We also declare an
488 * unused "Segment" class that is instantiated in minimal form
489 * only when serializing.
490 *
491 * Also, solely for compatibility with previous versions of this
492 * class, it extends AbstractMap, even though all of its methods
493 * are overridden, so it is just useless baggage.
494 *
495 * This file is organized to make things a little easier to follow
496 * while reading than they might otherwise: First the main static
497 * declarations and utilities, then fields, then main public
498 * methods (with a few factorings of multiple public methods into
499 * internal ones), then sizing methods, trees, traversers, and
500 * bulk operations.
501 */
502
503 /* ---------------- Constants -------------- */
504
|