Skip to content

Cell ID generator fix

Mladen Ivkovic requested to merge cellID_fix_2 into master

Generate unique cell IDs fix. Constraints:

  • must be thread safe
  • must be reproducible

Thread safe is given in any case, but the IDs are only reproducible if there are < 32^3 top level cells and the depth of the tree is <= 16.

We leave the first 15 bits of an unsigned long long for the top level cells, allowing for 32^3 unique top level cells. For every level of prodigy cells, we add three bits at the leftmost available position (i.e. increasing the value of the ID) based on the prodigy cell's position within the parent cell. Finally, add a leading 1 to mark that the cell ID is taken at that level and to make it unique.

Simplified Example:

  • using 3 rightmost bits instead of 15 for top level cells in this example
  • dots every three digits are included for improved readability
Depth     Cell ID binary
-------------------------
 0        000.000.000.001   [top level cell]
 1        000.001.000.001
 1        000.001.001.001
 1        000.001.010.001
 1        000.001.011.001
 1        000.001.100.001
 1        000.001.101.001
 1        000.001.110.001
 1        000.001.111.001
 2        001.000.000.001
 2        001.001.000.001
 2        001.010.000.001
 2        001.011.000.001
 2        001.100.000.001
 2        001.101.000.001
 2        001.110.000.001
 2        001.111.000.001
    .
    .
    .
 2        001.111.110.001
 2        001.111.111.001

etc

Current WIP status because I'm waiting for some bigger tests to finish, but this should work fine.

Edited by Mladen Ivkovic

Merge request reports