Add:Core:Made routing a background task

git-svn-id: http://svn.code.sf.net/p/navit/code/trunk/navit@1965 ffa7fe5e-494d-0410-b361-a75ebd5db220

6 files changed, 226 insertions, 136 deletions

diff --git a/navit/map.c b/navit/map.c
index eea5921b2..eb8d59a1c 100644
--- a/navit/map.c
+++ b/navit/map.c
@@ -335,8 +335,10 @@ map_rect_get_item_byid(struct map_rect *mr, int id_hi, int id_lo)
 void
 map_rect_destroy(struct map_rect *mr)
 {
-	mr->m->meth.map_rect_destroy(mr->priv);
-	g_free(mr);
+	if (mr) {
+		mr->m->meth.map_rect_destroy(mr->priv);
+		g_free(mr);
+	}
 }
 
 /**
diff --git a/navit/navigation.c b/navit/navigation.c
index 11f5d679a..fa7133d56 100644
--- a/navit/navigation.c
+++ b/navit/navigation.c
@@ -21,6 +21,7 @@
 #include <stdlib.h>
 #include <string.h>
 #include <math.h>
+#include <ctype.h>
 #include <glib.h>
 #include "debug.h"
 #include "profile.h"
@@ -54,6 +55,7 @@ struct suffix {
 };
 
 struct navigation {
+	struct route *route;
 	struct map *map;
 	struct item_hash *hash;
 	struct navigation_itm *first;
@@ -69,6 +71,7 @@ struct navigation {
 	int turn_around_limit;
 	int distance_turn;
 	int distance_last;
+	struct callback *route_cb;
 	int announce[route_item_last-route_item_first+1][3];
 };
 
@@ -82,6 +85,8 @@ struct navigation_command {
 	int length;
 };
 
+static void navigation_flush(struct navigation *this_);
+
 /**
  * @brief Calculates the delta between two angles
  * @param angle1 The first angle
@@ -1413,7 +1418,7 @@ show_maneuver(struct navigation *nav, struct navigation_itm *itm, struct navigat
 			}
 
 		} else {
-			d = g_strdup_printf("");
+			d = g_strdup("");
 		}
 		break;
 	default:
@@ -1597,8 +1602,8 @@ navigation_call_callbacks(struct navigation *this_, int force_speech)
 	}
 }
 
-void
-navigation_update(struct navigation *this_, struct route *route)
+static void
+navigation_update(struct navigation *this_, int mode)
 {
 	struct map *map;
 	struct map_rect *mr;
@@ -1608,9 +1613,15 @@ navigation_update(struct navigation *this_, struct route *route)
 	struct navigation_itm *itm;
 	int incr=0,first=1;
 
-	if (! route)
+	dbg(1,"enter %d\n", mode);
+	if (mode < 2 || mode == 4) 
+		navigation_flush(this_);
+	if (mode < 2)
+		return;
+		
+	if (! this_->route)
 		return;
-	map=route_get_map(route);
+	map=route_get_map(this_->route);
 	if (! map)
 		return;
 	mr=map_rect_new(map, NULL);
@@ -1644,7 +1655,7 @@ navigation_update(struct navigation *this_, struct route *route)
 	else {
 		if (! ritem) {
 			navigation_itm_new(this_, NULL);
-			make_maneuvers(this_,route);
+			make_maneuvers(this_,this_->route);
 		}
 		calculate_dest_distance(this_, incr);
 		dbg(2,"destination distance old=%d new=%d\n", this_->distance_last, this_->first->dest_length);
@@ -1664,7 +1675,7 @@ navigation_update(struct navigation *this_, struct route *route)
 	map_rect_destroy(mr);
 }
 
-void
+static void
 navigation_flush(struct navigation *this_)
 {
 	navigation_destroy_itms_cmds(this_, NULL);
@@ -2071,6 +2082,13 @@ navigation_map_new(struct map_methods *meth, struct attr **attrs)
 	return ret;
 }
 
+void
+navigation_set_route(struct navigation *this_, struct route *route)
+{
+	this_->route=route;
+	this_->route_cb=callback_new_attr_1(callback_cast(navigation_update), attr_route, this_);
+	route_add_callback(route, this_->route_cb);
+}
 
 void
 navigation_init(void)
diff --git a/navit/navigation.h b/navit/navigation.h
index 0aea185d2..ae6c7210e 100644
--- a/navit/navigation.h
+++ b/navit/navigation.h
@@ -33,12 +33,11 @@ struct navigation;
 struct route;
 struct navigation *navigation_new(struct attr *parent, struct attr **attrs);
 int navigation_set_announce(struct navigation *this_, enum item_type type, int *level);
-void navigation_update(struct navigation *this_, struct route *route);
-void navigation_flush(struct navigation *this_);
 void navigation_destroy(struct navigation *this_);
 int navigation_register_callback(struct navigation *this_, enum attr_type type, struct callback *cb);
 void navigation_unregister_callback(struct navigation *this_, enum attr_type type, struct callback *cb);
 struct map *navigation_get_map(struct navigation *this_);
+void navigation_set_route(struct navigation *this_, struct route *route);
 void navigation_init(void);
 /* end of prototypes */
 #ifdef __cplusplus
diff --git a/navit/navit.c b/navit/navit.c
index 21b22b5ca..ef07d89b3 100644
--- a/navit/navit.c
+++ b/navit/navit.c
@@ -66,10 +66,6 @@
 
 //! The navit_vehicule
 struct navit_vehicle {
-	int update;
-	/*! Limit of the update counter. See navit_add_vehicle */
-	int update_curr;
-	/*! Deprecated : Update counter itself. When it reaches 'update' counts, route is updated */
 	int follow;
 	/*! Limit of the follow counter. See navit_add_vehicle */
 	int follow_curr;
@@ -113,9 +109,7 @@ struct navit {
 	struct navit_vehicle *vehicle;
 	struct callback_list *attr_cbl;
 	int pid;
-	struct callback *nav_speech_cb;
-	struct callback *roadbook_callback;
-	struct callback *popup_callback;
+	struct callback *nav_speech_cb, *roadbook_callback, *popup_callback, *route_cb;
 	struct datawindow *roadbook_window;
 	struct map *bookmark;
 	struct map *former_destination;
@@ -211,6 +205,22 @@ navit_draw_displaylist(struct navit *this_)
 		graphics_displaylist_draw(this_->gra, this_->displaylist, this_->trans, this_->layout_current, 1);
 }
 
+static void
+navit_redraw_route(struct navit *this_, int updated)
+{
+	dbg(1,"enter %d\n", updated);
+	if (this_->ready != 3)
+		return;
+	if (updated <= 3)
+		return;
+	if (this_->vehicle) {
+		if (this_->vehicle->follow == 1)
+			return;
+		this_->vehicle->follow_curr=this_->vehicle->follow;
+	}
+	navit_draw(this_);
+}
+
 void
 navit_handle_resize(struct navit *this_, int w, int h)
 {
@@ -858,10 +868,6 @@ navit_set_destination(struct navit *this_, struct pcoord *c, const char *descrip
 	callback_list_call_attr_0(this_->attr_cbl, attr_destination);
 	if (this_->route) {
 		route_set_destination(this_->route, c);
-		if (this_->navigation) {
-			navigation_flush(this_->navigation);
-			navigation_update(this_->navigation, this_->route);
-		}
 
 		if (this_->ready == 3)
 			navit_draw(this_);
@@ -1170,8 +1176,6 @@ navit_init(struct navit *this_)
 {
 	struct mapset *ms;
 	struct map *map;
-	GList *l;
-	struct navit_vehicle *nv;
 
 	if (!this_->gui) {
 		dbg(0,"no gui\n");
@@ -1195,18 +1199,6 @@ navit_init(struct navit *this_)
 		return;
 	}
 	graphics_init(this_->gra);
-#if 0
-	l=this_->vehicles;
-	while (l) {
-		dbg(1,"parsed one vehicle\n");
-		nv=l->data;
-		nv->callback.type=attr_callback;
-		nv->callback.u.callback=callback_new_2(callback_cast(navit_vehicle_update), this_, nv);
-		vehicle_add_attr(nv->vehicle, &nv->callback);
-		vehicle_set_attr(nv->vehicle, &this_->self, NULL);
-		l=g_list_next(l);
-	}
-#endif
 	if (this_->mapsets) {
 		ms=this_->mapsets->data;
 		if (this_->route) {
@@ -1239,9 +1231,17 @@ navit_init(struct navit *this_)
 		navit_add_bookmarks_from_file(this_);
 		navit_add_former_destinations_from_file(this_);
 	}
-	if (this_->navigation && this_->speech) {
-		this_->nav_speech_cb=callback_new_1(callback_cast(navit_speak), this_);
-		navigation_register_callback(this_->navigation, attr_navigation_speech, this_->nav_speech_cb);
+	if (this_->route) {
+		this_->route_cb=callback_new_attr_1(callback_cast(navit_redraw_route), attr_route, this_);
+		route_add_callback(this_->route, this_->route_cb);
+	}
+	if (this_->navigation) {
+		if (this_->speech) {
+			this_->nav_speech_cb=callback_new_1(callback_cast(navit_speak), this_);
+			navigation_register_callback(this_->navigation, attr_navigation_speech, this_->nav_speech_cb);
+		}
+		if (this_->route)
+			navigation_set_route(this_->navigation, this_->route);
 	}
 	char *center_file = navit_get_center_file(FALSE);
 	navit_set_center_from_file(this_, center_file);
@@ -1778,15 +1778,13 @@ navit_vehicle_update(struct navit *this_, struct navit_vehicle *nv)
 			nv->coord.y=cursor_pc.y;
 		}
 	}
-	if (nv->update_curr == 1) {
-		if (this_->route) {
-			if (this_->tracking && this_->tracking_flag)
-				route_set_position_from_tracking(this_->route, this_->tracking);
-			else
-				route_set_position(this_->route, &cursor_pc);
-		}
-		callback_list_call_attr_0(this_->attr_cbl, attr_position);
+	if (this_->route) {
+		if (this_->tracking && this_->tracking_flag)
+			route_set_position_from_tracking(this_->route, this_->tracking);
+		else
+			route_set_position(this_->route, &cursor_pc);
 	}
+	callback_list_call_attr_0(this_->attr_cbl, attr_position);
 	navit_textfile_debug_log(this_, "type=trackpoint_tracked");
 	transform(this_->trans, pro, &nv->coord, &cursor_pnt, 1, 0, 0, NULL);
 	if (!transform_within_border(this_->trans, &cursor_pnt, border)) {
@@ -1809,8 +1807,6 @@ navit_vehicle_update(struct navit *this_, struct navit_vehicle *nv)
 	if (this_->pid && nv->speed > 2)
 		kill(this_->pid, SIGWINCH);
 #endif
-	if (this_->route && nv->update_curr == 1)
-		navigation_update(this_->navigation, this_->route);
 	if ((nv->follow_curr == 1) && (!this_->button_pressed)) {
 		if (this_->cursor_flag && ((time(NULL) - this_->last_moved) > this_->center_timeout) && (recenter)) {
 			navit_set_center_cursor(this_, &nv->coord, nv->dir, 50, 80);
@@ -1825,10 +1821,6 @@ navit_vehicle_update(struct navit *this_, struct navit_vehicle *nv)
 		nv->follow_curr--;
 	else
 		nv->follow_curr=nv->follow;
-	if (nv->update_curr > 1)
-		nv->update_curr--;
-	else
-		nv->update_curr=nv->update;
 	callback_list_call_attr_2(this_->attr_cbl, attr_position_coord_geo, this_, nv->vehicle);
 	if (pnt)
 		navit_vehicle_draw(this_, nv, pnt);
@@ -1854,13 +1846,6 @@ navit_set_position(struct navit *this_, struct pcoord *c)
 	if (this_->route) {
 		route_set_position(this_->route, c);
 		callback_list_call_attr_0(this_->attr_cbl, attr_position);
-		if (this_->navigation) {
-			navigation_update(this_->navigation, this_->route);
-#if 0
-			map_dump_file(route_get_map(this_->route), "route.txt");
-			map_dump_file(navigation_get_map(this_->navigation), "navigation.txt");
-#endif
-		}
 	}
 	if (this_->ready == 3)
 		navit_draw(this_);
@@ -1883,15 +1868,12 @@ static int
 navit_add_vehicle(struct navit *this_, struct vehicle *v)
 {
 	struct navit_vehicle *nv=g_new0(struct navit_vehicle, 1);
-	struct attr update,follow,color,active, color2, animate;
+	struct attr follow,color,active, color2, animate;
 	nv->vehicle=v;
-	nv->update=1;
 	nv->follow=0;
 	nv->last.x = 0;
 	nv->last.y = 0;
 	nv->animate_cursor=0;
-	if ((vehicle_get_attr(v, attr_update, &update, NULL)))
-		nv->update=nv->update=update.u.num;
 	if ((vehicle_get_attr(v, attr_follow, &follow, NULL)))
 		nv->follow=nv->follow=follow.u.num;
 	if ((vehicle_get_attr(v, attr_color, &color, NULL)))
@@ -1900,7 +1882,6 @@ navit_add_vehicle(struct navit *this_, struct vehicle *v)
 		nv->c2=color2.u.color;
 	else
 		nv->c2=NULL;
-	nv->update_curr=nv->update;
 	nv->follow_curr=nv->follow;
 	this_->vehicles=g_list_append(this_->vehicles, nv);
 	if ((vehicle_get_attr(v, attr_active, &active, NULL)) && active.u.num)
diff --git a/navit/route.c b/navit/route.c
index 870d21cdf..5542cc08c 100644
--- a/navit/route.c
+++ b/navit/route.c
@@ -64,6 +64,8 @@
 #include "transform.h"
 #include "plugin.h"
 #include "fib.h"
+#include "event.h"
+#include "callback.h"
 
 
 struct map_priv {
@@ -155,6 +157,7 @@ struct route_info {
  * This structure describes a whole routing path
  */
 struct route_path {
+	int updated;						/**< The path has only been updated */
 	struct route_path_segment *path;			/**< The first segment in the path, i.e. the segment one should 
 												 *  drive in next */
 	struct route_path_segment *path_last;		/**< The last segment in the path */
@@ -175,7 +178,6 @@ struct route_path {
  * This struct holds all information about a route.
  */
 struct route {
-	int version;				/**< Counts how many times this route got updated */
 	struct mapset *ms;			/**< The mapset this route is built upon */
 	unsigned flags;
 	struct route_info *pos;		/**< Current position within this route */
@@ -185,6 +187,9 @@ struct route {
 	struct route_path *path2;	/**< Pointer to the route path */
 	struct map *map;
 	struct map *graph_map;
+	struct callback * route_graph_done_cb ; /**< Callback when route graph is done */
+	struct callback * route_graph_flood_done_cb ; /**< Callback when route graph flooding is done */
+	struct callback_list *cbl;	/**< Callback list to call when route changes */
 	int destination_distance;	/**< Distance to the destination at which the destination is considered "reached" */
 	int speedlist[route_item_last-route_item_first+1];	/**< The speedlist for this route */
 };
@@ -195,6 +200,14 @@ struct route {
  * This structure describes a whole routing graph
  */
 struct route_graph {
+	int busy;					/**< The graph is being built */
+	struct map_selection *sel;			/**< The rectangle selection for the graph */
+	struct mapset_handle *h;			/**< Handle to the mapset */	
+	struct map *m;					/**< Pointer to the currently active map */	
+	struct map_rect *mr;				/**< Pointer to the currently active map rectangle */	
+	struct callback *idle_cb;			/**< Idle callback to process the graph */
+	struct callback *done_cb;			/**< Callback when graph is done */
+	struct event_idle *idle_ev;			/**< The pointer to the idle event */
 	struct route_graph_point *route_points;		/**< Pointer to the first route_graph_point in the linked list of  all points */
    	struct route_graph_segment *route_segments; /**< Pointer to the first route_graph_segment in the linked list of all segments */
 #define HASH_SIZE 8192
@@ -217,11 +230,12 @@ struct route_graph_point_iterator {
 
 static struct route_info * route_find_nearest_street(struct mapset *ms, struct pcoord *c);
 static struct route_graph_point *route_graph_get_point(struct route_graph *this, struct coord *c);
-static void route_graph_update(struct route *this);
+static void route_graph_update(struct route *this, struct callback *cb);
+static void route_graph_build_done(struct route_graph *rg, int cancel);
 static struct route_path *route_path_new(struct route_graph *this, struct route_path *oldpath, struct route_info *pos, struct route_info *dst, int *speedlist);
 static void route_process_street_graph(struct route_graph *this, struct item *item);
 static void route_graph_destroy(struct route_graph *this);
-static void route_path_update(struct route *this);
+static void route_path_update(struct route *this, int cancel);
 
 /**
  * @brief Returns the projection used for this route
@@ -343,16 +357,12 @@ route_new(struct attr *parent, struct attr **attrs)
 	struct route *this=g_new0(struct route, 1);
 	struct attr dest_attr;
 
-	if (!this) {
-		printf("%s:Out of memory\n", __FUNCTION__);
-		return NULL;
-	}
-
 	if (attr_generic_get_attr(attrs, NULL, attr_destination_distance, &dest_attr, NULL)) {
 		this->destination_distance = dest_attr.u.num;
 	} else {
 		this->destination_distance = 50; // Default value
 	}
+	this->cbl=callback_list_new();
 
 	return this;
 }
@@ -587,6 +597,24 @@ route_destination_reached(struct route *this)
 	return 1;
 }
 
+static void
+route_path_update_done(struct route *this, int new_graph)
+{
+	struct route_path *oldpath=this->path2;
+	int val;
+
+	this->path2=route_path_new(this->graph, oldpath, this->pos, this->dst, this->speedlist);
+	route_path_destroy(oldpath);
+	if (this->path2) {
+		if (new_graph)
+			val=4;
+		else
+			val=2+!this->path2->updated;
+	} else
+		val=1;
+	callback_list_call_attr_1(this->cbl, attr_route, (void *)val);
+}
+
 /**
  * @brief Updates the route graph and the route path if something changed with the route
  *
@@ -599,31 +627,25 @@ route_destination_reached(struct route *this)
  * @param this The route to update
  */
 static void
-route_path_update(struct route *this)
+route_path_update(struct route *this, int cancel)
 {
-	struct route_path *oldpath = NULL;
 	if (! this->pos || ! this->dst) {
 		route_path_destroy(this->path2);
 		this->path2 = NULL;
 		return;
 	}
 	/* the graph is destroyed when setting the destination */
-	if (this->graph && this->pos && this->dst && this->path2) {
+	if (this->graph && !cancel) {
 		// we can try to update
-		oldpath = this->path2;
+		route_path_update_done(this, 0);
+	} else {
+		route_path_destroy(this->path2);
 		this->path2 = NULL;
 	}
-	if (! this->graph || !(this->path2=route_path_new(this->graph, oldpath, this->pos, this->dst, this->speedlist))) {
-		profile(0,NULL);
-		route_graph_update(this);
-		this->path2=route_path_new(this->graph, oldpath, this->pos, this->dst, this->speedlist);
-		profile(1,"route_path_new");
-		profile(0,"end");
-	}
-
-	if (oldpath) {
-		/* Destroy what's left */
-		route_path_destroy(oldpath);
+	if (! this->graph || !this->path2) {
+		if (! this->route_graph_flood_done_cb)
+			this->route_graph_flood_done_cb=callback_new_2(callback_cast(route_path_update_done), this, 1);
+		route_graph_update(this, this->route_graph_flood_done_cb);
 	}
 }
 
@@ -664,8 +686,7 @@ route_set_position(struct route *this, struct pcoord *pos)
 	if (! this->pos)
 		return;
 	route_info_distances(this->pos, pos->pro);
-	if (this->dst) 
-		route_path_update(this);
+	route_path_update(this, 0);
 }
 
 /**
@@ -705,7 +726,7 @@ route_set_position_from_tracking(struct route *this, struct tracking *tracking)
 	dbg(3,"street 0=(0x%x,0x%x) %d=(0x%x,0x%x)\n", ret->street->c[0].x, ret->street->c[0].y, ret->street->count-1, ret->street->c[ret->street->count-1].x, ret->street->c[ret->street->count-1].y);
 	this->pos=ret;
 	if (this->dst) 
-		route_path_update(this);
+		route_path_update(this, 0);
 	dbg(2,"ret\n");
 }
 
@@ -822,14 +843,15 @@ route_set_destination(struct route *this, struct pcoord *dst)
 	if (dst) {
 		this->dst=route_find_nearest_street(this->ms, dst);
 		if(this->dst)
-		route_info_distances(this->dst, dst->pro);
-	}
+			route_info_distances(this->dst, dst->pro);
+	} else 
+		callback_list_call_attr_1(this->cbl, attr_route, (void *)0);
 	profile(1,"find_nearest_street");
 
 	/* The graph has to be destroyed and set to NULL, otherwise route_path_update() doesn't work */
 	route_graph_destroy(this->graph);
 	this->graph=NULL;
-	route_path_update(this);
+	route_path_update(this, 1);
 	profile(0,"end");
 }
 
@@ -1117,12 +1139,12 @@ route_path_add_item(struct route_path *this, struct item *item, int len, struct
  * @param dir Order in which to add the coordinates. See route_path_add_item()
  * @param straight Indicates if this segment is being entered "straight". See route_check_straight().
  */
-static void
+static int
 route_path_add_item_from_graph(struct route_path *this, struct route_path *oldpath,
 				   struct route_graph_segment *rgs, int len, int offset, int dir, int straight)
 {
 	struct route_path_segment *segment;
-	int i,ccnt = 0;
+	int i,ccnt = 0, ret=1;
 	struct coord ca[2048];
 
 	if (oldpath) {
@@ -1131,17 +1153,13 @@ route_path_add_item_from_graph(struct route_path *this, struct route_path *oldpa
 			segment = route_extract_segment_from_path(oldpath,
 							 &rgs->item, offset);
 			
-			if (segment)
+			if (segment) 
 				goto linkold;
 		}
 	}
 
 	ccnt = get_item_seg_coords(&rgs->item, ca, 2047, &rgs->start->c, &rgs->end->c);
 	segment= g_malloc0(sizeof(*segment) + sizeof(struct coord) * ccnt);
-	if (!segment) {
-		printf("%s:Out of memory\n", __FUNCTION__);
-		return;
-	}
 	segment->direction=dir;
 	if (dir > 0) {
 		for (i = 0 ; i < ccnt ; i++)
@@ -1158,6 +1176,7 @@ route_path_add_item_from_graph(struct route_path *this, struct route_path *oldpa
 		route_check_roundabout(rgs, 13, (dir < 1), NULL);
 	}
 
+	ret=0;
 	segment->item=rgs->item;
 	segment->offset = offset;
 linkold:
@@ -1166,6 +1185,8 @@ linkold:
 	item_hash_insert(this->path_hash,  &rgs->item, (void *)ccnt);
 
 	route_path_add_segment(this, segment);
+
+	return ret;
 }
 
 /**
@@ -1195,6 +1216,7 @@ static void
 route_graph_destroy(struct route_graph *this)
 {
 	if (this) {
+		route_graph_build_done(this, 1);
 		route_graph_free_points(this);
 		route_graph_free_segments(this);
 		g_free(this);
@@ -1346,7 +1368,7 @@ compare(void *v1, void *v2)
  * at this algorithm.
  */
 static void
-route_graph_flood(struct route_graph *this, struct route_info *dst, int *speedlist)
+route_graph_flood(struct route_graph *this, struct route_info *dst, int *speedlist, struct callback *cb)
 {
 	struct route_graph_point *p_min,*end=NULL;
 	struct route_graph_segment *s;
@@ -1438,6 +1460,7 @@ route_graph_flood(struct route_graph *this, struct route_info *dst, int *speedli
 		}
 	}
 	fh_deleteheap(heap);
+	callback_call_0(cb);
 }
 
 /**
@@ -1460,6 +1483,7 @@ route_path_new_offroad(struct route_graph *this, struct route_info *pos, struct
 	ret=g_new0(struct route_path, 1);
 	ret->path_hash=item_hash_new();
 	route_path_add_item(ret, NULL, pos->lenextra+dst->lenextra, &pos->c, NULL, 0, &dst->c, 1);
+	ret->updated=1;
 
 	return ret;
 }
@@ -1499,6 +1523,7 @@ route_path_new_trivial(struct route_graph *this, struct route_info *pos, struct
 		route_path_add_item(ret, &sd->item, pos->lenneg-dst->lenneg, &pos->lp, sd->c+dst->pos+1, pos->pos-dst->pos, &dst->lp, -1);
 	if (dst->lenextra) 
 		route_path_add_item(ret, NULL, dst->lenextra, &dst->lp, NULL, 0, &dst->c, 1);
+	ret->updated=1;
 	return ret;
 }
 
@@ -1561,6 +1586,7 @@ route_path_new(struct route_graph *this, struct route_path *oldpath, struct rout
 		val2=start2->end->end->value;
 	}
 	ret=g_new0(struct route_path, 1);
+	ret->updated=1;
 	if (pos->lenextra) 
 		route_path_add_item(ret, NULL, pos->lenextra, &pos->c, NULL, 0, &pos->lp, 1);
 	if (start1 && (val1 < val2)) {
@@ -1585,10 +1611,12 @@ route_path_new(struct route_graph *this, struct route_path *oldpath, struct rout
 		len+=seg_len;
 	
 		if (s->start == start) {		
-			route_path_add_item_from_graph(ret, oldpath, s, seg_len, s->offset, 1, is_straight);
+			if (!route_path_add_item_from_graph(ret, oldpath, s, seg_len, s->offset, 1, is_straight))
+				ret->updated=0;
 			start=s->end;
 		} else {
-			route_path_add_item_from_graph(ret, oldpath, s, seg_len, s->offset, -1, is_straight);
+			if (!route_path_add_item_from_graph(ret, oldpath, s, seg_len, s->offset, -1, is_straight))
+				ret->updated=0;
 			start=s->start;
 		}
 
@@ -1612,6 +1640,61 @@ route_path_new(struct route_graph *this, struct route_path *oldpath, struct rout
 	return ret;
 }
 
+static int
+route_graph_build_next_map(struct route_graph *rg)
+{
+	do {
+		rg->m=mapset_next(rg->h, 1);
+		if (! rg->m)
+			return 0;
+		map_rect_destroy(rg->mr);
+		rg->mr=map_rect_new(rg->m, rg->sel);
+	} while (!rg->mr);
+		
+	return 1;
+}
+
+static void
+route_graph_build_done(struct route_graph *rg, int cancel)
+{
+	dbg(1,"cancel=%d\n",cancel);
+	event_remove_idle(rg->idle_ev);
+	callback_destroy(rg->idle_cb);
+	map_rect_destroy(rg->mr);
+        mapset_close(rg->h);
+	route_free_selection(rg->sel);
+	rg->idle_ev=NULL;
+	rg->idle_cb=NULL;
+	rg->mr=NULL;
+	rg->h=NULL;
+	rg->sel=NULL;
+	if (! cancel)
+		callback_call_0(rg->done_cb);
+	rg->busy=0;
+}
+
+static void
+route_graph_build_idle(struct route_graph *rg)
+{
+	int count=1000;
+	struct item *item;
+
+	while (count > 0) {
+		for (;;) {	
+			item=map_rect_get_item(rg->mr);
+			if (item)
+				break;
+			if (!route_graph_build_next_map(rg)) {
+				route_graph_build_done(rg, 0);
+				return;
+			}
+		}
+		if (item->type >= type_street_0 && item->type <= type_ferry) 
+			route_process_street_graph(rg, item);
+		count--;
+	}
+}
+
 /**
  * @brief Builds a new route graph from a mapset
  *
@@ -1625,41 +1708,35 @@ route_path_new(struct route_graph *this, struct route_path *oldpath, struct rout
  * @param ms The mapset to build the route graph from
  * @param c1 Corner 1 of the rectangle to use from the map
  * @param c2 Corner 2 of the rectangle to use from the map
+ * @param done_cb The callback which will be called when graph is complete
  * @return The new route graph.
  */
 static struct route_graph *
-route_graph_build(struct mapset *ms, struct coord *c1, struct coord *c2)
+route_graph_build(struct mapset *ms, struct coord *c1, struct coord *c2, struct callback *done_cb)
 {
 	struct route_graph *ret=g_new0(struct route_graph, 1);
-	struct map_selection *sel;
-	struct mapset_handle *h;
-	struct map_rect *mr;
-	struct map *m;
-	struct item *item;
 
-	if (!ret) {
-		printf("%s:Out of memory\n", __FUNCTION__);
-		return ret;
-	}
-	sel=route_calc_selection(c1, c2);
-	h=mapset_open(ms);
-	while ((m=mapset_next(h,1))) {
-		mr=map_rect_new(m, sel);
-		if (! mr)
-			continue;
-		while ((item=map_rect_get_item(mr))) {
-			if (item->type >= type_street_0 && item->type <= type_ferry) {
-				route_process_street_graph(ret, item);
-			}
-		}
-		map_rect_destroy(mr);
-        }
-        mapset_close(h);
-	route_free_selection(sel);
+	dbg(1,"enter\n");
+
+	ret->sel=route_calc_selection(c1, c2);
+	ret->h=mapset_open(ms);
+	ret->done_cb=done_cb;
+	ret->busy=1;
+	if (route_graph_build_next_map(ret)) {
+		ret->idle_cb=callback_new_1(callback_cast(route_graph_build_idle), ret);
+		ret->idle_ev=event_add_idle(50, ret->idle_cb);
+	} else
+		route_graph_build_done(ret, 0);
 
 	return ret;
 }
 
+static void
+route_graph_update_done(struct route *this, struct callback *cb)
+{
+	route_graph_flood(this->graph, this->dst, this->speedlist, cb);
+}
+
 /**
  * @brief Updates the route graph
  *
@@ -1669,15 +1746,13 @@ route_graph_build(struct mapset *ms, struct coord *c1, struct coord *c2)
  * @param this The route to update the graph for
  */
 static void
-route_graph_update(struct route *this)
+route_graph_update(struct route *this, struct callback *cb)
 {
 	route_graph_destroy(this->graph);
-	profile(1,"graph_free");
-	this->graph=route_graph_build(this->ms, &this->pos->c, &this->dst->c);
-	profile(1,"route_graph_build");
-	route_graph_flood(this->graph, this->dst, this->speedlist);
-	profile(1,"route_graph_flood");
-	this->version++;
+	callback_destroy(this->route_graph_done_cb);
+	this->route_graph_done_cb=callback_new_2(callback_cast(route_graph_update_done), this, cb);
+	callback_list_call_attr_1(this->cbl, attr_route, (void *)0);
+	this->graph=route_graph_build(this->ms, &this->pos->c, &this->dst->c, this->route_graph_done_cb);
 }
 
 /**
@@ -2453,6 +2528,19 @@ route_set_projection(struct route *this_, enum projection pro)
 }
 
 void
+route_add_callback(struct route *this_, struct callback *cb)
+{
+	callback_list_add(this_->cbl, cb);
+}
+
+void
+route_remove_callback(struct route *this_, struct callback *cb)
+{
+	callback_list_remove(this_->cbl, cb);
+}
+
+
+void
 route_init(void)
 {
 	plugin_register_map_type("route", route_map_new);
diff --git a/navit/route.h b/navit/route.h
index 133fb4b7e..686e16394 100644
--- a/navit/route.h
+++ b/navit/route.h
@@ -110,6 +110,8 @@ struct map *route_get_graph_map(struct route *route);
 void route_toggle_routegraph_display(struct route *route);
 void route_set_projection(struct route *this_, enum projection pro);
 int route_destination_reached(struct route *this);
+void route_add_callback(struct route *this_, struct callback *cb);
+void route_remove_callback(struct route *this_, struct callback *cb);
 void route_init(void);
 int route_pos_contains(struct route *this, struct item *item);