From 12fd76a2d1d4e985c18d3daf9db72309029c4262 Mon Sep 17 00:00:00 2001 From: Justin Hwang Date: Wed, 4 Jun 2025 15:05:23 -0400 Subject: [PATCH] feat: add gridRing and _gridRingInternal --- CMakeLists.txt | 2 + CMakeTests.cmake | 2 + src/apps/filters/h3.c | 10 +- src/apps/testapps/testGridRing.c | 304 +++++++++++++++++++++++ src/apps/testapps/testGridRingInternal.c | 62 +++++ src/apps/testapps/testGridRingUnsafe.c | 16 +- src/apps/testapps/testH3Memory.c | 34 +++ src/h3lib/include/algos.h | 3 + src/h3lib/include/h3api.h.in | 12 +- src/h3lib/lib/algos.c | 103 +++++++- 10 files changed, 537 insertions(+), 11 deletions(-) create mode 100644 src/apps/testapps/testGridRing.c create mode 100644 src/apps/testapps/testGridRingInternal.c diff --git a/CMakeLists.txt b/CMakeLists.txt index a83290557..b59b470f1 100644 --- a/CMakeLists.txt +++ b/CMakeLists.txt @@ -242,6 +242,8 @@ set(OTHER_SOURCE_FILES src/apps/testapps/testGetIcosahedronFaces.c src/apps/testapps/testLatLng.c src/apps/testapps/testLatLngInternal.c + src/apps/testapps/testGridRing.c + src/apps/testapps/testGridRingInternal.c src/apps/testapps/testGridRingUnsafe.c src/apps/testapps/testH3SetToVertexGraphInternal.c src/apps/testapps/testBBoxInternal.c diff --git a/CMakeTests.cmake b/CMakeTests.cmake index 62b60fab1..f2331558c 100644 --- a/CMakeTests.cmake +++ b/CMakeTests.cmake @@ -204,6 +204,8 @@ add_h3_test(testCellToBoundaryEdgeCases add_h3_test(testCompactCells src/apps/testapps/testCompactCells.c) add_h3_test(testGridDisk src/apps/testapps/testGridDisk.c) add_h3_test(testGridDiskInternal src/apps/testapps/testGridDiskInternal.c) +add_h3_test(testGridRing src/apps/testapps/testGridRing.c) +add_h3_test(testGridRingInternal src/apps/testapps/testGridRingInternal.c) add_h3_test(testGridRingUnsafe src/apps/testapps/testGridRingUnsafe.c) add_h3_test(testGridDisksUnsafe src/apps/testapps/testGridDisksUnsafe.c) add_h3_test(testCellToParent src/apps/testapps/testCellToParent.c) diff --git a/src/apps/filters/h3.c b/src/apps/filters/h3.c index bf1e507b2..8e1a17367 100644 --- a/src/apps/filters/h3.c +++ b/src/apps/filters/h3.c @@ -642,14 +642,18 @@ SUBCOMMAND(gridRing, .helpText = "Maximum grid distance for the output set"}; Arg *args[] = {&gridRingArg, &helpArg, &cellArg, &kArg, &formatArg}; PARSE_SUBCOMMAND(argc, argv, args); - int64_t len = k == 0 ? 1 : 6 * k; // The length is fixed for gridRingUnsafe - // since it doesn't support pentagons + int64_t len; + H3Error err = H3_EXPORT(maxGridRingSize)(k, &len); + if (err) { + fprintf(stderr, "Invalid k"); + exit(1); + } H3Index *out = calloc(len, sizeof(H3Index)); if (out == NULL) { fprintf(stderr, "Failed to allocate memory for the output H3 indexes"); exit(1); } - H3Error err = H3_EXPORT(gridRingUnsafe)(cell, k, out); + err = H3_EXPORT(gridRingUnsafe)(cell, k, out); if (err) { // For the CLI, we'll just do things less efficiently if there's an // error here. If you use `gridDiskDistances` and only pay attention to diff --git a/src/apps/testapps/testGridRing.c b/src/apps/testapps/testGridRing.c new file mode 100644 index 000000000..29984e05e --- /dev/null +++ b/src/apps/testapps/testGridRing.c @@ -0,0 +1,304 @@ +/* + * Copyright 2025 Uber Technologies, Inc. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include + +#include "algos.h" +#include "constants.h" +#include "h3Index.h" +#include "h3api.h" +#include "test.h" + +SUITE(gridRing) { + LatLng sf = {0.659966917655, 2 * 3.14159 - 2.1364398519396}; + H3Index sfHex; + t_assertSuccess(H3_EXPORT(latLngToCell)(&sf, 9, &sfHex)); + + TEST(identityGridRing) { + H3Index k0[] = {0}; + t_assertSuccess(H3_EXPORT(gridRing)(sfHex, 0, k0)); + t_assert(k0[0] == sfHex, "generated identity k-ring"); + } + + TEST(ring1) { + H3Index k1[] = {0, 0, 0, 0, 0, 0}; + H3Index expectedK1[] = {0x89283080ddbffff, 0x89283080c37ffff, + 0x89283080c27ffff, 0x89283080d53ffff, + 0x89283080dcfffff, 0x89283080dc3ffff}; + t_assertSuccess(H3_EXPORT(gridRing)(sfHex, 1, k1)); + + for (int i = 0; i < 6; i++) { + t_assert(k1[i] != 0, "index is populated"); + int inList = 0; + for (int j = 0; j < 6; j++) { + if (k1[i] == expectedK1[j]) { + inList++; + } + } + t_assert(inList == 1, "index found in expected set"); + } + } + + TEST(ring2) { + H3Index k2[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}; + H3Index expectedK2[] = { + 0x89283080ca7ffff, 0x89283080cafffff, 0x89283080c33ffff, + 0x89283080c23ffff, 0x89283080c2fffff, 0x89283080d5bffff, + 0x89283080d43ffff, 0x89283080d57ffff, 0x89283080d1bffff, + 0x89283080dc7ffff, 0x89283080dd7ffff, 0x89283080dd3ffff}; + t_assertSuccess(H3_EXPORT(gridRing)(sfHex, 2, k2)); + + for (int i = 0; i < 12; i++) { + t_assert(k2[i] != 0, "index is populated"); + int inList = 0; + for (int j = 0; j < 12; j++) { + if (k2[i] == expectedK2[j]) { + inList++; + } + } + t_assert(inList == 1, "index found in expected set"); + } + } + + TEST(gridRing0_PolarPentagon) { + H3Index polar; + setH3Index(&polar, 0, 4, 0); + H3Index k2[] = {0, 0, 0, 0, 0, 0}; + H3Index expectedK2[] = {0x8007fffffffffff, 0x8001fffffffffff, + 0x8011fffffffffff, 0x801ffffffffffff, + 0x8019fffffffffff, 0}; + t_assertSuccess(H3_EXPORT(gridRing)(polar, 1, k2)); + + int k2present = 0; + for (int i = 0; i < 6; i++) { + if (k2[i] != 0) { + k2present++; + int inList = 0; + for (int j = 0; j < 6; j++) { + if (k2[i] == expectedK2[j]) { + inList++; + } + } + t_assert(inList == 1, "index found in expected set"); + } + } + t_assert(k2present == 5, "pentagon has 5 neighbors in k-ring 1"); + } + + TEST(gridRing1_PolarPentagon) { + H3Index polar; + setH3Index(&polar, 1, 4, 0); + H3Index k2[] = {0, 0, 0, 0, 0, 0}; + H3Index expectedK2[] = {0x81093ffffffffff, 0x81097ffffffffff, + 0x8108fffffffffff, 0x8108bffffffffff, + 0x8109bffffffffff, 0}; + t_assertSuccess(H3_EXPORT(gridRing)(polar, 1, k2)); + + int k2present = 0; + for (int i = 0; i < 6; i++) { + if (k2[i] != 0) { + k2present++; + int inList = 0; + for (int j = 0; j < 6; j++) { + if (k2[i] == expectedK2[j]) { + inList++; + } + } + t_assert(inList == 1, "index found in expected set"); + } + } + t_assert(k2present == 5, "pentagon has 5 neighbors in k-ring 1"); + } + + TEST(gridRing1_PolarPentagon_k3) { + H3Index polar; + setH3Index(&polar, 1, 4, 0); + H3Index k2[18] = {0}; + H3Index expectedK2[18] = {0x811fbffffffffff, + 0x81003ffffffffff, + 0x81183ffffffffff, + 0x8111bffffffffff, + 0x81067ffffffffff, + 0x811e7ffffffffff, + 0x8101bffffffffff, + 0x81107ffffffffff, + 0x81063ffffffffff, + 0x811e3ffffffffff, + 0x8119bffffffffff, + 0x81103ffffffffff, + 0x81007ffffffffff, + 0x81187ffffffffff, + 0x8107bffffffffff, + 0, + 0, + 0}; + t_assertSuccess(H3_EXPORT(gridRing)(polar, 3, k2)); + + int k2present = 0; + for (int i = 0; i < 18; i++) { + if (k2[i] != 0) { + k2present++; + int inList = 0; + for (int j = 0; j < 18; j++) { + if (k2[i] == expectedK2[j]) { + inList++; + } + } + t_assert(inList == 1, "index found in expected set"); + } + } + t_assert(k2present == 15, "pentagon has 15 neighbors in k-ring 3"); + } + + TEST(gridRing1_Pentagon_k4) { + H3Index pent; + setH3Index(&pent, 1, 14, 0); + H3Index k2[24] = {0}; + H3Index expectedK2[24] = { + 0x81227ffffffffff, + 0x81293ffffffffff, + 0x8136bffffffffff, + 0x81167ffffffffff, + 0x81477ffffffffff, + 0x810dbffffffffff, + 0x81473ffffffffff, + 0x81237ffffffffff, + 0x81127ffffffffff, + 0x8126bffffffffff, + 0x81177ffffffffff, + 0x810d3ffffffffff, + 0x8150fffffffffff, + 0x8102fffffffffff, + 0x8129bffffffffff, + 0x8102bffffffffff, + 0x81507ffffffffff, + 0x8136fffffffffff, + 0x8127bffffffffff, + 0x81137ffffffffff, + 0, + 0, + 0, + 0, + }; + t_assertSuccess(H3_EXPORT(gridRing)(pent, 4, k2)); + + int k2present = 0; + for (int i = 0; i < 24; i++) { + if (k2[i] != 0) { + k2present++; + int inList = 0; + for (int j = 0; j < 24; j++) { + if (k2[i] == expectedK2[j]) { + inList++; + } + } + t_assert(inList == 1, "index found in expected set"); + } + } + t_assert(k2present == 20, "pentagon has 20 neighbors in k-ring 4"); + } + + TEST(gridRing_matches_gridDiskDistancesSafe) { + for (int res = 0; res < 2; res++) { + for (int i = 0; i < NUM_BASE_CELLS; i++) { + H3Index bc; + setH3Index(&bc, 0, i, 0); + int64_t childrenSz; + t_assertSuccess( + H3_EXPORT(uncompactCellsSize)(&bc, 1, res, &childrenSz)); + H3Index *children = calloc(childrenSz, sizeof(H3Index)); + t_assertSuccess(H3_EXPORT(uncompactCells)(&bc, 1, children, + childrenSz, res)); + + for (int j = 0; j < childrenSz; j++) { + if (children[j] == 0) { + continue; + } + + for (int k = 0; k < 3; k++) { + int64_t kSz; + t_assertSuccess(H3_EXPORT(maxGridDiskSize)(k, &kSz)); + + int64_t ringSize; + t_assertSuccess( + H3_EXPORT(maxGridRingSize)(k, &ringSize)); + + H3Index *ring = calloc(ringSize, sizeof(H3Index)); + t_assertSuccess( + H3_EXPORT(gridRing)(children[j], k, ring)); + + H3Index *internalNeighbors = + calloc(kSz, sizeof(H3Index)); + int *internalDistances = calloc(kSz, sizeof(int)); + t_assertSuccess(H3_EXPORT(gridDiskDistancesSafe)( + children[j], k, internalNeighbors, + internalDistances)); + + int found = 0; + int internalFound = 0; + for (int iRing = 0; iRing < ringSize; iRing++) { + if (ring[iRing] != 0) { + found++; + + for (int64_t iInternal = 0; iInternal < kSz; + iInternal++) { + if (internalNeighbors[iInternal] == + ring[iRing]) { + internalFound++; + + t_assert( + internalDistances[iInternal] == k, + "Ring and internal agree on " + "distance"); + + break; + } + } + + t_assert(found == internalFound, + "Ring and internal implementations " + "produce same output"); + } + } + free(internalNeighbors); + free(internalDistances); + free(ring); + } + } + + free(children); + } + } + } + + TEST(maxGridRingSize_invalid) { + int64_t sz; + t_assert(H3_EXPORT(maxGridRingSize)(-1, &sz) == E_DOMAIN, + "negative k is invalid"); + } + + TEST(maxGridRingSize_identity) { + int64_t sz; + t_assertSuccess(H3_EXPORT(maxGridRingSize)(0, &sz)); + t_assert(sz == 1, "k = 0 returns 1"); + } + + TEST(maxGridRingSize) { + int64_t sz; + t_assertSuccess(H3_EXPORT(maxGridRingSize)(2, &sz)); + t_assert(sz == 12, "k = 2 returns 12"); + } +} diff --git a/src/apps/testapps/testGridRingInternal.c b/src/apps/testapps/testGridRingInternal.c new file mode 100644 index 000000000..35af3aab2 --- /dev/null +++ b/src/apps/testapps/testGridRingInternal.c @@ -0,0 +1,62 @@ +/* + * Copyright 2025 Uber Technologies, Inc. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include + +#include "algos.h" +#include "constants.h" +#include "h3Index.h" +#include "test.h" + +SUITE(gridRingInternal) { + LatLng sf = {0.659966917655, 2 * 3.14159 - 2.1364398519396}; + H3Index sfHex; + t_assertSuccess(H3_EXPORT(latLngToCell)(&sf, 9, &sfHex)); + + TEST(identityGridRing) { + H3Index k0[] = {0}; + t_assertSuccess(_gridRingInternal(sfHex, 0, k0)); + t_assert(k0[0] == sfHex, "generated identity k-ring"); + } + + TEST(negativeK) { + H3Index k0[] = {0}; + t_assert(_gridRingInternal(sfHex, -1, k0) == E_DOMAIN, + "Should return an error when k is negative"); + } + + TEST(gridDiskInvalid) { + const int k = 1000; + int64_t kSz; + t_assertSuccess(H3_EXPORT(maxGridDiskSize)(k, &kSz)); + H3Index *neighbors = calloc(kSz, sizeof(H3Index)); + t_assert(_gridRingInternal(0x7fffffffffffffff, k, neighbors) == + E_CELL_INVALID, + "_gridRingInternal returns error for invalid input"); + free(neighbors); + } + + TEST(gridDiskInvalidDigit) { + const int k = 2; + int64_t kSz; + t_assertSuccess(H3_EXPORT(maxGridDiskSize)(k, &kSz)); + H3Index *neighbors = calloc(kSz, sizeof(H3Index)); + t_assert(_gridRingInternal(0x4d4b00fe5c5c3030, k, neighbors) == + E_CELL_INVALID, + "_gridRingInternal returns error for invalid input"); + free(neighbors); + } +} diff --git a/src/apps/testapps/testGridRingUnsafe.c b/src/apps/testapps/testGridRingUnsafe.c index 24c01d75d..481ad6100 100644 --- a/src/apps/testapps/testGridRingUnsafe.c +++ b/src/apps/testapps/testGridRingUnsafe.c @@ -19,6 +19,7 @@ #include "algos.h" #include "constants.h" #include "h3Index.h" +#include "h3api.h" #include "test.h" SUITE(gridRingUnsafe) { @@ -26,6 +27,12 @@ SUITE(gridRingUnsafe) { H3Index sfHex; t_assertSuccess(H3_EXPORT(latLngToCell)(&sf, 9, &sfHex)); + TEST(negativeK) { + H3Index k0[] = {0}; + t_assert(H3_EXPORT(gridRingUnsafe)(sfHex, -1, k0) == E_DOMAIN, + "Should return an error when k is negative"); + } + TEST(identityGridRing) { H3Index k0[] = {0}; t_assertSuccess(H3_EXPORT(gridRingUnsafe)(sfHex, 0, k0)); @@ -112,11 +119,14 @@ SUITE(gridRingUnsafe) { } for (int k = 0; k < 3; k++) { - int ringSz = k != 0 ? 6 * k : 1; int64_t kSz; t_assertSuccess(H3_EXPORT(maxGridDiskSize)(k, &kSz)); - H3Index *ring = calloc(ringSz, sizeof(H3Index)); + int64_t ringSize; + t_assertSuccess( + H3_EXPORT(maxGridRingSize)(k, &ringSize)); + + H3Index *ring = calloc(ringSize, sizeof(H3Index)); H3Error failed = H3_EXPORT(gridRingUnsafe)(children[j], k, ring); @@ -130,7 +140,7 @@ SUITE(gridRingUnsafe) { int found = 0; int internalFound = 0; - for (int iRing = 0; iRing < ringSz; iRing++) { + for (int iRing = 0; iRing < ringSize; iRing++) { if (ring[iRing] != 0) { found++; diff --git a/src/apps/testapps/testH3Memory.c b/src/apps/testapps/testH3Memory.c index 76687b17d..e8c713a4b 100644 --- a/src/apps/testapps/testH3Memory.c +++ b/src/apps/testapps/testH3Memory.c @@ -128,6 +128,40 @@ SUITE(h3Memory) { free(gridDiskOutput); } + TEST(gridRing) { + const int k = 2; + int64_t ringSize; + t_assertSuccess(H3_EXPORT(maxGridRingSize)(k, &ringSize)); + H3Index *gridRingOutput = calloc(ringSize, sizeof(H3Index)); + + resetMemoryCounters(0); + t_assertSuccess(H3_EXPORT(gridRing)(sunnyvale, k, gridRingOutput)); + t_assert(actualAllocCalls == 0, "gridRing did not call alloc"); + t_assert(actualFreeCalls == 0, "gridRing did not call free"); + + resetMemoryCounters(2); + t_assertSuccess(H3_EXPORT(gridRing)(pentagon, k, gridRingOutput)); + t_assert(actualAllocCalls == 2, "gridRing called alloc 2 times"); + t_assert(actualFreeCalls == 2, "gridRing called free 2 times"); + + resetMemoryCounters(0); + failAlloc = true; + t_assert( + H3_EXPORT(gridRing)(pentagon, k, gridRingOutput) == E_MEMORY_ALLOC, + "gridRing returns E_MEMORY_ALLOC"); + t_assert(actualAllocCalls == 1, "gridRing called alloc 1 time"); + t_assert(actualFreeCalls == 0, "gridRing did not call free"); + + resetMemoryCounters(1); + t_assert( + H3_EXPORT(gridRing)(pentagon, k, gridRingOutput) == E_MEMORY_ALLOC, + "gridRing returns E_MEMORY_ALLOC"); + t_assert(actualAllocCalls == 2, "gridRing called alloc 2 times"); + t_assert(actualFreeCalls == 1, "gridRing called free 1 time"); + + free(gridRingOutput); + } + TEST(compactCells) { int k = 9; int64_t hexCount; diff --git a/src/h3lib/include/algos.h b/src/h3lib/include/algos.h index 740343861..0589c1ecc 100644 --- a/src/h3lib/include/algos.h +++ b/src/h3lib/include/algos.h @@ -53,4 +53,7 @@ H3Error _getEdgeHexagons(const GeoLoop *geoloop, int64_t numHexagons, int res, // The safe gridDiskDistances algorithm. H3Error _gridDiskDistancesInternal(H3Index origin, int k, H3Index *out, int *distances, int64_t maxIdx, int curK); + +// The safe gridRing algorithm. +H3Error _gridRingInternal(H3Index origin, int k, H3Index *out); #endif diff --git a/src/h3lib/include/h3api.h.in b/src/h3lib/include/h3api.h.in index 466762c1a..ae1ab994f 100644 --- a/src/h3lib/include/h3api.h.in +++ b/src/h3lib/include/h3api.h.in @@ -282,12 +282,18 @@ DECLSPEC H3Error H3_EXPORT(gridDiskDistances)(H3Index origin, int k, H3Index *out, int *distances); /** @} */ -/** @defgroup gridRingUnsafe gridRingUnsafe - * Functions for gridRingUnsafe +/** @defgroup gridRing gridRing + * Functions for gridRing * @{ */ -/** @brief hollow hexagon ring at some origin */ +/** @brief maximum number of hexagons in hollow k-ring */ +DECLSPEC H3Error H3_EXPORT(maxGridRingSize)(int k, int64_t *out); + +/** @brief hollow hexagon ring k distance from origin */ DECLSPEC H3Error H3_EXPORT(gridRingUnsafe)(H3Index origin, int k, H3Index *out); + +/** @brief hollow hexagon ring k distance from origin */ +DECLSPEC H3Error H3_EXPORT(gridRing)(H3Index origin, int k, H3Index *out); /** @} */ /** @defgroup polygonToCells polygonToCells diff --git a/src/h3lib/lib/algos.c b/src/h3lib/lib/algos.c index 1b20bf5ef..f21da3b3c 100644 --- a/src/h3lib/lib/algos.c +++ b/src/h3lib/lib/algos.c @@ -334,6 +334,103 @@ H3Error H3_EXPORT(gridDiskDistancesSafe)(H3Index origin, int k, H3Index *out, return _gridDiskDistancesInternal(origin, k, out, distances, maxIdx, 0); } +/** + * Maximum number of cells that result from the gridRing algorithm with the + * given k. + * + * @param k k value, k >= 0. + * @param out size in indexes + */ +H3Error H3_EXPORT(maxGridRingSize)(int k, int64_t *out) { + if (k < 0) { + return E_DOMAIN; + } + if (k == 0) { + *out = 1; + return E_SUCCESS; + } + *out = 6 * (int64_t)k; + return E_SUCCESS; +} + +/** + * Returns the "hollow" ring of hexagons at exactly grid distance k from + * the origin hexagon. In particular, k=0 returns just the origin hexagon. + * + * Elements of the output array may be left zero, as can happen when crossing a + * pentagon. + * + * @param origin Origin location. + * @param k k >= 0 + * @param out Array which must be of size 6 * k (or 1 if k == 0) + * @return 0 if successful; nonzero otherwise. + */ +H3Error H3_EXPORT(gridRing)(H3Index origin, int k, H3Index *out) { + // Optimistically try the faster gridDiskUnsafe algorithm first + const H3Error failed = H3_EXPORT(gridRingUnsafe)(origin, k, out); + if (!failed) { + return E_SUCCESS; + } + // Fast algo failed, fall back to slower, correct algo + // and also wipe out array because contents untrustworthy + memset(out, 0, 6 * k * sizeof(H3Index)); + return _gridRingInternal(origin, k, out); +} + +/** + * Internal algorithm for the safe but slow version of gridRing + * + * This function uses _gridDiskDistancesInternal to get all cells up to distance + * k, then filters those results to include only cells exactly at distance k. + * + * @param origin Origin cell. + * @param k Exact distance to filter for. + * @param out Array which must be of size 6 * k (or 1 if k == 0). This is where + * the final filtered results will be placed. + * @return H3Error indicating success or failure. + */ +H3Error _gridRingInternal(H3Index origin, int k, H3Index *out) { + // Short-circuit on 'identity' ring + if (k == 0) { + out[0] = origin; + return E_SUCCESS; + } + + int64_t maxIdx; + H3Error err = H3_EXPORT(maxGridDiskSize)(k, &maxIdx); + if (err) { + return err; + } + + H3Index *disk_out = H3_MEMORY(calloc)(maxIdx, sizeof(H3Index)); + if (!disk_out) { + return E_MEMORY_ALLOC; + } + int *disk_distances = H3_MEMORY(calloc)(maxIdx, sizeof(int)); + if (!disk_distances) { + H3_MEMORY(free)(disk_out); + return E_MEMORY_ALLOC; + } + + err = _gridDiskDistancesInternal(origin, k, disk_out, disk_distances, + maxIdx, 0); + if (err) { + H3_MEMORY(free)(disk_out); + H3_MEMORY(free)(disk_distances); + return err; + } + + int current_idx = 0; + for (int64_t i = 0; i < maxIdx; ++i) { + if (disk_out[i] != 0 && disk_distances[i] == k) { + out[current_idx++] = disk_out[i]; + } + } + H3_MEMORY(free)(disk_out); + H3_MEMORY(free)(disk_distances); + return E_SUCCESS; +} + /** * Returns the hexagon index neighboring the origin, in the direction dir. * @@ -690,6 +787,9 @@ H3Error H3_EXPORT(gridDisksUnsafe)(H3Index *h3Set, int length, int k, * @return 0 if successful; nonzero otherwise. */ H3Error H3_EXPORT(gridRingUnsafe)(H3Index origin, int k, H3Index *out) { + if (k < 0) { + return E_DOMAIN; + } // Short-circuit on 'identity' ring if (k == 0) { out[0] = origin; @@ -755,9 +855,8 @@ H3Error H3_EXPORT(gridRingUnsafe)(H3Index origin, int k, H3Index *out) { // failure. if (lastIndex != origin) { return E_PENTAGON; - } else { - return E_SUCCESS; } + return E_SUCCESS; } /**