10357358860

Committed 12 Aug 2024 06:30PM UTC coverage: 98.826%. Remained the same

Build # 10357358860

Build Type

push

github

Committed by

web-flow

Commit Message

Website: Enable zoom in/out on mobile (#897)

* update website for mobile interaction

* format

Run Details

1635 of 1669 branches covered (97.96%)

Branch coverage included in aggregate %.

2825 of 2844 relevant lines covered (99.33%)

35359289.03 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

99.15

/src/h3lib/lib/vertexGraph.c

/*
 * Copyright 2017-2018, 2020-2021 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.
 */
/** @file vertexGraph.c
 * @brief   Data structure for storing a graph of vertices
 */

#include "vertexGraph.h"

#include <assert.h>
#include <math.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

#include "alloc.h"
#include "latLng.h"

/**
 * Initialize a new VertexGraph
 * @param graph       Graph to initialize
 * @param  numBuckets Number of buckets to include in the graph
 * @param  res        Resolution of the hexagons whose vertices we're storing
 */
void initVertexGraph(VertexGraph *graph, int numBuckets, int res) {
    if (numBuckets > 0) {
        graph->buckets = H3_MEMORY(calloc)(numBuckets, sizeof(VertexNode *));
        assert(graph->buckets != NULL);
    } else {
        graph->buckets = NULL;
    }
    graph->numBuckets = numBuckets;
    graph->size = 0;
    graph->res = res;
}

/**
 * Destroy a VertexGraph's sub-objects, freeing their memory. The caller is
 * responsible for freeing memory allocated to the VertexGraph struct itself.
 * @param graph Graph to destroy
 */
void destroyVertexGraph(VertexGraph *graph) {
    VertexNode *node;
    while ((node = firstVertexNode(graph)) != NULL) {
        removeVertexNode(graph, node);
    }
    H3_MEMORY(free)(graph->buckets);
}

/**
 * Get an integer hash for a lat/lng point, at a precision determined
 * by the current hexagon resolution.
 * TODO: Light testing suggests this might not be sufficient at resolutions
 * finer than 10. Design a better hash function if performance and collisions
 * seem to be an issue here.
 * @param  vertex     Lat/lng vertex to hash
 * @param  res        Resolution of the hexagon the vertex belongs to
 * @param  numBuckets Number of buckets in the graph
 * @return            Integer hash
 */
uint32_t _hashVertex(const LatLng *vertex, int res, int numBuckets) {
    // Simple hash: Take the sum of the lat and lng with a precision level
    // determined by the resolution, converted to int, modulo bucket count.
    return (uint32_t)fmod(fabs((vertex->lat + vertex->lng) * pow(10, 15 - res)),
                          numBuckets);
}

void _initVertexNode(VertexNode *node, const LatLng *fromVtx,
                     const LatLng *toVtx) {
    node->from = *fromVtx;
    node->to = *toVtx;
    node->next = NULL;
}

/**
 * Add a edge to the graph
 * @param graph   Graph to add node to
 * @param fromVtx Start vertex
 * @param toVtx   End vertex
 * @return        Pointer to the new node
 */
VertexNode *addVertexNode(VertexGraph *graph, const LatLng *fromVtx,
                          const LatLng *toVtx) {
    // Make the new node
    VertexNode *node = H3_MEMORY(malloc)(sizeof(VertexNode));
    assert(node != NULL);
    _initVertexNode(node, fromVtx, toVtx);
    // Determine location
    uint32_t index = _hashVertex(fromVtx, graph->res, graph->numBuckets);
    // Check whether there's an existing node in that spot
    VertexNode *currentNode = graph->buckets[index];
    if (currentNode == NULL) {
        // Set bucket to the new node
        graph->buckets[index] = node;
    } else {
        // Find the end of the list
        do {
            // Check the the edge we're adding doesn't already exist
            if (geoAlmostEqual(&currentNode->from, fromVtx) &&
                geoAlmostEqual(&currentNode->to, toVtx)) {
                // already exists, bail
                H3_MEMORY(free)(node);
                return currentNode;
            }
            if (currentNode->next != NULL) {
                currentNode = currentNode->next;
            }
        } while (currentNode->next != NULL);
        // Add the new node to the end of the list
        currentNode->next = node;
    }
    graph->size++;
    return node;
}

/**
 * Remove a node from the graph. The input node will be freed, and should
 * not be used after removal.
 * @param graph Graph to mutate
 * @param node  Node to remove
 * @return      0 on success, 1 on failure (node not found)
 */
int removeVertexNode(VertexGraph *graph, VertexNode *node) {
    // Determine location
    uint32_t index = _hashVertex(&node->from, graph->res, graph->numBuckets);
    VertexNode *currentNode = graph->buckets[index];
    int found = 0;
    if (currentNode != NULL) {
        if (currentNode == node) {
            graph->buckets[index] = node->next;
            found = 1;
        }
        // Look through the list
        while (!found && currentNode->next != NULL) {
            if (currentNode->next == node) {
                // splice the node out
                currentNode->next = node->next;
                found = 1;
            }
            currentNode = currentNode->next;
        }
    }
    if (found) {
        H3_MEMORY(free)(node);
        graph->size--;
        return 0;
    }
    // Failed to find the node
    return 1;
}

/**
 * Find the Vertex node for a given edge, if it exists
 * @param  graph   Graph to look in
 * @param  fromVtx Start vertex
 * @param  toVtx   End vertex, or NULL if we don't care
 * @return         Pointer to the vertex node, if found
 */
VertexNode *findNodeForEdge(const VertexGraph *graph, const LatLng *fromVtx,
                            const LatLng *toVtx) {
    // Determine location
    uint32_t index = _hashVertex(fromVtx, graph->res, graph->numBuckets);
    // Check whether there's an existing node in that spot
    VertexNode *node = graph->buckets[index];
    if (node != NULL) {
        // Look through the list and see if we find the edge
        do {
            if (geoAlmostEqual(&node->from, fromVtx) &&
                (toVtx == NULL || geoAlmostEqual(&node->to, toVtx))) {
                return node;
            }
            node = node->next;
        } while (node != NULL);
    }
    // Iteration lookup fail
    return NULL;
}

/**
 * Find a Vertex node starting at the given vertex
 * @param  graph   Graph to look in
 * @param  fromVtx Start vertex
 * @return         Pointer to the vertex node, if found
 */
VertexNode *findNodeForVertex(const VertexGraph *graph, const LatLng *fromVtx) {
    return findNodeForEdge(graph, fromVtx, NULL);
}

/**
 * Get the next vertex node in the graph.
 * @param  graph Graph to iterate
 * @return       Vertex node, or NULL if at the end
 */
VertexNode *firstVertexNode(const VertexGraph *graph) {
    VertexNode *node = NULL;
    int currentIndex = 0;
    while (node == NULL) {
        if (currentIndex < graph->numBuckets) {
            // find the first node in the next bucket
            node = graph->buckets[currentIndex];
        } else {
            // end of iteration
            return NULL;
        }
        currentIndex++;
    }
    return node;
}

1	/*
2	* Copyright 2017-2018, 2020-2021 Uber Technologies, Inc.
3	*
4	* Licensed under the Apache License, Version 2.0 (the "License");
5	* you may not use this file except in compliance with the License.
6	* You may obtain a copy of the License at
7	*
8	* http://www.apache.org/licenses/LICENSE-2.0
9	*
10	* Unless required by applicable law or agreed to in writing, software
11	* distributed under the License is distributed on an "AS IS" BASIS,
12	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13	* See the License for the specific language governing permissions and
14	* limitations under the License.
15	*/
16	/** @file vertexGraph.c
17	* @brief Data structure for storing a graph of vertices
18	*/
19
20	#include "vertexGraph.h"
21
22	#include <assert.h>
23	#include <math.h>
24	#include <stdint.h>
25	#include <stdio.h>
26	#include <stdlib.h>
27
28	#include "alloc.h"
29	#include "latLng.h"
30
31	/**
32	* Initialize a new VertexGraph
33	* @param graph Graph to initialize
34	* @param numBuckets Number of buckets to include in the graph
35	* @param res Resolution of the hexagons whose vertices we're storing
36	*/
37	void initVertexGraph(VertexGraph *graph, int numBuckets, int res) {	59✔
38	if (numBuckets > 0) {	59✔
39	graph->buckets = H3_MEMORY(calloc)(numBuckets, sizeof(VertexNode *));	57✔
40	assert(graph->buckets != NULL);	57✔
41	} else {
42	graph->buckets = NULL;	2✔
43	}
44	graph->numBuckets = numBuckets;	59✔
45	graph->size = 0;	59✔
46	graph->res = res;	59✔
47	}	59✔
48
49	/**
50	* Destroy a VertexGraph's sub-objects, freeing their memory. The caller is
51	* responsible for freeing memory allocated to the VertexGraph struct itself.
52	* @param graph Graph to destroy
53	*/
54	void destroyVertexGraph(VertexGraph *graph) {	59✔
55	VertexNode *node;
56	while ((node = firstVertexNode(graph)) != NULL) {	148✔
57	removeVertexNode(graph, node);	89✔
58	}
59	H3_MEMORY(free)(graph->buckets);	59✔
60	}	59✔
61
62	/**
63	* Get an integer hash for a lat/lng point, at a precision determined
64	* by the current hexagon resolution.
65	* TODO: Light testing suggests this might not be sufficient at resolutions
66	* finer than 10. Design a better hash function if performance and collisions
67	* seem to be an issue here.
68	* @param vertex Lat/lng vertex to hash
69	* @param res Resolution of the hexagon the vertex belongs to
70	* @param numBuckets Number of buckets in the graph
71	* @return Integer hash
72	*/
73	uint32_t _hashVertex(const LatLng *vertex, int res, int numBuckets) {	8,062✔
74	// Simple hash: Take the sum of the lat and lng with a precision level
75	// determined by the resolution, converted to int, modulo bucket count.
76	return (uint32_t)fmod(fabs((vertex->lat + vertex->lng) * pow(10, 15 - res)),	8,062✔
77	numBuckets);
78	}
79
80	void _initVertexNode(VertexNode node, const LatLng fromVtx,	2,006✔
81	const LatLng *toVtx) {
82	node->from = *fromVtx;	2,006✔
83	node->to = *toVtx;	2,006✔
84	node->next = NULL;	2,006✔
85	}	2,006✔
86
87	/**
88	* Add a edge to the graph
89	* @param graph Graph to add node to
90	* @param fromVtx Start vertex
91	* @param toVtx End vertex
92	* @return Pointer to the new node
93	*/
94	VertexNode addVertexNode(VertexGraph graph, const LatLng *fromVtx,	2,006✔
95	const LatLng *toVtx) {
96	// Make the new node
97	VertexNode *node = H3_MEMORY(malloc)(sizeof(VertexNode));	2,006✔
98	assert(node != NULL);	2,006✔
99	_initVertexNode(node, fromVtx, toVtx);	2,006✔
100	// Determine location
101	uint32_t index = _hashVertex(fromVtx, graph->res, graph->numBuckets);	2,006✔
102	// Check whether there's an existing node in that spot
103	VertexNode *currentNode = graph->buckets[index];	2,006✔
104	if (currentNode == NULL) {	2,006✔
105	// Set bucket to the new node
106	graph->buckets[index] = node;	541✔
107	} else {
108	// Find the end of the list
109	do {
110	// Check the the edge we're adding doesn't already exist
111	if (geoAlmostEqual(&currentNode->from, fromVtx) &&	7,703✔
112	geoAlmostEqual(&currentNode->to, toVtx)) {	40✔
113	// already exists, bail
114	H3_MEMORY(free)(node);	2✔
115	return currentNode;	2✔
116	}
117	if (currentNode->next != NULL) {	7,661✔
118	currentNode = currentNode->next;	7,146✔
119	}
120	} while (currentNode->next != NULL);	7,661✔
121	// Add the new node to the end of the list
122	currentNode->next = node;	1,463✔
123	}
124	graph->size++;	2,004✔
125	return node;	2,004✔
126	}
127
128	/**
129	* Remove a node from the graph. The input node will be freed, and should
130	* not be used after removal.
131	* @param graph Graph to mutate
132	* @param node Node to remove
133	* @return 0 on success, 1 on failure (node not found)
134	*/
135	int removeVertexNode(VertexGraph graph, VertexNode node) {	2,005✔
136	// Determine location
137	uint32_t index = _hashVertex(&node->from, graph->res, graph->numBuckets);	2,005✔
138	VertexNode *currentNode = graph->buckets[index];	2,005✔
139	int found = 0;	2,005✔
140	if (currentNode != NULL) {	2,005✔
141	if (currentNode == node) {	2,004✔
142	graph->buckets[index] = node->next;	1,224✔
143	found = 1;	1,224✔
144	}
145	// Look through the list
146	while (!found && currentNode->next != NULL) {	4,672!
147	if (currentNode->next == node) {	2,668✔
148	// splice the node out
149	currentNode->next = node->next;	780✔
150	found = 1;	780✔
151	}
152	currentNode = currentNode->next;	2,668✔
153	}
154	}
155	if (found) {	2,005✔
156	H3_MEMORY(free)(node);	2,004✔
157	graph->size--;	2,004✔
158	return 0;	2,004✔
159	}
160	// Failed to find the node
161	return 1;	1✔
162	}
163
164	/**
165	* Find the Vertex node for a given edge, if it exists
166	* @param graph Graph to look in
167	* @param fromVtx Start vertex
168	* @param toVtx End vertex, or NULL if we don't care
169	* @return Pointer to the vertex node, if found
170	*/
171	VertexNode findNodeForEdge(const VertexGraph graph, const LatLng *fromVtx,	3,917✔
172	const LatLng *toVtx) {
173	// Determine location
174	uint32_t index = _hashVertex(fromVtx, graph->res, graph->numBuckets);	3,917✔
175	// Check whether there's an existing node in that spot
176	VertexNode *node = graph->buckets[index];	3,917✔
177	if (node != NULL) {	3,917✔
178	// Look through the list and see if we find the edge
179	do {
180	if (geoAlmostEqual(&node->from, fromVtx) &&	13,573✔
181	(toVtx == NULL \|\| geoAlmostEqual(&node->to, toVtx))) {	1,626✔
182	return node;	1,871✔
183	}
184	node = node->next;	11,702✔
185	} while (node != NULL);	11,702✔
186	}
187	// Iteration lookup fail
188	return NULL;	2,046✔
189	}
190
191	/**
192	* Find a Vertex node starting at the given vertex
193	* @param graph Graph to look in
194	* @param fromVtx Start vertex
195	* @return Pointer to the vertex node, if found
196	*/
197	VertexNode findNodeForVertex(const VertexGraph graph, const LatLng *fromVtx) {	998✔
198	return findNodeForEdge(graph, fromVtx, NULL);	998✔
199	}
200
201	/**
202	* Get the next vertex node in the graph.
203	* @param graph Graph to iterate
204	* @return Vertex node, or NULL if at the end
205	*/
206	VertexNode firstVertexNode(const VertexGraph graph) {	246✔
207	VertexNode *node = NULL;	246✔
208	int currentIndex = 0;	246✔
209	while (node == NULL) {	1,791✔
210	if (currentIndex < graph->numBuckets) {	1,648✔
211	// find the first node in the next bucket
212	node = graph->buckets[currentIndex];	1,545✔
213	} else {
214	// end of iteration
215	return NULL;	103✔
216	}
217	currentIndex++;	1,545✔
218	}
219	return node;	143✔
220	}

uber / h3 / 10357358860

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous