source: subversion/applications/rendering/gosmore/libgosm.cpp @ 20346

Last change on this file since 20346 was 20346, checked in by nic, 10 years ago

Searching: Add a few French prefixes and fix the "the" prefix.

Breaks backward compatibility.

Rebuild: Ignore more irrelevent tags, incl postal_code.
Elemstyles: Less crowded and more meaningful rendering in European cities.
Rendering: Fix text bug. (Thanks Willem-Jan). Fix area bug.

  • Property svn:executable set to *
File size: 96.3 KB
Line 
1#ifndef _WIN32
2#include <sys/mman.h>
3#include <fcntl.h>
4#include <sys/stat.h>
5#include <sys/types.h>
6#else
7#include <windows.h>
8#endif
9
10#include <stdio.h>
11#include <unistd.h>
12#include <vector>
13#include <deque>
14#include <string>
15#include <map>
16#include <assert.h>
17#include <float.h>
18using namespace std;
19
20#include "libgosm.h"
21
22routeNodeType *route = NULL, *shortest = NULL;
23routeHeapType *routeHeap;
24long dhashSize, dLength;
25int routeHeapSize, tlat, tlon, flat, flon, rlat, rlon, routeHeapMaxSize;
26int *hashTable, bucketsMin1, pakHead = 0xEB3A943, routeSuccess = FALSE;
27char *gosmData, *gosmSstr[searchCnt];
28
29ndType *ndBase;
30styleStruct *style;
31int stylecount;
32wayType *gosmSway[searchCnt];
33
34// store the maximum speeds (over all waytypes) of each vehicle type
35int TagCmp (const char *a, const char *b)
36{ // This works like the ordering of books in a library : We ignore
37  // meaningless words like "the", "street" and "north". We (should) also map
38  // deprecated words to their new words, like petrol to fuel
39  // TODO : We should consider an algorithm like double metasound.
40  static const char *omit[] = { /* "the", in the middle of a name ?? */
41    "ave", "avenue", "blvd", "boulevard", "byp", "bypass",
42    "cir", "circle", "close", "cres", "crescent", "ct", "court", "ctr",
43      "center",
44    "dr", "drive", "hwy", "highway", "ln", "lane", "loop",
45    "pass", "pky", "parkway", "pl", "place", "plz", "plaza",
46    /* "run" */ "rd", "road", "sq", "square", "st", "street",
47    "ter", "terrace", "tpke", "turnpike", /*trce, trace, trl, trail */
48    "walk",  "way"
49  };
50  static const char *words[] = { "", "first", "second", "third", "fourth",
51    "fifth", "sixth", "seventh", "eighth", "nineth", "tenth", "eleventh",
52    "twelth", "thirteenth", "fourteenth", "fifthteenth", "sixteenth",
53    "seventeenth", "eighteenth", "nineteenth", "twentieth" };
54  static const char *teens[] = { "", "", "twenty ", "thirty ", "fourty ",
55    "fifty ", "sixty ", "seventy ", "eighty ", "ninety " };
56 
57  if (strncasecmp (a, "the ", 4) == 0) a += 4;
58  else if (strncasecmp (a, "de ", 3) == 0) a += 3;
59  else if (strncasecmp (a, "rue ", 4) == 0) a += 4;
60  else if (strncasecmp (a, "avenue ", 7) == 0) a += 7;
61  else if (strncasecmp (a, "boulevard ", 10) == 0) a += 10;
62  if (strncasecmp (b, "the ", 4) == 0) b += 4;
63  else if (strncasecmp (b, "de ", 3) == 0) b += 3;
64  else if (strncasecmp (b, "rue ", 4) == 0) b += 4;
65  else if (strncasecmp (b, "avenue ", 7) == 0) b += 7;
66  else if (strncasecmp (b, "boulevard ", 10) == 0) b += 10;
67  if (strchr ("WEST", a[0]) && a[1] == ' ') a += 2; // e.g. N 21st St
68  if (strchr ("WEST", b[0]) && b[1] == ' ') b += 2;
69
70  for (;;) {
71    char n[2][30] = { "", "" };
72    const char *ptr[2];
73    int wl[2];
74    for (int i = 0; i < 2; i++) {
75      const char **p = i ? &b : &a;
76      if ((*p)[0] == ' ') {
77        for (int i = 0; i < int (sizeof (omit) / sizeof (omit[0])); i++) {
78          if (strncasecmp (*p + 1, omit[i], strlen (omit[i])) == 0 &&
79              !isalpha ((*p)[1 + strlen (omit[i])])) {
80            (*p) += 1 + strlen (omit[i]);
81            break;
82          }
83        }
84      }
85      if (isdigit (**p) && (!isdigit((*p)[1]) || !isdigit ((*p)[2]))
86              /* && isalpha (*p + strcspn (*p, "0123456789"))*/) {
87        // while (atoi (*p) > 99) (*p)++; // Buggy
88        if (atoi (*p) > 20) strcpy (n[i], teens[atoi ((*p)++) / 10]);
89        strcat (n[i], words[atoi (*p)]);
90        while (isdigit (**p) /*|| isalpha (**p)*/) (*p)++;
91        ptr[i] = n[i];
92        wl[i] = strlen (n[i]);
93      }
94      else {
95        ptr[i] = *p;
96        wl[i] = **p == ' ' ? 1 : strcspn (*p , " \n");
97      }
98    }
99    int result = strncasecmp (ptr[0], ptr[1], wl[0] < wl[1] ? wl[1] : wl[0]);
100    if (result || *ptr[0] == '\0' || *ptr[0] == '\n') return result;
101    if (n[0][0] == '\0') a += wl[1]; // In case b was 21st
102    if (n[1][0] == '\0') b += wl[0]; // In case a was 32nd
103  }
104}
105
106/* 1. Bsearch idx such that
107      ZEnc (way[idx]) < ZEnc (clon/lat) < ZEnc (way[idx+1])
108   2. Fill the list with ways around idx.
109   3. Now there's a circle with clon/clat as its centre and that runs through
110      the worst way just found. Let's say it's diameter is d. There exist
111      4 Z squares smaller that 2d by 2d that cover this circle. Find them
112      with binary search and search through them for the nearest ways.
113   The worst case is when the nearest nodes are far along a relatively
114   straight line.
115*/
116int *GosmIdxSearch (const char *key, unsigned z)
117{
118  int *idx =
119    (int *)(ndBase + hashTable[bucketsMin1 + (bucketsMin1 >> 7) + 2]);
120  for (int l = 0, h = hashTable - idx; ;) {
121    char *tag = gosmData + idx[(h + l) / 2];
122    int diff = TagCmp (tag, key);
123    while (*--tag) {}
124    if (diff > 0 || (diff == 0 &&
125      ZEnc ((unsigned)((wayType *)tag)[-1].clat >> 16, 
126            (unsigned)((wayType *)tag)[-1].clon >> 16) >= z)) h = (h + l) / 2;
127    else l = (h + l) / 2 + 1;
128    if (l >= h) return idx + h;
129  }
130}
131
132void GosmSearch (int clon, int clat, const char *key)
133{
134  __int64 dista[searchCnt];
135  int *idx =
136    (int *)(ndBase + hashTable[bucketsMin1 + (bucketsMin1 >> 7) + 2]);
137  int l = GosmIdxSearch (key, 0) - idx, count;
138//  char *lastName = data + idx[min (hashTable - idx),
139//    int (sizeof (gosmSway) / sizeof (gosmSway[0]))) + l - 1];
140  int cz = ZEnc ((unsigned) clat >> 16, (unsigned) clon >> 16);
141  for (count = 0; count + l < hashTable - idx && count < searchCnt;) {
142    int m[2], c = count, ipos, dir, bits;
143    m[0] = GosmIdxSearch (gosmData + idx[count + l], cz) - idx;
144    m[1] = m[0] - 1;
145    __int64 distm[2] = { -1, -1 }, big = ((unsigned __int64) 1 << 63) - 1;
146    while (c < searchCnt && (distm[0] < big || distm[1] < big)) {
147      dir = distm[0] < distm[1] ? 0 : 1;
148      if (distm[dir] != -1) {
149        for (ipos = c; count < ipos && distm[dir] < dista[ipos - 1]; ipos--) {
150          dista[ipos] = dista[ipos - 1];
151          gosmSway[ipos] = gosmSway[ipos - 1];
152          gosmSstr[ipos] = gosmSstr[ipos - 1];
153        }
154        char *tag = gosmData + idx[m[dir]];
155        gosmSstr[ipos] = tag;
156        while (*--tag) {}
157        gosmSway[ipos] = (wayType*)tag - 1;
158        dista[ipos] = distm[dir];
159        c++;
160      }
161      m[dir] += dir ? 1 : -1;
162
163      if (0 <= m[dir] && m[dir] < hashTable - idx &&
164        TagCmp (gosmData + idx[m[dir]], gosmData + idx[count + l]) == 0) {
165        char *tag = gosmData + idx[m[dir]];
166        while (*--tag) {}
167        distm[dir] = Sqr ((__int64)(clon - ((wayType*)tag)[-1].clon)) +
168          Sqr ((__int64)(clat - ((wayType*)tag)[-1].clat));
169      }
170      else distm[dir] = big;
171    }
172    if (count == c) break; // Something's wrong. idx[count + l] not found !
173    if (c >= searchCnt) {
174      c = count; // Redo the adding
175      for (bits = 0; bits < 16 && dista[searchCnt - 1] >> (bits * 2 + 32);
176        bits++) {}
177/* Print Z's for first solution
178      for (int j = c; j < searchCnt; j++) {
179        for (int i = 0; i < 32; i++) printf ("%d%s",
180          (ZEnc ((unsigned) gosmSway[j]->clat >> 16,
181                 (unsigned) gosmSway[j]->clon >> 16) >> (31 - i)) & 1,
182          i == 31 ? " y\n" : i % 2 ? " " : "");
183      } */
184/* Print centre, up, down, right and left to see if they're in the square
185      for (int i = 0; i < 32; i++) printf ("%d%s", (cz >> (31 - i)) & 1,
186        i == 31 ? " x\n" : i % 2 ? " " : "");
187      for (int i = 0; i < 32; i++) printf ("%d%s", (
188        ZEnc ((unsigned)(clat + (int) sqrt (dista[searchCnt - 1])) >> 16,
189              (unsigned)clon >> 16) >> (31 - i)) & 1,
190        i == 31 ? " x\n" : i % 2 ? " " : "");
191      for (int i = 0; i < 32; i++) printf ("%d%s", (
192        ZEnc ((unsigned)(clat - (int) sqrt (dista[searchCnt - 1])) >> 16,
193              (unsigned)clon >> 16) >> (31 - i)) & 1,
194        i == 31 ? " x\n" : i % 2 ? " " : "");
195      for (int i = 0; i < 32; i++) printf ("%d%s", (
196        ZEnc ((unsigned)clat >> 16,
197              (unsigned)(clon + (int) sqrt (dista[searchCnt - 1])) >> 16) >> (31 - i)) & 1,
198        i == 31 ? " x\n" : i % 2 ? " " : "");
199      for (int i = 0; i < 32; i++) printf ("%d%s", (
200        ZEnc ((unsigned)clat >> 16,
201              (unsigned)(clon - (int) sqrt (dista[searchCnt - 1])) >> 16) >> (31 - i)) & 1,
202        i == 31 ? " x\n" : i % 2 ? " " : "");
203*/     
204      int swap = cz ^ ZEnc (
205        (unsigned) (clat + (clat & (1 << (bits + 16))) * 4 -
206                                              (2 << (bits + 16))) >> 16,
207        (unsigned) (clon + (clon & (1 << (bits + 16))) * 4 -
208                                              (2 << (bits + 16))) >> 16);
209      // Now we search through the 4 squares around (clat, clon)
210      for (int mask = 0, maskI = 0; maskI < 4; mask += 0x55555555, maskI++) {
211        int s = GosmIdxSearch (gosmData + idx[count + l],
212          (cz ^ (mask & swap)) & ~((4 << (bits << 1)) - 1)) - idx;
213/* Print the square
214        for (int i = 0; i < 32; i++) printf ("%d%s",
215          (((cz ^ (mask & swap)) & ~((4 << (bits << 1)) - 1)) >> (31 - i)) & 1,
216          i == 31 ? "\n" : i % 2 ? " " : "");
217        for (int i = 0; i < 32; i++) printf ("%d%s",
218          (((cz ^ (mask & swap)) | ((4 << (bits << 1)) - 1)) >> (31 - i)) & 1,
219          i == 31 ? "\n" : i % 2 ? " " : "");
220*/
221        for (;;) {
222          char *tag = gosmData + idx[s++];
223          if (TagCmp (gosmData + idx[count + l], tag) != 0) break;
224          while (*--tag) {}
225          wayType *w = (wayType*)tag - 1;
226          if ((ZEnc ((unsigned)w->clat >> 16, (unsigned) w->clon >> 16) ^
227               cz ^ (mask & swap)) >> (2 + (bits << 1))) break;
228          __int64 d = Sqr ((__int64)(w->clat - clat)) +
229                      Sqr ((__int64)(w->clon - clon));
230          if (count < searchCnt || d < dista[count - 1]) {
231            if (count < searchCnt) count++;
232            for (ipos = count - 1; ipos > c && d < dista[ipos - 1]; ipos--) {
233              dista[ipos] = dista[ipos - 1];
234              gosmSway[ipos] = gosmSway[ipos - 1];
235              gosmSstr[ipos] = gosmSstr[ipos - 1];
236            }
237            gosmSway[ipos] = w;
238            dista[ipos] = d;
239            gosmSstr[ipos] = gosmData + idx[s - 1];
240          }
241        } // For each entry in the square
242      } // For each of the 4 squares
243      break; // count < searchCnt implies a bug. Don't loop infinitely.
244    } // If the search list is filled by tags with this text
245    count = c;
246  } // For each
247  for (int k = count; k < searchCnt; k++) gosmSstr[k] = NULL;
248}
249
250/*------------------------------- OsmItr --------------------------------*/
251int Next (OsmItr &itr) /* Friend of osmItr */
252{
253  do {
254    itr.nd[0]++;
255    while (itr.nd[0] >= itr.end) {
256      if ((itr.slon += itr.tsize) == itr.right) {
257        itr.slon = itr.left;  /* Here we wrap around from N85 to S85 ! */
258        if ((itr.slat += itr.tsize) == itr.bottom) return FALSE;
259      }
260      int bucket = Hash (itr.slon, itr.slat, itr.tsize != TILESIZE);
261      itr.nd[0] = ndBase + hashTable[bucket];
262      itr.end = ndBase + hashTable[bucket + 1];
263    }
264  } while (((itr.nd[0]->lon ^ itr.slon) & (~(itr.tsize - 1))) ||
265           ((itr.nd[0]->lat ^ itr.slat) & (~(itr.tsize - 1))));
266/*      ((itr.hs[1] = (halfSegType *) (data + itr.hs[0]->other)) > itr.hs[0] &&
267       itr.left <= itr.hs[1]->lon && itr.hs[1]->lon < itr.right &&
268       itr.top <= itr.hs[1]->lat && itr.hs[1]->lat < itr.bottom)); */
269/* while nd[0] is a hash collision, */ 
270  return TRUE;
271}
272
273/* Routing starts at the 'to' point and moves to the 'from' point. This will
274   help when we do in car navigation because the 'from' point will change
275   often while the 'to' point stays fixed, so we can keep the array of nodes.
276   It also makes the generation of the directions easier.
277
278   We use "double hashing" to keep track of the shortest distance to each
279   node. So we guess an upper limit for the number of nodes that will be
280   considered and then multiply by a few so that there won't be too many
281   clashes. For short distances we allow for dense urban road networks,
282   but beyond a certain point there is bound to be farmland or seas.
283
284   We call nodes that recently had their "best" increased "active". The
285   active nodes are stored in a heap so that we can quickly find the most
286   promissing one.
287   
288   OSM nodes are not our "graph-theor"etic nodes. Our "graph-theor"etic nodes
289   are "states", namely the ability to reach nd directly from nd->other[dir]
290*/
291#ifdef ROUTE_CALIBRATE
292int routeAddCnt;
293#define ROUTE_SET_ADDND_COUNT(x) routeAddCnt = (x)
294#define ROUTE_SHOW_STATS printf ("%d / %d\n", routeAddCnt, dhashSize); \
295  fprintf (stderr, "flat=%lf&flon=%lf&tlat=%lf&tlon=%lf&fast=%d&v=motorcar\n", \
296    LatInverse (flat), LonInverse (flon), LatInverse (tlat), \
297    LonInverse (tlon), fast)
298// This ratio must be around 0.5. Close to 0 or 1 is bad
299#else
300#define ROUTE_SET_ADDND_COUNT(x)
301#define ROUTE_SHOW_STATS
302#endif
303
304static ndType *endNd[2] = { NULL, NULL}, from;
305static int toEndNd[2][2];
306
307void GosmFreeRoute (void)
308{
309  if (route) {
310  #ifndef _WIN32
311    munmap (route, (sizeof (*route)) * dhashSize);
312  #else
313    free (route);
314  #endif
315    free (routeHeap);
316    route = NULL;
317  }   
318  routeSuccess = FALSE;
319}
320
321routeNodeType *AddNd (ndType *nd, int dir, int cost, routeNodeType *newshort)
322{ /* This function is called when we find a valid route that consists of the
323     segments (hs, hs->other), (newshort->hs, newshort->hs->other),
324     (newshort->shortest->hs, newshort->shortest->hs->other), .., 'to'
325     with cost 'cost'.
326     
327     When cost is -1, this function just returns the entry for nd without
328     modifying anything. */
329  if (nd->lat == INT_MIN) return NULL; // Nodes missing from OSM-XML
330  unsigned i = 0, hash = (intptr_t) nd / 10 + dir;
331  routeNodeType *n;
332
333  //if ((routeHeapSize & 0xff) == 0) printf ("%d %d\n", dhashSize, routeHeapSize);
334  do {
335    if (i++ > 10) {
336      //fprintf (stderr, "Double hash bailout : Table full. %9d %p\n",
337      //  routeHeapSize, nd);
338      // If you get the
339      return NULL;
340    }
341    n = route + (/*(hash >> 16) ^ */hash) % dhashSize;
342
343    hash -= hash << 6;
344    hash ^= hash >> 17;
345    hash -= hash << 9;
346    hash ^= hash << 4;
347    hash -= hash << 3;
348    hash ^= hash << 10;
349    hash ^= hash >> 15;
350
351//    hash = (unsigned) (hash * (__int64) 1664525 + 1013904223);
352           
353    if (n->nd == NULL) { /* First visit of this node */
354      if (cost < 0) return NULL;
355      if (routeHeapSize >= routeHeapMaxSize) {
356        //printf ("Route Heap too big\n");
357        return NULL;
358      }
359      n->nd = nd;
360      routeHeap[routeHeapSize].best = 0x7fffffff;
361      /* Will do later : routeHeap[routeHeapSize].r = n; */
362      n->heapIdx = routeHeapSize++;
363      n->dir = dir;
364      n->remain = lrint (sqrt (Sqr ((__int64)(nd->lat - rlat)) +
365                               Sqr ((__int64)(nd->lon - rlon))));
366      if (!shortest || n->remain < shortest->remain) shortest = n;
367
368      ROUTE_SET_ADDND_COUNT (routeAddCnt + 1);
369    }
370  } while (n->nd != nd || n->dir != dir);
371
372  routeHeapType h;
373  h.r = n;
374  h.best = cost + n->remain - (!newshort ? 0 : newshort->heapIdx < 0
375    ? newshort->remain + newshort->heapIdx
376    : newshort->remain - routeHeap[newshort->heapIdx].best);
377  // TODO make sure newshort is never in the heap and exploit it.
378  if (cost >= 0 && (n->heapIdx < 0 ? -n->heapIdx : routeHeap[n->heapIdx].best)
379                   > h.best) {
380    n->shortest = newshort;
381    if (n->heapIdx < 0) n->heapIdx = routeHeapSize++;
382    for (; n->heapIdx > 1 && h.best < routeHeap[n->heapIdx / 2].best; n->heapIdx /= 2) {
383      memcpy (routeHeap + n->heapIdx, routeHeap + n->heapIdx / 2,
384        sizeof (*routeHeap));
385      routeHeap[n->heapIdx].r->heapIdx = n->heapIdx;
386    }
387    memcpy (&routeHeap[n->heapIdx], &h, sizeof (routeHeap[n->heapIdx]));
388  }
389  return n;
390}
391
392inline int IsOneway (wayType *w, int Vehicle)
393{
394  return Vehicle != footR &&
395    (w->bits & (1 << (Vehicle == bicycleR ? bicycleOneway : onewayR)));
396  //!((Vehicle == footR || Vehicle == bicycleR) &&
397  //  (w->bits & (1 << motorcarR))) && (w->bits & (1<<onewayR));
398}
399
400// left-hand drive country aproximate bounding boxes
401static const int lhtBbox[][4] = {
402  { Longitude (10.2), Latitude (-85.0), Longitude (42.1), Latitude (4.7) },
403  // Africa. Not correct for Angola, DRC and a few other poor countries.
404  { Longitude (-14.11), Latitude (49.83), Longitude (1.84), Latitude (60.03) },
405  // UK & IE
406  { Longitude (68.0), Latitude (0.0), Longitude (90.2), Latitude (31.4) },
407  // India & Sri Lanka
408  { Longitude (9.3), Latitude (-85.0), Longitude (179.0), Latitude (19.1) },
409  // Aus, NZ, Indonesia, Malazia, Thailand.
410  { Longitude (129.55), Latitude (18.0), Longitude (145.84), Latitude (45.55) }
411  // Japan
412};
413
414static int lht = FALSE, Vehicle, fast;
415
416void Route (int recalculate, int plon, int plat, int _vehicle, int _fast)
417{ /* Recalculate is faster but only valid if 'to', 'Vehicle' and
418     'fast' did not change */
419/* We start by finding the segment that is closest to 'from' and 'to' */
420  ROUTE_SET_ADDND_COUNT (0);
421  shortest = NULL;
422  routeSuccess = FALSE;
423  Vehicle = _vehicle;
424  fast = _fast;
425  for (int i = recalculate ? 0 : 1; i < 2; i++) {
426    int lon = i ? flon : tlon, lat = i ? flat : tlat;
427    __int64 bestd = (__int64) 1 << 62;
428    /* find min (Sqr (distance)). Use long long so we don't loose accuracy */
429    OsmItr itr (lon - 100000, lat - 100000, lon + 100000, lat + 100000);
430    /* Search 1km x 1km around 'from' for the nearest segment to it */
431    while (Next (itr)) {
432      // We don't do for (int dir = 0; dir < 1; dir++) {
433      // because if our search box is large enough, it will also give us
434      // the other node.
435      if (!(Way (itr.nd[0])->bits & (1 << Vehicle))) {
436        continue;
437      }
438      if (itr.nd[0]->other[0] == 0) continue;
439      __int64 lon0 = lon - itr.nd[0]->lon, lat0 = lat - itr.nd[0]->lat,
440              lon1 = lon - (itr.nd[0] + itr.nd[0]->other[0])->lon,
441              lat1 = lat - (itr.nd[0] + itr.nd[0]->other[0])->lat,
442              dlon = lon1 - lon0, dlat = lat1 - lat0;
443      /* We use Pythagoras to test angles for being greater that 90 and
444         consequently if the point is behind hs[0] or hs[1].
445         If the point is "behind" hs[0], measure distance to hs[0] with
446         Pythagoras. If it's "behind" hs[1], use Pythagoras to hs[1]. If
447         neither, use perpendicular distance from a point to a line */
448      int segLen = lrint (sqrt ((double)(Sqr(dlon) + Sqr (dlat))));
449      __int64 d = dlon * lon0 >= - dlat * lat0 ? Sqr (lon0) + Sqr (lat0) :
450        dlon * lon1 <= - dlat * lat1 ? Sqr (lon1) + Sqr (lat1) :
451        Sqr ((dlon * lat1 - dlat * lon1) / segLen);
452     
453      wayType *w = Way (itr.nd[0]);
454      if (i) { // For 'from' we take motion into account
455        __int64 motion = segLen ? 3 * (dlon * plon + dlat * plat) / segLen
456          : 0;
457        // What is the most appropriate multiplier for motion ?
458        if (motion > 0 && IsOneway (w, Vehicle)) d += Sqr (motion);
459        else d -= Sqr (motion);
460        // Is it better to say :
461        // d = lrint (sqrt ((double) d));
462        // if (motion < 0 || IsOneway (w)) d += motion;
463        // else d -= motion;
464      }
465     
466      if (d < bestd) {
467        bestd = d;
468        double invSpeed = !fast ? 1.0 : Style (w)->invSpeed[Vehicle];
469        //printf ("%d %lf\n", i, invSpeed);
470        toEndNd[i][0] =
471          lrint (sqrt ((double)(Sqr (lon0) + Sqr (lat0))) * invSpeed);
472        toEndNd[i][1] =
473          lrint (sqrt ((double)(Sqr (lon1) + Sqr (lat1))) * invSpeed);
474//        if (dlon * lon1 <= -dlat * lat1) toEndNd[i][1] += toEndNd[i][0] * 9;
475//        if (dlon * lon0 >= -dlat * lat0) toEndNd[i][0] += toEndNd[i][1] * 9;
476
477        if (IsOneway (w, Vehicle)) toEndNd[i][1 - i] = 200000000;
478        /*  It's possible to go up a oneway at the end, but at a huge penalty*/
479        endNd[i] = itr.nd[0];
480        /* The router only stops after it has traversed endHs[1], so if we
481           want 'limit' to be accurate, we must subtract it's length
482        if (i) {
483          toEndHs[1][0] -= segLen;
484          toEndHs[1][1] -= segLen;
485        } */
486      }
487    } /* For each candidate segment */
488    if (bestd == ((__int64) 1 << 62) || !endNd[0]) {
489      endNd[i] = NULL;
490      //fprintf (stderr, "No segment nearby\n");
491      return;
492    }
493  } /* For 'from' and 'to', find segment that passes nearby */
494  from.lat = flat;
495  from.lon = flon;
496  if (recalculate || !route) {
497    GosmFreeRoute ();
498    routeHeapSize = 1; /* Leave position 0 open to simplify the math */
499    #ifndef _WIN32
500    // Google "zero-fill-on-demand". Basically all the reasons they mention are valid.
501    // In particular, while gosmore is paused while a page is swapped in, the OS can
502    // zero some pages for us.
503    int dzero = open ("/dev/zero", O_RDWR);
504    long long ds = sysconf (_SC_PAGESIZE) * (long long) sysconf (_SC_PHYS_PAGES) /
505      (sizeof (*routeHeap) + sizeof (*route) + 40);
506    dhashSize = ds > INT_MAX ? INT_MAX : ds;
507    routeHeapMaxSize = lrint (sqrt (dhashSize)) * 3;
508    routeHeap = (routeHeapType*) malloc (routeHeapMaxSize * sizeof (*routeHeap));
509    if (!routeHeap || dzero == -1 ||
510        (route = (routeNodeType*) mmap (NULL, dhashSize * sizeof (*route),
511        PROT_READ | PROT_WRITE, MAP_SHARED, dzero, 0)) == MAP_FAILED) {
512      fprintf (stderr, "Error: Mmap of dnull for routing arrays\n");
513      route = NULL;
514      return;
515    }
516    if (dzero != -1) close (dzero);
517    #else
518    MEMORYSTATUS memStat;
519    GlobalMemoryStatus (&memStat);
520    dhashSize = (memStat.dwAvailPhys - 400000) /
521                 (sizeof (*route) + sizeof (*routeHeap) + 40);
522
523    routeHeapMaxSize = lrint (sqrt (dhashSize)) * 3;
524    routeHeap = (routeHeapType*) malloc (routeHeapMaxSize * sizeof (*routeHeap));
525    if (!routeHeap) return;
526    if (!(route = (routeNodeType*) calloc (sizeof (*route), dhashSize))) return;
527    #endif
528
529    rlat = flat;
530    rlon = flon;
531    AddNd (endNd[0], 0, toEndNd[0][0], NULL);
532    AddNd (endNd[0] + endNd[0]->other[0], 1, toEndNd[0][1], NULL);
533    AddNd (endNd[0], 1, toEndNd[0][0], NULL);
534    AddNd (endNd[0] + endNd[0]->other[0], 0, toEndNd[0][1], NULL);
535
536    #ifdef INSPECT
537    printf ("\ncycleonewa: %s\n",
538      Way (endNd[0])->bits & (1 << bicycleOneway) ? "yes" : "no");
539    #define M(x) printf ("%10s: %s\n", #x, \
540                   Way (endNd[0])->bits & (1 << x ## R) ? "yes" : "no");
541    RESTRICTIONS
542    #undef M
543    // A bit confusing when the user clicks a way on which the selected
544    // vehicle type is not allowed, because endNd will then be a different
545    // way.
546    #endif
547  }
548  else {
549    routeNodeType *frn = AddNd (&from, 0, -1, NULL);
550    if (frn) {
551      if (frn->heapIdx < 0) frn->heapIdx = -0x7fffffff;
552      else routeHeap[frn->heapIdx].best = 0x7fffffff;
553    }
554
555    routeNodeType *rn = AddNd (endNd[1], 0, -1, NULL);
556    if (rn) AddNd (&from, 0, toEndNd[1][1], rn);
557    routeNodeType *rno = AddNd (endNd[1] + endNd[1]->other[0], 1, -1, NULL);
558    if (rno) AddNd (&from, 0, toEndNd[1][0], rno);
559  }
560  lht = FALSE;
561  // keep lht true if we are not in any of the lhtBbox
562  for (size_t i = 0; i < sizeof (lhtBbox) / sizeof (lhtBbox[0]); i++) {
563    lht = lht || (lhtBbox[i][0] < tlon && lhtBbox[i][1] < tlat &&
564                  tlon < lhtBbox[i][2] && tlat < lhtBbox[i][3]);
565  }
566  // printf (lht ? "Left Hand Traffic\n" : "Right Hand Traffic\n");
567}
568
569int RouteLoop (void)
570{
571  // printf ("%ld %ld\n", clock (), CLOCKS_PER_SEC); // Calibrate loop below
572  for (int i = 0; i < 20000 && routeHeapSize > 1; i++) {
573    routeNodeType *root = routeHeap[1].r;
574    root->heapIdx = -routeHeap[1].best; /* Root now removed from the heap */
575    routeHeapSize--;
576    for (int i = 2; i / 2 < routeHeapSize; ) {
577      routeHeapType *end = &routeHeap[routeHeapSize];
578      int sml = i >= routeHeapSize || routeHeap[i].best > end->best
579        ? (i + 1 >= routeHeapSize || routeHeap[i].best > end->best
580           ? routeHeapSize : i + 1)
581        : routeHeap[i].best < routeHeap[i + 1].best ? i : i + 1;
582      memcpy (routeHeap + i / 2, routeHeap + sml, sizeof (*routeHeap));
583      routeHeap[i / 2].r->heapIdx = i / 2;
584      i = sml * 2;
585    }
586    if (root->nd == &from) { // Remove 'from' from the heap in case we
587      shortest = root->shortest; // get called with recalculate=0
588      routeSuccess = TRUE;
589      return FALSE;
590    }
591    if (root->nd == (!root->dir ? endNd[1] : endNd[1] + endNd[1]->other[0])) {
592      AddNd (&from, 0, toEndNd[1][1 - root->dir], root);
593    }
594    ndType *nd = root->nd, *other, *firstNd, *restrictItr;
595    while (nd > ndBase && nd[-1].lon == nd->lon &&
596      nd[-1].lat == nd->lat) nd--; /* Find first nd in node */
597    firstNd = nd; // Save it for checking layout and restrictions
598    int rootIsAdestination = Way (root->nd)->destination & (1 << Vehicle);
599    /* Now work through the segments connected to root. */
600   
601    unsigned layout[4] = { 0, 0, 0, 0 }, lmask = 1;
602    ndType *rtother = root->nd + root->nd->other[root->dir], *layoutNd[4];
603    // We categorize each segment leaving this junction according to the
604    // angle it form with the 'root' segment. The angles are 315 to 45,
605    // 45 to 135, 135 to 225 and 225 to 315 degrees.
606    do {
607      lmask <<= 2;
608      for (int dir = 0; dir < 2; dir++) {
609        if (nd->other[dir] != 0) {
610          other = nd + nd->other[dir];
611          int dot = (other->lat - nd->lat) * (nd->lat - rtother->lat) +
612                    (other->lon - nd->lon) * (nd->lon - rtother->lon);
613          int cross = (other->lat - nd->lat) * (nd->lon - rtother->lon) -
614                      (other->lon - nd->lon) * (nd->lat - rtother->lat);
615          int azimuth = (dot > cross ? 0 : 3) ^ (dot + cross > 0 ? 0 : 1);
616          layout[azimuth] |= lmask << dir;
617          layoutNd[azimuth] = nd;
618        }
619      }
620    } while (++nd < ndBase + hashTable[bucketsMin1 + 1] &&
621             nd->lon == nd[-1].lon && nd->lat == nd[-1].lat);
622             
623    //printf ("%d %d %d %d\n", layout[0], layout[1], layout[2], layout[3]);
624    nd = firstNd;
625    lmask = 1;
626    do {
627      if (StyleNr (Way (nd)) >= barrier_bollard &&
628          StyleNr (Way (nd)) <= barrier_toll_booth &&
629          !(Way (nd)->bits & (1 << Vehicle))) break;
630      lmask <<= 2;
631    /*  if (root->remain > 2500000 && -root->heapIdx - root->remain > 2500000 &&
632          (StyleNr (Way (nd)) == highway_residential ||
633           StyleNr (Way (nd)) == highway_service ||
634           StyleNr (Way (nd)) == highway_living_street ||
635           StyleNr (Way (nd)) == highway_unclassified)) continue;*/
636      /* When more than 250km from the start and the finish, ignore minor
637         roads. This reduces the number of calculations. */
638      for (int dir = 0; dir < 2; dir++) {
639        if (nd == root->nd && dir == root->dir) continue;
640        /* Don't consider an immediate U-turn to reach root->hs->other.
641           This doesn't exclude 179.99 degree turns though. */
642       
643        if (nd->other[dir] == 0) continue;
644        if (Vehicle != footR && Vehicle != bicycleR) {
645          for (restrictItr = firstNd; restrictItr->other[0] == 0 &&
646                          restrictItr->other[1] == 0; restrictItr++) {
647            wayType *= Way (restrictItr);
648            if (StyleNr (w) >= restriction_no_right_turn &&
649                StyleNr (w) <= restriction_only_straight_on &&
650                atoi ((char*)(w + 1) + 1) == nd->wayPtr &&
651            (StyleNr (w) <= restriction_no_straight_on) ==
652            (atoi (strchr ((char*)(w + 1) + 1, ' ')) == root->nd->wayPtr)) {
653              break;
654            }
655          }
656          if (restrictItr->other[0] == 0 &&
657              restrictItr->other[1] == 0) continue;
658        }
659        // Tagged node, start or end of way or restriction.
660       
661        other = nd + nd->other[dir];
662        wayType *w = Way (nd);
663
664        // // DEBUGGING
665        // char label[255], *strings;
666        // strings=(char*)(w+1)+1;
667        // memset(label,0,255);
668        // strncpy(label,strings,strcspn(strings,"\n"));
669        // printf ("DEBUG: %s (%d) %lf\n", label, StyleNr(w),
670        //      Style(w)->invSpeed[Vehicle]);
671
672
673        int myV = Vehicle == bicycleR && (!(w->bits & (1 << bicycleR)) 
674          || ((w->bits & (1 << bicycleOneway)) && !dir)) ? footR : Vehicle;
675        // If pedestrians are allowed and cyclists not, we can dismount and
676        // walk. The same applies when we can't cycle in the wrong direction.
677        if ((w->bits & (1 << myV)) && (dir || !IsOneway (w, myV))) {
678          int d = lrint (sqrt ((double)
679            (Sqr ((__int64)(nd->lon - other->lon)) +
680             Sqr ((__int64)(nd->lat - other->lat)))) *
681            (!fast ? 1.0 : Style (w)->invSpeed[Vehicle]));
682          if (Vehicle != myV) d *= 4; // Penalty for dismounting
683          if (rootIsAdestination && !(w->destination & (1 << Vehicle))) {
684            d += 5000000; // 500km penalty for entering v='destination' area.
685          }
686         
687          // If (lmask<<dir)&layout[x] is set, we are going approximately
688          // in direction x * 90 degrees, relative to the direction we
689          // are going to (Remember that we are coming from 'root')
690          // If layout[x] is not zero, there are segments going in that
691          // direction
692          if (layout[lht ? 1 : 3] && ((lmask << dir) & layout[lht ? 3 : 1])
693              && fast && Style (w)->scaleMax > 100000) {
694            d += 50000 * (fast ? Style (w)->invSpeed[Vehicle] : 1);
695          // Turning right in the UK (or left in the rest of the world), when
696          // we are on a major road (secondary+) that continues straight on,
697          // you will probably have to wait for oncoming traffic.
698          }
699         
700          if (layout[1] && layout[3] && ((lmask << dir) & layout[0])) {
701            // Straight over a T-junction
702            if ((Way (layoutNd[1])->bits & (1 << motorcarR)) &&
703                (Way (layoutNd[3])->bits & (1 << motorcarR)) && fast) {
704            // And motorcars are allowed on both sides
705              d += (Style (Way (layoutNd[1]))->invSpeed[motorcarR] <
706                    Style (w)->invSpeed[motorcarR] ? 10000 : 3000) *
707                    (fast ? Style (w)->invSpeed[Vehicle] : 1);
708            // Crossing a road that is faster that the road we are traveling
709            // on incurs a 100m penalty. If they are equal, the penality is
710            // 30m. TODO: residential crossing residential should be less,
711            // perhaps 20m.
712            }
713          }
714         
715          ndType *n2 = root->nd + root->nd->other[root->dir];
716          __int64 straight =
717            (n2->lat - nd->lat) * (__int64)(nd->lat - other->lat) +
718            (n2->lon - nd->lon) * (__int64)(nd->lon - other->lon), left =
719            (n2->lat - nd->lat) * (__int64)(nd->lon - other->lon) -
720            (n2->lon - nd->lon) * (__int64)(nd->lat - other->lat);
721          // Note: We need not calculate these, because we can check the relevant
722          // bits in layout
723           
724          // The code below adds a penalty to making a U-turn when an oncoming road
725          // exists for example where a bidirectional road splits into two oneways.
726          // We can add an extra condition to allow a right turn in right hand
727          // traffic countries. Something like '&& lht ? left : -left > 0)'
728         
729          // Currently the threshold angle is 45 degrees (a turn of more than 135 degrees).
730          // We can vary it using this line:
731          // straight = straight * lrint (tan (M_PI / 180 * 45) * 100) / 100;
732          if (straight < -left && straight < left && layout[2]) d += 50000 *
733            (fast ? Style (w)->invSpeed[Vehicle] : 1);
734          // Note: The layout values I've seen during debugging didn't add up.
735         
736          AddNd (other, 1 - dir, d, root);
737        } // If we found a segment we may follow
738      } // for each direction
739    } while (++nd < ndBase + hashTable[bucketsMin1 + 1] &&
740             nd->lon == nd[-1].lon && nd->lat == nd[-1].lat);
741  } // While there are active nodes left
742  ROUTE_SHOW_STATS;
743//  if (fastest) printf ("%lf
744//  printf ("%lf km\n", limit / 100000.0);
745  return routeHeapSize > 1;
746}
747
748int JunctionType (ndType *nd)
749{
750  int ret = 'j';
751  while (nd > ndBase && nd[-1].lon == nd->lon &&
752    nd[-1].lat == nd->lat) nd--;
753  int segCnt = 0; // Count number of segments at x->shortest
754  do {
755    // TODO : Only count segment traversable by 'Vehicle'
756    // Except for the case where a cyclist passes a motorway_link.
757    // TODO : Don't count oneways entering the roundabout
758    if (nd->other[0] != 0) segCnt++;
759    if (nd->other[1] != 0) segCnt++;
760    if (StyleNr (Way (nd)) == highway_traffic_signals) {
761      ret = 't';
762    }
763    if (StyleNr (Way (nd)) == highway_mini_roundabout) {
764      ret = 'm';
765    }   
766  } while (++nd < ndBase + hashTable[bucketsMin1 + 1] &&
767           nd->lon == nd[-1].lon && nd->lat == nd[-1].lat);
768  return segCnt > 2 ? toupper (ret) : ret;
769}
770
771int GosmInit (void *d, long size)
772{
773  if (!d) return FALSE;
774  gosmData = (char*) d;
775  ndBase = (ndType *)(gosmData + ((int*)(gosmData + size))[-1]);
776  bucketsMin1 = ((int *) (gosmData + size))[-2];
777  stylecount = ((int *) (gosmData + size))[-3];
778  style = (struct styleStruct *)
779    (gosmData + size - sizeof (stylecount) * 3) - stylecount;
780  hashTable = (int *) (style) - bucketsMin1 - (bucketsMin1 >> 7) - 3;
781 
782  memset (gosmSway, 0, sizeof (gosmSway));
783
784  return ndBase && hashTable && *(int*) gosmData == pakHead;
785}
786
787// *** EVERYTHING AFTER THIS POINT IS NOT IN THE WINDOWS BUILDS ***
788
789#ifndef _WIN32
790
791void CalculateInvSpeeds (styleStruct *srec, int styleCnt)
792{
793  // for vehicle
794  for (int i = 0; i < layerBit1; i++) {
795    double maxspeed = 0; // More vehicle limit than (legal) maxspeed.
796    for (int j = 0; j < styleCnt; j++) {
797      maxspeed = max (srec[j].aveSpeed[i], maxspeed);
798    }
799    // for style
800    for (int j = 0; j < styleCnt; j++) {
801      // if no speed is defined for a vehicle on this style, then
802      // set the aveSpeed to be the maximum of any other
803      // vehicles. This speed will only be used if vehicle=yes is
804      // defined on the way. (e.g. highway=foot motorcar=yes)
805      if (srec[j].aveSpeed[i] == 0) { 
806        for (int k = 0; k < layerBit1; k++) {
807          if (srec[j].aveSpeed[i] < srec[j].aveSpeed[k]) {
808            srec[j].aveSpeed[i] = srec[j].aveSpeed[k];
809          } 
810        } // without breaking the normal maximum speed for this vehicle
811        if (srec[j].aveSpeed[i] > maxspeed) {
812          srec[j].aveSpeed[i] = maxspeed;
813        }
814      }
815      // store the proportion of maxspeed for routing
816      srec[j].invSpeed[i] = maxspeed / srec[j].aveSpeed[i];
817    }
818  }
819}
820
821void GosmLoadAltStyle(const char* elemstylefile, const char* iconscsvfile) {
822//  static styleStruct srec[2 << STYLE_BITS];
823  elemstyleMapping map[2 << STYLE_BITS]; // this is needed for
824                                         // LoadElemstyles but ignored
825  styleStruct *old = style;
826  style = (styleStruct*) malloc (stylecount * sizeof (*style)); // Mem leak
827  memcpy (style, old, stylecount * sizeof (*style));
828  //memset (&srec, 0, sizeof (srec)); // defined globally
829  memset (&map, 0, sizeof (map));
830  LoadElemstyles(elemstylefile, iconscsvfile, style, map);
831  CalculateInvSpeeds (style, stylecount);
832}
833
834/*--------------------------------- Rebuild code ---------------------------*/
835// These defines are only used during rebuild
836
837#include <sys/mman.h>
838#include <libxml/xmlreader.h>
839
840#define MAX_BUCKETS (1<<26)
841#define IDXGROUPS 676
842#define NGROUPS 60
843#define MAX_NODES 9000000 /* Max in a group */
844#define S2GROUPS 129 // Last group is reserved for lowzoom halfSegs
845#define NGROUP(x)  ((x) / MAX_NODES % NGROUPS + IDXGROUPS)
846#define S1GROUPS NGROUPS
847#define S1GROUP(x) ((x) / MAX_NODES % NGROUPS + IDXGROUPS + NGROUPS)
848#define S2GROUP(x) ((x) / (MAX_BUCKETS / (S2GROUPS - 1)) + IDXGROUPS + NGROUPS * 2)
849#define PAIRS (16 * 1024 * 1024)
850#define PAIRGROUPS 120
851#define PAIRGROUP(x) ((x) / PAIRS + S2GROUP (0) + S2GROUPS)
852#define PAIRGROUPS2 120
853#define PAIRGROUP2(x) ((x) / PAIRS + PAIRGROUP (0) + PAIRGROUPS)
854#define FIRST_LOWZ_OTHER (PAIRS * (PAIRGROUPS - 1))
855
856#define REBUILDWATCH(x) fprintf (stderr, "%3d %s\n", ++rebuildCnt, #x); x
857
858#define TO_HALFSEG -1 // Rebuild only
859
860struct halfSegType { // Rebuild only
861  int lon, lat, other, wayPtr;
862};
863
864struct nodeType {
865  int id, lon, lat;
866};
867
868char *data;
869
870inline nodeType *FindNode (nodeType *table, int id)
871{
872  unsigned hash = id;
873  for (;;) {
874    nodeType *n = &table[hash % MAX_NODES];
875    if (n->id < 0 || n->id == id) return n;
876    hash = hash * (__int64) 1664525 + 1013904223;
877  }
878}
879
880int HalfSegCmp (const halfSegType *a, const halfSegType *b)
881{
882  int lowz = a->other < -2 || FIRST_LOWZ_OTHER <= a->other;
883  int hasha = Hash (a->lon, a->lat, lowz), hashb = Hash (b->lon, b->lat, lowz);
884  return hasha != hashb ? hasha - hashb : a->lon != b->lon ? a->lon - b->lon :
885    a->lat != b->lat ? a->lat - b->lat :
886    (b->other < 0 && b[1].other < 0 ? 1 : 0) -
887    (a->other < 0 && a[1].other < 0 ? 1 : 0);
888} // First sort by hash bucket, then by lon, then by lat.
889// If they are all the same, the nodes goes in the front where so that it's
890// easy to iterate through the turn restrictions.
891
892int IdxCmp (const void *aptr, const void *bptr)
893{
894  char *ta = data + *(unsigned *)aptr, *tb = data + *(unsigned *)bptr;
895  int tag = TagCmp (ta, tb);
896  while (*--ta) {}
897  while (*--tb) {}
898  unsigned a = ZEnc ((unsigned)((wayType *)ta)[-1].clat >> 16, 
899                     (unsigned)((wayType *)ta)[-1].clon >> 16);
900  unsigned b = ZEnc ((unsigned)((wayType *)tb)[-1].clat >> 16, 
901                     (unsigned)((wayType *)tb)[-1].clon >> 16);
902  return tag ? tag : a < b ? -1 : 1;
903}
904
905/* To reduce the number of cache misses and disk seeks we need to construct
906 the pack file so that waysTypes that are physically close to each other, are
907 also close to each other in the file. We only know where ways are physically
908 after the first pass, so the reordering is one done during a bbox rebuild.
909 
910 Finding an optimal solution is quite similar to find a soluting to the
911 traveling salesman problem. Instead we just place them in 2-D Hilbert curve
912 order using a qsort. */
913typedef struct {
914  wayType *w;
915  int idx;
916} masterWayType;
917
918int MasterWayCmp (const void *a, const void *b)
919{
920  int r[2], t, s, i, lead;
921  for (i = 0; i < 2; i++) {
922    t = ZEnc (((masterWayType *)(i ? b : a))->w->clon >> 16,
923      ((unsigned)((masterWayType *)(i ? b : a))->w->clat) >> 16);
924    s = ((((unsigned)t & 0xaaaaaaaa) >> 1) | ((t & 0x55555555) << 1)) ^ ~t;
925    for (lead = 1 << 30; lead; lead >>= 2) {
926      if (!(t & lead)) t ^= ((t & (lead << 1)) ? s : ~s) & (lead - 1);
927    }
928    r[i] = ((t & 0xaaaaaaaa) >> 1) ^ t;
929  }
930  return r[0] < r[1] ? 1 : r[0] > r[1] ? -1 : 0;
931}
932
933int LoadElemstyles(/* in */ const char *elemstylesfname, 
934                   const char *iconsfname,
935                   /* out */ styleStruct *srec, elemstyleMapping *map)
936{
937   //------------------------- elemstyle.xml : --------------------------
938    int ruleCnt = 0, styleCnt = firstElemStyle;
939    // zero-out elemstyle-to-stylestruct mappings
940    FILE *icons_csv = fopen (iconsfname, "r");
941    xmlTextReaderPtr sXml = xmlNewTextReaderFilename (elemstylesfname);
942    if (!sXml || !icons_csv) {
943      fprintf (stderr, "Either icons.csv or elemstyles.xml not found\n");
944      return 3;
945    }
946    styleStruct s;
947    memset (&s, 0, sizeof (s));
948    s.lineColour = -1;
949    s.areaColour = -1;
950
951    for (int i = 0; i < styleCnt; i++) memcpy (&srec[i], &s, sizeof (s));
952
953    /* If elemstyles contain these, we can delete these assignments : */
954    for (int i = restriction_no_right_turn;
955            i <= restriction_only_straight_on; i++) {
956      strcpy(map[i].style_k,"restriction");
957      srec[i].scaleMax = 1;
958      srec[i].lineColour = 0; // Make it match.
959    }
960    strcpy(map[restriction_no_right_turn].style_v,"no_right_turn");
961    strcpy(map[restriction_no_left_turn].style_v,"no_left_turn");
962    strcpy(map[restriction_no_u_turn].style_v,"no_u_turn");
963    strcpy(map[restriction_no_straight_on].style_v,"no_straight_on");
964    strcpy(map[restriction_only_right_turn].style_v,"only_right_turn");
965    strcpy(map[restriction_only_left_turn].style_v,"only_left_turn");
966    strcpy(map[restriction_only_straight_on].style_v,"only_straight_on");
967    /* These strcpys are necessary because elemstyles does not contain them */
968   
969    while (xmlTextReaderRead (sXml)) {
970      char *name = (char*) xmlTextReaderName (sXml);
971      //xmlChar *val = xmlTextReaderValue (sXml);
972      if (xmlTextReaderNodeType (sXml) == XML_READER_TYPE_ELEMENT) {
973        if (strcasecmp (name, "scale_max") == 0) {
974          while (xmlTextReaderRead (sXml) && // memory leak :
975            xmlStrcmp (xmlTextReaderName (sXml), BAD_CAST "#text") != 0) {}
976          s.scaleMax = atoi ((char *) xmlTextReaderValue (sXml));
977        }
978        while (xmlTextReaderMoveToNextAttribute (sXml)) {
979          char *n = (char *) xmlTextReaderName (sXml);
980          char *v = (char *) xmlTextReaderValue (sXml);
981          if (strcasecmp (name, "condition") == 0) {
982            if (strcasecmp (n, "k") == 0) strcpy(map[styleCnt].style_k, v);
983            if (strcasecmp (n, "v") == 0) strcpy(map[styleCnt].style_v, v);
984          }
985          if (strcasecmp (name, "line") == 0) {
986            if (strcasecmp (n, "width") == 0) {
987              s.lineWidth = atoi (v);
988            }
989            if (strcasecmp (n, "realwidth") == 0) {
990              s.lineRWidth = atoi (v);
991            }
992            if (strcasecmp (n, "colour") == 0) {
993              sscanf (v, "#%x", &s.lineColour);
994            }
995            if (strcasecmp (n, "colour_bg") == 0) {
996              sscanf (v, "#%x", &s.lineColourBg);
997            }
998            s.dashed = s.dashed ||
999              (strcasecmp (n, "dashed") == 0 && strcasecmp (v, "true") == 0);
1000          }
1001          if (strcasecmp (name, "area") == 0) {
1002            if (strcasecmp (n, "colour") == 0) {
1003              sscanf (v, "#%x", &s.areaColour);
1004            }
1005          }
1006          if (strcasecmp (name, "icon") == 0) {
1007            if (strcasecmp (n, "src") == 0) {
1008              /*while (v[strcspn ((char *) v, "/ ")]) {
1009                v[strcspn ((char *) v, "/ ")] = '_';
1010              }*/
1011              char line[400], fnd = FALSE;
1012              static const char *set[] = { "map-icons/classic.big/",
1013                "map-icons/classic.small/", "map-icons/square.big/",
1014                "map-icons/square.small/" };
1015              for (int i = 0; i < 4; i++) {
1016                s.x[i * 4 + 2] = s.x[i * 4 + 3] = 1;
1017              // Default to 1x1 dummys
1018                int slen = strlen (set[i]), vlen = strlen (v);
1019                rewind (icons_csv);
1020                while (fgets (line, sizeof (line) - 1, icons_csv)) {
1021                  if (strncmp (line, set[i], slen) == 0 &&
1022                      strncmp (line + slen, v, vlen - 1) == 0) {
1023                    sscanf (line + slen + vlen, ":%d:%d:%d:%d",
1024                      s.x + i * 4,     s.x + i * 4 + 1,
1025                      s.x + i * 4 + 2, s.x + i * 4 + 3);
1026                    fnd = TRUE;
1027                  }
1028                }
1029              }
1030              if (!fnd) fprintf (stderr, "Icon %s not found\n", v);
1031            }
1032          }
1033          if (strcasecmp (name, "routing") == 0 && atoi (v) > 0) {
1034            #define M(field) if (strcasecmp (n, #field) == 0) {\
1035              map[styleCnt].defaultRestrict |= 1 << field ## R; \
1036              s.aveSpeed[field ## R] = atof (v); \
1037            }
1038            RESTRICTIONS
1039            #undef M
1040          }
1041         
1042          xmlFree (v);
1043          xmlFree (n);
1044        }
1045      }
1046      else if (xmlTextReaderNodeType (sXml) == XML_READER_TYPE_END_ELEMENT
1047                  && strcasecmp ((char *) name, "rule") == 0) {
1048        int ipos;
1049        #define s(k,v,shortname,extraTags) { #k, #v },
1050        static const char *stylet[][2] = { STYLES };
1051        #undef s
1052        for (ipos = 0; ipos < firstElemStyle; ipos++) {
1053          if (strcmp (stylet[ipos][0], map[styleCnt].style_k) == 0 && 
1054              strcmp (stylet[ipos][1], map[styleCnt].style_v) == 0) break;
1055        }
1056        map[ipos < firstElemStyle ? ipos : styleCnt].ruleNr = ruleCnt++;
1057        if (ipos < firstElemStyle) {
1058          memcpy (&srec[ipos], &s, sizeof (srec[ipos]));
1059          map[ipos].defaultRestrict = map[styleCnt].defaultRestrict;
1060          map[styleCnt].defaultRestrict = 0;
1061          strcpy(map[ipos].style_k,map[styleCnt].style_k);
1062          strcpy(map[ipos].style_v,map[styleCnt].style_v);
1063        }
1064        else if (styleCnt < (2 << STYLE_BITS) - 2) {
1065          memcpy (&srec[styleCnt++], &s, sizeof (srec[0]));
1066        }
1067        else fprintf (stderr, "Too many rules. Increase STYLE_BITS\n");
1068
1069        memset (&s, 0, sizeof (s));
1070        s.lineColour = -1;
1071        s.areaColour = -1;
1072      }
1073      xmlFree (name);
1074      //xmlFree (val);     
1075    }
1076
1077    xmlFreeTextReader (sXml);
1078
1079    return styleCnt;
1080}
1081
1082struct ltstr
1083{
1084  bool operator ()(const char *a, const char *b) const
1085  {
1086    return strcmp (a, b) < 0;
1087  }
1088};
1089
1090struct k2vType {
1091  map<const char *, const char *, ltstr> m;
1092  const char *operator[](const char *k) const
1093  {
1094    return m.find (k) == m.end () ? NULL : m.find (k)->second;
1095  } // For std:map the operator[] is not const, so we wrap it in a new class
1096};
1097
1098typedef char *membershipType;
1099
1100inline char *Role (membershipType rt)
1101{
1102  return !rt ? NULL : rt + strlen (rt) + 1;
1103}
1104
1105char *Find (membershipType rt, const char *key)
1106{
1107  if (!rt) return NULL;
1108  rt += strlen (rt) + 1; // id
1109  rt += strlen (rt) + 1; // role
1110  while (*rt != '\0' && strcmp (key, rt) != 0) {
1111    rt += strlen (rt) + 1; // id
1112    rt += strlen (rt) + 1; // role   
1113  }
1114  return *rt == '\0' ? NULL : rt + strlen (rt) + 1;
1115}
1116
1117membershipType Next (membershipType rt)
1118{
1119  if (!rt) return NULL;
1120  membershipType old = rt;
1121  while (*rt != '\0') {
1122    rt += strlen (rt) + 1; // id or k
1123    rt += strlen (rt) + 1; // role or v
1124  }
1125  return strcmp (rt + 1, old) == 0 ? rt + 1 : NULL; // Compare ids
1126}
1127
1128//----------------------------[ Osm2Gosmore ]-----------------------------
1129// This function translates the complicated and ever changing language of
1130// OSM into the superfast Gosmore language.
1131//
1132// Before Gosmore calls this function it will have matched the tags to
1133// an entry in elemstyles.xml and filled in 's'. If there are multiple
1134// matches, the first one is chosen. You can modify the values of 's',
1135// but be aware that the number of different 's' records are limited. So
1136// you should map (quantitize) rarely used values (like 38 km/h) to more
1137// frequently used values (like 40 km/h).
1138//
1139// It will also have filled in the access and destination fields of w.
1140// During a second pass, the center point of w will also be valid. So
1141// you can test if the way was inside any object for which you have data,
1142// like a city. Or you can adjust the average speed of unpaved ways based on
1143// an average annual rainfall map.
1144//
1145// You are also supplied with the relations table (rStart and rEnd). It has
1146// one entry for each relation that the the object is a member of. Use
1147// Next () to iterate through them, Role () to determine how it affects this
1148// way and Find () to examine the it's tags.
1149//
1150// You must return a list of strings which will be concatenated into the
1151// storage of the object and indexed for searching purposes. Normally each
1152// string will occupy one line (end in '\n'). For
1153// example { "Macdonalds\n", "restaurant\n" }.
1154// Empty lines are removed and will not be indexed. And strings can span
1155// any number of lines. So
1156//   { "Jerusalem\nar:", "al-Quds\n" } is equivalent to
1157//   { "Jerusalem\n", "\nar:", "al-Quds\n" }
1158// and it means that the object can be searched for as Jerusalem and al-Quds.
1159// Furthermore, a clever renderer can then render the correct name.
1160// A single line can also be indexed multiple times. For example
1161// { "city:", "Paris\n" } will be indexed as "Paris" and "city:Paris".
1162//
1163// NOTE: Gosmore currently requires that you return the same strings during
1164// both passes of the rebuild, i.e. the strings cannot depend on w.clat or clon
1165
1166deque<string> Osm2Gosmore (int /*id*/, k2vType &k2v, wayType &w,
1167  styleStruct &s, int isNode, int isRelation, membershipType membership,
1168  k2vType &wayRole /* Only for relations, and only for those members who are ways.
1169                      role->file offset in decimal */)
1170{
1171  deque<string> result;
1172 
1173/*  char idStr[12]; // Add way id so that it appear in cgi-bin output
1174  sprintf (idStr, "%d", idStr);
1175  result.push_front (string (idStr) + '\n'); */
1176 
1177  // First add name and 'ref' to the front so that they are displayed
1178  if (k2v["name"]) {
1179    result.push_front (string (k2v["name"]) + "\n");
1180    if (k2v["place"] && strcmp (k2v["place"], "city") == 0) {
1181      result.push_back ("city:" + string (k2v["name"]) + "\n");
1182    }
1183  }
1184  else if (k2v["left:district"]) {
1185    result.push_front (string ("\n") + k2v["left:district"] + '\n');
1186  }
1187  else if (k2v["right:district"]) {
1188    result.push_front (string ("\n") + k2v["right:district"] + '\n');
1189  }
1190  else if (k2v["left:municipality"]) {
1191    result.push_front (string ("\n") + k2v["left:municipality"] + '\n');
1192  }
1193  else if (k2v["right:municipality"]) {
1194    result.push_front (string ("\n") + k2v["right:municipality"] + '\n');
1195  }
1196  else {
1197    membershipType m; // Could be something like a boundary
1198    for (m = membership; m && !Find (m, "name"); m = Next (m)) {}
1199    if (m) result.push_front (string ("\n") + Find (m, "name") + '\n');
1200    // Put name on a new line so that it will not be indexed.
1201  }
1202 
1203  if (k2v["ref"]) result.push_back (string (k2v["ref"]) + "\n");
1204  if (k2v["operator"]) result.push_back (string (k2v["operator"]) + "\n");
1205  map<const char *, const char *, ltstr>::iterator i = k2v.m.begin ();
1206  // Go through all the tags and add all the interesting things to 'result'
1207  // so that they will be indexed.
1208  for (; i != k2v.m.end (); i++) {
1209    if (strcmp (i->first, "name") != 0 &&
1210        strcmp (i->first, "ref") != 0 &&
1211        strcmp (i->first, "operator") != 0 &&
1212        strncasecmp (i->first, "tiger:", 6) != 0 &&
1213        strcmp (i->first, "created_by") != 0 &&
1214        strcmp (i->first, "converted_by") != 0 &&
1215        strncasecmp (i->first, "source", 6) != 0 &&
1216        strncasecmp (i->first, "AND_", 4) != 0 &&
1217        strncasecmp (i->first, "AND:", 4) != 0 &&
1218        strncasecmp (i->first, "kms:", 4) != 0 &&
1219        strncasecmp (i->first, "LandPro08:", 10) != 0 &&
1220        strncasecmp (i->first, "NHD:", 4) != 0 &&
1221        strncasecmp (i->first, "massgis:", 8) != 0 &&
1222        strncasecmp (i->first, "scgis-shp:", 10) != 0 &&
1223        strcmp (i->first, "addr:street") != 0 &&
1224        strcmp (i->first, "addr:postcode") != 0 &&
1225        strcmp (i->first, "addr:district") != 0 &&
1226        strcmp (i->first, "addr:region") != 0 &&
1227        strcmp (i->first, "addr:state") != 0 &&
1228        strcmp (i->first, "addr:city") != 0 &&
1229        strcmp (i->first, "addr:country") != 0 &&
1230        !(strcmp (i->first, "addr:conscriptionnumber") == 0 && k2v["addr:housenumber"]) &&
1231        // The mvcr:adresa import sets both the conscription number & housenumber
1232        !(strcmp (i->first, "postal_code") == 0 && !isNode) &&
1233        // Many European ways include the postal code. Although it's nice to be able to
1234        // highlight all the streets in a postal code (after searching), it's more likely
1235        // to slow down the software unnecessarily.
1236
1237        strncasecmp (i->first, "KSJ2:", 5) != 0 && 
1238        strncasecmp (i->first, "geobase:", 8)  != 0 &&
1239        strncasecmp (i->first, "kms:", 4)  != 0 &&
1240        strncasecmp (i->first, "openGeoDB:", 10)  != 0 &&
1241        strncasecmp (i->first, "gnis:", 5)  != 0 &&
1242        strncasecmp (i->first, "CLC:", 4)  != 0 && // CORINE Land Cover
1243
1244        strcmp (i->second, // Abuse of the 'note' tag !
1245          "Experimental import of Irish places and POIs from GNS Dataset") != 0 &&
1246        strcmp (i->second, // What is the difference between Key:comment and Key:note ?
1247          "Experimental import of Canadian places and POIs from GNS Dataset") != 0 &&
1248       
1249        strncasecmp (i->first, "gns:", 4)  != 0 &&
1250        strcmp (i->first, "place_county") != 0 && 
1251       
1252        strcmp (i->first, "code_department") != 0 && // France / EtienneChoveBot
1253        strcmp (i->first, "ref:INSEE") != 0 && // France / EtienneChoveBot
1254
1255        strncasecmp (i->first, "it:fvg:ctrn:", 12)  != 0 && // What is this??
1256
1257        strncasecmp (i->first, "3dshapes:", 9)  != 0 && // Import in the Netherlands
1258
1259        strncasecmp (i->first, "TMC:", 4)  != 0 && // Traffic broadcast info esp. Germany
1260
1261        strncasecmp (i->first, "cladr:", 6)  != 0 && // Some Russian import
1262       
1263        strncmp (i->first, "BP:", 2)  != 0 && // British Petroleum import
1264        strcmp (i->first, "amenity:eftpos") != 0 && // Payment method not important
1265
1266        strncasecmp (i->first, "chile:", 6)  != 0 && // vialidad.cl import
1267        strncasecmp (i->first, "navibot:", 8)  != 0 && // navimont's tag
1268       
1269        strncasecmp (i->first, "is_in:", 6)  != 0 && // teryt
1270       
1271        strncasecmp (i->first, "teryt:", 6)  != 0 && // in Poland
1272
1273        strncasecmp (i->first, "naptan:", 7)  != 0 && // UK bus stops
1274        !((strcmp (i->first, "local_ref") == 0 || strcmp (i->first, "name") == 0 ||
1275          /* strcmp (i->first, "route_ref") == 0 ||*/ strcmp (i->first, "asset_ref") == 0 ||
1276           strcmp (i->first, "ref") == 0) && k2v["naptan:CommonName"]) &&
1277        // This second test removes the names, refs and local_refs from naptan bus stops,
1278        // as the information is not very useful.
1279       
1280        (strcmp (i->first, "census:population") != 0 || !k2v["population"]) && // GNIS import
1281       
1282        strncmp (i->first, "qroti:", 6) != 0 &&
1283
1284        strcmp (i->first, "area") != 0 && // Too vague
1285        strcmp (i->first, "building") != 0 &&
1286        strcmp (i->first, "building:use") != 0 &&
1287
1288        strcmp (i->second, "surveillance") != 0 && // man_made=...
1289        strcmp (i->first, "surveillance") != 0 && // e.g. ...=indoor
1290        // I doubt anyone will have a legal reason to search for a security camera
1291       
1292        strcmp (i->first, "note:ja") != 0 &&
1293       
1294        !(strcmp (i->first, "ref") == 0 && strncmp (i->second, "http://", 7) == 0) &&
1295        // Abused during the EPA import
1296
1297        strcmp (i->second, "tree") != 0 && // A few of these in Berlin
1298       
1299        strcmp (i->first, "import_uuid") != 0 &&
1300        strcmp (i->first, "attribution") /* Mostly MassGIS */ != 0 &&
1301        strcmp (i->first, "layer") != 0 &&
1302        strcmp (i->first, "history") != 0 &&
1303        strcmp (i->first, "direction") != 0 &&
1304        strcmp (i->first, "maxspeed") != 0 &&
1305        strcmp (i->first, "maxwidth") != 0 &&
1306        strcmp (i->first, "access") != 0 &&
1307        strcmp (i->first, "motorcar") != 0 &&
1308        strcmp (i->first, "bicycle") != 0 &&
1309        strcmp (i->first, "foot") != 0 &&
1310        strcmp (i->first, "goods") != 0 &&
1311        strcmp (i->first, "hgv") != 0 &&
1312        strcmp (i->first, "horse") != 0 &&
1313        strcmp (i->first, "motorcycle") != 0 &&
1314        strcmp (i->first, "psv") != 0 &&
1315        strcmp (i->first, "moped") != 0 &&
1316        strcmp (i->first, "mofa") != 0 &&
1317        strcmp (i->first, "motorboat") != 0 &&
1318        strcmp (i->first, "boat") != 0 &&
1319        strcmp (i->first, "oneway") != 0 &&
1320        strcmp (i->first, "roundabout") != 0 &&
1321        strcmp (i->first, "time") != 0 &&
1322        strcmp (i->first, "timestamp") != 0 && // User WanMil in Luxembourg
1323        strcmp (i->first, "ele") != 0 &&
1324        strcmp (i->first, "hdop") != 0 &&
1325        strcmp (i->first, "sat") != 0 &&
1326        strcmp (i->first, "pdop") != 0 &&
1327        strcmp (i->first, "speed") != 0 &&
1328        strcmp (i->first, "course") != 0 &&
1329        strcmp (i->first, "fix") != 0 &&
1330        strcmp (i->first, "vdop") != 0 &&
1331        strcmp (i->first, "image") != 0 && // =http://www.flickr...
1332        strcmp (i->second, "no") != 0      &&
1333        strcmp (i->second, "false") != 0 &&
1334        strcmp (i->first, "sagns_id") != 0 &&
1335        strcmp (i->first, "sangs_id") != 0 &&
1336        strcmp (i->first, "is_in") != 0 &&
1337        strcmp (i->second, "level_crossing") != 0 && // railway=level_crossing
1338        strcmp (i->second, "living_street") != 0 &&
1339        strcmp (i->second, "residential") != 0 &&
1340        strcmp (i->second, "unclassified") != 0 &&
1341        strcmp (i->second, "tertiary") != 0 &&
1342        strcmp (i->second, "secondary") != 0 && 
1343        strcmp (i->second, "primary") != 0 && // Esp. ValidateMode
1344        strcmp (i->second, "junction") != 0 && 
1345   /* Not approved and when it isn't obvious
1346      from the ways that it's a junction, the tag will
1347      often be something ridiculous like
1348      junction=junction ! */
1349        // blocked as highway:  strcmp (i->second, "mini_roundabout") != 0
1350        //                      && strcmp (i->second, "roundabout") != 0
1351        strcmp (i->second, "place_of_worship") != 0 && // Too vague to include
1352        strcmp (i->first, "crossing") != 0 &&
1353        strcmp (i->first, "barrier") != 0 &&
1354        strcmp (i->second, "traffic_signals") != 0 &&
1355        strcmp (i->first, "editor") != 0 &&
1356        strcmp (i->first, "power") != 0 && // Power towers
1357        strcmp (i->first, "class") != 0 /* esp. class=node */ &&
1358        strcmp (i->first, "type") != 0 &&
1359        /* "type=..." is only allow for boules grounds. We block it because it
1360        is often misused. */
1361         0 != strcmp (i->second, 
1362  "National-Land Numerical Information (Railway) 2007, MLIT Japan") &&
1363         0 != strcmp (i->second, 
1364  "National-Land Numerical Information (Lake and Pond) 2005, MLIT Japan") &&
1365         0 != strcmp (i->second, 
1366  "National-Land Numerical Information (Administrative area) 2007, MLIT Japan") &&
1367         strcmp (i->second, "coastline_old") != 0 &&
1368         strcmp (i->first, "upload_tag") != 0 &&
1369         strcmp (i->first, "admin_level") != 0 &&
1370         (!isNode || (strcmp (i->first, "highway") != 0 &&
1371                      strcmp (i->second, "water") != 0 &&
1372                      strcmp (i->first, "abutters") != 0 &&
1373                      strcmp (i->second, "coastline") != 0))) {
1374      result.push_back (
1375        strcmp (i->first, "population") == 0 ? string ("\npop. ") + i->second + '\n':
1376        // Don't index population figures, but make it obvious what it is.
1377        strcmp (i->first, "phone") == 0 || strcmp (i->first, "addr:housenumber") == 0 ?
1378          string ("\n") + i->second + '\n':
1379        // Don't index phonenumbers or housenumbers.
1380        // Some day I hope to include housenumber data into the data for the street it is on.
1381        // Then, when the user enters a housenumber and a street name,
1382        // we search by street and filter by housenumber
1383        strcmp (i->first, "noexit") == 0 ? string ("\nnoexit\n") :
1384        // Don't index noexit
1385        strncasecmp (i->first, "wikipedia", 9) == 0 ?
1386                         string ("\nwikipedia\n") :
1387        // Don't index wikipedia names, but make it obvious that it's on there.
1388        string (strcmp (i->second, "true") == 0 ||
1389                strcmp (i->second, "yes") == 0 || strcmp (i->second, "1") == 0
1390                ? strncasecmp (i->first, "amenity:", 8) == 0 ? i->first + 8
1391                // Strip off amenity: from things like amenity:restaurant (BP import)
1392                : i->first : i->second) + "\n");
1393    }
1394  }
1395  membershipType m;
1396  for (m = membership; m && !(Find (m, "route") &&
1397    strcmp (Find (m, "route"), "bicycle") == 0); m = Next (m)) {}
1398  // We go through all the relations (regardless of role), but stop if we find
1399  // one with route=bicycle. Then m will be set.
1400  if (m || k2v["lcn_ref"] || k2v["rcn_ref"] || k2v["ncn_ref"]) {
1401    // if part of a cycle route relation or if it has a cycle network reference
1402    s.aveSpeed[bicycleR] = 20;
1403    // then we say cyclists will love it.
1404  }
1405 
1406  if (isRelation && k2v["restriction"] && wayRole["from"] && wayRole["to"]) {
1407    result.push_front (
1408      string ("\n") + wayRole["from"] + ' ' + wayRole["to"] + '\n');
1409    // A turn restriction with both a 'from' and a 'to'. Put the offsets (not
1410    // OSM-ids) encoded as decimal (ASCII) where the router expects them.
1411   
1412  }
1413  // Reduce the aveSpeeds when maxspeed mandates it
1414  if (k2v["maxspeed"] && isdigit (k2v["maxspeed"][0])) {
1415    const char *m = k2v["maxspeed"];
1416    double maxs = atof (m), best = 30, m2km = 1.609344;
1417    // Here we find the first alphabetic character and compare it to 'm'
1418    if (tolower (m[strcspn (m, "KMPSkmps")]) == 'm') maxs *= m2km;
1419    // choose the closest of these values ...
1420    int v[] = { 5,7,10,15,20,30,32,40,45,50,60,70,80,90,100,110,120,130 };
1421    for (unsigned i = 0; i < sizeof (v) / sizeof (v[1]); i++) {
1422      // ... either in km/h
1423      if (fabs (maxs - best) > fabs (maxs - v[i])) best = v[i];
1424      // ... or in miles/h
1425      if (fabs (maxs - best) > fabs (maxs - v[i] * m2km)) best = v[i] * m2km;
1426    }
1427    s.aveSpeed[accessR] = best;
1428    for (int i = 0; i < layerBit1; i++) {
1429      if (s.aveSpeed[i] > best) s.aveSpeed[i] = best;
1430    }
1431  }
1432  // Now adjust for track type.
1433  if (k2v["tracktype"] && isdigit (k2v["tracktype"][5])) {
1434    s.aveSpeed[motorcarR] *= ('6' - k2v["tracktype"][5]) / 5.0;
1435    // Alternatively use ... (6 - atoi (k2v["tracktype"] + 5)) / 5.0;
1436    // TODO: Mooaar
1437  }
1438  if ((w.bits & (1 << onewayR)) && !(k2v["cycleway"] &&
1439    (strcmp (k2v["cycleway"], "opposite_lane") == 0 ||
1440     strcmp (k2v["cycleway"], "opposite_track") == 0 ||
1441     strcmp (k2v["cycleway"], "opposite") == 0))) {
1442    // On oneway roads, cyclists are only allowed to go in the opposite
1443    // direction, if the cycleway tag exist and starts with "opposite"
1444    w.bits |= 1 << bicycleOneway;
1445  }
1446//  printf ("%.5lf %.5lf\n", LonInverse (w.clon), LatInverse (w.clat));
1447  return result;
1448}
1449
1450#define FWRITEY(y) { perror ("fwrite @ " #y); exit (1); }
1451#define FWRITEX(x) FWRITEY (x) // Use argument prescan feature of CPP
1452#define FWRITE(addr,size,count,f) { if (fwrite (addr, size, count, f) \
1453                                      != (size_t)(count)) FWRITEX (__LINE__) }
1454
1455ndType *LFollow (ndType *nd, ndType *ndItr, wayType *w, int forward)
1456{ // Helper function when a way is copied into lowzoom table.
1457  if (forward) {
1458    nd += nd->other[1];
1459    if (nd->other[1]) return nd;
1460  }
1461  if (nd->lat == nd[1].lat && nd->lon == nd[1].lon) {
1462    if ((nd->lat != nd[2].lat || nd->lon != nd[2].lon) &&
1463        (nd->lat != nd[-1].lat || nd->lon != nd[-1].lon ||
1464         // If there is a 3rd object there,
1465         (nd[-1].other[0] == 0 && nd[-1].other[0] == 0)) &&
1466        // then it must be a node
1467        nd + 1 != ndItr && nd[1].other[!forward ? 1 : 0] == 0
1468        // Must not loop back to start and must not be T juntion
1469        && StyleNr (w) == StyleNr ((wayType*)(data + nd[1].wayPtr))) nd++;
1470  }
1471  else if (nd->lat == nd[-1].lat && nd->lon == nd[-1].lon &&
1472           (nd->lat != nd[-2].lat || nd->lon != nd[-2].lon ||
1473            // If there is a 3rd object there,
1474            (nd[-2].other[0] == 0 && nd[-2].other[0] == 0)) &&
1475            // then it must be a node
1476           nd - 1 != ndItr && nd[-1].other[!forward ? 1 : 0] == 0
1477           // Must not loop back to start and must not be T juntion
1478           && StyleNr (w) == StyleNr ((wayType*)(data + nd[-1].wayPtr))) nd--;
1479  // If nd ends at a point where exactly two ways meet and they have the same
1480  // StyleNr we can 'route' across it.
1481  // But we can't go back to wayPtr, e.g. circular way.
1482  return nd;
1483}
1484
1485int RebuildPak(const char* pakfile, const char* elemstylefile, 
1486               const char* iconscsvfile, const char* masterpakfile, 
1487               const int bbox[4]) {
1488  assert (layerBit3 < 32);
1489
1490  int rebuildCnt = 0;
1491  FILE *pak, *masterf;
1492  int ndStart;
1493  wayType *master = NULL;
1494  if (strcmp(masterpakfile,"")) {
1495    if (!(masterf = fopen64 (masterpakfile, "r")) ||
1496        fseek (masterf, -sizeof (ndStart), SEEK_END) != 0 ||
1497        fread (&ndStart, sizeof (ndStart), 1, masterf) != 1 ||
1498        (long)(master = (wayType *)mmap (NULL, ndStart, PROT_READ,
1499                                         MAP_SHARED, fileno (masterf), 
1500                                         0)) == -1) {
1501      fprintf (stderr, "Unable to open %s for bbox rebuild\n",masterpakfile);
1502      return 4;
1503    }
1504  }
1505 
1506  if (!(pak = fopen64 (pakfile, "w+"))) {
1507    fprintf (stderr, "Cannot create %s\n",pakfile);
1508    return 2;
1509  }
1510  FWRITE (&pakHead, sizeof (pakHead), 1, pak);
1511
1512  //------------------------ elemstylesfile : -----------------------------
1513  styleStruct srec[2 << STYLE_BITS];
1514  elemstyleMapping eMap[2 << STYLE_BITS];
1515  memset (&srec, 0, sizeof (srec));
1516  memset (&eMap, 0, sizeof (eMap));
1517 
1518  int elemCnt = LoadElemstyles(elemstylefile, iconscsvfile,
1519                                srec, eMap), styleCnt = elemCnt;
1520 
1521 
1522  //------------------ OSM Data File (/dev/stdin) : ------------------------
1523  xmlTextReaderPtr xml = xmlReaderForFd (STDIN_FILENO, "", NULL, 0);
1524  FILE *groupf[PAIRGROUP2 (0) + PAIRGROUPS2];
1525  char groupName[PAIRGROUP2 (0) + PAIRGROUPS2][9];
1526  for (int i = 0; i < PAIRGROUP2 (0) + PAIRGROUPS2; i++) {
1527    sprintf (groupName[i], "%c%c%d.tmp", i / 26 % 26 + 'a', i % 26 + 'a',
1528             i / 26 / 26);
1529    if (i < S2GROUP (0) && !(groupf[i] = fopen64 (groupName[i], "w+"))) {
1530      fprintf (stderr, "Cannot create temporary file.\n"
1531               "Possibly too many open files, in which case you must run "
1532               "ulimit -n or recompile\n");
1533      return 9;
1534     
1535    }
1536  }
1537 
1538#if 0 // For making sure we have a Hilbert curve
1539  bucketsMin1 = MAX_BUCKETS - 1;
1540  for (int x = 0; x < 16; x++) {
1541    for (int y = 0; y < 16; y++) {
1542      printf ("%7d ", Hash (x << TILEBITS, y << TILEBITS));
1543    }
1544    printf ("\n");
1545  }
1546#endif
1547   
1548  nodeType nd;
1549  halfSegType s[2];
1550  int nOther = 0, lowzOther = FIRST_LOWZ_OTHER, isNode = 0;
1551  int yesMask = 0, noMask = 0;
1552  struct {
1553    wayType *w; // Pointer to the first version in the master file.
1554    int off;
1555  } *wayFseek = NULL;
1556  int wStyle = elemCnt, ref = 0;
1557  int relationType = 0, onewayReverse = 0;
1558  vector<int> wayMember;
1559  map<int,int> wayId;
1560  wayType w;
1561  w.clat = 0;
1562  w.clon = 0;
1563  w.dlat = INT_MIN;
1564  w.dlon = INT_MIN;
1565  w.bits = 0;
1566  w.destination = 0;
1567 
1568  // if we are doing a second pass bbox rebuild
1569  if (master) {
1570    masterWayType *masterWay = (masterWayType *) 
1571      malloc (sizeof (*masterWay) * (ndStart / (sizeof (wayType) + 4)));
1572   
1573    unsigned i = 0, offset = ftell (pak), wcnt;
1574    wayType *m = (wayType *)(((char *)master) + offset);
1575    for (wcnt = 0; (char*) m < (char*) master + ndStart; wcnt++) {
1576      if (bbox[0] <= m->clat + m->dlat && bbox[1] <= m->clon + m->dlon &&
1577          m->clat - m->dlat <= bbox[2] && m->clon - m->dlon <= bbox[3]) {
1578        masterWay[i].idx = wcnt;
1579        masterWay[i++].w = m;
1580      }
1581      m = (wayType*)((char*)m +
1582                     ((1 + strlen ((char*)(m + 1) + 1) + 1 + 3) & ~3)) + 1;
1583    }
1584    qsort (masterWay, i, sizeof (*masterWay), MasterWayCmp);
1585    assert (wayFseek = (typeof (wayFseek)) calloc (sizeof (*wayFseek),
1586                                      ndStart / (sizeof (wayType) + 4)));
1587    for (unsigned j = 0; j < i; j++) {
1588      wayFseek[masterWay[j].idx].off = offset;
1589      wayFseek[masterWay[j].idx].w = masterWay[j].w;
1590      offset += sizeof (*masterWay[j].w) +
1591        ((1 + strlen ((char*)(masterWay[j].w + 1) + 1) + 1 + 3) & ~3);
1592    }
1593    wayFseek[wcnt].off = offset;
1594    fflush (pak);
1595    if (ftruncate (fileno (pak), offset) != 0) perror ("ftruncate");
1596    free (masterWay);
1597    fseek (pak, wayFseek->off, SEEK_SET);
1598  }
1599 
1600  char *relationTable;
1601  FILE *relationTableFile = fopen ("relations.tbl", "r");
1602  if (!relationTableFile || fseek (relationTableFile, 0, SEEK_END) != 0 ||
1603      (relationTable = (char*) mmap (NULL, ftell (relationTableFile), PROT_READ,
1604        MAP_SHARED, fileno (relationTableFile), 0)) == (char*)-1) {
1605    relationTable = (char*) "z1"; // Stopper
1606    fprintf (stderr, "Processing without relations table\n");
1607  }
1608 
1609  char *tag_k = NULL, *role = NULL; //, *tags = (char *) BAD_CAST xmlStrdup (BAD_CAST "");
1610  //char *nameTag = NULL;
1611  k2vType k2v, wayRole; // wayRole should be a vector< struct{char*,int} > ...
1612  deque<int> wayNd;
1613  map<int, deque<int> > outer;
1614  REBUILDWATCH (while (xmlTextReaderRead (xml))) {
1615    char *name = (char *) BAD_CAST xmlTextReaderName (xml);
1616    //xmlChar *value = xmlTextReaderValue (xml); // always empty
1617    if (xmlTextReaderNodeType (xml) == XML_READER_TYPE_ELEMENT) {
1618      isNode = stricmp (name, "way") != 0 && stricmp (name, "relation") != 0
1619        && (stricmp (name, "node") == 0 || isNode);
1620      while (xmlTextReaderMoveToNextAttribute (xml)) {
1621        char *aname = (char *) BAD_CAST xmlTextReaderName (xml);
1622        char *avalue = (char *) BAD_CAST xmlTextReaderValue (xml);
1623        //        if (xmlStrcasecmp (name, "node") == 0)
1624        if (stricmp (aname, "id") == 0) nd.id = atoi (avalue);
1625        if (stricmp (aname, "lat") == 0) nd.lat = Latitude (atof (avalue));
1626        if (stricmp (aname, "lon") == 0) nd.lon = Longitude (atof (avalue));
1627        if (stricmp (aname, "ref") == 0) ref = atoi (avalue);
1628        if (stricmp (aname, "type") == 0) relationType = avalue[0];
1629
1630#define K_IS(x) (stricmp (tag_k, x) == 0)
1631#define V_IS(x) (stricmp (avalue, x) == 0)
1632
1633        if (stricmp (aname, "role") == 0) role = avalue;
1634        else if (stricmp (aname, "v") == 0) {
1635         
1636          int newStyle = 0;
1637          // TODO: this for loop could be clearer as a while
1638          for (; newStyle < elemCnt && !(K_IS (eMap[newStyle].style_k) &&
1639                                          (eMap[newStyle].style_v[0] == '\0' || V_IS (eMap[newStyle].style_v)) &&
1640                                          (isNode ? srec[newStyle].x[2] :
1641                                           srec[newStyle].lineColour != -1 ||
1642                                           srec[newStyle].areaColour != -1)); newStyle++) {}
1643          // elemstyles rules are from most important to least important
1644          // Ulf has placed rules at the beginning that will highlight
1645          // errors, like oneway=true -> icon=deprecated. So they must only
1646          // match nodes when no line or area colour was given and only
1647          // match ways when no icon was given.
1648          if (K_IS ("junction") && V_IS ("roundabout")) {
1649            yesMask |= (1 << onewayR) | (1 << roundaboutR);
1650          }
1651          else if (newStyle < elemCnt && 
1652                   (wStyle == elemCnt || 
1653                    eMap[wStyle].ruleNr > eMap[newStyle].ruleNr)) {
1654            wStyle = newStyle;
1655          }
1656         
1657          if (K_IS ("layer")) w.bits |= atoi (avalue) << 29;
1658         
1659#define M(field) else if (K_IS (#field)) {                              \
1660            if (V_IS ("yes") || V_IS ("1") || V_IS ("permissive") ||    \
1661                V_IS ("true") || V_IS ("designated") ||                 \
1662                V_IS ("official") || V_IS ("-1")) {                     \
1663              yesMask |= 1 << field ## R;                               \
1664              if (K_IS ("oneway") && V_IS ("-1")) onewayReverse = TRUE; \
1665            } else if (V_IS ("no") || V_IS ("0") || V_IS ("private")) { \
1666              noMask |= 1 << field ## R;                                \
1667            }                                                           \
1668            else if (V_IS ("destination")) {                            \
1669              yesMask |= 1 << field ## R;                               \
1670              w.destination |= 1 << field ## R;                         \
1671            }                                                           \
1672          }
1673          RESTRICTIONS
1674#undef M
1675           
1676          k2v.m[tag_k] = avalue; // Will be freed after Osm2Gosmore()
1677        }
1678        else if (stricmp (aname, "k") == 0) tag_k = avalue;
1679        else xmlFree (avalue); // Not "k", "v" or "role"
1680       
1681        xmlFree (aname);
1682      } /* While it's an attribute */
1683      if (/*relationType == 'w' && */ stricmp (name, "member") == 0) {
1684        //map<int,int>::iterator refId = wayId.find (ref);
1685        //if (refId != wayId.end ()) wayMember.push_back (refId->second);
1686        wayMember.push_back (ref);
1687      }
1688      if (!wayFseek || wayFseek->off) { // This test / guard is no longer needed.
1689        if (stricmp (name, "member") == 0 && role) {
1690          if (relationType == 'n' && stricmp (role, "via") == 0) wayNd.push_back (ref);
1691         
1692          map<int,int>::iterator refId = wayId.find (ref);
1693          if (relationType == 'w' && refId != wayId.end ()) {
1694            char tmp[12];
1695            sprintf (tmp, "%d", refId->second);
1696            wayRole.m[role] = (char*) xmlStrdup (BAD_CAST tmp);
1697          }
1698          else xmlFree (role);
1699          role = NULL;
1700        }
1701        else if (stricmp (name, "nd") == 0) wayNd.push_back (ref);
1702      }
1703      if (stricmp (name, "node") == 0 && bbox[0] <= nd.lat &&
1704          bbox[1] <= nd.lon && nd.lat <= bbox[2] && nd.lon <= bbox[3]) {
1705        FWRITE (&nd, sizeof (nd), 1, groupf[NGROUP (nd.id)]);
1706      }
1707    }
1708    if (xmlTextReaderNodeType (xml) == XML_READER_TYPE_END_ELEMENT) {
1709      int nameIsNode = stricmp (name, "node") == 0;
1710      int nameIsRelation = stricmp (name, "relation") == 0;
1711      if (nameIsRelation && k2v["type"] &&
1712          strcmp (k2v["type"], "multipolygon") == 0) {
1713        while (!wayMember.empty ()) {
1714          int idx;
1715          for (idx = wayMember.size () - 1; !outer[wayMember[idx]].empty () ; idx--) {
1716            deque<int> *o = &outer[wayMember[idx]];
1717            if (wayNd.empty () || wayNd.back () == o->front () || idx == 0) {
1718              if (!wayNd.empty () && wayNd.back () == o->front ()) wayNd.pop_back ();
1719              wayNd.insert (wayNd.end (), o->begin (), o->end ());
1720              break;
1721            }
1722            if (wayNd.back () == o->back ()) {
1723              wayNd.pop_back ();
1724              wayNd.insert (wayNd.end (), o->rbegin (), o->rend ());
1725              break;
1726            }
1727          }
1728          //printf ("iiiiiiiii %d %d %d %u %s %s\n", idx, nd.id, wayMember[idx],
1729          //  outer[wayMember[idx]].size (), eMap[wStyle].style_k, eMap[wStyle].style_v);
1730          wayMember[idx] = wayMember.back ();
1731          wayMember.pop_back ();
1732        }
1733      }
1734      if (nameIsRelation) wayMember.clear ();
1735      if (stricmp (name, "way") == 0 || nameIsNode || nameIsRelation) {
1736        if (!nameIsRelation && !nameIsNode) {
1737          wayId[nd.id] = ftell (pak);
1738        }
1739        /*if (nameTag) {
1740          char *oldTags = tags;
1741          tags = (char *) xmlStrdup (BAD_CAST "\n");
1742          tags = (char *) xmlStrcat (BAD_CAST tags, BAD_CAST nameTag);
1743          tags = (char *) xmlStrcat (BAD_CAST tags, BAD_CAST oldTags);
1744          xmlFree (oldTags);
1745          xmlFree (nameTag);
1746          nameTag = NULL;
1747        }*/
1748        while (*relationTable < (isNode ? 'n' : nameIsRelation ? 'x' : 'w') ||
1749            (*relationTable == (isNode ? 'n' : nameIsRelation ? 'x' : 'w') &&
1750             atoi (relationTable + 1) < nd.id)) {
1751          do {
1752            relationTable += strlen (relationTable) + 1;
1753            relationTable += strlen (relationTable) + 1;
1754          } while (*relationTable++ != '\0');
1755        }
1756        membershipType membership =
1757          *relationTable == (isNode ? 'n' : nameIsRelation ? 'x' : 'w') &&
1758              atoi (relationTable + 1) == nd.id ? relationTable : NULL;
1759
1760        for (membershipType m = membership; m; m = Next (m)) {
1761          if (strcmp (Role (m), "inner") == 0 && wStyle == elemCnt) {
1762            for (wStyle = 0; wStyle < elemCnt; wStyle++) {
1763              if (strcmp (eMap[wStyle].style_k, "natural") == 0 &&
1764                  strcmp (eMap[wStyle].style_v, "glacier") == 0) break;
1765              // Rendering does not support holes, so we just render something
1766              // close to the background colour
1767            }
1768          }
1769          else if (strcmp (Role (m), "outer") == 0) {
1770            outer[nd.id] = deque<int> ();
1771            outer[nd.id].insert (outer[nd.id].end (), wayNd.begin (), wayNd.end ());
1772          }
1773        }
1774       
1775        if (wStyle == elemCnt /* 1 trick that did help enough to make files < 400MB
1776          || (!k2v["name"] && srec[wStyle].areaColour != -1)*/ ) wayNd.clear ();
1777        else {
1778          s[0].other = -2;
1779          while (!wayNd.empty ()) {
1780            s[0].wayPtr = ftell (pak);
1781            s[1].wayPtr = TO_HALFSEG;
1782            s[1].other = s[0].other + 1;
1783            s[0].lat = onewayReverse ? wayNd.back () : wayNd.front ();
1784            /*if (lowzListCnt >=
1785                int (sizeof (lowzList) / sizeof (lowzList[0]))) lowzListCnt--;
1786            lowzList[lowzListCnt++] = s[0].lat; */
1787            if (onewayReverse) wayNd.pop_back ();
1788            else wayNd.pop_front ();
1789            s[0].other = wayNd.empty () ? -2 : nOther++ * 2;
1790            FWRITE (s, sizeof (s), 1, groupf[S1GROUP (s[0].lat)]);
1791          }
1792          if (nameIsNode && (!wayFseek || wayFseek->off)) {
1793            s[0].lat = nd.id; // Create 2 fake halfSegs
1794            s[0].wayPtr = ftell (pak);
1795            s[1].wayPtr = TO_HALFSEG;
1796            s[0].other = -2; // No next
1797            s[1].other = -1; // No prev
1798            //lowzList[lowzListCnt++] = nd.id;
1799            FWRITE (s, sizeof (s), 1, groupf[S1GROUP (s[0].lat)]);
1800          }
1801         
1802          w.bits |= ~noMask & (yesMask | (eMap[wStyle].defaultRestrict &
1803                                          ((noMask & (1 << accessR)) ? (1 << onewayR) : ~0)));
1804          if (w.destination & (1 << accessR)) w.destination = ~0;
1805          memcpy (&srec[styleCnt], &srec[wStyle], sizeof (srec[0]));
1806          if (wayFseek && wayFseek->off) {
1807            w.clat = wayFseek->w->clat;
1808            w.clon = wayFseek->w->clon;
1809            w.dlat = wayFseek->w->dlat;
1810            w.dlon = wayFseek->w->dlon;
1811          }
1812          deque<string> tags = Osm2Gosmore (nd.id, k2v, w, srec[styleCnt], isNode,
1813            nameIsRelation, membership, wayRole);
1814          while (memcmp (&srec[styleCnt], &srec[wStyle], sizeof (srec[0]))
1815                 != 0) wStyle++;
1816          w.bits += wStyle;
1817          if (wStyle == styleCnt) {
1818            if (styleCnt == (2 << STYLE_BITS) - 2) {
1819              fprintf (stderr, "*** Warning: Too many styles !!!\n");
1820            }
1821            if (styleCnt < (2 << STYLE_BITS) - 1) styleCnt++;
1822          }
1823         
1824          /*if (srec[StyleNr (&w)].scaleMax > 10000000 &&
1825              (!wayFseek || wayFseek->off)) {
1826            for (int i = 0; i < lowzListCnt; i++) {
1827              if (i % 10 && i < lowzListCnt - 1) continue; // Skip some
1828              s[0].lat = lowzList[i];
1829              s[0].wayPtr = ftell (pak);
1830              s[1].wayPtr = TO_HALFSEG;
1831              s[1].other = i == 0 ? -4 : lowzOther++;
1832              s[0].other = i == lowzListCnt -1 ? -4 : lowzOther++;
1833              FWRITE (s, sizeof (s), 1, groupf[S1GROUP (s[0].lat)]);
1834            }
1835          }
1836          lowzListCnt = 0; */
1837         
1838          /*if (StyleNr (&w) < elemCnt && stricmp (eMap[StyleNr (&w)].style_v,
1839                                                  "city") == 0 && tags[0] == '\n') {
1840            int nlen = strcspn (tags + 1, "\n");
1841            char *n = (char *) xmlMalloc (strlen (tags) + 1 + nlen + 5 + 1);
1842            strcpy (n, tags);
1843            memcpy (n + strlen (tags), tags, 1 + nlen);
1844            strcpy (n + strlen (tags) + 1 + nlen, " City");
1845            //fprintf (stderr, "Mark : %s\n", n + strlen (tags) + 1);
1846            xmlFree (tags);
1847            tags = n;
1848          }
1849          char *compact = tags[0] == '\n' ? tags + 1 : tags; */
1850          if (!wayFseek || wayFseek->off) {
1851            FWRITE (&w, sizeof (w), 1, pak);
1852            FWRITE ("", 1, 1, pak); // '\0' at the front
1853            unsigned newln = 0;
1854            for (; !tags.empty (); tags.pop_front ()) {
1855              if (newln) FWRITE ("\n", 1, 1, pak);
1856              const char *compact = tags.front().c_str ();
1857              if (tags.front ()[0] == '\n') compact++;
1858              else {
1859                // If all the idxes went into a single file, this can
1860                // be simplified a lot. One day when RAM is cheap.
1861                string line;
1862                deque<string>::iterator tItr = tags.begin ();
1863                do line += *tItr;
1864                while (!strchr ((*tItr++).c_str (), '\n') &&
1865                       tItr != tags.end ());
1866               
1867                unsigned grp, idx = ftell (pak);
1868                for (grp = 0; grp < IDXGROUPS - 1 &&
1869                 TagCmp (groupName[grp], (char*) line.c_str ()) < 0; grp++) {}
1870                FWRITE (&idx, sizeof (idx), 1, groupf[grp]);
1871              }
1872              unsigned l = strlen (compact);
1873              newln = l > 0 && compact[l - 1] == '\n' ? 1 : 0;
1874              if (l > newln) FWRITE (compact, l - newln, 1, pak);
1875            }
1876            FWRITE ("", 1, 1, pak); // '\0' at the back
1877/*          for (char *ptr = tags; *ptr != '\0'; ) {
1878              if (*ptr++ == '\n') {
1879                unsigned idx = ftell (pak) + ptr - 1 - tags, grp;
1880                for (grp = 0; grp < IDXGROUPS - 1 &&
1881                       TagCmp (groupName[grp], ptr) < 0; grp++) {}
1882                FWRITE (&idx, sizeof (idx), 1, groupf[grp]);
1883              }
1884            }
1885            FWRITE (compact, strlen (compact) + 1, 1, pak); */
1886           
1887            // Write variable length tags and align on 4 bytes
1888            if (ftell (pak) & 3) {
1889              FWRITE ("   ", 4 - (ftell (pak) & 3), 1, pak);
1890            }
1891          }
1892          if (wayFseek) fseek (pak, (++wayFseek)->off, SEEK_SET);
1893          //xmlFree (tags); // Just set tags[0] = '\0'
1894          //tags = (char *) xmlStrdup (BAD_CAST "");
1895        }
1896        //tags[0] = '\0'; // Erase nodes with short names
1897        yesMask = noMask = 0;
1898        w.bits = 0;
1899        w.destination = 0;
1900        wStyle = elemCnt;
1901        onewayReverse = FALSE;
1902        while (!k2v.m.empty ()) {
1903          xmlFree ((char*) k2v.m.begin()->second);
1904          xmlFree ((char*) k2v.m.begin()->first);
1905          k2v.m.erase (k2v.m.begin ());
1906        }
1907        while (!wayRole.m.empty ()) {
1908          xmlFree ((char*) wayRole.m.begin()->second);
1909          xmlFree ((char*) wayRole.m.begin()->first);
1910          wayRole.m.erase (wayRole.m.begin ());
1911        }
1912      }
1913    } // if it was </...>
1914    xmlFree (name);
1915  } // While reading xml
1916  wayId.clear ();
1917  assert (nOther * 2 < FIRST_LOWZ_OTHER);
1918  bucketsMin1 = (nOther >> 5) | (nOther >> 4);
1919  bucketsMin1 |= bucketsMin1 >> 2;
1920  bucketsMin1 |= bucketsMin1 >> 4;
1921  bucketsMin1 |= bucketsMin1 >> 8;
1922  bucketsMin1 |= bucketsMin1 >> 16;
1923  assert (bucketsMin1 < MAX_BUCKETS);
1924 
1925  for (int i = 0; i < IDXGROUPS; i++) fclose (groupf[i]);
1926  for (int i = S2GROUP (0); i < PAIRGROUP2 (0) + PAIRGROUPS2; i++) {
1927    assert (groupf[i] = fopen64 (groupName[i], "w+"));
1928  } // Avoid exceeding ulimit
1929 
1930  nodeType *nodes = (nodeType *) malloc (sizeof (*nodes) * MAX_NODES);
1931  if (!nodes) {
1932    fprintf (stderr, "Out of memory. Reduce MAX_NODES and increase GRPs\n");
1933    return 3;
1934  }
1935  for (int i = NGROUP (0); i < NGROUP (0) + NGROUPS; i++) {
1936    rewind (groupf[i]);
1937    memset (nodes, -1, sizeof (*nodes) * MAX_NODES);
1938    REBUILDWATCH (while (fread (&nd, sizeof (nd), 1, groupf[i]) == 1)) {
1939      memcpy (FindNode (nodes, nd.id), &nd, sizeof (nd));
1940    }
1941    fclose (groupf[i]);
1942    unlink (groupName[i]);
1943    rewind (groupf[i + NGROUPS]);
1944    REBUILDWATCH (while (fread (s, sizeof (s), 1, groupf[i + NGROUPS])
1945                         == 1)) {
1946      nodeType *n = FindNode (nodes, s[0].lat);
1947      //if (n->id == -1) printf ("** Undefined node %d\n", s[0].lat);
1948      s[0].lat = s[1].lat = n->id != -1 ? n->lat : INT_MIN;
1949      s[0].lon = s[1].lon = n->id != -1 ? n->lon : INT_MIN;
1950      FWRITE (s, sizeof (s), 1,
1951              groupf[-2 <= s[0].other && s[0].other < FIRST_LOWZ_OTHER
1952                     ? S2GROUP (Hash (s[0].lon, s[0].lat)) : PAIRGROUP (0) - 1]);
1953    }
1954    fclose (groupf[i + NGROUPS]);
1955    unlink (groupName[i + NGROUPS]);
1956  }
1957  free (nodes);
1958 
1959  struct {
1960    int nOther1, final;
1961  } offsetpair;
1962  offsetpair.final = 0;
1963 
1964  hashTable = (int *) malloc (sizeof (*hashTable) *
1965                              (bucketsMin1 + (bucketsMin1 >> 7) + 3));
1966  int bucket = -1;
1967  for (int i = S2GROUP (0); i < S2GROUP (0) + S2GROUPS; i++) {
1968    fflush (groupf[i]);
1969    size_t size = ftell (groupf[i]);
1970    rewind (groupf[i]);
1971    REBUILDWATCH (halfSegType *seg = (halfSegType *) mmap (NULL, size,
1972                                                           PROT_READ | PROT_WRITE, MAP_SHARED, fileno (groupf[i]), 0));
1973    qsort (seg, size / sizeof (s), sizeof (s),
1974           (int (*)(const void *, const void *))HalfSegCmp);
1975    for (int j = 0; j < int (size / sizeof (seg[0])); j++) {
1976      if (!(j & 1)) {
1977        while (bucket < Hash (seg[j].lon, seg[j].lat, FALSE)) {
1978//                            i >= S2GROUP (0) + S2GROUPS - 1)) {
1979          hashTable[++bucket] = offsetpair.final / 2;
1980        }
1981      }
1982      offsetpair.nOther1 = seg[j].other;
1983      if (seg[j].other >= 0) FWRITE (&offsetpair, sizeof (offsetpair), 1,
1984                                     groupf[PAIRGROUP (offsetpair.nOther1)]);
1985      offsetpair.final++;
1986    }
1987    munmap (seg, size);
1988  }
1989  while (bucket < bucketsMin1 + 1) {
1990    hashTable[++bucket] = offsetpair.final / 2;
1991  }
1992 
1993  ndType ndWrite;
1994  ndWrite.wayPtr = s[0].wayPtr; // sizeof (pakHead); // Anything halfvalid
1995  ndWrite.lon = ndWrite.lat = INT_MIN;
1996  ndWrite.other[0] = ndWrite.other[1] = 0;
1997  FWRITE (&ndWrite, sizeof (ndWrite), 1, pak); // Insert 'stopper' record
1998
1999  ndStart = ftell (pak);
2000 
2001  int *pairing = (int *) malloc (sizeof (*pairing) * PAIRS);
2002  for (int i = PAIRGROUP (0); i < PAIRGROUP (0) + PAIRGROUPS; i++) {
2003    REBUILDWATCH (rewind (groupf[i]));
2004    while (fread (&offsetpair, sizeof (offsetpair), 1, groupf[i]) == 1) {
2005      pairing[offsetpair.nOther1 % PAIRS] = offsetpair.final;
2006    }
2007    int pairs = ftell (groupf[i]) / sizeof (offsetpair);
2008    for (int j = 0; j < pairs; j++) {
2009      offsetpair.final = pairing[j ^ 1];
2010      offsetpair.nOther1 = pairing[j];
2011      FWRITE (&offsetpair, sizeof (offsetpair), 1,
2012              groupf[PAIRGROUP2 (offsetpair.nOther1)]);
2013    }
2014    fclose (groupf[i]);
2015    unlink (groupName[i]);
2016  }
2017  free (pairing);
2018 
2019  int s2grp = S2GROUP (0), pairs, totalp = 0;
2020  halfSegType *seg = (halfSegType *) malloc (PAIRS * sizeof (*seg));
2021  assert (seg /* Out of memory. Reduce PAIRS for small scale rebuilds. */);
2022  for (int i = PAIRGROUP2 (0); i < PAIRGROUP2 (0) + PAIRGROUPS2; i++) {
2023    REBUILDWATCH (for (pairs = 0; pairs < PAIRS &&
2024                         s2grp < S2GROUP (0) + S2GROUPS; )) {
2025      if (fread (&seg[pairs], sizeof (seg[0]), 2, groupf [s2grp]) == 2) {
2026        pairs += 2;
2027      }
2028      else {
2029        fclose (groupf[s2grp]);
2030        unlink (groupName[s2grp]);
2031        s2grp++;
2032      }
2033    }
2034    rewind (groupf[i]);
2035    while (fread (&offsetpair, sizeof (offsetpair), 1, groupf[i]) == 1) {
2036      seg[offsetpair.nOther1 % PAIRS].other = offsetpair.final;
2037    }
2038    for (int j = 0; j < pairs; j += 2) {
2039      ndWrite.wayPtr = seg[j].wayPtr;
2040      ndWrite.lat = seg[j].lat;
2041      ndWrite.lon = seg[j].lon;
2042      ndWrite.other[0] = //seg[j].other >> 1; // Right shift handles -1 the
2043        seg[j].other < 0 ? 0 : (seg[j].other >> 1) - totalp;
2044      ndWrite.other[1] = //seg[j + 1].other >> 1; // way we want.
2045        seg[j + 1].other < 0 ? 0 : (seg[j + 1].other >> 1) - totalp;
2046      totalp++;
2047      FWRITE (&ndWrite, sizeof (ndWrite), 1, pak);
2048    }
2049    fclose (groupf[i]);
2050    unlink (groupName[i]);
2051  }
2052  free (seg);
2053  ndWrite.wayPtr = s[0].wayPtr; // sizeof (pakHead); // Anything halfvalid
2054  ndWrite.lon = ndWrite.lat = INT_MIN;
2055  ndWrite.other[0] = ndWrite.other[1] = 0;
2056  FWRITE (&ndWrite, sizeof (ndWrite), 1, pak); // Insert 'stopper' record
2057  hashTable[bucket]++; // And reserve space for it.
2058 
2059  fflush (pak);
2060  data = (char *) mmap (NULL, ftell (pak),
2061                        PROT_READ | PROT_WRITE, MAP_SHARED, fileno (pak), 0);
2062  fseek (pak, ftell (pak), SEEK_SET);
2063  vector<halfSegType> lseg;
2064  ndBase = (ndType*)(data + ndStart);
2065  REBUILDWATCH (for (ndType *ndItr = ndBase;
2066                ndItr < ndBase + hashTable[bucketsMin1 + 1]; ndItr++)) {
2067  //while (fread (&ndWrite, sizeof (ndWrite), 1, pak) == 1)) {
2068    wayType *way = (wayType*) (data + ndItr->wayPtr);
2069    /* The difficult way of calculating bounding boxes,
2070       namely to adjust the centerpoint (it does save us a pass) : */
2071    // Block lost nodes with if (ndItr->lat == INT_MIN) continue;
2072    if (way->clat + way->dlat < ndItr->lat) {
2073      way->dlat = way->dlat < 0 ? 0 : // Bootstrap
2074        (way->dlat - way->clat + ndItr->lat) / 2;
2075      way->clat = ndItr->lat - way->dlat;
2076    }
2077    if (way->clat - way->dlat > ndItr->lat) {
2078      way->dlat = (way->dlat + way->clat - ndItr->lat) / 2;
2079      way->clat = ndItr->lat + way->dlat;
2080    }
2081    if (way->clon + way->dlon < ndItr->lon) {
2082      way->dlon = way->dlon < 0 ? 0 : // Bootstrap
2083        (way->dlon - way->clon + ndItr->lon) / 2;
2084      way->clon = ndItr->lon - way->dlon;
2085    }
2086    if (way->clon - way->dlon > ndItr->lon) {
2087      way->dlon = (way->dlon + way->clon - ndItr->lon) / 2;
2088      way->clon = ndItr->lon + way->dlon;
2089    }
2090
2091    // This is a simplified version of the rebuild: It does not use groups or files
2092    // and the lats & lons have been dereferenced previously. So the pairing is
2093    // simplified a lot.
2094    ndType *prev = LFollow (ndItr, ndItr, way, 0);
2095    if (!ndItr->other[0] && prev->wayPtr >= ndItr->wayPtr) {
2096      int length = 0;
2097      ndType *end;
2098      for (end = ndItr; end->other[1]; end = LFollow (end, ndItr, way, 1)) {
2099        length += lrint (sqrt (Sqr ((double)(end->lat - end[end->other[1]].lat)) +
2100                               Sqr ((double)(end->lon - end[end->other[1]].lon))));
2101        if (prev != ndItr && end->wayPtr < ndItr->wayPtr) break;
2102        // If it is circular and we didn't start at the way with the lowest
2103        // wayPtr, then we abort
2104      }
2105      if ((prev == ndItr || prev == end) && (length > 500000 ||
2106                  (end == ndItr && srec[StyleNr (way)].scaleMax > 100000))) {
2107        //printf (prev == ndItr ? "%3d Non circular %s\n" : "%3d Circular %s\n",
2108        //  ndItr - ndBase, (char*)(way+1)+1);
2109        //if (prev == ndItr) printf ("Circular\n");
2110        //printf ("%d\n", srec[StyleNr (way)].scaleMax);
2111        deque<ndType*> dp (1, end); // Stack for Ramer-Douglas-Peucker algorithm
2112        for (ndType *nd = ndItr; ; ) {
2113          ndType *worst = NULL, *dpItr; // Look for worst between nd and dp.back()
2114          if (nd != end) {
2115            double len = sqrt (Sqr ((double)(dp.back()->lon - nd->lon)) +
2116                               Sqr ((double)(nd->lat - dp.back ()->lat)));
2117            double latc = (dp.back ()->lon - nd->lon) / len, maxeps = 10000;
2118            double lonc = (nd->lat - dp.back ()->lat) / len, eps;
2119            for (dpItr = nd; dpItr != dp.back (); dpItr = LFollow (dpItr, ndItr, way, 1)) {
2120              eps = len == 0 ? sqrt (Sqr ((double)(dpItr->lat - nd->lat) -
2121                                          (double)(dpItr->lon - nd->lon))) :
2122                fabs ((dpItr->lat - nd->lat) * latc + (dpItr->lon - nd->lon) * lonc);
2123              if (eps > maxeps) {
2124                maxeps = eps;
2125                worst = dpItr;
2126              }
2127            }
2128          }
2129          if (worst) dp.push_back (worst);
2130          else { // The segment is reasonable
2131            lseg.push_back (halfSegType ());
2132            lseg.back ().lon = nd->lon;
2133            lseg.back ().lat = nd->lat;
2134            lseg.back ().wayPtr = ndItr->wayPtr;
2135            lseg.push_back (halfSegType ());
2136            lseg.back ().lon = nd->lon; // Unnecessary !
2137            lseg.back ().lat = nd->lat; // Unnecessary !
2138            lseg.back ().wayPtr = TO_HALFSEG; // Unnecessary !
2139            lseg.back ().other = nd == ndItr ? -4 : lowzOther++;
2140            (&lseg.back ())[-1].other = nd == end ? -4 : lowzOther++;
2141            // Be careful of the conditional post increment when rewriting this code !
2142            if (nd == end) break;
2143            nd = dp.back ();
2144            dp.pop_back ();
2145          }
2146        } // While DP has not passed the end
2147        //printf ("%d %d\n", lowzOther, lseg.size ());
2148      } // If the way belongs in the lowzoom
2149    } // If it was the start of a way
2150  } // For each highzoom nd
2151  REBUILDWATCH (qsort (&lseg[0], lseg.size () / 2, sizeof (lseg[0]) * 2, 
2152    (int (*)(const void *, const void *))HalfSegCmp));
2153  int *lpair = new int[lowzOther - FIRST_LOWZ_OTHER];
2154  for (unsigned i = 0; i < lseg.size (); i++) {
2155    if (!(i & 1)) {
2156      while (bucket < Hash (lseg[i].lon, lseg[i].lat, TRUE)) {
2157        hashTable[++bucket] = i / 2 + hashTable[bucketsMin1 + 1];
2158      }
2159    }
2160    if (lseg[i].other >= 0) lpair[lseg[i].other - FIRST_LOWZ_OTHER] = i;
2161  }
2162  while (bucket < bucketsMin1 + (bucketsMin1 >> 7) + 2) {
2163    hashTable[++bucket] = lseg.size () / 2 + hashTable[bucketsMin1 + 1];
2164  }
2165  for (int i = 0; i < lowzOther - FIRST_LOWZ_OTHER; i += 2) {
2166    lseg[lpair[i]].other = lpair[i + 1];
2167    lseg[lpair[i + 1]].other = lpair[i];
2168  }
2169  delete lpair;
2170  for (unsigned i = 0; i < lseg.size (); i += 2) {
2171    ndWrite.lat = lseg[i].lat;
2172    ndWrite.lon = lseg[i].lon;
2173    ndWrite.wayPtr = lseg[i].wayPtr;
2174    ndWrite.other[0] = lseg[i].other < 0 ? 0 : (lseg[i].other >> 1) - i / 2;
2175    ndWrite.other[1] = lseg[i + 1].other < 0 ? 0 : (lseg[i + 1].other >> 1) - i / 2;
2176    FWRITE (&ndWrite, sizeof (ndWrite), 1, pak);
2177    //printf ("%3d %10d %10d %10d %3d %3d\n", i / 2, ndWrite.lat, ndWrite.lon, ndWrite.wayPtr,
2178    //  ndWrite.other[0], ndWrite.other[1]);
2179  }
2180 
2181#ifndef LAMBERTUS
2182  REBUILDWATCH (for (int i = 0; i < IDXGROUPS; i++)) {
2183    assert (groupf[i] = fopen64 (groupName[i], "r+"));
2184    fseek (groupf[i], 0, SEEK_END);
2185    int fsize = ftell (groupf[i]);
2186    if (fsize > 0) {
2187      fflush (groupf[i]);
2188      unsigned *idx = (unsigned *) mmap (NULL, fsize,
2189                                         PROT_READ | PROT_WRITE, MAP_SHARED, fileno (groupf[i]), 0);
2190      qsort (idx, fsize / sizeof (*idx), sizeof (*idx), IdxCmp);
2191      FWRITE (idx, fsize, 1, pak);
2192#if 0
2193      for (int j = 0; j < fsize / (int) sizeof (*idx); j++) {
2194        printf ("%.*s\n", strcspn (data + idx[j], "\n"), data + idx[j]);
2195      }
2196#endif
2197      munmap (idx, fsize);
2198    }
2199    fclose (groupf[i]);
2200    unlink (groupName[i]);
2201  }
2202#endif // LAMBERTUS
2203  //    printf ("ndCount=%d\n", ndCount);
2204  munmap (data, ndStart);
2205  FWRITE (hashTable, sizeof (*hashTable),
2206          bucketsMin1 + (bucketsMin1 >> 7) + 3, pak);
2207         
2208  CalculateInvSpeeds (srec, styleCnt);
2209  FWRITE (&srec, sizeof (srec[0]), styleCnt, pak);
2210  FWRITE (&styleCnt, sizeof(styleCnt), 1, pak); // File ends with these
2211  FWRITE (&bucketsMin1, sizeof (bucketsMin1), 1, pak); // 3 variables
2212  FWRITE (&ndStart, sizeof (ndStart), 1, pak); /* for ndBase */
2213
2214  fclose (pak);
2215  free (hashTable);
2216
2217  return 0;
2218}
2219
2220/*==================================== SortRelations ======================================*/
2221int XmlTee (void * /*context*/, char *buf, int len)
2222{
2223  int n = fread (buf, 1, len, stdin);
2224  fwrite (buf, 1, n, stdout);
2225  return n; // == 0 ? -1 : n;
2226}
2227
2228int XmlClose (void */*context*/) { return 0; }
2229
2230struct memberType {
2231  int ref, type;
2232  const char *role, *tags;
2233};
2234
2235int MemberCmp (const memberType *a, const memberType *b)
2236{
2237  return a->type == b->type ? a->ref - b->ref : a->type - b->type;
2238}
2239
2240int SortRelations (void)
2241{
2242  xmlTextReaderPtr xml = xmlReaderForIO (XmlTee, XmlClose, NULL, "", NULL, 0);
2243    //xmlReaderForFd (STDIN_FILENO, "", NULL, 0);
2244  vector<memberType> member;
2245  unsigned rStart = 0, rel = FALSE;
2246  string *s = new string ();
2247  #ifdef MKDENSITY_CSV
2248  int lat, lon, *cnt = (int *) calloc (1024 * 1024, sizeof (*cnt));
2249  #endif
2250  while (xmlTextReaderRead (xml)) {
2251    if (xmlTextReaderNodeType (xml) == XML_READER_TYPE_ELEMENT) {
2252      char *name = (char *) BAD_CAST xmlTextReaderName (xml);
2253     
2254      #ifdef MKDENSITY_CSV
2255      if (stricmp (name, "node") == 0) {
2256        while (xmlTextReaderMoveToNextAttribute (xml)) {
2257          char *aname = (char *) BAD_CAST xmlTextReaderName (xml); 
2258          char *avalue = (char *) BAD_CAST xmlTextReaderValue (xml);
2259          if (stricmp (aname, "lat") == 0) lat = Latitude (atof (avalue));
2260          if (stricmp (aname, "lon") == 0) lon = Longitude (atof (avalue));
2261          xmlFree (aname);
2262          xmlFree (avalue);
2263        }
2264        cnt[(lat / (1 << 22) + 512) * 1024 + (lon / (1 << 22) + 512)]++;
2265      }
2266      xmlFree (name);
2267      continue;
2268      #endif
2269     
2270      rel = rel || stricmp (name, "relation") == 0;
2271      if (stricmp (name, "relation") == 0 && rStart < member.size ()) {
2272        while (rStart < member.size ()) member[rStart++].tags = s->c_str ();
2273        s = new string (); // It leaks memory, but it cannot be freed until
2274                           // moments before exit.
2275      }
2276      if (rel && (stricmp (name, "member") == 0 || stricmp (name, "tag") == 0)) {
2277        if (name[0] == 'm') member.push_back (memberType ());
2278        while (xmlTextReaderMoveToNextAttribute (xml)) {
2279          char *aname = (char *) BAD_CAST xmlTextReaderName (xml); 
2280          char *avalue = (char *) BAD_CAST xmlTextReaderValue (xml);
2281          if (stricmp (aname, "type") == 0) {
2282            member.back ().type = avalue[0] == 'r' ? 'x' : avalue[0];
2283          }
2284          else if (stricmp (aname, "ref") == 0) member.back ().ref = atoi (avalue);
2285          else if (name[0] == 't' && stricmp (aname, "k") == 0) {
2286            *s += avalue;
2287            *s += '\n';
2288          } // I assume that "<tag" implies "k=..." followed by "v=..."
2289          else if (name[0] == 't' && stricmp (aname, "v") == 0) {
2290            *s += avalue;
2291            *s += '\n';
2292          }
2293         
2294          if (stricmp (aname, "role") == 0) member.back ().role = avalue;
2295          else xmlFree (avalue);
2296         
2297          xmlFree (aname);
2298        }
2299      }
2300      xmlFree (name);
2301    }
2302  }
2303  #ifdef MKDENSITY_CSV
2304  FILE *df = fopen ("density.csv", "w");
2305  for (lat = 1023; lat >= 0; lat--) {
2306    for (lon = 0; lon < 1024; lon++) {
2307      fprintf (df, "%d%c", cnt[lat * 1024 + lon], lon == 1023 ? '\n' : ' ');
2308    }
2309  }
2310  return 0;
2311  #endif
2312  while (rStart < member.size ()) member[rStart++].tags = s->c_str ();
2313  qsort (&member[0], member.size (), sizeof (member[0]),
2314         (int (*)(const void *, const void *)) MemberCmp);
2315  FILE *idx = fopen ("relations.tbl", "w");
2316  for (unsigned i = 0; i < member.size (); i++) {
2317    fprintf (idx, "%c%d%c%s%c", member[i].type, member[i].ref, '\0', member[i].role, '\0');
2318    for (const char *ptr = member[i].tags; *ptr; ptr += strcspn (ptr, "\n") + 1) {
2319      fprintf (idx, "%.*s%c", (int) strcspn (ptr, "\n"), ptr, '\0');
2320    }
2321    fprintf (idx, "%c", '\0');
2322  }
2323  fprintf (idx, "z1%c", '\0'); // Insert stopper
2324  return 0;
2325}
2326
2327#endif
Note: See TracBrowser for help on using the repository browser.