Node bit 6 is set on a primary node if there are nodes with secondary values below the common secondary weight (05).

Node bit 5 is set on a primary or secondary node if there are nodes with tertiary values below the common tertiary weight (05).

Node bit 3 distinguishes a tailored node, which has no weight value, from a node with an explicit (root or default) weight.

At most 1M nodes, limited by the 20 bits in node bit fields.

Data structure for assigning tailored weights and CEs. Doubly-linked lists of nodes in mostly collation order. Each list starts with a root primary node and ends with a nextIndex of 0. When there are any nodes in the list, then there is always a root primary node at index 0. This allows some code not to have to check explicitly for nextIndex==0. Root primary nodes have 32-bit weights but do not have previous indexes. All other nodes have at most 16-bit weights and do have previous indexes. Nodes with explicit weights store root collator weights, or default weak weights (e.g., secondary 05) for stronger nodes. "Tailored" nodes, with the IS_TAILORED bit set, do not store explicit weights but rather create a difference of a certain strength from the preceding node. A root node is followed by either - a root/default node of the same strength, or - a root/default node of the next-weaker strength, or - a tailored node of the same strength. A node of a given strength normally implies "common" weights on weaker levels. A node with HAS_BEFORE2 must be immediately followed by a secondary node with an explicit below-common weight, then a secondary tailored node, and later an explicit common-secondary node. The below-common weight can be a root weight, or it can be BEFORE_WEIGHT16 for tailoring before an implied common weight or before the lowest root weight. (&[before 2] resets to an explicit secondary node so that the following addRelation(secondary) tailors right after that. If we did not have this node and instead were to reset on the primary node, then addRelation(secondary) would skip forward to the the COMMON_WEIGHT16 node.) If the flag is not set, then there are no explicit secondary nodes with the common or lower weights. Same for HAS_BEFORE3 for tertiary nodes and weights. A node must not have both flags set. Tailored CEs are initially represented in a CollationDataBuilder as temporary CEs which point to stable indexes in this list, and temporary CEs stored in a CollationDataBuilder only point to tailored nodes. A temporary CE in the ces[] array may point to a non-tailored reset-before-position node, until the next relation is added. At the end, the tailored weights are allocated as necessary, then the tailored nodes are replaced with final CEs, and the CollationData is rewritten by replacing temporary CEs with final ones. We cannot simply insert new nodes in the middle of the array because that would invalidate the indexes stored in existing temporary CEs. We need to use a linked graph with stable indexes to existing nodes. A doubly-linked list seems easiest to maintain. Each node is stored as an long, with its fields stored as bit fields. Root primary node: - primary weight: 32 bits 63..32 - reserved/unused/zero: 4 bits 31..28 Weaker root nodes & tailored nodes: - a weight: 16 bits 63..48 + a root or default weight for a non-tailored node + unused/zero for a tailored node - index to the previous node: 20 bits 47..28 All types of nodes: - index to the next node: 20 bits 27..8 + nextIndex=0 in last node per root-primary list - reserved/unused/zero bits: bits 7, 4, 2 - HAS_BEFORE2: bit 6 - HAS_BEFORE3: bit 5 - IS_TAILORED: bit 3 - the difference strength (primary/secondary/tertiary/quaternary): 2 bits 1..0 We could allocate structs with pointers, but we would have to store them in a pointer list so that they can be indexed from temporary CEs, and they would require more memory allocations.

Indexes of nodes with root primary weights, sorted by primary. Compact form of a TreeMap from root primary to node index. This is a performance optimization for finding reset positions. Without this, we would have to search through the entire nodes list. It also allows storing root primary weights in list head nodes, without previous index, leaving room in root primary nodes for 32-bit primary weights.