in h3_h3Index.c [465:673]
H3Error H3_EXPORT(compactCells)(const H3Index *h3Set, H3Index *compactedSet,
const int64_t numHexes) {
if (numHexes == 0) {
return E_SUCCESS;
}
int res = H3_GET_RESOLUTION(h3Set[0]);
if (res == 0) {
// No compaction possible, just copy the set to output
for (int64_t i = 0; i < numHexes; i++) {
compactedSet[i] = h3Set[i];
}
return E_SUCCESS;
}
H3Index *remainingHexes = H3_MEMORY(malloc)(numHexes * sizeof(H3Index));
if (!remainingHexes) {
return E_MEMORY_ALLOC;
}
memcpy(remainingHexes, h3Set, numHexes * sizeof(H3Index));
H3Index *hashSetArray = H3_MEMORY(calloc)(numHexes, sizeof(H3Index));
if (!hashSetArray) {
H3_MEMORY(free)(remainingHexes);
return E_MEMORY_ALLOC;
}
H3Index *compactedSetOffset = compactedSet;
int64_t numRemainingHexes = numHexes;
while (numRemainingHexes) {
res = H3_GET_RESOLUTION(remainingHexes[0]);
int parentRes = res - 1;
// If parentRes is less than zero, we've compacted all the way up to the
// base cells. Time to process the remaining cells.
if (parentRes >= 0) {
// Put the parents of the hexagons into the temp array
// via a hashing mechanism, and use the reserved bits
// to track how many times a parent is duplicated
for (int64_t i = 0; i < numRemainingHexes; i++) {
H3Index currIndex = remainingHexes[i];
// TODO: This case is coverable (reachable by fuzzer)
if (currIndex != 0) {
// If the reserved bits were set by the caller, the
// algorithm below may encounter undefined behavior
// because it expects to have set the reserved bits
// itself.
if (H3_GET_RESERVED_BITS(currIndex) != 0) {
H3_MEMORY(free)(remainingHexes);
H3_MEMORY(free)(hashSetArray);
return E_CELL_INVALID;
}
H3Index parent;
H3Error parentError =
H3_EXPORT(cellToParent)(currIndex, parentRes, &parent);
// Should never be reachable as a result of the compact
// algorithm. Can happen if cellToParent errors e.g.
// because of incompatible resolutions.
if (parentError) {
H3_MEMORY(free)(remainingHexes);
H3_MEMORY(free)(hashSetArray);
return parentError;
}
// Modulus hash the parent into the temp array
int64_t loc = (int64_t)(parent % numRemainingHexes);
int64_t loopCount = 0;
while (hashSetArray[loc] != 0) {
if (NEVER(loopCount > numRemainingHexes)) {
// This case should not be possible because at
// most one index is placed into hashSetArray
// per numRemainingHexes.
H3_MEMORY(free)(remainingHexes);
H3_MEMORY(free)(hashSetArray);
return E_FAILED;
}
H3Index tempIndex =
hashSetArray[loc] & H3_RESERVED_MASK_NEGATIVE;
if (tempIndex == parent) {
int count =
H3_GET_RESERVED_BITS(hashSetArray[loc]) + 1;
int limitCount = 7;
if (H3_EXPORT(isPentagon)(
tempIndex & H3_RESERVED_MASK_NEGATIVE)) {
limitCount--;
}
// One is added to count for this check to match
// one being added to count later in this
// function when checking for all children being
// present.
if (count + 1 > limitCount) {
// Only possible on duplicate input
H3_MEMORY(free)(remainingHexes);
H3_MEMORY(free)(hashSetArray);
return E_DUPLICATE_INPUT;
}
H3_SET_RESERVED_BITS(parent, count);
hashSetArray[loc] = H3_NULL;
} else {
loc = (loc + 1) % numRemainingHexes;
}
loopCount++;
}
hashSetArray[loc] = parent;
}
}
}
// Determine which parent hexagons have a complete set
// of children and put them in the compactableHexes array
int64_t compactableCount = 0;
int64_t maxCompactableCount =
numRemainingHexes / 6; // Somehow all pentagons; conservative
if (maxCompactableCount == 0) {
memcpy(compactedSetOffset, remainingHexes,
numRemainingHexes * sizeof(remainingHexes[0]));
break;
}
H3Index *compactableHexes =
H3_MEMORY(calloc)(maxCompactableCount, sizeof(H3Index));
if (!compactableHexes) {
H3_MEMORY(free)(remainingHexes);
H3_MEMORY(free)(hashSetArray);
return E_MEMORY_ALLOC;
}
for (int64_t i = 0; i < numRemainingHexes; i++) {
if (hashSetArray[i] == 0) continue;
int count = H3_GET_RESERVED_BITS(hashSetArray[i]) + 1;
// Include the deleted direction for pentagons as implicitly "there"
if (H3_EXPORT(isPentagon)(hashSetArray[i] &
H3_RESERVED_MASK_NEGATIVE)) {
// We need this later on, no need to recalculate
H3_SET_RESERVED_BITS(hashSetArray[i], count);
// Increment count after setting the reserved bits,
// since count is already incremented above, so it
// will be the expected value for a complete hexagon.
count++;
}
if (count == 7) {
// Bingo! Full set!
compactableHexes[compactableCount] =
hashSetArray[i] & H3_RESERVED_MASK_NEGATIVE;
compactableCount++;
}
}
// Uncompactable hexes are immediately copied into the
// output compactedSetOffset
int64_t uncompactableCount = 0;
for (int64_t i = 0; i < numRemainingHexes; i++) {
H3Index currIndex = remainingHexes[i];
// TODO: This case is coverable (reachable by fuzzer)
if (currIndex != H3_NULL) {
bool isUncompactable = true;
// Resolution 0 cells always uncompactable, and trying to take
// the res -1 parent of a cell is invalid.
if (parentRes >= 0) {
H3Index parent;
H3Error parentError =
H3_EXPORT(cellToParent)(currIndex, parentRes, &parent);
if (NEVER(parentError)) {
H3_MEMORY(free)(compactableHexes);
H3_MEMORY(free)(remainingHexes);
H3_MEMORY(free)(hashSetArray);
return parentError;
}
// Modulus hash the parent into the temp array
// to determine if this index was included in
// the compactableHexes array
int64_t loc = (int64_t)(parent % numRemainingHexes);
int64_t loopCount = 0;
do {
if (NEVER(loopCount > numRemainingHexes)) {
// This case should not be possible because at most
// one index is placed into hashSetArray per input
// hexagon.
H3_MEMORY(free)(compactableHexes);
H3_MEMORY(free)(remainingHexes);
H3_MEMORY(free)(hashSetArray);
return E_FAILED;
}
H3Index tempIndex =
hashSetArray[loc] & H3_RESERVED_MASK_NEGATIVE;
if (tempIndex == parent) {
int count =
H3_GET_RESERVED_BITS(hashSetArray[loc]) + 1;
if (count == 7) {
isUncompactable = false;
}
break;
} else {
loc = (loc + 1) % numRemainingHexes;
}
loopCount++;
} while (hashSetArray[loc] != parent);
}
if (isUncompactable) {
compactedSetOffset[uncompactableCount] = remainingHexes[i];
uncompactableCount++;
}
}
}
// Set up for the next loop
memset(hashSetArray, 0, numHexes * sizeof(H3Index));
compactedSetOffset += uncompactableCount;
memcpy(remainingHexes, compactableHexes,
compactableCount * sizeof(H3Index));
numRemainingHexes = compactableCount;
H3_MEMORY(free)(compactableHexes);
}
H3_MEMORY(free)(remainingHexes);
H3_MEMORY(free)(hashSetArray);
return E_SUCCESS;
}