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

Last change on this file since 34655 was 30327, checked in by nic, 6 years ago

close #5110
Fix seg fault after rebuilding some very large extracts.

  • Property svn:executable set to *
File size: 101.1 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 (unsigned mask = 0; (mask & 7) != 4; mask += 0x55555555) {
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                atol ((char*)(w + 1) + 1) == nd->wayPtr &&
679            (StyleNr (w) <= restriction_no_straight_on) ==
680            (atol (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 + ((unsigned*)(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;
913  unsigned wayPtr;
914};
915
916struct wayPartType { // Rebuild only
917  int other;
918  unsigned wayPtr;
919  long long id;
920};
921
922struct nodeType {
923  long long id;
924  int lon, lat;
925};
926
927char *data;
928int max_nodes;
929
930inline nodeType *FindNode (nodeType *table, long long id)
931{
932  unsigned hash = id;
933  for (;;) {
934    nodeType *n = &table[hash % max_nodes];
935    if (n->id < 0 || n->id == id) return n;
936    hash = hash * (__int64) 1664525 + 1013904223;
937  }
938}
939
940int HalfSegCmp (const halfSegType *a, const halfSegType *b)
941{
942  int lowz = a->other < -2 || FIRST_LOWZ_OTHER <= a->other;
943  int hasha = Hash (a->lon, a->lat, lowz), hashb = Hash (b->lon, b->lat, lowz);
944  return hasha != hashb ? hasha - hashb : a->lon != b->lon ? a->lon - b->lon :
945    a->lat != b->lat ? a->lat - b->lat :
946    (b->other < 0 && b[1].other < 0 ? 1 : 0) -
947    (a->other < 0 && a[1].other < 0 ? 1 : 0);
948} // First sort by hash bucket, then by lon, then by lat.
949// If they are all the same, the nodes goes in the front where so that it's
950// easy to iterate through the turn restrictions.
951
952int IdxCmp (const void *aptr, const void *bptr)
953{
954  char *ta = data + *(unsigned *)aptr, *tb = data + *(unsigned *)bptr;
955  int tag = TagCmp (ta, tb);
956  while (*--ta) {}
957  while (*--tb) {}
958  unsigned a = ZEnc ((unsigned)((wayType *)ta)[-1].clat >> 16, 
959                     (unsigned)((wayType *)ta)[-1].clon >> 16);
960  unsigned b = ZEnc ((unsigned)((wayType *)tb)[-1].clat >> 16, 
961                     (unsigned)((wayType *)tb)[-1].clon >> 16);
962  return tag ? tag : a < b ? -1 : 1;
963}
964
965/* To reduce the number of cache misses and disk seeks we need to construct
966 the pack file so that waysTypes that are physically close to each other, are
967 also close to each other in the file. We only know where ways are physically
968 after the first pass, so the reordering is one done during a bbox rebuild.
969 
970 Finding an optimal solution is quite similar to find a soluting to the
971 traveling salesman problem. Instead we just place them in 2-D Hilbert curve
972 order using a qsort. */
973typedef struct {
974  wayType *w;
975  int idx;
976} masterWayType;
977
978int MasterWayCmp (const void *a, const void *b)
979{
980  int r[2], t, s, i, lead;
981  for (i = 0; i < 2; i++) {
982    t = ZEnc (((masterWayType *)(i ? b : a))->w->clon >> 16,
983      ((unsigned)((masterWayType *)(i ? b : a))->w->clat) >> 16);
984    s = ((((unsigned)t & 0xaaaaaaaa) >> 1) | ((t & 0x55555555) << 1)) ^ ~t;
985    for (lead = 1 << 30; lead; lead >>= 2) {
986      if (!(t & lead)) t ^= ((t & (lead << 1)) ? s : ~s) & (lead - 1);
987    }
988    r[i] = ((t & 0xaaaaaaaa) >> 1) ^ t;
989  }
990  return r[0] < r[1] ? 1 : r[0] > r[1] ? -1 : 0;
991}
992
993int LoadElemstyles(/* in */ const char *elemstylesfname, 
994                   const char *iconsfname,
995                   /* out */ styleStruct *srec, elemstyleMapping *map)
996{
997   //------------------------- elemstyle.xml : --------------------------
998    int ruleCnt = 0, styleCnt = firstElemStyle;
999    // zero-out elemstyle-to-stylestruct mappings
1000    FILE *icons_csv = fopen (iconsfname, "rb");
1001    xmlTextReaderPtr sXml = xmlNewTextReaderFilename (elemstylesfname);
1002    if (!sXml || !icons_csv) {
1003      fprintf (stderr, "Either icons.csv or elemstyles.xml not found\n");
1004      return 3;
1005    }
1006    styleStruct s;
1007    memset (&s, 0, sizeof (s));
1008    s.lineColour = -1;
1009    s.areaColour = -1;
1010
1011    for (int i = 0; i < styleCnt; i++) memcpy (&srec[i], &s, sizeof (s));
1012
1013    /* If elemstyles contain these, we can delete these assignments : */
1014    for (int i = restriction_no_right_turn;
1015            i <= restriction_only_straight_on; i++) {
1016      strcpy(map[i].style_k,"restriction");
1017      srec[i].scaleMax = 1;
1018      srec[i].lineColour = 0; // Make it match.
1019    }
1020    strcpy(map[restriction_no_right_turn].style_v,"no_right_turn");
1021    strcpy(map[restriction_no_left_turn].style_v,"no_left_turn");
1022    strcpy(map[restriction_no_u_turn].style_v,"no_u_turn");
1023    strcpy(map[restriction_no_straight_on].style_v,"no_straight_on");
1024    strcpy(map[restriction_only_right_turn].style_v,"only_right_turn");
1025    strcpy(map[restriction_only_left_turn].style_v,"only_left_turn");
1026    strcpy(map[restriction_only_straight_on].style_v,"only_straight_on");
1027    /* These strcpys are necessary because elemstyles does not contain them */
1028   
1029    while (xmlTextReaderRead (sXml)) {
1030      char *name = (char*) xmlTextReaderName (sXml);
1031      //xmlChar *val = xmlTextReaderValue (sXml);
1032      if (xmlTextReaderNodeType (sXml) == XML_READER_TYPE_ELEMENT) {
1033        if (strcasecmp (name, "scale_max") == 0) {
1034          while (xmlTextReaderRead (sXml) && // memory leak :
1035            xmlStrcmp (xmlTextReaderName (sXml), BAD_CAST "#text") != 0) {}
1036          s.scaleMax = atoi ((char *) xmlTextReaderValue (sXml));
1037        }
1038        while (xmlTextReaderMoveToNextAttribute (sXml)) {
1039          char *n = (char *) xmlTextReaderName (sXml);
1040          char *v = (char *) xmlTextReaderValue (sXml);
1041          if (strcasecmp (name, "condition") == 0) {
1042            if (strcasecmp (n, "k") == 0) strcpy(map[styleCnt].style_k, v);
1043            if (strcasecmp (n, "v") == 0) strcpy(map[styleCnt].style_v, v);
1044          }
1045          if (strcasecmp (name, "line") == 0) {
1046            if (strcasecmp (n, "width") == 0) {
1047              s.lineWidth = atoi (v);
1048            }
1049            if (strcasecmp (n, "realwidth") == 0) {
1050              s.lineRWidth = atoi (v);
1051            }
1052            if (strcasecmp (n, "colour") == 0) {
1053              sscanf (v, "#%x", &s.lineColour);
1054            }
1055            if (strcasecmp (n, "colour_bg") == 0) {
1056              sscanf (v, "#%x", &s.lineColourBg);
1057            }
1058            s.dashed = s.dashed ||
1059              (strcasecmp (n, "dashed") == 0 && strcasecmp (v, "true") == 0);
1060          }
1061          if (strcasecmp (name, "area") == 0) {
1062            if (strcasecmp (n, "colour") == 0) {
1063              sscanf (v, "#%x", &s.areaColour);
1064            }
1065          }
1066          if (strcasecmp (name, "icon") == 0) {
1067            if (strcasecmp (n, "src") == 0) {
1068              /*while (v[strcspn ((char *) v, "/ ")]) {
1069                v[strcspn ((char *) v, "/ ")] = '_';
1070              }*/
1071              char line[400], fnd = FALSE;
1072              static const char *set[] = { "map-icons/classic.big/",
1073                "map-icons/classic.small/", "map-icons/square.big/",
1074                "map-icons/square.small/" };
1075              for (int i = 0; i < 4; i++) {
1076                s.x[i * 4 + 2] = s.x[i * 4 + 3] = 1;
1077              // Default to 1x1 dummys
1078                int slen = strlen (set[i]), vlen = strlen (v);
1079                rewind (icons_csv);
1080                while (fgets (line, sizeof (line) - 1, icons_csv)) {
1081                  if (strncmp (line, set[i], slen) == 0 &&
1082                      strncmp (line + slen, v, vlen - 1) == 0) {
1083                    sscanf (line + slen + vlen, ":%d:%d:%d:%d",
1084                      s.x + i * 4,     s.x + i * 4 + 1,
1085                      s.x + i * 4 + 2, s.x + i * 4 + 3);
1086                    fnd = TRUE;
1087                  }
1088                }
1089              }
1090              if (!fnd) fprintf (stderr, "Icon %s not found\n", v);
1091            }
1092          }
1093          if (strcasecmp (name, "routing") == 0 && atoi (v) > 0) {
1094            #define M(field) if (strcasecmp (n, #field) == 0) {\
1095              map[styleCnt].defaultRestrict |= 1 << field ## R; \
1096              s.aveSpeed[field ## R] = atof (v); \
1097            }
1098            RESTRICTIONS
1099            #undef M
1100          }
1101         
1102          xmlFree (v);
1103          xmlFree (n);
1104        }
1105      }
1106      else if (xmlTextReaderNodeType (sXml) == XML_READER_TYPE_END_ELEMENT
1107                  && strcasecmp ((char *) name, "rule") == 0) {
1108        int ipos;
1109        #define s(k,v,shortname,extraTags) { #k, #v },
1110        static const char *stylet[][2] = { STYLES };
1111        #undef s
1112        for (ipos = 0; ipos < firstElemStyle; ipos++) {
1113          if (strcmp (stylet[ipos][0], map[styleCnt].style_k) == 0 && 
1114              strcmp (stylet[ipos][1], map[styleCnt].style_v) == 0) break;
1115        }
1116        map[ipos < firstElemStyle ? ipos : styleCnt].ruleNr = ruleCnt++;
1117        if (ipos < firstElemStyle) {
1118          memcpy (&srec[ipos], &s, sizeof (srec[ipos]));
1119          map[ipos].defaultRestrict = map[styleCnt].defaultRestrict;
1120          map[styleCnt].defaultRestrict = 0;
1121          strcpy(map[ipos].style_k,map[styleCnt].style_k);
1122          strcpy(map[ipos].style_v,map[styleCnt].style_v);
1123        }
1124        else if (styleCnt < (2 << STYLE_BITS) - 2) {
1125          memcpy (&srec[styleCnt++], &s, sizeof (srec[0]));
1126        }
1127        else fprintf (stderr, "Too many rules. Increase STYLE_BITS\n");
1128
1129        memset (&s, 0, sizeof (s));
1130        s.lineColour = -1;
1131        s.areaColour = -1;
1132      }
1133      xmlFree (name);
1134      //xmlFree (val);     
1135    }
1136
1137    xmlFreeTextReader (sXml);
1138
1139    return styleCnt;
1140}
1141
1142struct ltstr
1143{
1144  bool operator ()(const char *a, const char *b) const
1145  {
1146    return strcmp (a, b) < 0;
1147  }
1148};
1149
1150struct k2vType {
1151  map<const char *, const char *, ltstr> m;
1152  const char *operator[](const char *k) const
1153  {
1154    return m.find (k) == m.end () ? NULL : m.find (k)->second;
1155  } // For std:map the operator[] is not const, so we wrap it in a new class
1156};
1157
1158typedef char *membershipType;
1159
1160inline char *Role (membershipType rt)
1161{
1162  return !rt ? NULL : rt + strlen (rt) + 1;
1163}
1164
1165char *Find (membershipType rt, const char *key)
1166{
1167  if (!rt) return NULL;
1168  rt += strlen (rt) + 1; // id
1169  rt += strlen (rt) + 1; // role
1170  while (*rt != '\0' && strcmp (key, rt) != 0) {
1171    rt += strlen (rt) + 1; // id
1172    rt += strlen (rt) + 1; // role   
1173  }
1174  return *rt == '\0' ? NULL : rt + strlen (rt) + 1;
1175}
1176
1177membershipType Next (membershipType rt)
1178{
1179  if (!rt) return NULL;
1180  membershipType old = rt;
1181  while (*rt != '\0') {
1182    rt += strlen (rt) + 1; // id or k
1183    rt += strlen (rt) + 1; // role or v
1184  }
1185  return strcmp (rt + 1, old) == 0 ? rt + 1 : NULL; // Compare ids
1186}
1187
1188//----------------------------[ Osm2Gosmore ]-----------------------------
1189// This function translates the complicated and ever changing language of
1190// OSM into the superfast Gosmore language.
1191//
1192// Before Gosmore calls this function it will have matched the tags to
1193// an entry in elemstyles.xml and filled in 's'. If there are multiple
1194// matches, the first one is chosen. You can modify the values of 's',
1195// but be aware that the number of different 's' records are limited. So
1196// you should map (quantitize) rarely used values (like 38 km/h) to more
1197// frequently used values (like 40 km/h).
1198//
1199// It will also have filled in the access and destination fields of w.
1200// During a second pass, the center point of w will also be valid. So
1201// you can test if the way was inside any object for which you have data,
1202// like a city. Or you can adjust the average speed of unpaved ways based on
1203// an average annual rainfall map.
1204//
1205// You are also supplied with the relations table (rStart and rEnd). It has
1206// one entry for each relation that the the object is a member of. Use
1207// Next () to iterate through them, Role () to determine how it affects this
1208// way and Find () to examine the it's tags.
1209//
1210// You must return a list of strings which will be concatenated into the
1211// storage of the object and indexed for searching purposes. Normally each
1212// string will occupy one line (end in '\n'). For
1213// example { "Macdonalds\n", "restaurant\n" }.
1214// Empty lines are removed and will not be indexed. And strings can span
1215// any number of lines. So
1216//   { "Jerusalem\nar:", "al-Quds\n" } is equivalent to
1217//   { "Jerusalem\n", "\nar:", "al-Quds\n" }
1218// and it means that the object can be searched for as Jerusalem and al-Quds.
1219// Furthermore, a clever renderer can then render the correct name.
1220// A single line can also be indexed multiple times. For example
1221// { "city:", "Paris\n" } will be indexed as "Paris" and "city:Paris".
1222//
1223// NOTE: Gosmore currently requires that you return the same strings during
1224// both passes of the rebuild, i.e. the strings cannot depend on w.clat or clon
1225
1226deque<string> Osm2Gosmore (int /*id*/, k2vType &k2v, wayType &w,
1227  styleStruct &s, int isNode, int isRelation, membershipType membership,
1228  k2vType &wayRole /* Only for relations, and only for those members who are ways.
1229                      role->file offset in decimal */)
1230{
1231  deque<string> result;
1232 
1233/*  char idStr[12]; // Add way id so that it appear in cgi-bin output
1234  sprintf (idStr, "%d", idStr);
1235  result.push_front (string (idStr) + '\n'); */
1236 
1237  // First add name and 'ref' to the front so that they are displayed
1238  if (k2v["name"]) {
1239    result.push_front (string (k2v["name"]) + "\n");
1240    if (k2v["place"] && strcmp (k2v["place"], "city") == 0) {
1241      result.push_back ("city:" + string (k2v["name"]) + "\n");
1242    }
1243  }
1244  else if (k2v["left:district"]) {
1245    result.push_front (string ("\n") + k2v["left:district"] + '\n');
1246  }
1247  else if (k2v["right:district"]) {
1248    result.push_front (string ("\n") + k2v["right:district"] + '\n');
1249  }
1250  else if (k2v["left:municipality"]) {
1251    result.push_front (string ("\n") + k2v["left:municipality"] + '\n');
1252  }
1253  else if (k2v["right:municipality"]) {
1254    result.push_front (string ("\n") + k2v["right:municipality"] + '\n');
1255  }
1256  else {
1257    membershipType m; // Could be something like a boundary
1258    for (m = membership; m && !Find (m, "name"); m = Next (m)) {}
1259    if (m) result.push_front (string ("\n") + Find (m, "name") + '\n');
1260    // Put name on a new line so that it will not be indexed.
1261  }
1262 
1263  if (k2v["ref"]) result.push_back (string (k2v["ref"]) + "\n");
1264  if (k2v["operator"]) result.push_back (string (k2v["operator"]) + "\n");
1265  map<const char *, const char *, ltstr>::iterator i = k2v.m.begin ();
1266  // Go through all the tags and add all the interesting things to 'result'
1267  // so that they will be indexed.
1268  for (; i != k2v.m.end (); i++) {
1269    if (strcmp (i->first, "name") != 0 &&
1270        strcmp (i->first, "ref") != 0 &&
1271        strcmp (i->first, "operator") != 0 &&
1272        strncasecmp (i->first, "tiger:", 6) != 0 &&
1273        strcmp (i->first, "created_by") != 0 &&
1274        strcmp (i->first, "converted_by") != 0 &&
1275        strncasecmp (i->first, "source", 6) != 0 &&
1276        strncasecmp (i->first, "AND_", 4) != 0 &&
1277        strncasecmp (i->first, "AND:", 4) != 0 &&
1278        strncasecmp (i->first, "kms:", 4) != 0 &&
1279        strncasecmp (i->first, "LandPro08:", 10) != 0 &&
1280        strncasecmp (i->first, "NHD:", 4) != 0 &&
1281        strncasecmp (i->first, "massgis:", 8) != 0 &&
1282        strncasecmp (i->first, "scgis-shp:", 10) != 0 &&
1283        strcmp (i->first, "addr:street") != 0 &&
1284        strcmp (i->first, "addr:postcode") != 0 &&
1285        strcmp (i->first, "addr:district") != 0 &&
1286        strcmp (i->first, "addr:region") != 0 &&
1287        strcmp (i->first, "addr:state") != 0 &&
1288        strcmp (i->first, "addr:city") != 0 &&
1289        strcmp (i->first, "addr:country") != 0 &&
1290        !(strcmp (i->first, "addr:conscriptionnumber") == 0 && k2v["addr:housenumber"]) &&
1291        // The mvcr:adresa import sets both the conscription number & housenumber
1292        !(strcmp (i->first, "postal_code") == 0 && !isNode) &&
1293        // Many European ways include the postal code. Although it's nice to be able to
1294        // highlight all the streets in a postal code (after searching), it's more likely
1295        // to slow down the software unnecessarily.
1296
1297        strncasecmp (i->first, "KSJ2:", 5) != 0 && 
1298        strncasecmp (i->first, "geobase:", 8)  != 0 &&
1299        strncasecmp (i->first, "kms:", 4)  != 0 &&
1300        strncasecmp (i->first, "openGeoDB:", 10)  != 0 &&
1301        strncasecmp (i->first, "gnis:", 5)  != 0 &&
1302        strncasecmp (i->first, "CLC:", 4)  != 0 && // CORINE Land Cover
1303
1304        strcmp (i->second, // Abuse of the 'note' tag !
1305          "Experimental import of Irish places and POIs from GNS Dataset") != 0 &&
1306        strcmp (i->second, // What is the difference between Key:comment and Key:note ?
1307          "Experimental import of Canadian places and POIs from GNS Dataset") != 0 &&
1308       
1309        strncasecmp (i->first, "gns:", 4)  != 0 &&
1310        strcmp (i->first, "place_county") != 0 && 
1311       
1312        strcmp (i->first, "code_department") != 0 && // France / EtienneChoveBot
1313        strcmp (i->first, "ref:INSEE") != 0 && // France / EtienneChoveBot
1314
1315        strncasecmp (i->first, "it:fvg:ctrn:", 12)  != 0 && // What is this??
1316
1317        strncasecmp (i->first, "3dshapes:", 9)  != 0 && // Import in the Netherlands
1318
1319        strncasecmp (i->first, "TMC:", 4)  != 0 && // Traffic broadcast info esp. Germany
1320
1321        strncasecmp (i->first, "cladr:", 6)  != 0 && // Some Russian import
1322       
1323        strncmp (i->first, "BP:", 2)  != 0 && // British Petroleum import
1324        strcmp (i->first, "amenity:eftpos") != 0 && // Payment method not important
1325
1326        strncasecmp (i->first, "chile:", 6)  != 0 && // vialidad.cl import
1327        strncasecmp (i->first, "navibot:", 8)  != 0 && // navimont's tag
1328       
1329        strncasecmp (i->first, "is_in:", 6)  != 0 && // teryt
1330       
1331        strncasecmp (i->first, "teryt:", 6)  != 0 && // in Poland
1332
1333        strncasecmp (i->first, "naptan:", 7)  != 0 && // UK bus stops
1334        !((strcmp (i->first, "local_ref") == 0 || strcmp (i->first, "name") == 0 ||
1335          /* strcmp (i->first, "route_ref") == 0 ||*/ strcmp (i->first, "asset_ref") == 0 ||
1336           strcmp (i->first, "ref") == 0) && k2v["naptan:CommonName"]) &&
1337        // This second test removes the names, refs and local_refs from naptan bus stops,
1338        // as the information is not very useful.
1339       
1340        (strcmp (i->first, "census:population") != 0 || !k2v["population"]) && // GNIS import
1341       
1342        strncmp (i->first, "qroti:", 6) != 0 &&
1343
1344        strcmp (i->first, "area") != 0 && // Too vague
1345        strcmp (i->first, "building") != 0 &&
1346        strcmp (i->first, "building:use") != 0 &&
1347
1348        strcmp (i->second, "surveillance") != 0 && // man_made=...
1349        strcmp (i->first, "surveillance") != 0 && // e.g. ...=indoor
1350        // I doubt anyone will have a legal reason to search for a security camera
1351       
1352        strcmp (i->first, "note:ja") != 0 &&
1353       
1354        !(strcmp (i->first, "ref") == 0 && strncmp (i->second, "http://", 7) == 0) &&
1355        // Abused during the EPA import
1356
1357        strcmp (i->second, "tree") != 0 && // A few of these in Berlin
1358       
1359        strncasecmp (i->first, "CoCT:",5) != 0 && // Cape Town import
1360       
1361        strcmp (i->first, "import_uuid") != 0 &&
1362        strcmp (i->first, "attribution") /* Mostly MassGIS */ != 0 &&
1363        strcmp (i->second, "paved") != 0 && //surface=paved is the default
1364        strcmp (i->first, "layer") != 0 &&
1365        strcmp (i->first, "history") != 0 &&
1366        strcmp (i->first, "direction") != 0 &&
1367        strcmp (i->first, "maxspeed") != 0 &&
1368        strcmp (i->first, "maxwidth") != 0 &&
1369        strcmp (i->first, "access") != 0 &&
1370        strcmp (i->first, "motorcar") != 0 &&
1371        strcmp (i->first, "bicycle") != 0 &&
1372        strcmp (i->first, "foot") != 0 &&
1373        strcmp (i->first, "goods") != 0 &&
1374        strcmp (i->first, "hgv") != 0 &&
1375        strcmp (i->first, "horse") != 0 &&
1376        strcmp (i->first, "motorcycle") != 0 &&
1377        strcmp (i->first, "psv") != 0 &&
1378        strcmp (i->first, "moped") != 0 &&
1379        strcmp (i->first, "mofa") != 0 &&
1380        strcmp (i->first, "motorboat") != 0 &&
1381        strcmp (i->first, "boat") != 0 &&
1382        strcmp (i->first, "oneway") != 0 &&
1383        strcmp (i->first, "roundabout") != 0 &&
1384        strcmp (i->first, "time") != 0 &&
1385        strcmp (i->first, "timestamp") != 0 && // User WanMil in Luxembourg
1386        strcmp (i->first, "ele") != 0 &&
1387        strcmp (i->first, "hdop") != 0 &&
1388        strcmp (i->first, "sat") != 0 &&
1389        strcmp (i->first, "pdop") != 0 &&
1390        strcmp (i->first, "speed") != 0 &&
1391        strcmp (i->first, "course") != 0 &&
1392        strcmp (i->first, "fix") != 0 &&
1393        strcmp (i->first, "vdop") != 0 &&
1394        strcmp (i->first, "image") != 0 && // =http://www.flickr...
1395        strcmp (i->second, "no") != 0      &&
1396        strcmp (i->second, "false") != 0 &&
1397        strcmp (i->first, "sagns_id") != 0 &&
1398        strcmp (i->first, "sangs_id") != 0 &&
1399        strcmp (i->first, "is_in") != 0 &&
1400        strcmp (i->second, "level_crossing") != 0 && // railway=level_crossing
1401        strcmp (i->second, "living_street") != 0 &&
1402        strcmp (i->second, "residential") != 0 &&
1403        strcmp (i->second, "unclassified") != 0 &&
1404        strcmp (i->second, "tertiary") != 0 &&
1405        strcmp (i->second, "secondary") != 0 && 
1406        strcmp (i->second, "primary") != 0 && // Esp. ValidateMode
1407        strcmp (i->first, "service") != 0 && // =driveway/parking_aisle is trivial
1408        strcmp (i->second, "junction") != 0 && 
1409   /* Not approved and when it isn't obvious
1410      from the ways that it's a junction, the tag will
1411      often be something ridiculous like
1412      junction=junction ! */
1413        // blocked as highway:  strcmp (i->second, "mini_roundabout") != 0
1414        //                      && strcmp (i->second, "roundabout") != 0
1415        strcmp (i->second, "place_of_worship") != 0 && // Too vague to include
1416        strcmp (i->first, "crossing") != 0 &&
1417        strcmp (i->first, "barrier") != 0 &&
1418        strcmp (i->second, "traffic_signals") != 0 &&
1419        strcmp (i->first, "editor") != 0 &&
1420        strcmp (i->first, "power") != 0 && // Power towers
1421        strcmp (i->first, "class") != 0 /* esp. class=node */ &&
1422        strcmp (i->first, "type") != 0 &&
1423        /* "type=..." is only allow for boules grounds. We block it because it
1424        is often misused. */
1425         0 != strcmp (i->second, 
1426  "National-Land Numerical Information (Railway) 2007, MLIT Japan") &&
1427         0 != strcmp (i->second, 
1428  "National-Land Numerical Information (Lake and Pond) 2005, MLIT Japan") &&
1429         0 != strcmp (i->second, 
1430  "National-Land Numerical Information (Administrative area) 2007, MLIT Japan") &&
1431         strcmp (i->second, "coastline_old") != 0 &&
1432         strcmp (i->first, "upload_tag") != 0 &&
1433         strcmp (i->first, "admin_level") != 0 &&
1434         (!isNode || (strcmp (i->first, "highway") != 0 &&
1435                      strcmp (i->second, "water") != 0 &&
1436                      strcmp (i->first, "abutters") != 0 &&
1437                      strcmp (i->second, "coastline") != 0))) {
1438      result.push_back (
1439        strcmp (i->first, "population") == 0 ? string ("\npop. ") + i->second + '\n':
1440        // Don't index population figures, but make it obvious what it is.
1441        strcmp (i->first, "highway") == 0 ? string ("\n ") :
1442        // This is to save space. We don't drop the tag completely because we don't
1443        // footways, service roads, cycleways etc to have empty strings because
1444        // ValidateMode will highlight them.
1445        strcmp (i->first, "phone") == 0 || strcmp (i->first, "addr:housenumber") == 0 ?
1446          string ("\n") + i->second + '\n':
1447        // Don't index highway types, phonenumbers or housenumbers.
1448        // Some day I hope to include housenumber data into the data for the street it is on.
1449        // Then, when the user enters a housenumber and a street name,
1450        // we search by street and filter by housenumber
1451        strcmp (i->first, "noexit") == 0 ? string ("\nnoexit\n") :
1452        // Don't index noexit
1453        strncasecmp (i->first, "wikipedia", 9) == 0 ?
1454                         string ("\nwikipedia\n") :
1455        // Don't index wikipedia names, but make it obvious that it's on there.
1456        string (strcmp (i->second, "true") == 0 ||
1457                strcmp (i->second, "yes") == 0 || strcmp (i->second, "1") == 0
1458                ? strncasecmp (i->first, "amenity:", 8) == 0 ? i->first + 8
1459                // Strip off amenity: from things like amenity:restaurant (BP import)
1460                : strcmp (i->first, "bridge") == 0 ? "\nbridge"
1461                // No need to index bridge
1462                : i->first : i->second) + "\n");
1463    }
1464  }
1465  membershipType m;
1466  for (m = membership; m && !(Find (m, "route") &&
1467    strcmp (Find (m, "route"), "bicycle") == 0); m = Next (m)) {}
1468  // We go through all the relations (regardless of role), but stop if we find
1469  // one with route=bicycle. Then m will be set.
1470  if (m || k2v["lcn_ref"] || k2v["rcn_ref"] || k2v["ncn_ref"]) {
1471    // if part of a cycle route relation or if it has a cycle network reference
1472    s.aveSpeed[bicycleR] = 20;
1473    // then we say cyclists will love it.
1474  }
1475  for (m = membership; m; m = Next (m)) {
1476    if (Find (m, "route")) {
1477      result.push_back (string (Find (m, "relation_id")) + '\n');
1478    } // If it's a route add it's relation_id and index it.
1479  }
1480 
1481  if (isRelation && k2v["restriction"] && wayRole["from"] && wayRole["to"]) {
1482    result.push_front (
1483      string ("\n") + wayRole["from"] + ' ' + wayRole["to"] + '\n');
1484    // A turn restriction with both a 'from' and a 'to'. Put the offsets (not
1485    // OSM-ids) encoded as decimal (ASCII) where the router expects them.
1486   
1487  }
1488  // Reduce the aveSpeeds when maxspeed mandates it
1489  if (k2v["maxspeed"] && isdigit (k2v["maxspeed"][0])) {
1490    const char *m = k2v["maxspeed"];
1491    double maxs = atof (m), best = 30, m2km = 1.609344;
1492    // Here we find the first alphabetic character and compare it to 'm'
1493    if (tolower (m[strcspn (m, "KMPSkmps")]) == 'm') maxs *= m2km;
1494    // choose the closest of these values ...
1495    int v[] = { 5,7,10,15,20,30,32,40,45,50,60,70,80,90,100,110,120,130 };
1496    for (unsigned i = 0; i < sizeof (v) / sizeof (v[1]); i++) {
1497      // ... either in km/h
1498      if (fabs (maxs - best) > fabs (maxs - v[i])) best = v[i];
1499      // ... or in miles/h
1500      if (fabs (maxs - best) > fabs (maxs - v[i] * m2km)) best = v[i] * m2km;
1501    }
1502    s.aveSpeed[accessR] = best;
1503    for (int i = 0; i < layerBit1; i++) {
1504      if (s.aveSpeed[i] > best) s.aveSpeed[i] = best;
1505    }
1506  }
1507  // Now adjust for track type.
1508  if ((k2v["tracktype"] && isdigit (k2v["tracktype"][5])) ||
1509    (k2v["highway"] && strcmp (k2v["highway"], "track") == 0)) {
1510    // many tracks don't have a tracktype, assume them as rather slow
1511    int tracktype = 2;
1512    if (k2v["tracktype"] && isdigit (k2v["tracktype"][5]))
1513      tracktype = atoi (k2v["tracktype"] + 5);
1514    s.aveSpeed[motorcarR] *= (6 - tracktype) / 5.0;
1515    if (tracktype >= 3) s.aveSpeed[bicycleR] *= (6 - tracktype) / 4.0;
1516    if (tracktype == 5) s.aveSpeed[footR] *= 0.8;
1517  }
1518  if ((w.bits & (1 << onewayR)) && !(k2v["cycleway"] &&
1519    (strcmp (k2v["cycleway"], "opposite_lane") == 0 ||
1520     strcmp (k2v["cycleway"], "opposite_track") == 0 ||
1521     strcmp (k2v["cycleway"], "opposite") == 0)) &&
1522     !(k2v["oneway:bicycle"] && (strcmp (k2v["oneway:bicycle"], "0") == 0 ||
1523                                strcmp (k2v["oneway:bicycle"], "no") == 0))) {
1524    // On oneway roads, cyclists are only allowed to go in the opposite
1525    // direction, if the cycleway tag exist and starts with "opposite"
1526    w.bits |= 1 << bicycleOneway;
1527  }
1528//  printf ("%.5lf %.5lf\n", LonInverse (w.clon), LatInverse (w.clat));
1529  return result;
1530}
1531
1532#define FWRITEY(y) { perror ("fwrite @ " #y); exit (1); }
1533#define FWRITEX(x) FWRITEY (x) // Use argument prescan feature of CPP
1534#define FWRITE(addr,size,count,f) { if (fwrite (addr, size, count, f) \
1535                                      != (size_t)(count)) FWRITEX (__LINE__) }
1536
1537ndType *LFollow (ndType *nd, ndType *ndItr, wayType *w, int forward)
1538{ // Helper function when a way is copied into lowzoom table.
1539  if (forward) {
1540    nd += nd->other[0];
1541    if (nd->other[0]) return nd;
1542  }
1543  if (nd->lat == nd[1].lat && nd->lon == nd[1].lon) {
1544    if ((nd->lat != nd[2].lat || nd->lon != nd[2].lon) &&
1545        (nd->lat != nd[-1].lat || nd->lon != nd[-1].lon ||
1546         // If there is a 3rd object there,
1547         (nd[-1].other[1] == 0 && nd[-1].other[1] == 0)) &&
1548        // then it must be a node
1549        nd + 1 != ndItr && nd[1].other[forward ? 1 : 0] == 0
1550        // Must not loop back to start and must not be T juntion
1551        && StyleNr (w) == StyleNr ((wayType*)(data + nd[1].wayPtr))) nd++;
1552  }
1553  else if (nd->lat == nd[-1].lat && nd->lon == nd[-1].lon &&
1554           (nd->lat != nd[-2].lat || nd->lon != nd[-2].lon ||
1555            // If there is a 3rd object there,
1556            (nd[-2].other[1] == 0 && nd[-2].other[1] == 0)) &&
1557            // then it must be a node
1558           nd - 1 != ndItr && nd[-1].other[forward ? 1 : 0] == 0
1559           // Must not loop back to start and must not be T juntion
1560           && StyleNr (w) == StyleNr ((wayType*)(data + nd[-1].wayPtr))) nd--;
1561  // If nd ends at a point where exactly two ways meet and they have the same
1562  // StyleNr we can 'route' across it.
1563  // But we can't go back to wayPtr, e.g. circular way.
1564  return nd;
1565}
1566
1567int RebuildPak(const char* pakfile, const char* elemstylefile, 
1568               const char* iconscsvfile, const char* masterpakfile, 
1569               const int bbox[4]) {
1570  assert (layerBit3 < 32);
1571
1572  int rebuildCnt = 0;
1573  FILE *pak, *masterf;
1574  unsigned ndStart;
1575  wayType *master = NULL;
1576  if (strcmp(masterpakfile,"")) {
1577    if (!(masterf = fopen64 (masterpakfile, "rb")) ||
1578        fseek (masterf, -sizeof (ndStart), SEEK_END) != 0 ||
1579        fread (&ndStart, sizeof (ndStart), 1, masterf) != 1 ||
1580        (long)(master = (wayType *)mmap (NULL, ndStart, PROT_READ,
1581                                         MAP_SHARED, fileno (masterf), 
1582                                         0)) == -1) {
1583      fprintf (stderr, "Unable to open %s for bbox rebuild\n",masterpakfile);
1584      return 4;
1585    }
1586  }
1587 
1588  if (!(pak = fopen64 (pakfile, "w+b"))) {
1589    fprintf (stderr, "Cannot create %s\n",pakfile);
1590    return 2;
1591  }
1592  FWRITE (&pakHead, sizeof (pakHead), 1, pak);
1593
1594  //------------------------ elemstylesfile : -----------------------------
1595  styleStruct *srec =
1596    (styleStruct*) calloc ((2 << STYLE_BITS), sizeof (*srec));
1597  elemstyleMapping *eMap =
1598    (elemstyleMapping*) calloc ((2 << STYLE_BITS), sizeof (*eMap));
1599 
1600  int elemCnt = LoadElemstyles(elemstylefile, iconscsvfile,
1601                                srec, eMap), styleCnt = elemCnt;
1602 
1603 
1604  //------------------ OSM Data File (/dev/stdin) : ------------------------
1605  max_nodes = ((time (NULL) - 1351071438) * (long long) 20 + 1980820697) /
1606    NGROUPS; // Linear extrapolation from Oct 2012 at 20 nodes / second.
1607  xmlTextReaderPtr xml = xmlReaderForFd (STDIN_FILENO, "", NULL, 0);
1608  FILE *groupf[PAIRGROUP2 (0) + PAIRGROUPS2];
1609  char groupName[PAIRGROUP2 (0) + PAIRGROUPS2][9];
1610  for (int i = 0; i < PAIRGROUP2 (0) + PAIRGROUPS2; i++) {
1611    sprintf (groupName[i], "%c%c%d.tmp", i / 26 % 26 + 'a', i % 26 + 'a',
1612             i / 26 / 26);
1613    if (i < S2GROUP (0) && !(groupf[i] = fopen64 (groupName[i], "w+b"))) {
1614      perror ("Cannot create temporary file.\n"
1615               "Possibly too many open files, in which case you must run "
1616               "ulimit -n or recompile\n");
1617      return 9;
1618     
1619    }
1620  }
1621 
1622#if 0 // For making sure we have a Hilbert curve
1623  bucketsMin1 = MAX_BUCKETS - 1;
1624  for (int x = 0; x < 16; x++) {
1625    for (int y = 0; y < 16; y++) {
1626      printf ("%7d ", Hash (x << TILEBITS, y << TILEBITS));
1627    }
1628    printf ("\n");
1629  }
1630#endif
1631   
1632  nodeType nd;
1633  wayPartType wp[2];
1634  int nOther = 0, lowzOther = FIRST_LOWZ_OTHER, isNode = 0;
1635  int yesMask = 0, noMask = 0;
1636  struct {
1637    wayType *w; // Pointer to the first version in the master file.
1638    int off;
1639  } *wayFseek = NULL;
1640  int wStyle = elemCnt, relationType = 0, onewayReverse = 0;
1641  long long ref = 0;
1642  vector<int> wayMember;
1643  map<int,int> wayId;
1644  wayType w;
1645  w.clat = 0;
1646  w.clon = 0;
1647  w.dlat = INT_MIN;
1648  w.dlon = INT_MIN;
1649  w.bits = 0;
1650  w.destination = 0;
1651 
1652  // if we are doing a second pass bbox rebuild
1653  if (master) {
1654    masterWayType *masterWay = (masterWayType *) 
1655      malloc (sizeof (*masterWay) * (ndStart / (sizeof (wayType) + 4)));
1656   
1657    unsigned i = 0, offset = ftell (pak), wcnt;
1658    wayType *m = (wayType *)(((char *)master) + offset);
1659    for (wcnt = 0; (char*) m < (char*) master + ndStart; wcnt++) {
1660      if (bbox[0] <= m->clat + m->dlat && bbox[1] <= m->clon + m->dlon &&
1661          m->clat - m->dlat <= bbox[2] && m->clon - m->dlon <= bbox[3]) {
1662        masterWay[i].idx = wcnt;
1663        masterWay[i++].w = m;
1664      }
1665      m = (wayType*)((char*)m +
1666                     ((1 + strlen ((char*)(m + 1) + 1) + 1 + 3) & ~3)) + 1;
1667    }
1668    qsort (masterWay, i, sizeof (*masterWay), MasterWayCmp);
1669    assert (wayFseek = (typeof (wayFseek)) calloc (sizeof (*wayFseek),
1670                                      ndStart / (sizeof (wayType) + 4)));
1671    for (unsigned j = 0; j < i; j++) {
1672      wayFseek[masterWay[j].idx].off = offset;
1673      wayFseek[masterWay[j].idx].w = masterWay[j].w;
1674      offset += sizeof (*masterWay[j].w) +
1675        ((1 + strlen ((char*)(masterWay[j].w + 1) + 1) + 1 + 3) & ~3);
1676    }
1677    wayFseek[wcnt].off = offset;
1678    fflush (pak);
1679    if (ftruncate (fileno (pak), offset) != 0) perror ("ftruncate");
1680    free (masterWay);
1681    fseek (pak, wayFseek->off, SEEK_SET);
1682  }
1683 
1684  char *relationTable;
1685  FILE *relationTableFile = fopen ("relations.tbl", "rb");
1686  if (!relationTableFile || fseek (relationTableFile, 0, SEEK_END) != 0 ||
1687      (relationTable = (char*) mmap (NULL, ftell (relationTableFile), PROT_READ,
1688        MAP_SHARED, fileno (relationTableFile), 0)) == (char*)-1) {
1689    relationTable = (char*) "z1"; // Stopper
1690    fprintf (stderr, "Processing without relations table\n");
1691  }
1692 
1693  char *tag_k = NULL, *role = NULL; //, *tags = (char *) BAD_CAST xmlStrdup (BAD_CAST "");
1694  //char *nameTag = NULL;
1695  k2vType k2v, wayRole; // wayRole should be a vector< struct{char*,int} > ...
1696  deque<long long> wayNd;
1697  map<int, deque<long long> > outer;
1698  REBUILDWATCH (while (xmlTextReaderRead (xml) == 1)) {
1699    char *name = (char *) BAD_CAST xmlTextReaderName (xml);
1700    //xmlChar *value = xmlTextReaderValue (xml); // always empty
1701    if (xmlTextReaderNodeType (xml) == XML_READER_TYPE_ELEMENT) {
1702      isNode = stricmp (name, "way") != 0 && stricmp (name, "relation") != 0
1703        && (stricmp (name, "node") == 0 || isNode);
1704      while (xmlTextReaderMoveToNextAttribute (xml)) {
1705        char *aname = (char *) BAD_CAST xmlTextReaderName (xml);
1706        char *avalue = (char *) BAD_CAST xmlTextReaderValue (xml);
1707        //        if (xmlStrcasecmp (name, "node") == 0)
1708        if (stricmp (aname, "id") == 0) nd.id = atoll (avalue);
1709        if (stricmp (aname, "lat") == 0) nd.lat = Latitude (atof (avalue));
1710        if (stricmp (aname, "lon") == 0) nd.lon = Longitude (atof (avalue));
1711        if (stricmp (aname, "ref") == 0) ref = atoll (avalue);
1712        if (stricmp (aname, "type") == 0) relationType = avalue[0];
1713
1714#define K_IS(x) (stricmp (tag_k, x) == 0)
1715#define V_IS(x) (stricmp (avalue, x) == 0)
1716
1717        if (stricmp (aname, "role") == 0) role = avalue;
1718        else if (stricmp (aname, "v") == 0) {
1719         
1720          int newStyle = 0;
1721          // TODO: this for loop could be clearer as a while
1722          for (; newStyle < elemCnt && !(K_IS (eMap[newStyle].style_k) &&
1723                                          (eMap[newStyle].style_v[0] == '\0' || V_IS (eMap[newStyle].style_v)) &&
1724                                          (isNode ? srec[newStyle].x[2] :
1725                                           srec[newStyle].lineColour != -1 ||
1726                                           srec[newStyle].areaColour != -1)); newStyle++) {}
1727          // elemstyles rules are from most important to least important
1728          // Ulf has placed rules at the beginning that will highlight
1729          // errors, like oneway=true -> icon=deprecated. So they must only
1730          // match nodes when no line or area colour was given and only
1731          // match ways when no icon was given.
1732          if (K_IS ("junction") && V_IS ("roundabout")) {
1733            yesMask |= (1 << onewayR) | (1 << roundaboutR);
1734          }
1735          else if (newStyle < elemCnt && 
1736                   (wStyle == elemCnt || 
1737                    eMap[wStyle].ruleNr > eMap[newStyle].ruleNr)) {
1738            wStyle = newStyle;
1739          }
1740         
1741          if (K_IS ("layer")) w.bits |= atoi (avalue) << 29;
1742         
1743#define M(field) else if (K_IS (#field)) {                              \
1744            if (V_IS ("yes") || V_IS ("1") || V_IS ("permissive") ||    \
1745                V_IS ("true") || V_IS ("designated") ||                 \
1746                V_IS ("official") || V_IS ("-1")) {                     \
1747              yesMask |= 1 << field ## R;                               \
1748              if (K_IS ("oneway") && V_IS ("-1")) onewayReverse = TRUE; \
1749            } else if (V_IS ("no") || V_IS ("0") || V_IS ("private")) { \
1750              noMask |= 1 << field ## R;                                \
1751            }                                                           \
1752            else if (V_IS ("destination")) {                            \
1753              yesMask |= 1 << field ## R;                               \
1754              w.destination |= 1 << field ## R;                         \
1755            }                                                           \
1756          }
1757          RESTRICTIONS
1758#undef M
1759           
1760          k2v.m[tag_k] = avalue; // Will be freed after Osm2Gosmore()
1761        }
1762        else if (stricmp (aname, "k") == 0) tag_k = avalue;
1763        else xmlFree (avalue); // Not "k", "v" or "role"
1764       
1765        xmlFree (aname);
1766      } /* While it's an attribute */
1767      if (/*relationType == 'w' && */ stricmp (name, "member") == 0) {
1768        //map<int,int>::iterator refId = wayId.find (ref);
1769        //if (refId != wayId.end ()) wayMember.push_back (refId->second);
1770        wayMember.push_back (ref);
1771      }
1772      if (!wayFseek || wayFseek->off) { // This test / guard is no longer needed.
1773        if (stricmp (name, "member") == 0 && role) {
1774          if (relationType == 'n' && stricmp (role, "via") == 0) wayNd.push_back (ref);
1775         
1776          map<int,int>::iterator refId = wayId.find (ref);
1777          if (relationType == 'w' && refId != wayId.end ()) {
1778            char tmp[12];
1779            sprintf (tmp, "%d", refId->second);
1780            wayRole.m[role] = (char*) xmlStrdup (BAD_CAST tmp);
1781          }
1782          else xmlFree (role);
1783          role = NULL;
1784        }
1785        else if (stricmp (name, "nd") == 0) wayNd.push_back (ref);
1786      }
1787      if (stricmp (name, "node") == 0 && bbox[0] <= nd.lat &&
1788          bbox[1] <= nd.lon && nd.lat <= bbox[2] && nd.lon <= bbox[3]) {
1789        FWRITE (&nd, sizeof (nd), 1, groupf[NGROUP (nd.id)]);
1790      }
1791    }
1792    if (xmlTextReaderNodeType (xml) == XML_READER_TYPE_END_ELEMENT) {
1793      int nameIsNode = stricmp (name, "node") == 0;
1794      int nameIsRelation = stricmp (name, "relation") == 0;
1795      if (nameIsRelation && k2v["type"] &&
1796          strcmp (k2v["type"], "multipolygon") == 0) {
1797        while (!wayMember.empty ()) {
1798          int idx;
1799          for (idx = wayMember.size () - 1; !outer[wayMember[idx]].empty () ; idx--) {
1800            deque<long long> *o = &outer[wayMember[idx]];
1801            if (wayNd.empty () || wayNd.back () == o->front () || idx == 0) {
1802              if (!wayNd.empty () && wayNd.back () == o->front ()) wayNd.pop_back ();
1803              wayNd.insert (wayNd.end (), o->begin (), o->end ());
1804              break;
1805            }
1806            if (wayNd.back () == o->back ()) {
1807              wayNd.pop_back ();
1808              wayNd.insert (wayNd.end (), o->rbegin (), o->rend ());
1809              break;
1810            }
1811          }
1812          //printf ("iiiiiiiii %d %d %d %u %s %s\n", idx, nd.id, wayMember[idx],
1813          //  outer[wayMember[idx]].size (), eMap[wStyle].style_k, eMap[wStyle].style_v);
1814          wayMember[idx] = wayMember.back ();
1815          wayMember.pop_back ();
1816        }
1817      }
1818      if (nameIsRelation) wayMember.clear ();
1819      if (stricmp (name, "way") == 0 || nameIsNode || nameIsRelation) {
1820        if (!nameIsRelation && !nameIsNode) {
1821          wayId[nd.id] = ftell (pak);
1822        }
1823        /*if (nameTag) {
1824          char *oldTags = tags;
1825          tags = (char *) xmlStrdup (BAD_CAST "\n");
1826          tags = (char *) xmlStrcat (BAD_CAST tags, BAD_CAST nameTag);
1827          tags = (char *) xmlStrcat (BAD_CAST tags, BAD_CAST oldTags);
1828          xmlFree (oldTags);
1829          xmlFree (nameTag);
1830          nameTag = NULL;
1831        }*/
1832        while (*relationTable < (isNode ? 'n' : nameIsRelation ? 'x' : 'w') ||
1833            (*relationTable == (isNode ? 'n' : nameIsRelation ? 'x' : 'w') &&
1834             atoi (relationTable + 1) < nd.id)) {
1835          do {
1836            relationTable += strlen (relationTable) + 1;
1837            relationTable += strlen (relationTable) + 1;
1838          } while (*relationTable++ != '\0');
1839        }
1840        membershipType membership =
1841          *relationTable == (isNode ? 'n' : nameIsRelation ? 'x' : 'w') &&
1842              atoll (relationTable + 1) == nd.id ? relationTable : NULL;
1843
1844        for (membershipType m = membership; m; m = Next (m)) {
1845          if (strcmp (Role (m), "inner") == 0 && wStyle == elemCnt) {
1846            for (wStyle = 0; wStyle < elemCnt; wStyle++) {
1847              if (strcmp (eMap[wStyle].style_k, "natural") == 0 &&
1848                  strcmp (eMap[wStyle].style_v, "glacier") == 0) break;
1849              // Rendering does not support holes, so we just render something
1850              // close to the background colour
1851            }
1852          }
1853          else if (strcmp (Role (m), "outer") == 0) {
1854            outer[nd.id] = deque<long long> ();
1855            outer[nd.id].insert (outer[nd.id].end (), wayNd.begin (), wayNd.end ());
1856          }
1857        }
1858       
1859        #ifdef ONLY_ROUTING
1860        if (wStyle != highway_traffic_signals &&
1861            wStyle != highway_mini_roundabout &&
1862            !(wStyle >= restriction_no_right_turn &&
1863              wStyle <= restriction_only_straight_on) &&
1864            !(wStyle >= barrier_bollard &&
1865              wStyle <= barrier_toll_booth) &&
1866            !eMap[wStyle].defaultRestrict) wStyle = elemCnt;
1867        #endif
1868        if (wStyle == elemCnt /* 1 trick that did help enough to make files < 400MB
1869          || (!k2v["name"] && srec[wStyle].areaColour != -1)*/ ) wayNd.clear ();
1870        else {
1871          wp[0].other = -2;
1872          while (!wayNd.empty ()) {
1873            wp[0].wayPtr = ftell (pak);
1874            wp[1].wayPtr = TO_HALFSEG;
1875            wp[1].other = wp[0].other + 1;
1876            wp[0].id = onewayReverse ? wayNd.back () : wayNd.front ();
1877            /*if (lowzListCnt >=
1878                int (sizeof (lowzList) / sizeof (lowzList[0]))) lowzListCnt--;
1879            lowzList[lowzListCnt++] = s[0].lat; */
1880            if (onewayReverse) wayNd.pop_back ();
1881            else wayNd.pop_front ();
1882            wp[0].other = wayNd.empty () ? -2 : nOther++ * 2;
1883            FWRITE (wp, sizeof (wp), 1, groupf[S1GROUP (wp[0].id)]);
1884          }
1885          if (nameIsNode && (!wayFseek || wayFseek->off)) {
1886            wp[0].id = nd.id; // Create 2 fake halfSegs
1887            wp[0].wayPtr = ftell (pak);
1888            wp[1].wayPtr = TO_HALFSEG;
1889            wp[0].other = -2; // No next
1890            wp[1].other = -1; // No prev
1891            //lowzList[lowzListCnt++] = nd.id;
1892            FWRITE (wp, sizeof (wp), 1, groupf[S1GROUP (wp[0].id)]);
1893          }
1894         
1895          w.bits |= ~noMask & ((yesMask & (1 << accessR)) 
1896                               ? yesMask | ((1 << onewayR) - (1 << (accessR + 1)))
1897                               : yesMask | (eMap[wStyle].defaultRestrict &
1898                                          ((noMask & (1 << accessR)) ? (1 << onewayR) : ~0)));
1899          if (w.destination & (1 << accessR)) w.destination = ~0;
1900          memcpy (&srec[styleCnt], &srec[wStyle], sizeof (srec[0]));
1901          if (wayFseek && wayFseek->off) {
1902            w.clat = wayFseek->w->clat;
1903            w.clon = wayFseek->w->clon;
1904            w.dlat = wayFseek->w->dlat;
1905            w.dlon = wayFseek->w->dlon;
1906          }
1907          deque<string> tags = Osm2Gosmore (nd.id, k2v, w, srec[styleCnt], isNode,
1908            nameIsRelation, membership, wayRole);
1909          while (memcmp (&srec[styleCnt], &srec[wStyle], sizeof (srec[0]))
1910                 != 0) wStyle++;
1911          w.bits += wStyle;
1912          if (wStyle == styleCnt) {
1913            if (styleCnt == (2 << STYLE_BITS) - 2) {
1914              fprintf (stderr, "*** Warning: Too many styles !!!\n");
1915            }
1916            if (styleCnt < (2 << STYLE_BITS) - 1) styleCnt++;
1917          }
1918         
1919          /*if (srec[StyleNr (&w)].scaleMax > 10000000 &&
1920              (!wayFseek || wayFseek->off)) {
1921            for (int i = 0; i < lowzListCnt; i++) {
1922              if (i % 10 && i < lowzListCnt - 1) continue; // Skip some
1923              s[0].lat = lowzList[i];
1924              s[0].wayPtr = ftell (pak);
1925              s[1].wayPtr = TO_HALFSEG;
1926              s[1].other = i == 0 ? -4 : lowzOther++;
1927              s[0].other = i == lowzListCnt -1 ? -4 : lowzOther++;
1928              FWRITE (s, sizeof (s), 1, groupf[S1GROUP (s[0].lat)]);
1929            }
1930          }
1931          lowzListCnt = 0; */
1932         
1933          /*if (StyleNr (&w) < elemCnt && stricmp (eMap[StyleNr (&w)].style_v,
1934                                                  "city") == 0 && tags[0] == '\n') {
1935            int nlen = strcspn (tags + 1, "\n");
1936            char *n = (char *) xmlMalloc (strlen (tags) + 1 + nlen + 5 + 1);
1937            strcpy (n, tags);
1938            memcpy (n + strlen (tags), tags, 1 + nlen);
1939            strcpy (n + strlen (tags) + 1 + nlen, " City");
1940            //fprintf (stderr, "Mark : %s\n", n + strlen (tags) + 1);
1941            xmlFree (tags);
1942            tags = n;
1943          }
1944          char *compact = tags[0] == '\n' ? tags + 1 : tags; */
1945          if (!wayFseek || wayFseek->off) {
1946            FWRITE (&w, sizeof (w), 1, pak);
1947            FWRITE ("", 1, 1, pak); // '\0' at the front
1948            unsigned newln = 0;
1949            for (; !tags.empty (); tags.pop_front ()) {
1950              if (newln) FWRITE ("\n", 1, 1, pak);
1951              const char *compact = tags.front().c_str ();
1952              if (tags.front ()[0] == '\n') compact++;
1953              else {
1954                #ifndef ONLY_ROUTING
1955                // If all the idxes went into a single file, this can
1956                // be simplified a lot. One day when RAM is cheap.
1957                string line;
1958                deque<string>::iterator tItr = tags.begin ();
1959                do line += *tItr;
1960                while (!strchr ((*tItr++).c_str (), '\n') &&
1961                       tItr != tags.end ());
1962               
1963                unsigned grp, idx = ftell (pak);
1964                for (grp = 0; grp < IDXGROUPS - 1 &&
1965                 TagCmp (groupName[grp], (char*) line.c_str ()) < 0; grp++) {}
1966                FWRITE (&idx, sizeof (idx), 1, groupf[grp]);
1967                #endif
1968              }
1969              unsigned l = strlen (compact);
1970              newln = l > 0 && compact[l - 1] == '\n' ? 1 : 0;
1971              if (l > newln) FWRITE (compact, l - newln, 1, pak);
1972            }
1973            FWRITE ("", 1, 1, pak); // '\0' at the back
1974/*          for (char *ptr = tags; *ptr != '\0'; ) {
1975              if (*ptr++ == '\n') {
1976                unsigned idx = ftell (pak) + ptr - 1 - tags, grp;
1977                for (grp = 0; grp < IDXGROUPS - 1 &&
1978                       TagCmp (groupName[grp], ptr) < 0; grp++) {}
1979                FWRITE (&idx, sizeof (idx), 1, groupf[grp]);
1980              }
1981            }
1982            FWRITE (compact, strlen (compact) + 1, 1, pak); */
1983           
1984            // Write variable length tags and align on 4 bytes
1985            if (ftell (pak) & 3) {
1986              FWRITE ("   ", 4 - (ftell (pak) & 3), 1, pak);
1987            }
1988          }
1989          if (wayFseek) fseek (pak, (++wayFseek)->off, SEEK_SET);
1990          //xmlFree (tags); // Just set tags[0] = '\0'
1991          //tags = (char *) xmlStrdup (BAD_CAST "");
1992        }
1993        //tags[0] = '\0'; // Erase nodes with short names
1994        yesMask = noMask = 0;
1995        w.bits = 0;
1996        w.destination = 0;
1997        wStyle = elemCnt;
1998        onewayReverse = FALSE;
1999        while (!k2v.m.empty ()) {
2000          xmlFree ((char*) k2v.m.begin()->second);
2001          xmlFree ((char*) k2v.m.begin()->first);
2002          k2v.m.erase (k2v.m.begin ());
2003        }
2004        while (!wayRole.m.empty ()) {
2005          xmlFree ((char*) wayRole.m.begin()->second);
2006          xmlFree ((char*) wayRole.m.begin()->first);
2007          wayRole.m.erase (wayRole.m.begin ());
2008        }
2009      }
2010    } // if it was </...>
2011    xmlFree (name);
2012  } // While reading xml
2013  wayId.clear ();
2014  fprintf (stderr, "nOther=%d FIRST_LOWZ_OTHER=%d\n", nOther, FIRST_LOWZ_OTHER);
2015  assert (nOther * 2 < FIRST_LOWZ_OTHER);
2016  bucketsMin1 = (nOther >> 5) | (nOther >> 4);
2017  bucketsMin1 |= bucketsMin1 >> 2;
2018  bucketsMin1 |= bucketsMin1 >> 4;
2019  bucketsMin1 |= bucketsMin1 >> 8;
2020  bucketsMin1 |= bucketsMin1 >> 16;
2021  assert (bucketsMin1 < MAX_BUCKETS);
2022 
2023  for (int i = 0; i < IDXGROUPS; i++) fclose (groupf[i]);
2024  for (int i = S2GROUP (0); i < PAIRGROUP2 (0) + PAIRGROUPS2; i++) {
2025    assert (groupf[i] = fopen64 (groupName[i], "w+b"));
2026  } // Avoid exceeding ulimit
2027 
2028  nodeType *nodes = (nodeType *) malloc (sizeof (*nodes) * max_nodes);
2029  if (!nodes) {
2030    fprintf (stderr, "Out of memory. Reduce MAX_NODES and increase GRPs\n");
2031    return 3;
2032  }
2033  halfSegType s[2];
2034  for (int i = NGROUP (0); i < NGROUP (0) + NGROUPS; i++) {
2035    rewind (groupf[i]);
2036    memset (nodes, -1, sizeof (*nodes) * max_nodes);
2037    REBUILDWATCH (while (fread (&nd, sizeof (nd), 1, groupf[i]) == 1)) {
2038      memcpy (FindNode (nodes, nd.id), &nd, sizeof (nd));
2039    }
2040    fclose (groupf[i]);
2041    unlink (groupName[i]);
2042    rewind (groupf[i + NGROUPS]);
2043    REBUILDWATCH (while (fread (wp, sizeof (wp), 1, groupf[i + NGROUPS])
2044                         == 1)) {
2045      nodeType *n = FindNode (nodes, wp[0].id);
2046      //if (n->id == -1) printf ("** Undefined node %d\n", s[0].lat);
2047      s[0].other = wp[0].other;
2048      s[1].other = wp[1].other;
2049      s[0].wayPtr = wp[0].wayPtr;
2050      s[1].wayPtr = wp[1].wayPtr;
2051      s[0].lat = s[1].lat = n->id != -1 ? n->lat : INT_MIN;
2052      s[0].lon = s[1].lon = n->id != -1 ? n->lon : INT_MIN;
2053      FWRITE (s, sizeof (s), 1,
2054              groupf[-2 <= s[0].other && s[0].other < FIRST_LOWZ_OTHER
2055                     ? S2GROUP (Hash (s[0].lon, s[0].lat)) : PAIRGROUP (0) - 1]);
2056    }
2057    fclose (groupf[i + NGROUPS]);
2058    unlink (groupName[i + NGROUPS]);
2059  }
2060  free (nodes);
2061 
2062  struct {
2063    int nOther1, final;
2064  } offsetpair;
2065  offsetpair.final = 0;
2066 
2067  hashTable = (int *) malloc (sizeof (*hashTable) *
2068                              (bucketsMin1 + (bucketsMin1 >> 7) + 3));
2069  int bucket = -1;
2070  for (int i = S2GROUP (0); i < S2GROUP (0) + S2GROUPS; i++) {
2071    fflush (groupf[i]);
2072    size_t size = ftell (groupf[i]);
2073    rewind (groupf[i]);
2074    REBUILDWATCH (halfSegType *seg = (halfSegType *) mmap (NULL, size,
2075                                                           PROT_READ | PROT_WRITE, MAP_SHARED, fileno (groupf[i]), 0));
2076    qsort (seg, size / sizeof (s), sizeof (s),
2077           (int (*)(const void *, const void *))HalfSegCmp);
2078    for (int j = 0; j < int (size / sizeof (seg[0])); j++) {
2079      if (!(j & 1)) {
2080        while (bucket < Hash (seg[j].lon, seg[j].lat, FALSE)) {
2081//                            i >= S2GROUP (0) + S2GROUPS - 1)) {
2082          hashTable[++bucket] = offsetpair.final / 2;
2083        }
2084      }
2085      offsetpair.nOther1 = seg[j].other;
2086      if (seg[j].other >= 0) FWRITE (&offsetpair, sizeof (offsetpair), 1,
2087                                     groupf[PAIRGROUP (offsetpair.nOther1)]);
2088      offsetpair.final++;
2089    }
2090    munmap (seg, size);
2091  }
2092  while (bucket < bucketsMin1 + 1) {
2093    hashTable[++bucket] = offsetpair.final / 2;
2094  }
2095 
2096  ndType ndWrite;
2097  ndWrite.wayPtr = s[0].wayPtr; // sizeof (pakHead); // Anything halfvalid
2098  ndWrite.lon = ndWrite.lat = INT_MIN;
2099  ndWrite.other[0] = ndWrite.other[1] = 0;
2100  FWRITE (&ndWrite, sizeof (ndWrite), 1, pak); // Insert 'stopper' record
2101
2102  assert (ftell (pak) < (1LL<<32));
2103  // If this assert fails, wayPtr no longer fits in 32 bits
2104  ndStart = ftell (pak);
2105 
2106  int *pairing = (int *) malloc (sizeof (*pairing) * PAIRS);
2107  for (int i = PAIRGROUP (0); i < PAIRGROUP (0) + PAIRGROUPS; i++) {
2108    REBUILDWATCH (rewind (groupf[i]));
2109    while (fread (&offsetpair, sizeof (offsetpair), 1, groupf[i]) == 1) {
2110      pairing[offsetpair.nOther1 % PAIRS] = offsetpair.final;
2111    }
2112    int pairs = ftell (groupf[i]) / sizeof (offsetpair);
2113    for (int j = 0; j < pairs; j++) {
2114      offsetpair.final = pairing[j ^ 1];
2115      offsetpair.nOther1 = pairing[j];
2116      FWRITE (&offsetpair, sizeof (offsetpair), 1,
2117              groupf[PAIRGROUP2 (offsetpair.nOther1)]);
2118    }
2119    fclose (groupf[i]);
2120    unlink (groupName[i]);
2121  }
2122  free (pairing);
2123 
2124  int s2grp = S2GROUP (0), pairs, totalp = 0;
2125  halfSegType *seg = (halfSegType *) malloc (PAIRS * sizeof (*seg));
2126  assert (seg /* Out of memory. Reduce PAIRS for small scale rebuilds. */);
2127  for (int i = PAIRGROUP2 (0); i < PAIRGROUP2 (0) + PAIRGROUPS2; i++) {
2128    REBUILDWATCH (for (pairs = 0; pairs < PAIRS &&
2129                         s2grp < S2GROUP (0) + S2GROUPS; )) {
2130      if (fread (&seg[pairs], sizeof (seg[0]), 2, groupf [s2grp]) == 2) {
2131        pairs += 2;
2132      }
2133      else {
2134        fclose (groupf[s2grp]);
2135        unlink (groupName[s2grp]);
2136        s2grp++;
2137      }
2138    }
2139    rewind (groupf[i]);
2140    while (fread (&offsetpair, sizeof (offsetpair), 1, groupf[i]) == 1) {
2141      seg[offsetpair.nOther1 % PAIRS].other = offsetpair.final;
2142    }
2143    for (int j = 0; j < pairs; j += 2) {
2144      ndWrite.wayPtr = seg[j].wayPtr;
2145      ndWrite.lat = seg[j].lat;
2146      ndWrite.lon = seg[j].lon;
2147      ndWrite.other[0] = //seg[j].other >> 1; // Right shift handles -1 the
2148        seg[j].other < 0 ? 0 : (seg[j].other >> 1) - totalp;
2149      ndWrite.other[1] = //seg[j + 1].other >> 1; // way we want.
2150        seg[j + 1].other < 0 ? 0 : (seg[j + 1].other >> 1) - totalp;
2151      totalp++;
2152      FWRITE (&ndWrite, sizeof (ndWrite), 1, pak);
2153    }
2154    fclose (groupf[i]);
2155    unlink (groupName[i]);
2156  }
2157  free (seg);
2158  ndWrite.wayPtr = s[0].wayPtr; // sizeof (pakHead); // Anything halfvalid
2159  ndWrite.lon = ndWrite.lat = INT_MIN;
2160  ndWrite.other[0] = ndWrite.other[1] = 0;
2161  FWRITE (&ndWrite, sizeof (ndWrite), 1, pak); // Insert 'stopper' record
2162  hashTable[bucket]++; // And reserve space for it.
2163 
2164  fflush (pak);
2165  data = (char *) mmap (NULL, ftell (pak),
2166                        PROT_READ | PROT_WRITE, MAP_SHARED, fileno (pak), 0);
2167  fseek (pak, ftell (pak), SEEK_SET);
2168  vector<halfSegType> lseg;
2169  ndBase = (ndType*)(data + ndStart);
2170  #ifndef ONLY_ROUTING
2171  REBUILDWATCH (for (ndType *ndItr = ndBase;
2172                ndItr < ndBase + hashTable[bucketsMin1 + 1]; ndItr++)) {
2173  //while (fread (&ndWrite, sizeof (ndWrite), 1, pak) == 1)) {
2174    wayType *way = (wayType*) (data + ndItr->wayPtr);
2175    /* The difficult way of calculating bounding boxes,
2176       namely to adjust the centerpoint (it does save us a pass) : */
2177    // Block lost nodes with if (ndItr->lat == INT_MIN) continue;
2178    if (way->clat + way->dlat < ndItr->lat) {
2179      way->dlat = way->dlat < 0 ? 0 : // Bootstrap
2180        (way->dlat - way->clat + ndItr->lat) / 2;
2181      way->clat = ndItr->lat - way->dlat;
2182    }
2183    if (way->clat - way->dlat > ndItr->lat) {
2184      way->dlat = (way->dlat + way->clat - ndItr->lat) / 2;
2185      way->clat = ndItr->lat + way->dlat;
2186    }
2187    if (way->clon + way->dlon < ndItr->lon) {
2188      way->dlon = way->dlon < 0 ? 0 : // Bootstrap
2189        (way->dlon - way->clon + ndItr->lon) / 2;
2190      way->clon = ndItr->lon - way->dlon;
2191    }
2192    if (way->clon - way->dlon > ndItr->lon) {
2193      way->dlon = (way->dlon + way->clon - ndItr->lon) / 2;
2194      way->clon = ndItr->lon + way->dlon;
2195    }
2196
2197    // This is a simplified version of the rebuild: It does not use groups or files
2198    // and the lats & lons have been dereferenced previously. So the pairing is
2199    // simplified a lot.
2200    ndType *prev = LFollow (ndItr, ndItr, way, 0);
2201    if (!ndItr->other[1] && prev->wayPtr >= ndItr->wayPtr) {
2202      int length = 0;
2203      ndType *end;
2204      for (end = ndItr; end->other[0]; end = LFollow (end, ndItr, way, 1)) {
2205        length += lrint (sqrt (Sqr ((double)(end->lat - end[end->other[0]].lat)) +
2206                               Sqr ((double)(end->lon - end[end->other[0]].lon))));
2207        if (prev != ndItr && end->wayPtr < ndItr->wayPtr) break;
2208        // If it is circular and we didn't start at the way with the lowest
2209        // wayPtr, then we abort
2210      }
2211      if ((prev == ndItr || prev == end) && (length > 500000 ||
2212                  (end == ndItr && srec[StyleNr (way)].scaleMax > 100000))) {
2213        //printf (prev == ndItr ? "%3d Non circular %s\n" : "%3d Circular %s\n",
2214        //  ndItr - ndBase, (char*)(way+1)+1);
2215        //if (prev == ndItr) printf ("Circular\n");
2216        //printf ("%d\n", srec[StyleNr (way)].scaleMax);
2217        deque<ndType*> dp (1, end); // Stack for Ramer-Douglas-Peucker algorithm
2218        for (ndType *nd = ndItr; ; ) {
2219          ndType *worst = NULL, *dpItr; // Look for worst between nd and dp.back()
2220          if (nd != end) {
2221            double len = sqrt (Sqr ((double)(dp.back()->lon - nd->lon)) +
2222                               Sqr ((double)(nd->lat - dp.back ()->lat)));
2223            double latc = (dp.back ()->lon - nd->lon) / len, maxeps = 10000;
2224            double lonc = (nd->lat - dp.back ()->lat) / len, eps;
2225            for (dpItr = nd; dpItr != dp.back (); dpItr = LFollow (dpItr, ndItr, way, 1)) {
2226              eps = len == 0 ? sqrt (Sqr ((double)(dpItr->lat - nd->lat) -
2227                                          (double)(dpItr->lon - nd->lon))) :
2228                fabs ((dpItr->lat - nd->lat) * latc + (dpItr->lon - nd->lon) * lonc);
2229              if (eps > maxeps) {
2230                maxeps = eps;
2231                worst = dpItr;
2232              }
2233            }
2234          }
2235          if (worst) dp.push_back (worst);
2236          else { // The segment is reasonable
2237            lseg.push_back (halfSegType ());
2238            lseg.back ().lon = nd->lon;
2239            lseg.back ().lat = nd->lat;
2240            lseg.back ().wayPtr = ndItr->wayPtr;
2241            lseg.push_back (halfSegType ());
2242            lseg.back ().lon = nd->lon; // Unnecessary !
2243            lseg.back ().lat = nd->lat; // Unnecessary !
2244            lseg.back ().wayPtr = TO_HALFSEG; // Unnecessary !
2245            lseg.back ().other = nd == ndItr ? -4 : lowzOther++;
2246            (&lseg.back ())[-1].other = nd == end ? -4 : lowzOther++;
2247            // Be careful of the conditional post increment when rewriting this code !
2248            if (nd == end) break;
2249            nd = dp.back ();
2250            dp.pop_back ();
2251          }
2252        } // While DP has not passed the end
2253        //printf ("%d %d\n", lowzOther, lseg.size ());
2254      } // If the way belongs in the lowzoom
2255    } // If it was the start of a way
2256  } // For each highzoom nd
2257  #endif
2258  REBUILDWATCH (qsort (&lseg[0], lseg.size () / 2, sizeof (lseg[0]) * 2, 
2259    (int (*)(const void *, const void *))HalfSegCmp));
2260  int *lpair = new int[lowzOther - FIRST_LOWZ_OTHER];
2261  for (unsigned i = 0; i < lseg.size (); i++) {
2262    if (!(i & 1)) {
2263      while (bucket < Hash (lseg[i].lon, lseg[i].lat, TRUE)) {
2264        hashTable[++bucket] = i / 2 + hashTable[bucketsMin1 + 1];
2265      }
2266    }
2267    if (lseg[i].other >= 0) lpair[lseg[i].other - FIRST_LOWZ_OTHER] = i;
2268  }
2269  while (bucket < bucketsMin1 + (bucketsMin1 >> 7) + 2) {
2270    hashTable[++bucket] = lseg.size () / 2 + hashTable[bucketsMin1 + 1];
2271  }
2272  for (int i = 0; i < lowzOther - FIRST_LOWZ_OTHER; i += 2) {
2273    lseg[lpair[i]].other = lpair[i + 1];
2274    lseg[lpair[i + 1]].other = lpair[i];
2275  }
2276  delete lpair;
2277  for (unsigned i = 0; i < lseg.size (); i += 2) {
2278    ndWrite.lat = lseg[i].lat;
2279    ndWrite.lon = lseg[i].lon;
2280    ndWrite.wayPtr = lseg[i].wayPtr;
2281    ndWrite.other[0] = lseg[i].other < 0 ? 0 : (lseg[i].other >> 1) - i / 2;
2282    ndWrite.other[1] = lseg[i + 1].other < 0 ? 0 : (lseg[i + 1].other >> 1) - i / 2;
2283    FWRITE (&ndWrite, sizeof (ndWrite), 1, pak);
2284    //printf ("%3d %10d %10d %10d %3d %3d\n", i / 2, ndWrite.lat, ndWrite.lon, ndWrite.wayPtr,
2285    //  ndWrite.other[0], ndWrite.other[1]);
2286  }
2287 
2288  REBUILDWATCH (for (int i = 0; i < IDXGROUPS; i++)) {
2289    assert (groupf[i] = fopen64 (groupName[i], "r+b"));
2290    fseek (groupf[i], 0, SEEK_END);
2291    int fsize = ftell (groupf[i]);
2292    if (fsize > 0) {
2293      fflush (groupf[i]);
2294      unsigned *idx = (unsigned *) mmap (NULL, fsize,
2295                                         PROT_READ | PROT_WRITE, MAP_SHARED, fileno (groupf[i]), 0);
2296      qsort (idx, fsize / sizeof (*idx), sizeof (*idx), IdxCmp);
2297      FWRITE (idx, fsize, 1, pak);
2298#if 0
2299      for (int j = 0; j < fsize / (int) sizeof (*idx); j++) {
2300        printf ("%.*s\n", strcspn (data + idx[j], "\n"), data + idx[j]);
2301      }
2302#endif
2303      munmap (idx, fsize);
2304    }
2305    fclose (groupf[i]);
2306    unlink (groupName[i]);
2307  }
2308  //    printf ("ndCount=%d\n", ndCount);
2309  munmap (data, ndStart);
2310  FWRITE (hashTable, sizeof (*hashTable),
2311          bucketsMin1 + (bucketsMin1 >> 7) + 3, pak);
2312         
2313  CalculateInvSpeeds (srec, styleCnt);
2314  FWRITE (srec, sizeof (srec[0]), styleCnt, pak);
2315  FWRITE (&styleCnt, sizeof(styleCnt), 1, pak); // File ends with these
2316  FWRITE (&bucketsMin1, sizeof (bucketsMin1), 1, pak); // 3 variables
2317  FWRITE (&ndStart, sizeof (ndStart), 1, pak); /* for ndBase */
2318
2319  fclose (pak);
2320  free (hashTable);
2321
2322  return 0;
2323}
2324
2325/*==================================== SortRelations ======================================*/
2326int XmlTee (void * /*context*/, char *buf, int len)
2327{
2328  int n = fread (buf, 1, len, stdin);
2329  fwrite (buf, 1, n, stdout);
2330  return n; // == 0 ? -1 : n;
2331}
2332
2333int XmlClose (void */*context*/) { return 0; }
2334
2335struct memberType {
2336  int type;
2337  long long ref;
2338  const char *role, *tags;
2339};
2340
2341int MemberCmp (const memberType *a, const memberType *b)
2342{
2343  return a->type == b->type ? a->ref - b->ref : a->type - b->type;
2344}
2345
2346int SortRelations (void)
2347{
2348  xmlTextReaderPtr xml = xmlReaderForIO (XmlTee, XmlClose, NULL, "", NULL, 0);
2349    //xmlReaderForFd (STDIN_FILENO, "", NULL, 0);
2350  vector<memberType> member;
2351  unsigned rStart = 0, rel = FALSE;
2352  string *s = new string ();
2353  #ifdef MKDENSITY_CSV
2354  int lat, lon, *cnt = (int *) calloc (1024 * 1024, sizeof (*cnt));
2355  #endif
2356  while (xmlTextReaderRead (xml) == 1) {
2357    if (xmlTextReaderNodeType (xml) == XML_READER_TYPE_ELEMENT) {
2358      char *name = (char *) BAD_CAST xmlTextReaderName (xml);
2359     
2360      #ifdef MKDENSITY_CSV
2361      if (stricmp (name, "node") == 0) {
2362        while (xmlTextReaderMoveToNextAttribute (xml)) {
2363          char *aname = (char *) BAD_CAST xmlTextReaderName (xml); 
2364          char *avalue = (char *) BAD_CAST xmlTextReaderValue (xml);
2365          if (stricmp (aname, "lat") == 0) lat = Latitude (atof (avalue));
2366          if (stricmp (aname, "lon") == 0) lon = Longitude (atof (avalue));
2367          xmlFree (aname);
2368          xmlFree (avalue);
2369        }
2370        cnt[(lat / (1 << 22) + 512) * 1024 + (lon / (1 << 22) + 512)]++;
2371      }
2372      xmlFree (name);
2373      continue;
2374      #endif
2375     
2376      rel = rel || stricmp (name, "relation") == 0;
2377      if (stricmp (name, "relation") == 0) { // && rStart < member.size ()) {
2378        while (rStart < member.size ()) member[rStart++].tags = s->c_str ();
2379        s = new string (); // It leaks memory, but it cannot be freed until
2380                           // moments before exit.
2381        while (xmlTextReaderMoveToNextAttribute (xml)) {
2382          char *aname = (char *) BAD_CAST xmlTextReaderName (xml); 
2383          if (stricmp (aname, "id") == 0) {
2384            char *avalue = (char *) BAD_CAST xmlTextReaderValue (xml);
2385            *s += "relation_id\nr";
2386            *s += avalue;
2387            *s += '\n';
2388            xmlFree (avalue);
2389          }
2390          xmlFree (aname);
2391        }
2392      }
2393     
2394      if (rel && (stricmp (name, "member") == 0 || stricmp (name, "tag") == 0)) {
2395        if (name[0] == 'm') member.push_back (memberType ());
2396        while (xmlTextReaderMoveToNextAttribute (xml)) {
2397          char *aname = (char *) BAD_CAST xmlTextReaderName (xml); 
2398          char *avalue = (char *) BAD_CAST xmlTextReaderValue (xml);
2399          if (stricmp (aname, "type") == 0) {
2400            member.back ().type = avalue[0] == 'r' ? 'x' : avalue[0];
2401          }
2402          else if (stricmp (aname, "ref") == 0) member.back ().ref = atoll (avalue);
2403          else if (name[0] == 't' && stricmp (aname, "k") == 0) {
2404            *s += avalue;
2405            *s += '\n';
2406          } // I assume that "<tag" implies "k=..." followed by "v=..."
2407          else if (name[0] == 't' && stricmp (aname, "v") == 0) {
2408            *s += avalue;
2409            *s += '\n';
2410          }
2411         
2412          if (stricmp (aname, "role") == 0) member.back ().role = avalue;
2413          else xmlFree (avalue);
2414         
2415          xmlFree (aname);
2416        }
2417      }
2418      xmlFree (name);
2419    }
2420  }
2421  #ifdef MKDENSITY_CSV
2422  FILE *df = fopen ("density.csv", "wb");
2423  for (lat = 1023; lat >= 0; lat--) {
2424    for (lon = 0; lon < 1024; lon++) {
2425      fprintf (df, "%d%c", cnt[lat * 1024 + lon], lon == 1023 ? '\n' : ' ');
2426    }
2427  }
2428  return 0;
2429  #endif
2430  while (rStart < member.size ()) member[rStart++].tags = s->c_str ();
2431  qsort (&member[0], member.size (), sizeof (member[0]),
2432         (int (*)(const void *, const void *)) MemberCmp);
2433  FILE *idx = fopen ("relations.tbl", "wb");
2434  for (unsigned i = 0; i < member.size (); i++) {
2435    fprintf (idx, "%c%lld%c%s%c", member[i].type, member[i].ref, '\0', member[i].role, '\0');
2436    for (const char *ptr = member[i].tags; *ptr; ptr += strcspn (ptr, "\n") + 1) {
2437      fprintf (idx, "%.*s%c", (int) strcspn (ptr, "\n"), ptr, '\0');
2438    }
2439    fprintf (idx, "%c", '\0');
2440  }
2441  fprintf (idx, "z1%c", '\0'); // Insert stopper
2442  return 0;
2443}
2444
2445#endif
Note: See TracBrowser for help on using the repository browser.