in src/h3lib/lib/h3Index.c [280:448]
int H3_EXPORT(compact)(const H3Index* h3Set, H3Index* compactedSet,
const int numHexes) {
if (numHexes == 0) {
return COMPACT_SUCCESS;
}
int res = H3_GET_RESOLUTION(h3Set[0]);
if (res == 0) {
// No compaction possible, just copy the set to output
for (int i = 0; i < numHexes; i++) {
compactedSet[i] = h3Set[i];
}
return COMPACT_SUCCESS;
}
H3Index* remainingHexes = H3_MEMORY(malloc)(numHexes * sizeof(H3Index));
if (!remainingHexes) {
return COMPACT_ALLOC_FAILED;
}
memcpy(remainingHexes, h3Set, numHexes * sizeof(H3Index));
H3Index* hashSetArray = H3_MEMORY(calloc)(numHexes, sizeof(H3Index));
if (!hashSetArray) {
H3_MEMORY(free)(remainingHexes);
return COMPACT_ALLOC_FAILED;
}
H3Index* compactedSetOffset = compactedSet;
int numRemainingHexes = numHexes;
while (numRemainingHexes) {
res = H3_GET_RESOLUTION(remainingHexes[0]);
int parentRes = res - 1;
// 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 (int i = 0; i < numRemainingHexes; i++) {
H3Index currIndex = remainingHexes[i];
if (currIndex != 0) {
H3Index parent = H3_EXPORT(h3ToParent)(currIndex, parentRes);
// Modulus hash the parent into the temp array
int loc = (int)(parent % numRemainingHexes);
int loopCount = 0;
while (hashSetArray[loc] != 0) {
if (loopCount > numRemainingHexes) { // LCOV_EXCL_BR_LINE
// LCOV_EXCL_START
// 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 COMPACT_LOOP_EXCEEDED;
// LCOV_EXCL_STOP
}
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(h3IsPentagon)(
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 COMPACT_DUPLICATE;
}
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
int compactableCount = 0;
int 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 COMPACT_ALLOC_FAILED;
}
for (int 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(h3IsPentagon)(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
int uncompactableCount = 0;
for (int i = 0; i < numRemainingHexes; i++) {
H3Index currIndex = remainingHexes[i];
if (currIndex != H3_NULL) {
H3Index parent = H3_EXPORT(h3ToParent)(currIndex, parentRes);
// Modulus hash the parent into the temp array
// to determine if this index was included in
// the compactableHexes array
int loc = (int)(parent % numRemainingHexes);
int loopCount = 0;
bool isUncompactable = true;
do {
if (loopCount > numRemainingHexes) { // LCOV_EXCL_BR_LINE
// LCOV_EXCL_START
// 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 COMPACT_LOOP_EXCEEDED;
// LCOV_EXCL_STOP
}
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 COMPACT_SUCCESS;
}