Data Structures
struct	route_graph_point
	A point in the route graph. More...

struct	route_segment_data
	A segment in the route graph or path. More...

struct	size_weight_limit
	Size and weight limits for a route segment. More...

struct	route_graph_segment_data
	Data for a segment in the route graph. More...

struct	route_graph_segment
	A segment in the route graph. More...

struct	route_graph
	A complete route graph. More...

Macros
#define	RP_TRAFFIC_DISTORTION 1

#define	RP_TURN_RESTRICTION 2

#define	RP_TURN_RESTRICTION_RESOLVED 4

#define	RSD_MAXSPEED(x) ((int )route_segment_data_field_pos((x), attr_maxspeed))

Functions
struct route_graph *	route_get_graph (struct route *this_)
	Retrieves the route graph. More...

struct map_selection *	route_get_selection (struct route *this_)
	Retrieves the map selection for the route. More...

void	route_free_selection (struct map_selection *sel)
	Destroys a list of map selections. More...

void	route_add_traffic_distortion (struct route this_, struct item item)
	Adds a traffic distortion item to the route. More...

void	route_remove_traffic_distortion (struct route this_, struct item item)
	Removes a traffic distortion item from the route. More...

void	route_change_traffic_distortion (struct route this_, struct item item)
	Changes a traffic distortion item on the route. More...

struct route_graph_point *	route_graph_add_point (struct route_graph this, struct coord f)
	Inserts a point into the route graph at the specified coordinates. More...

void	route_graph_add_turn_restriction (struct route_graph this, struct item item)
	Adds a turn restriction item to the route graph. More...

void	route_graph_free_points (struct route_graph *this)
	Frees all the memory used for points in the route graph passed. More...

struct route_graph_point *	route_graph_get_point (struct route_graph this, struct coord c)
	Gets the first route_graph_point with the specified coordinates. More...

struct route_graph_point *	route_graph_get_point_next (struct route_graph this, struct coord c, struct route_graph_point *last)
	Gets the next route_graph_point with the specified coordinates. More...

void	route_graph_add_segment (struct route_graph this, struct route_graph_point start, struct route_graph_point end, struct route_graph_segment_data data)
	Inserts a new segment into the route graph. More...

int	route_graph_segment_is_duplicate (struct route_graph_point start, struct route_graph_segment_data data)
	Checks if the route graph already contains a particular segment. More...

void	route_graph_free_segments (struct route_graph *this)
	Destroys all segments of a route graph. More...

void	route_graph_build_done (struct route_graph *rg, int cancel)
	Releases all resources needed to build the route graph. More...

void	route_recalculate_partial (struct route *this_)
	Triggers partial recalculation of the route, based on the existing route graph. More...

void *	route_segment_data_field_pos (struct route_segment_data *seg, enum attr_type type)
	Returns the position of a certain field appended to a route graph segment. More...

Macro Definition Documentation

◆ RP_TRAFFIC_DISTORTION

#define RP_TRAFFIC_DISTORTION 1

◆ RP_TURN_RESTRICTION

#define RP_TURN_RESTRICTION 2

◆ RP_TURN_RESTRICTION_RESOLVED

#define RP_TURN_RESTRICTION_RESOLVED 4

◆ RSD_MAXSPEED

#define RSD_MAXSPEED ( x ) *((int *)route_segment_data_field_pos((x), attr_maxspeed))

Function Documentation

◆ route_add_traffic_distortion()

void route_add_traffic_distortion	(	struct route *	this_,
		struct item *	item
	)

Adds a traffic distortion item to the route.

Parameters

this_	The route
item	The item to add, must be of type_traffic_distortion

References route::graph, route_graph_add_traffic_distortion(), route_has_graph(), and route::vehicleprofile.

Referenced by tm_item_update_attrs().

◆ route_change_traffic_distortion()

void route_change_traffic_distortion	(	struct route *	this_,
		struct item *	item
	)

Changes a traffic distortion item on the route.

Attempting to change an idem which is not in the route graph will add it.

Parameters

this_	The route
item	The item to change, must be of type_traffic_distortion

References route::graph, route_graph_change_traffic_distortion(), route_has_graph(), and route::vehicleprofile.

Referenced by tm_item_update_attrs().

◆ route_free_selection()

void route_free_selection ( struct map_selection * sel )

Destroys a list of map selections.

Parameters

sel	Start of the list to be destroyed

References map_selection::next, and next.

Referenced by route_graph_build_done(), traffic_traff_android_destroy(), and traffic_traff_android_set_selection().

◆ route_get_graph()

struct route_graph* route_get_graph ( struct route * this_ )

Retrieves the route graph.

Returns: The route graph, or NULL if the route has no valid graph

References route::graph.

◆ route_get_selection()

struct map_selection* route_get_selection ( struct route * this_ )

Retrieves the map selection for the route.

References c, route_info::c, route::destinations, route::pos, route_calc_selection(), and route::vehicleprofile.

Referenced by traffic_process_messages_int(), and traffic_traff_android_set_selection().

◆ route_graph_add_point()

struct route_graph_point* route_graph_add_point	(	struct route_graph *	this,
		struct coord *	f
	)

Inserts a point into the route graph at the specified coordinates.

This will insert a point into the route graph at the coordinates passed in f. Note that the point is not yet linked to any segments.

If the route graph already contains a point at the specified coordinates, the existing point will be returned.

Parameters

this	The route graph to insert the point into
f	The coordinates at which the point should be inserted

Returns: The point inserted or NULL on failure

References p, route_graph_get_point(), and route_graph_point_new().

Referenced by route_graph_add_street(), route_graph_add_traffic_distortion(), route_graph_add_turn_restriction(), and traffic_location_populate_route_graph().

◆ route_graph_add_segment()

void route_graph_add_segment	(	struct route_graph *	this,
		struct route_graph_point *	start,
		struct route_graph_point *	end,
		struct route_graph_segment_data *	data
	)

Inserts a new segment into the route graph.

Parameters

this	The route graph to insert the segment into
start	The graph point which should be connected to the start of this segment
end	The graph point which should be connected to the end of this segment
data	The segment data

References AF_DANGEROUS_GOODS, AF_SEGMENTED, AF_SIZE_OR_WEIGHT_LIMIT, AF_SPEED_LIMIT, route_graph_point::c, data, route_graph_segment::data, dbg_assert, debug_route, route_graph_point::end, route_graph_segment::end, route_graph_segment::end_next, route_segment_data::flags, route_segment_data::item, route_segment_data::len, route_graph_segment::next, route_segment_data_size(), RSD_MAXSPEED, route_segment_data::score, size, route_graph_point::start, route_graph_segment::start, route_graph_segment::start_next, coord::x, and coord::y.

Referenced by route_graph_add_street(), route_graph_add_traffic_distortion(), route_graph_add_turn_restriction(), route_graph_clone_segment(), route_graph_set_traffic_distortion(), and traffic_location_populate_route_graph().

◆ route_graph_add_turn_restriction()

void route_graph_add_turn_restriction	(	struct route_graph *	this,
		struct item *	item
	)

Adds a turn restriction item to the route graph.

Parameters

this	The route graph to add to
item	The item to add, must be of `type_street_turn_restriction_no` or `type_street_turn_restriction_only`

References c, data, dbg, route_graph_point::flags, item, item_coord_get(), item_coord_rewind(), item_to_name(), lvl_debug, route_graph_add_point(), route_graph_add_segment(), RP_TURN_RESTRICTION, item::type, pcoord::x, and pcoord::y.

Referenced by route_graph_build_idle(), and traffic_location_populate_route_graph().

◆ route_graph_build_done()

void route_graph_build_done	(	struct route_graph *	rg,
		int	cancel
	)

Releases all resources needed to build the route graph.

If cancel is false, this function will start processing restrictions and ultimately call the route graph's done_cb callback.

The traffic module will always call this method with cancel set to true, as it does not process restrictions and has no callback. Inside the routing module, cancel will be true if, and only if, navigation has been aborted.

Parameters

rg	Points to the route graph
cancel	True if the process was aborted before completing, false if it completed normally

References route_graph::busy, callback_call_0, callback_destroy(), dbg, route_graph::done_cb, event_remove_idle(), route_graph::h, route_graph::idle_cb, route_graph::idle_ev, lvl_debug, map_rect_destroy(), mapset_close(), route_graph::mr, route_free_selection(), route_graph_process_restrictions(), and route_graph::sel.

Referenced by route_graph_build(), route_graph_build_idle(), route_graph_destroy(), traffic_location_get_matching_points(), and traffic_location_populate_route_graph().

◆ route_graph_free_points()

void route_graph_free_points ( struct route_graph * this )

Frees all the memory used for points in the route graph passed.

Parameters

this	The route graph to delete all points from

References route_graph_point::hash_next, HASH_SIZE, and next.

Referenced by route_graph_destroy(), and traffic_message_add_segments().

◆ route_graph_free_segments()

void route_graph_free_segments ( struct route_graph * this )

Destroys all segments of a route graph.

Parameters

this	The graph to destroy all segments from

References data, next, route_graph_segment::next, route_segment_data_size(), and size.

Referenced by route_graph_destroy(), and traffic_message_add_segments().

◆ route_graph_get_point()

struct route_graph_point* route_graph_get_point	(	struct route_graph *	this,
		struct coord *	c
	)

Gets the first route_graph_point with the specified coordinates.

Parameters

this	The route in which to search
c	Coordinates to search for

Returns: The point at the specified coordinates or NULL if not found

References c, and route_graph_get_point_next().

Referenced by route_graph_add_point(), route_graph_remove_traffic_distortion(), and traffic_location_get_matching_points().

◆ route_graph_get_point_next()

struct route_graph_point* route_graph_get_point_next	(	struct route_graph *	this,
		struct coord *	c,
		struct route_graph_point *	last
	)

Gets the next route_graph_point with the specified coordinates.

Parameters

this	The route in which to search
c	Coordinates to search for
last	The last route graph point returned to iterate over multiple points with the same coordinates, or NULL to return the first point

Returns: The point at the specified coordinates or NULL if not found

References c, p, pcoord::x, and pcoord::y.

Referenced by route_graph_get_point(), route_graph_get_segment(), route_graph_set_traffic_distortion(), and traffic_location_get_matching_points().

◆ route_graph_segment_is_duplicate()

int route_graph_segment_is_duplicate	(	struct route_graph_point *	start,
		struct route_graph_segment_data *	data
	)

Checks if the route graph already contains a particular segment.

This function compares the item IDs of both segments. If the item is segmented, the segment offset is also compared.

Parameters

start	The starting point of the segment
data	The data for the segment

References AF_SEGMENTED, data, route_graph_segment::data, route_segment_data::item, item_is_equal, route_graph_point::start, route_graph_segment::start, and route_graph_segment::start_next.

Referenced by route_graph_add_street(), and traffic_location_populate_route_graph().

◆ route_recalculate_partial()

void route_recalculate_partial ( struct route * this_ )

Triggers partial recalculation of the route, based on the existing route graph.

This is currently used when traffic distortions have been added, changed or removed. Future versions may also use it if the current position has changed to a portion of the route graph which has not been flooded (which is currently not necessary because the route graph is always flooded completely).

This tends to be faster than full recalculation, as only a subset of all points in the graph needs to be evaluated.

If segment costs have changed (as is the case with traffic distortions), all affected segments must have been added to, removed from or updated in the route graph before this method is called.

After recalculation, the route path is updated.

The function uses a modified LPA* algorithm for recalculations. Most modifications were made for compatibility with the old routing algorithm:

The heuristic is always assumed to be zero (which would turn A* into Dijkstra, formerly the basis of the routing algorithm, and makes our keys one-dimensional)
Currently, each pass evaluates all locally inconsistent points, leaving an empty heap at the end (though this may change in the future).

Parameters

this_ The route

References route_graph::busy, route::graph, route_graph_compute_shortest_path(), route_graph_is_path_computed(), route_has_graph(), route_path_update_done(), route_set_attr(), route_status_building_graph, attr::type, and route::vehicleprofile.

Referenced by traffic_process_messages_int().

◆ route_remove_traffic_distortion()

void route_remove_traffic_distortion	(	struct route *	this_,
		struct item *	item
	)

Removes a traffic distortion item from the route.

Removing a traffic distortion which is not in the route graph is a no-op.

Parameters

this_	The route
item	The item to remove, must be of type_traffic_distortion

References route::graph, route_graph_remove_traffic_distortion(), route_has_graph(), and route::vehicleprofile.

Referenced by tm_item_unref().

◆ route_segment_data_field_pos()

void* route_segment_data_field_pos	(	struct route_segment_data *	seg,
		enum attr_type	type
	)

Returns the position of a certain field appended to a route graph segment.

This function returns a pointer to a field that is appended to a route graph segment.

Parameters

seg	The route graph segment the field is appended to
type	Type of the field that should be returned

Returns: A pointer to a field of a certain type, or NULL if no such field is present

References AF_DANGEROUS_GOODS, AF_SEGMENTED, AF_SIZE_OR_WEIGHT_LIMIT, AF_SPEED_LIMIT, route_segment_data::flags, route_graph_point::seg, and type.

Data Structures

Macros

Functions

Macro Definition Documentation

◆ RP_TRAFFIC_DISTORTION

◆ RP_TURN_RESTRICTION

◆ RP_TURN_RESTRICTION_RESOLVED

◆ RSD_MAXSPEED

Function Documentation

◆ route_add_traffic_distortion()

◆ route_change_traffic_distortion()

◆ route_free_selection()

◆ route_get_graph()

◆ route_get_selection()

◆ route_graph_add_point()

◆ route_graph_add_segment()

◆ route_graph_add_turn_restriction()

◆ route_graph_build_done()

◆ route_graph_free_points()

◆ route_graph_free_segments()

◆ route_graph_get_point()

◆ route_graph_get_point_next()

◆ route_graph_segment_is_duplicate()

◆ route_recalculate_partial()

◆ route_remove_traffic_distortion()

◆ route_segment_data_field_pos()