source: subversion/applications/rendering/gosmore/jni/libgosm.cpp @ 29350

Last change on this file since 29350 was 28848, checked in by nic, 7 years ago

Rebuild: Fix bug with lowzoom coastline.

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