8000 Fix segfault in `removeVertexNode` due to negative hash by isaacbrodsky · Pull Request #94 · uber/h3 · GitHub
[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to content

Fix segfault in removeVertexNode due to negative hash #94

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 1 commit into from
Jul 18, 2018
Merged

Fix segfault in removeVertexNode due to negative hash #94

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
1 commit
Select commit
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading 8000
Diff view
Diff view
1 change: 1 addition & 0 deletions CHANGELOG.md
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -11,6 +11,7 @@ The public API of this library consists of the functions declared in file
### Fixed
- Ensured unused memory is cleared for pentagon children. (#84)
- Fixed compiler warnings in `h3ToGeoHier` and `h3ToGeoBoundaryHier`. (#90)
- Fixed a segfault in `h3SetToLinkedGeo` (#94)
### Changed
- Warnings are not errors by default. (#90)

Expand Down
122 changes: 60 additions & 62 deletions src/apps/testapps/testH3SetToLinkedGeo.c
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -1,5 +1,5 @@
/*
* Copyright 2017 Uber Technologies, Inc.
* Copyright 2017-2018 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.
Expand Down Expand Up @@ -29,130 +29,123 @@ H3Index* makeSet(char** hexes, int numHexes) {
BEGIN_TESTS(h3SetToLinkedGeo);

TEST(empty) {
LinkedGeoPolygon* polygon = calloc(1, sizeof(LinkedGeoPolygon));
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

heh

LinkedGeoPolygon polygon;
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Nice!

int numHexes = 0;
H3Index* set = makeSet(NULL, numHexes);

H3_EXPORT(h3SetToLinkedGeo)(set, numHexes, polygon);
H3_EXPORT(h3SetToLinkedGeo)(set, numHexes, &polygon);

t_assert(countLinkedLoops(polygon) == 0, "No loops added to polygon");
t_assert(countLinkedLoops(&polygon) == 0, "No loops added to polygon");

H3_EXPORT(destroyLinkedPolygon)(polygon);
H3_EXPORT(destroyLinkedPolygon)(&polygon);
free(set);
free(polygon);
}

TEST(singleHex) {
LinkedGeoPolygon* polygon = calloc(1, sizeof(LinkedGeoPolygon));
LinkedGeoPolygon polygon;
char* hexes[] = {"890dab6220bffff"};
int numHexes = sizeof(hexes) / sizeof(hexes[0]);
H3Index* set = makeSet(hexes, numHexes);

H3_EXPORT(h3SetToLinkedGeo)(set, numHexes, polygon);
H3_EXPORT(h3SetToLinkedGeo)(set, numHexes, &polygon);

t_assert(countLinkedLoops(polygon) == 1, "1 loop added to polygon");
t_assert(countLinkedCoords(polygon->first) == 6, "6 coords added to loop");
t_assert(countLinkedLoops(&polygon) == 1, "1 loop added to polygon");
t_assert(countLinkedCoords(polygon.first) == 6, "6 coords added to loop");

H3_EXPORT(destroyLinkedPolygon)(polygon);
H3_EXPORT(destroyLinkedPolygon)(&polygon);
free(set);
free(polygon);
}

TEST(contiguous2) {
LinkedGeoPolygon* polygon = calloc(1, sizeof(LinkedGeoPolygon));
LinkedGeoPolygon polygon;
char* hexes[] = {"8928308291bffff", "89283082957ffff"};
int numHexes = sizeof(hexes) / sizeof(hexes[0]);
H3Index* set = makeSet(hexes, numHexes);

H3_EXPORT(h3SetToLinkedGeo)(set, numHexes, polygon);
H3_EXPORT(h3SetToLinkedGeo)(set, numHexes, &polygon);

t_assert(countLinkedLoops(polygon) == 1, "1 loop added to polygon");
t_assert(countLinkedCoords(polygon->first) == 10,
t_assert(countLinkedLoops(&polygon) == 1, "1 loop added to polygon");
t_assert(countLinkedCoords(polygon.first) == 10,
"All coords added to loop except 2 shared");

H3_EXPORT(destroyLinkedPolygon)(polygon);
H3_EXPORT(destroyLinkedPolygon)(&polygon);
free(set);
free(polygon);
}

// TODO: This test asserts incorrect behavior - we should be creating multiple
// polygons, each with their own single loop. Update when the algorithm is
// corrected.
TEST(nonContiguous2) {
LinkedGeoPolygon* polygon = calloc(1, sizeof(LinkedGeoPolygon));
LinkedGeoPolygon polygon;
char* hexes[] = {"8928308291bffff", "89283082943ffff"};
int numHexes = sizeof(hexes) / sizeof(hexes[0]);
H3Index* set = makeSet(hexes, numHexes);

H3_EXPORT(h3SetToLinkedGeo)(set, numHexes, polygon);
H3_EXPORT(h3SetToLinkedGeo)(set, numHexes, &polygon);

t_assert(countLinkedLoops(polygon) == 2, "2 loops added to polygon");
t_assert(countLinkedCoords(polygon->first) == 6,
t_assert(countLinkedLoops(&polygon) == 2, "2 loops added to polygon");
t_assert(countLinkedCoords(polygon.first) == 6,
"All coords for one hex added to first loop");
t_assert(countLinkedCoords(polygon->first->next) == 6,
t_assert(countLinkedCoords(polygon.first->next) == 6,
"All coords for one hex added to second loop");

H3_EXPORT(destroyLinkedPolygon)(polygon);
H3_EXPORT(destroyLinkedPolygon)(&polygon);
free(set);
free(polygon);
}

TEST(contiguous3) {
LinkedGeoPolygon* polygon = calloc(1, sizeof(LinkedGeoPolygon));
LinkedGeoPolygon polygon;
char* hexes[] = {"8928308288bffff", "892830828d7ffff", "8928308289bffff"};
int numHexes = sizeof(hexes) / sizeof(hexes[0]);
H3Index* set = makeSet(hexes, numHexes);

H3_EXPORT(h3SetToLinkedGeo)(set, numHexes, polygon);
H3_EXPORT(h3SetToLinkedGeo)(set, numHexes, &polygon);

t_assert(countLinkedLoops(polygon) == 1, "1 loop added to polygon");
t_assert(countLinkedCoords(polygon->first) == 12,
t_assert(countLinkedLoops(&polygon) == 1, "1 loop added to polygon");
t_assert(countLinkedCoords(polygon.first) == 12,
"All coords added to loop except 6 shared");

H3_EXPORT(destroyLinkedPolygon)(polygon);
H3_EXPORT(destroyLinkedPolygon)(&polygon);
free(set);
free(polygon);
}

TEST(hole) {
LinkedGeoPolygon* polygon = calloc(1, sizeof(LinkedGeoPolygon));
LinkedGeoPolygon polygon;
char* hexes[] = {"892830828c7ffff", "892830828d7ffff", "8928308289bffff",
"89283082813ffff", "8928308288fffff", "89283082883ffff"};
int numHexes = sizeof(hexes) / sizeof(hexes[0]);
H3Index* set = makeSet(hexes, numHexes);

H3_EXPORT(h3SetToLinkedGeo)(set, numHexes, polygon);
H3_EXPORT(h3SetToLinkedGeo)(set, numHexes, &polygon);

t_assert(countLinkedLoops(polygon) == 2, "2 loops added to polygon");
t_assert(countLinkedCoords(polygon->first) == 6 * 3,
t_assert(countLinkedLoops(&polygon) == 2, "2 loops added to polygon");
t_assert(countLinkedCoords(polygon.first) == 6 * 3,
"All outer coords added to first loop");
t_assert(countLinkedCoords(polygon->first->next) == 6,
t_assert(countLinkedCoords(polygon.first->next) == 6,
"All inner coords added to second loop");

H3_EXPORT(destroyLinkedPolygon)(polygon);
H3_EXPORT(destroyLinkedPolygon)(&polygon);
free(set);
free(polygon);
}

TEST(pentagon) {
LinkedGeoPolygon* polygon = calloc(1, sizeof(LinkedGeoPolygon));
LinkedGeoPolygon polygon;
char* hexes[] = {"851c0003fffffff"};
int numHexes = sizeof(hexes) / sizeof(hexes[0]);
H3Index* set = makeSet(hexes, numHexes);

H3_EXPORT(h3SetToLinkedGeo)(set, numHexes, polygon);
H3_EXPORT(h3SetToLinkedGeo)(set, numHexes, &polygon);

t_assert(countLinkedLoops(polygon) == 1, "1 loop added to polygon");
t_assert(countLinkedCoords(polygon->first) == 10,
t_assert(countLinkedLoops(&polygon) == 1, "1 loop added to polygon");
t_assert(countLinkedCoords(polygon.first) == 10,
"10 coords (distorted pentagon) added to loop");

H3_EXPORT(destroyLinkedPolygon)(polygon);
H3_EXPORT(destroyLinkedPolygon)(&polygon);
free(set);
free(polygon);
}

TEST(2Ring) {
LinkedGeoPolygon* polygon = calloc(1, sizeof(LinkedGeoPolygon));
LinkedGeoPolygon polygon;
// 2-ring, in order returned by k-ring algo
char* hexes[] = {"8930062838bffff", "8930062838fffff", "89300628383ffff",
"8930062839bffff", "893006283d7ffff", "893006283c7ffff",
Expand All @@ -164,19 +157,18 @@ TEST(2Ring) {
int numHexes = sizeof(hexes) / sizeof(hexes[0]);
H3Index* set = makeSet(hexes, numHexes);

H3_EXPORT(h3SetToLinkedGeo)(set, numHexes, polygon);
H3_EXPORT(h3SetToLinkedGeo)(set, numHexes, &polygon);

t_assert(countLinkedLoops(polygon) == 1, "1 loop added to polygon");
t_assert(countLinkedCoords(polygon->first) == (6 * (2 * 2 + 1)),
t_assert(countLinkedLoops(&polygon) == 1, "1 loop added to polygon");
t_assert(countLinkedCoords(polygon.first) == (6 * (2 * 2 + 1)),
"Expected number of coords added to loop");

H3_EXPORT(destroyLinkedPolygon)(polygon);
H3_EXPORT(destroyLinkedPolygon)(&polygon);
free(set);
free(polygon);
}

TEST(2RingUnordered) {
LinkedGeoPolygon* polygon = calloc(1, sizeof(LinkedGeoPolygon));
LinkedGeoPolygon polygon;
// 2-ring in random order
char* hexes[] = {"89300628393ffff", "89300628383ffff", "89300628397ffff",
"89300628067ffff", "89300628387ffff", "893006283bbffff",
Expand All @@ -188,32 +180,38 @@ TEST(2RingUnordered) {
int numHexes = sizeof(hexes) / sizeof(hexes[0]);
H3Index* set = makeSet(hexes, numHexes);

H3_EXPORT(h3SetToLinkedGeo)(set, numHexes, polygon);
H3_EXPORT(h3SetToLinkedGeo)(set, numHexes, &polygon);

t_assert(countLinkedLoops(polygon) == 1, "1 loop added to polygon");
t_assert(countLinkedCoords(polygon->first) == (6 * (2 * 2 + 1)),
t_assert(countLinkedLoops(&polygon) == 1, "1 loop added to polygon");
t_assert(countLinkedCoords(polygon.first) == (6 * (2 * 2 + 1)),
"Expected number of coords added to loop");

H3_EXPORT(destroyLinkedPolygon)(polygon);
H3_EXPORT(destroyLinkedPolygon)(&polygon);
free(set);
free(polygon);
}

TEST(contiguous2distorted) {
LinkedGeoPolygon* polygon = calloc(1, sizeof(LinkedGeoPolygon));
LinkedGeoPolygon polygon;
char* hexes[] = {"894cc5365afffff", "894cc536537ffff"};
int numHexes = sizeof(hexes) / sizeof(hexes[0]);
H3Index* set = makeSet(hexes, numHexes);

H3_EXPORT(h3SetToLinkedGeo)(set, numHexes, polygon);
H3_EXPORT(h3SetToLinkedGeo)(set, numHexes, &polygon);

t_assert(countLinkedLoops(polygon) == 1, "1 loop added to polygon");
t_assert(countLinkedCoords(polygon->first) == 12,
t_assert(countLinkedLoops(&polygon) == 1, "1 loop added to polygon");
t_assert(countLinkedCoords(polygon.first) == 12,
"All coords added to loop except 2 shared");

H3_EXPORT(destroyLinkedPolygon)(polygon);
H3_EXPORT(destroyLinkedPolygon)(&polygon);
free(set);
free(polygon);
}

TEST(negativeHashedCoordinates) {
LinkedGeoPolygon polygon;
H3Index set[] = {0x88ad36c547fffffl, 0x88ad36c467fffffl};
H3_EXPORT(h3SetToLinkedGeo)(set, 2, &polygon);
t_assert(countLinkedLoops(&polygon) == 2, "2 loops added to polygon");
H3_EXPORT(destroyLinkedPolygon)(&polygon);
}

END_TESTS();
14 changes: 13 additions & 1 deletion src/apps/testapps/testVertexGraph.c
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -1,5 +1,5 @@
/*
* Copyright 2017 Uber Technologies, Inc.
* Copyright 2017-2018 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.
Expand Down Expand Up @@ -27,6 +27,8 @@ GeoCoord vertex1;
GeoCoord vertex2;
GeoCoord vertex3;
GeoCoord vertex4;
GeoCoord vertex5;
GeoCoord vertex6;

BEGIN_TESTS(vertexGraph);

Expand All @@ -35,6 +37,8 @@ setGeoDegs(&vertex1, 87.372002166, 166.160981117);
setGeoDegs(&vertex2, 87.370101364, 166.160184306);
setGeoDegs(&vertex3, 87.369088356, 166.196239997);
setGeoDegs(&vertex4, 87.369975080, 166.233115768);
setGeoDegs(&vertex5, 0, 0);
setGeoDegs(&vertex6, -10, -10);

TEST(makeVertexGraph) {
VertexGraph graph;
Expand Down Expand Up @@ -63,6 +67,14 @@ TEST(vertexHash) {
}
}

TEST(vertexHashNegative) {
int numBuckets = 10;
t_assert(_hashVertex(&vertex5, 5, numBuckets) < numBuckets,
"zero vertex hashes correctly");
t_assert(_hashVertex(&vertex6, 5, numBuckets) < numBuckets,
"negative coordinates vertex hashes correctly");
}

TEST(addVertexNode) {
VertexGraph graph;
initVertexGraph(&graph, 10, 9);
Expand Down
4 changes: 2 additions & 2 deletions src/h3lib/lib/vertexGraph.c
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -1,5 +1,5 @@
/*
* Copyright 2017 Uber Technologies, Inc.
* Copyright 2017-2018 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.
Expand Down Expand Up @@ -70,7 +70,7 @@ void destroyVertexGraph(VertexGraph* graph) {
uint32_t _hashVertex(const GeoCoord* vertex, int res, int numBuckets) {
// Simple hash: Take the sum of the lat and lon with a precision level
// determined by the resolution, converted to int, modulo bucket count.
return (uint32_t)fmod((vertex->lat + vertex->lon) * pow(10, 15 - res),
return (uint32_t)fmod(fabs((vertex->lat + vertex->lon) * pow(10, 15 - res)),
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

These math functions can kill your performance. You should benchmark these changes. Also might be worth comparing to sip hash using (const char*) &vertex->lat as input. I wonder which is faster.

Copy link
Collaborator Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Even better would be to assign an index to the individual vertices, removing the need for floating point equality/hashing entirely.

Copy link
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Agreed - I'd suggest we don't focus on the performance in this diff (can't imagine that a single fabs call will make that big a difference), and come back to it when the vertex index mode change is implemented. I'll open an issue for that now.

numBuckets);
}

Expand Down
0