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

Last change on this file since 16481 was 16362, checked in by lambertus, 10 years ago

Added filter for 'gnis:'-like keys (refs 2017)

  • Property svn:executable set to *
File size: 62.0 KB
Line 
1#ifdef ROUTE_SRV
2#include <sys/mman.h>
3#endif
4
5#include <stdio.h>
6#include <unistd.h>
7#include <vector>
8#include <assert.h>
9#include "float.h"
10using namespace std;
11
12#include "libgosm.h"
13
14routeNodeType *route = NULL, *shortest = NULL, **routeHeap;
15long dhashSize;
16int routeHeapSize, tlat, tlon, flat, flon, rlat, rlon;
17int *hashTable, bucketsMin1, pakHead = 0xEB3A942;
18char *gosmData, *gosmSstr[searchCnt];
19
20// this is used if the stylerec in the pakfile are overwritten with
21// one loaded from an alternative xml stylefile
22styleStruct srec[2 << STYLE_BITS];
23
24ndType *ndBase;
25int styleCnt;
26styleStruct *style;
27wayType *gosmSway[searchCnt];
28
29// store the maximum speeds (over all waytypes) of each vehicle type
30float maxspeeds[layerBit1];
31
32int TagCmp (char *a, char *b)
33{ // This works like the ordering of books in a library : We ignore
34  // meaningless words like "the", "street" and "north". We (should) also map
35  // deprecated words to their new words, like petrol to fuel
36  // TODO : We should consider an algorithm like double metasound.
37  static const char *omit[] = { /* "the", in the middle of a name ?? */
38    "ave", "avenue", "blvd", "boulevard", "byp", "bypass",
39    "cir", "circle", "close", "cres", "crescent", "ct", "court", "ctr",
40      "center",
41    "dr", "drive", "hwy", "highway", "ln", "lane", "loop",
42    "pass", "pky", "parkway", "pl", "place", "plz", "plaza",
43    /* "run" */ "rd", "road", "sq", "square", "st", "street",
44    "ter", "terrace", "tpke", "turnpike", /*trce, trace, trl, trail */
45    "walk",  "way"
46  };
47  static const char *words[] = { "", "first", "second", "third", "fourth",
48    "fifth", "sixth", "seventh", "eighth", "nineth", "tenth", "eleventh",
49    "twelth", "thirteenth", "fourteenth", "fifthteenth", "sixteenth",
50    "seventeenth", "eighteenth", "nineteenth", "twentieth" };
51  static const char *teens[] = { "", "", "twenty ", "thirty ", "fourty ",
52    "fifty ", "sixty ", "seventy ", "eighty ", "ninety " };
53 
54  if (stricmp (a, "the ") == 0) a += 4;
55  if (stricmp (b, "the ") == 0) b += 4;
56  if (strchr ("WEST", a[0]) && a[1] == ' ') a += 2; // e.g. N 21st St
57  if (strchr ("WEST", b[0]) && b[1] == ' ') b += 2;
58
59  for (;;) {
60    char n[2][30] = { "", "" }, *ptr[2];
61    int wl[2];
62    for (int i = 0; i < 2; i++) {
63      char **p = i ? &b : &a;
64      if ((*p)[0] == ' ') {
65        for (int i = 0; i < int (sizeof (omit) / sizeof (omit[0])); i++) {
66          if (strncasecmp (*p + 1, omit[i], strlen (omit[i])) == 0 &&
67              !isalpha ((*p)[1 + strlen (omit[i])])) {
68            (*p) += 1 + strlen (omit[i]);
69            break;
70          }
71        }
72      }
73      if (isdigit (**p) && (!isdigit((*p)[1]) || !isdigit ((*p)[2]))
74              /* && isalpha (*p + strcspn (*p, "0123456789"))*/) {
75        // while (atoi (*p) > 99) (*p)++; // Buggy
76        if (atoi (*p) > 20) strcpy (n[i], teens[atoi ((*p)++) / 10]);
77        strcat (n[i], words[atoi (*p)]);
78        while (isdigit (**p) /*|| isalpha (**p)*/) (*p)++;
79        ptr[i] = n[i];
80        wl[i] = strlen (n[i]);
81      }
82      else {
83        ptr[i] = *p;
84        wl[i] = **p == ' ' ? 1 : strcspn (*p , " \n");
85      }
86    }
87    int result = strncasecmp (ptr[0], ptr[1], wl[0] < wl[1] ? wl[1] : wl[0]);
88    if (result || *ptr[0] == '\0' || *ptr[0] == '\n') return result;
89    if (n[0][0] == '\0') a += wl[1]; // In case b was 21st
90    if (n[1][0] == '\0') b += wl[0]; // In case a was 32nd
91  }
92}
93
94/* 1. Bsearch idx such that
95      ZEnc (way[idx]) < ZEnc (clon/lat) < ZEnc (way[idx+1])
96   2. Fill the list with ways around idx.
97   3. Now there's a circle with clon/clat as its centre and that runs through
98      the worst way just found. Let's say it's diameter is d. There exist
99      4 Z squares smaller that 2d by 2d that cover this circle. Find them
100      with binary search and search through them for the nearest ways.
101   The worst case is when the nearest nodes are far along a relatively
102   straight line.
103*/
104static int IdxSearch (int *idx, int h, char *key, unsigned z)
105{
106  for (int l = 0; l < h;) {
107    char *tag = gosmData + idx[(h + l) / 2];
108    int diff = TagCmp (tag, key);
109    while (*--tag) {}
110    if (diff > 0 || (diff == 0 &&
111      ZEnc ((unsigned)((wayType *)tag)[-1].clat >> 16, 
112            (unsigned)((wayType *)tag)[-1].clon >> 16) >= z)) h = (h + l) / 2;
113    else l = (h + l) / 2 + 1;
114  }
115  return h;
116}
117
118void GosmSearch (int clon, int clat, char *key)
119{
120  __int64 dista[searchCnt];
121  char *taga[searchCnt];
122  int *idx =
123    (int *)(ndBase + hashTable[bucketsMin1 + (bucketsMin1 >> 7) + 2]);
124  int l = IdxSearch (idx, hashTable - idx, key, 0), count;
125//  char *lastName = data + idx[min (hashTable - idx),
126//    int (sizeof (gosmSway) / sizeof (gosmSway[0]))) + l - 1];
127  int cz = ZEnc ((unsigned) clat >> 16, (unsigned) clon >> 16);
128  for (count = 0; count + l < hashTable - idx && count < searchCnt;) {
129    int m[2], c = count, ipos, dir, bits;
130    m[0] = IdxSearch (idx, hashTable - idx, gosmData + idx[count + l], cz);
131    m[1] = m[0] - 1;
132    __int64 distm[2] = { -1, -1 }, big = ((unsigned __int64) 1 << 63) - 1;
133    while (c < searchCnt && (distm[0] < big || distm[1] < big)) {
134      dir = distm[0] < distm[1] ? 0 : 1;
135      if (distm[dir] != -1) {
136        for (ipos = c; count < ipos && distm[dir] < dista[ipos - 1]; ipos--) {
137          dista[ipos] = dista[ipos - 1];
138          gosmSway[ipos] = gosmSway[ipos - 1];
139          taga[ipos] = taga[ipos - 1];
140        }
141        char *tag = gosmData + idx[m[dir]];
142        taga[ipos] = tag;
143        while (*--tag) {}
144        gosmSway[ipos] = (wayType*)tag - 1;
145        dista[ipos] = distm[dir];
146        c++;
147      }
148      m[dir] += dir ? 1 : -1;
149
150      if (0 <= m[dir] && m[dir] < hashTable - idx &&
151        TagCmp (gosmData + idx[m[dir]], gosmData + idx[count + l]) == 0) {
152        char *tag = gosmData + idx[m[dir]];
153        while (*--tag) {}
154        distm[dir] = Sqr ((__int64)(clon - ((wayType*)tag)[-1].clon)) +
155          Sqr ((__int64)(clat - ((wayType*)tag)[-1].clat));
156      }
157      else distm[dir] = big;
158    }
159    if (count == c) break; // Something's wrong. idx[count + l] not found !
160    if (c >= searchCnt) {
161      c = count; // Redo the adding
162      for (bits = 0; bits < 16 && dista[searchCnt - 1] >> (bits * 2 + 32);
163        bits++) {}
164/* Print Z's for first solution
165      for (int j = c; j < searchCnt; j++) {
166        for (int i = 0; i < 32; i++) printf ("%d%s",
167          (ZEnc ((unsigned) gosmSway[j]->clat >> 16,
168                 (unsigned) gosmSway[j]->clon >> 16) >> (31 - i)) & 1,
169          i == 31 ? " y\n" : i % 2 ? " " : "");
170      } */
171/* Print centre, up, down, right and left to see if they're in the square
172      for (int i = 0; i < 32; i++) printf ("%d%s", (cz >> (31 - i)) & 1,
173        i == 31 ? " x\n" : i % 2 ? " " : "");
174      for (int i = 0; i < 32; i++) printf ("%d%s", (
175        ZEnc ((unsigned)(clat + (int) sqrt (dista[searchCnt - 1])) >> 16,
176              (unsigned)clon >> 16) >> (31 - i)) & 1,
177        i == 31 ? " x\n" : i % 2 ? " " : "");
178      for (int i = 0; i < 32; i++) printf ("%d%s", (
179        ZEnc ((unsigned)(clat - (int) sqrt (dista[searchCnt - 1])) >> 16,
180              (unsigned)clon >> 16) >> (31 - i)) & 1,
181        i == 31 ? " x\n" : i % 2 ? " " : "");
182      for (int i = 0; i < 32; i++) printf ("%d%s", (
183        ZEnc ((unsigned)clat >> 16,
184              (unsigned)(clon + (int) sqrt (dista[searchCnt - 1])) >> 16) >> (31 - i)) & 1,
185        i == 31 ? " x\n" : i % 2 ? " " : "");
186      for (int i = 0; i < 32; i++) printf ("%d%s", (
187        ZEnc ((unsigned)clat >> 16,
188              (unsigned)(clon - (int) sqrt (dista[searchCnt - 1])) >> 16) >> (31 - i)) & 1,
189        i == 31 ? " x\n" : i % 2 ? " " : "");
190*/     
191      int swap = cz ^ ZEnc (
192        (unsigned) (clat + (clat & (1 << (bits + 16))) * 4 -
193                                              (2 << (bits + 16))) >> 16,
194        (unsigned) (clon + (clon & (1 << (bits + 16))) * 4 -
195                                              (2 << (bits + 16))) >> 16);
196      // Now we search through the 4 squares around (clat, clon)
197      for (int mask = 0, maskI = 0; maskI < 4; mask += 0x55555555, maskI++) {
198        int s = IdxSearch (idx, hashTable - idx, gosmData + idx[count + l],
199          (cz ^ (mask & swap)) & ~((4 << (bits << 1)) - 1));
200/* Print the square
201        for (int i = 0; i < 32; i++) printf ("%d%s",
202          (((cz ^ (mask & swap)) & ~((4 << (bits << 1)) - 1)) >> (31 - i)) & 1,
203          i == 31 ? "\n" : i % 2 ? " " : "");
204        for (int i = 0; i < 32; i++) printf ("%d%s",
205          (((cz ^ (mask & swap)) | ((4 << (bits << 1)) - 1)) >> (31 - i)) & 1,
206          i == 31 ? "\n" : i % 2 ? " " : "");
207*/
208        for (;;) {
209          char *tag = gosmData + idx[s++];
210          if (TagCmp (gosmData + idx[count + l], tag) != 0) break;
211          while (*--tag) {}
212          wayType *w = (wayType*)tag - 1;
213          if ((ZEnc ((unsigned)w->clat >> 16, (unsigned) w->clon >> 16) ^
214               cz ^ (mask & swap)) >> (2 + (bits << 1))) break;
215          __int64 d = Sqr ((__int64)(w->clat - clat)) +
216                      Sqr ((__int64)(w->clon - clon));
217          if (count < searchCnt || d < dista[count - 1]) {
218            if (count < searchCnt) count++;
219            for (ipos = count - 1; ipos > c && d < dista[ipos - 1]; ipos--) {
220              dista[ipos] = dista[ipos - 1];
221              gosmSway[ipos] = gosmSway[ipos - 1];
222              taga[ipos] = taga[ipos - 1];
223            }
224            gosmSway[ipos] = w;
225            dista[ipos] = d;
226            taga[ipos] = gosmData + idx[s - 1];
227          }
228        } // For each entry in the square
229      } // For each of the 4 squares
230      break; // count < searchCnt implies a bug. Don't loop infinitely.
231    } // If the search list is filled by tags with this text
232    count = c;
233  } // For each
234  for (int i = 0; i < searchCnt; i++) free (gosmSstr[i]);
235  for (int j = 0; j < count; j++) {
236    gosmSstr[j] = (char *) malloc (strcspn (taga[j], "\n") + 1);
237    sprintf (gosmSstr[j], "%.*s", (int) strcspn (taga[j], "\n"), taga[j]);
238  }
239  for (int k = count; k < searchCnt; k++) gosmSstr[k] = NULL;
240}
241
242/*------------------------------- OsmItr --------------------------------*/
243int Next (OsmItr &itr) /* Friend of osmItr */
244{
245  do {
246    itr.nd[0]++;
247    while (itr.nd[0] >= itr.end) {
248      if ((itr.slon += itr.tsize) == itr.right) {
249        itr.slon = itr.left;  /* Here we wrap around from N85 to S85 ! */
250        if ((itr.slat += itr.tsize) == itr.bottom) return FALSE;
251      }
252      int bucket = Hash (itr.slon, itr.slat, itr.tsize != TILESIZE);
253      itr.nd[0] = ndBase + hashTable[bucket];
254      itr.end = ndBase + hashTable[bucket + 1];
255    }
256  } while (((itr.nd[0]->lon ^ itr.slon) & (~(itr.tsize - 1))) ||
257           ((itr.nd[0]->lat ^ itr.slat) & (~(itr.tsize - 1))));
258/*      ((itr.hs[1] = (halfSegType *) (data + itr.hs[0]->other)) > itr.hs[0] &&
259       itr.left <= itr.hs[1]->lon && itr.hs[1]->lon < itr.right &&
260       itr.top <= itr.hs[1]->lat && itr.hs[1]->lat < itr.bottom)); */
261/* while nd[0] is a hash collision, */ 
262  return TRUE;
263}
264
265/* Routing starts at the 'to' point and moves to the 'from' point. This will
266   help when we do in car navigation because the 'from' point will change
267   often while the 'to' point stays fixed, so we can keep the array of nodes.
268   It also makes the generation of the directions easier.
269
270   We use "double hashing" to keep track of the shortest distance to each
271   node. So we guess an upper limit for the number of nodes that will be
272   considered and then multiply by a few so that there won't be too many
273   clashes. For short distances we allow for dense urban road networks,
274   but beyond a certain point there is bound to be farmland or seas.
275
276   We call nodes that rescently had their "best" increased "active". The
277   active nodes are stored in a heap so that we can quickly find the most
278   promissing one.
279   
280   OSM nodes are not our "graph-theor"etic nodes. Our "graph-theor"etic nodes
281   are "states", namely the ability to reach nd directly from nd->other[dir]
282*/
283#ifdef ROUTE_CALIBRATE
284int routeAddCnt;
285#define ROUTE_SET_ADDND_COUNT(x) routeAddCnt = (x)
286#define ROUTE_SHOW_STATS printf ("%d / %d\n", routeAddCnt, dhashSize); \
287  fprintf (stderr, "flat=%lf&flon=%lf&tlat=%lf&tlon=%lf&fast=%d&v=motorcar\n", \
288    LatInverse (flat), LonInverse (flon), LatInverse (tlat), \
289    LonInverse (tlon), fast)
290// This ratio must be around 0.5. Close to 0 or 1 is bad
291#else
292#define ROUTE_SET_ADDND_COUNT(x)
293#define ROUTE_SHOW_STATS
294#endif
295
296static ndType *endNd[2] = { NULL, NULL}, from;
297static int toEndNd[2][2]; 
298
299routeNodeType *AddNd (ndType *nd, int dir, int cost, routeNodeType *newshort)
300{ /* This function is called when we find a valid route that consists of the
301     segments (hs, hs->other), (newshort->hs, newshort->hs->other),
302     (newshort->shortest->hs, newshort->shortest->hs->other), .., 'to'
303     with cost 'cost'.
304     
305     When cost is -1 this function just returns the entry for nd without
306     modifying anything. */
307  unsigned hash = (intptr_t) nd / 10 + dir, i = 0;
308  routeNodeType *n;
309  do {
310    #ifdef ROUTE_SRV
311    n = route + (nd == &from ? dhashSize - 2 : (nd - ndBase) * 2) + dir;
312    #else
313    if (i++ > 10) {
314      //fprintf (stderr, "Double hash bailout : Table full, hash function "
315      //  "bad or no route exists\n");
316      return NULL;
317    }
318    n = route + hash % dhashSize;
319    #endif
320    /* Linear congruential generator from wikipedia */
321    hash = (unsigned) (hash * (__int64) 1664525 + 1013904223);
322    if (n->nd == NULL) { /* First visit of this node */
323      if (cost < 0) return NULL;
324      n->nd = nd;
325      n->best = 0x7fffffff;
326      /* Will do later : routeHeap[routeHeapSize] = n; */
327      n->heapIdx = routeHeapSize++;
328      n->dir = dir;
329      n->remain = lrint (sqrt (Sqr ((__int64)(nd->lat - rlat)) +
330                               Sqr ((__int64)(nd->lon - rlon))));
331      if (!shortest || n->remain < shortest->remain) shortest = n;
332      ROUTE_SET_ADDND_COUNT (routeAddCnt + 1);
333    }
334  } while (n->nd != nd || n->dir != dir);
335
336  int diff = n->remain + (newshort ? newshort->best - newshort->remain : 0);
337  if (cost >= 0 && n->best > cost + diff) {
338    n->best = cost + diff;
339    n->shortest = newshort;
340    if (n->heapIdx < 0) n->heapIdx = routeHeapSize++;
341    for (; n->heapIdx > 1 &&
342         n->best < routeHeap[n->heapIdx / 2]->best; n->heapIdx /= 2) {
343      routeHeap[n->heapIdx] = routeHeap[n->heapIdx / 2];
344      routeHeap[n->heapIdx]->heapIdx = n->heapIdx;
345    }
346    routeHeap[n->heapIdx] = n;
347  }
348  return n;
349}
350
351inline int IsOneway (wayType *w, int Vehicle)
352{
353  return !((Vehicle == footR || Vehicle == bicycleR) &&
354    (w->bits & (1 << motorcarR))) && (w->bits & (1<<onewayR));
355}
356
357inline float GetWayInvSpeed (wayType *w, int Vehicle) {
358  if (w->maxspeed < Style (w)->aveSpeed[Vehicle]) {
359    // if w.maxspeed is less than the vehicle speed, then calculate
360    // invSpeed from w->maxspeed
361    // printf("DEBUG: overriding %f with %f (%f with %f)\n",
362    //     Style(w)->aveSpeed[Vehicle], w->maxspeed,
363    //     Style(w)->invSpeed[Vehicle], maxspeeds[Vehicle]/w->maxspeed);
364    return maxspeeds[Vehicle] / w->maxspeed;
365  } else {
366    // otherwise, just use the stored vehicle invSpeed
367    return Style (w)->invSpeed[Vehicle];
368  }
369}
370
371void Route (int recalculate, int plon, int plat, int Vehicle, int fast)
372{ /* Recalculate is faster but only valid if 'to', 'Vehicle' and
373     'fast' did not change */
374/* We start by finding the segment that is closest to 'from' and 'to' */
375  ROUTE_SET_ADDND_COUNT (0);
376  shortest = NULL;
377  for (int i = recalculate ? 0 : 1; i < 2; i++) {
378    int lon = i ? flon : tlon, lat = i ? flat : tlat;
379    __int64 bestd = (__int64) 1 << 62;
380    /* find min (Sqr (distance)). Use long long so we don't loose accuracy */
381    OsmItr itr (lon - 100000, lat - 100000, lon + 100000, lat + 100000);
382    /* Search 1km x 1km around 'from' for the nearest segment to it */
383    while (Next (itr)) {
384      // We don't do for (int dir = 0; dir < 1; dir++) {
385      // because if our search box is large enough, it will also give us
386      // the other node.
387      if (!(Way (itr.nd[0])->bits & (1 << Vehicle))) {
388        continue;
389      }
390      if (itr.nd[0]->other[0] < 0) continue;
391      __int64 lon0 = lon - itr.nd[0]->lon, lat0 = lat - itr.nd[0]->lat,
392              lon1 = lon - (ndBase + itr.nd[0]->other[0])->lon,
393              lat1 = lat - (ndBase + itr.nd[0]->other[0])->lat,
394              dlon = lon1 - lon0, dlat = lat1 - lat0;
395      /* We use Pythagoras to test angles for being greater that 90 and
396         consequently if the point is behind hs[0] or hs[1].
397         If the point is "behind" hs[0], measure distance to hs[0] with
398         Pythagoras. If it's "behind" hs[1], use Pythagoras to hs[1]. If
399         neither, use perpendicular distance from a point to a line */
400      int segLen = lrint (sqrt ((double)(Sqr(dlon) + Sqr (dlat))));
401      __int64 d = dlon * lon0 >= - dlat * lat0 ? Sqr (lon0) + Sqr (lat0) :
402        dlon * lon1 <= - dlat * lat1 ? Sqr (lon1) + Sqr (lat1) :
403        Sqr ((dlon * lat1 - dlat * lon1) / segLen);
404     
405      wayType *w = Way (itr.nd[0]);
406      if (i) { // For 'from' we take motion into account
407        __int64 motion = segLen ? 3 * (dlon * plon + dlat * plat) / segLen
408          : 0;
409        // What is the most appropriate multiplier for motion ?
410        if (motion > 0 && IsOneway (w, Vehicle)) d += Sqr (motion);
411        else d -= Sqr (motion);
412        // Is it better to say :
413        // d = lrint (sqrt ((double) d));
414        // if (motion < 0 || IsOneway (w)) d += motion;
415        // else d -= motion;
416      }
417     
418      if (d < bestd) {
419        bestd = d;
420        double invSpeed = !fast ? 1.0 : GetWayInvSpeed(w,Vehicle);
421        //printf ("%d %lf\n", i, invSpeed);
422        toEndNd[i][0] =
423          lrint (sqrt ((double)(Sqr (lon0) + Sqr (lat0))) * invSpeed);
424        toEndNd[i][1] =
425          lrint (sqrt ((double)(Sqr (lon1) + Sqr (lat1))) * invSpeed);
426//        if (dlon * lon1 <= -dlat * lat1) toEndNd[i][1] += toEndNd[i][0] * 9;
427//        if (dlon * lon0 >= -dlat * lat0) toEndNd[i][0] += toEndNd[i][1] * 9;
428
429        if (IsOneway (w, Vehicle)) toEndNd[i][1 - i] = 200000000;
430        /*  It's possible to go up a oneway at the end, but at a huge penalty*/
431        endNd[i] = itr.nd[0];
432        /* The router only stops after it has traversed endHs[1], so if we
433           want 'limit' to be accurate, we must subtract it's length
434        if (i) {
435          toEndHs[1][0] -= segLen;
436          toEndHs[1][1] -= segLen;
437        } */
438      }
439    } /* For each candidate segment */
440    if (bestd == ((__int64) 1 << 62) || !endNd[0]) {
441      endNd[i] = NULL;
442      //fprintf (stderr, "No segment nearby\n");
443      return;
444    }
445  } /* For 'from' and 'to', find segment that passes nearby */
446  from.lat = flat;
447  from.lon = flon;
448  if (recalculate || !route) {
449    #ifdef ROUTE_SRV
450    static FILE *tfile = NULL;
451    if (tfile) {
452      fclose (tfile);
453      munmap (route, (sizeof (*route) + sizeof (*routeHeap)) * dhashSize);
454    }
455    dhashSize = hashTable[bucketsMin1 + (bucketsMin1 >> 7) + 2] * 2;
456    if ((tfile = tmpfile ()) == NULL || ftruncate (fileno (tfile), dhashSize *
457               (sizeof (*route) + sizeof (*routeHeap))) != 0 ||
458        (route = (routeNodeType*) mmap (NULL, dhashSize *
459        (sizeof (*route) + sizeof (*routeHeap)),
460        PROT_READ | PROT_WRITE, MAP_SHARED, fileno (tfile), 0)) == MAP_FAILED) {
461      fprintf (stderr, "Ftruncate and Mmap of routing arrays\n");
462      route = NULL;
463      return;
464    }
465    #else
466    free (route);
467    dhashSize = Sqr ((tlon - flon) >> 16) + Sqr ((tlat - flat) >> 16) + 20;
468    dhashSize = dhashSize < 10000 ? dhashSize * 1000 : 10000000;
469    // Allocate one piece of memory for both route and routeHeap, so that
470    // we can easily retry if it fails on a small device
471    #ifdef _WIN32_WCE
472    MEMORYSTATUS memStat;
473    GlobalMemoryStatus (&memStat);
474    int lim = (memStat.dwAvailPhys - 1400000) / // Leave 1.4 MB free
475                 (sizeof (*route) + sizeof (*routeHeap));
476    if (dhashSize > lim && lim > 0) dhashSize = lim;
477    #endif
478
479    while (dhashSize > 0 && !(route = (routeNodeType*)
480        malloc ((sizeof (*route) + sizeof (*routeHeap)) * dhashSize))) {
481      dhashSize = dhashSize / 4 * 3;
482    }
483    memset (route, 0, (sizeof (*route) + sizeof (*routeHeap)) * dhashSize); 
484    #endif
485    routeHeapSize = 1; /* Leave position 0 open to simplify the math */
486    routeHeap = (routeNodeType**) (route + dhashSize) - 1;
487
488    rlat = flat;
489    rlon = flon;
490    AddNd (endNd[0], 0, toEndNd[0][0], NULL);
491    AddNd (ndBase + endNd[0]->other[0], 1, toEndNd[0][1], NULL);
492    AddNd (endNd[0], 1, toEndNd[0][0], NULL);
493    AddNd (ndBase + endNd[0]->other[0], 0, toEndNd[0][1], NULL);
494  }
495  else {
496    routeNodeType *frn = AddNd (&from, 0, -1, NULL);
497    if (frn) frn->best = 0x7fffffff;
498
499    routeNodeType *rn = AddNd (endNd[1], 0, -1, NULL);
500    if (rn) AddNd (&from, 0, toEndNd[1][1], rn);
501    routeNodeType *rno = AddNd (ndBase + endNd[1]->other[0], 1, -1, NULL);
502    if (rno) AddNd (&from, 0, toEndNd[1][0], rno);
503  }
504 
505  while (routeHeapSize > 1) {
506    routeNodeType *root = routeHeap[1];
507    routeHeapSize--;
508    int beste = routeHeap[routeHeapSize]->best;
509    for (int i = 2; ; ) {
510      int besti = i < routeHeapSize ? routeHeap[i]->best : beste;
511      int bestipp = i + 1 < routeHeapSize ? routeHeap[i + 1]->best : beste;
512      if (besti > bestipp) i++;
513      else bestipp = besti;
514      if (beste <= bestipp) {
515        routeHeap[i / 2] = routeHeap[routeHeapSize];
516        routeHeap[i / 2]->heapIdx = i / 2;
517        break;
518      }
519      routeHeap[i / 2] = routeHeap[i];
520      routeHeap[i / 2]->heapIdx = i / 2;
521      i = i * 2;
522    }
523    root->heapIdx = -1; /* Root now removed from the heap */
524    if (root->nd == &from) { // Remove 'from' from the heap in case we
525      shortest = root->shortest; // get called with recalculate=0
526      break;
527    }
528    if (root->nd == (!root->dir ? endNd[1] : ndBase + endNd[1]->other[0])) {
529      AddNd (&from, 0, toEndNd[1][1 - root->dir], root);
530    }
531    ndType *nd = root->nd, *other, *firstNd, *restrictItr;
532    while (nd > ndBase && nd[-1].lon == nd->lon &&
533      nd[-1].lat == nd->lat) nd--; /* Find first nd in node */
534    firstNd = nd; // Save it for checking restrictions
535    int rootIsAdestination = Way (root->nd)->destination & (1 << Vehicle);
536    /* Now work through the segments connected to root. */
537    do {
538      if (StyleNr (Way (nd)) >= barrier_bollard &&
539          StyleNr (Way (nd)) <= barrier_toll_booth &&
540          !(Way (nd)->bits & (1 << Vehicle))) break;
541      if (root->remain > 500000 && root->best - root->remain > 500000 &&
542          (StyleNr (Way (nd)) == highway_residential ||
543           StyleNr (Way (nd)) == highway_service ||
544           StyleNr (Way (nd)) == highway_living_street ||
545           StyleNr (Way (nd)) == highway_unclassified)) continue;
546      /* When more than 50km from the start and the finish, ignore minor
547         roads. This reduces the number of calculations. */
548      for (int dir = 0; dir < 2; dir++) {
549        if (nd == root->nd && dir == root->dir) continue;
550        /* Don't consider an immediate U-turn to reach root->hs->other.
551           This doesn't exclude 179.99 degree turns though. */
552       
553        if (nd->other[dir] < 0) continue;
554        if (Vehicle != footR && Vehicle != bicycleR) {
555          for (restrictItr = firstNd; restrictItr->other[0] < 0 &&
556                          restrictItr->other[1] < 0; restrictItr++) {
557            wayType *= Way (restrictItr);
558            if (StyleNr (w) < restriction_no_right_turn ||
559                StyleNr (w) > restriction_only_straight_on) continue;
560  //          printf ("aa\n");
561            if (atoi ((char*)(w + 1) + 1) == nd->wayPtr &&
562                atoi (strchr ((char*)(w + 1) + 1, ' ')) == root->nd->wayPtr) {
563               ndType *n2 = ndBase + root->nd->other[root->dir];
564               ndType *n0 = ndBase + nd->other[dir];
565               __int64 straight =
566                 (n2->lat - nd->lat) * (__int64)(nd->lat - n0->lat) +
567                 (n2->lon - nd->lon) * (__int64)(nd->lon - n0->lon), left =
568                 (n2->lat - nd->lat) * (__int64)(nd->lon - n0->lon) -
569                 (n2->lon - nd->lon) * (__int64)(nd->lat - n0->lat);
570               int azi = straight < left ? (straight < -left ? 3 : 0) :
571                 straight < -left ? 2 : 1;
572//               printf ("%d %9d %9d %d %d\n", azi, n2->lon - nd->lon, n0->lon - nd->lon, straight < left, straight < -left);
573//               printf ("%d %9d %9d\n", azi, n2->lat - nd->lat, n0->lat - nd->lat);
574               static const int no[] = { restriction_no_left_turn,
575                 restriction_no_straight_on, restriction_no_right_turn,
576                 restriction_no_u_turn },
577                 only[] = { restriction_only_left_turn,
578                 restriction_only_straight_on, restriction_only_right_turn,
579                 -1 /*  restriction_only_u_turn */ };
580               if (StyleNr (w) == only[azi ^ 1] ||
581                   StyleNr (w) == only[azi ^ 2] || StyleNr (w) == only[azi ^ 3]
582                   || StyleNr (w) == no[azi]) break;
583//               printf ("%d %d %d\n", azi, n2->lon, n0->lon);
584            }
585          }
586          if (restrictItr->other[0] < 0 &&
587              restrictItr->other[1] < 0) continue;
588        }
589        // Tagged node, start or end of way or restriction.
590       
591        other = ndBase + nd->other[dir];
592        wayType *w = Way (nd);
593        if ((w->bits & (1 << Vehicle)) && (dir || !IsOneway (w, Vehicle))) {
594          int d = lrint (sqrt ((double)
595            (Sqr ((__int64)(nd->lon - other->lon)) +
596             Sqr ((__int64)(nd->lat - other->lat)))) *
597                         (fast ? GetWayInvSpeed(w, Vehicle) : 1.0));     
598          if (rootIsAdestination && !(w->destination & (1 << Vehicle))) {
599            d += 5000000; // 500km penalty for entering v='destination' area.
600          }
601          AddNd (other, 1 - dir, d, root);
602        } // If we found a segment we may follow
603      }
604    } while (++nd < ndBase + hashTable[bucketsMin1 + 1] &&
605             nd->lon == nd[-1].lon && nd->lat == nd[-1].lat);
606  } // While there are active nodes left
607  ROUTE_SHOW_STATS;
608//  if (fastest) printf ("%lf
609//  printf ("%lf km\n", limit / 100000.0);
610}
611
612int JunctionType (ndType *nd)
613{
614  int ret = 'j';
615  while (nd > ndBase && nd[-1].lon == nd->lon &&
616    nd[-1].lat == nd->lat) nd--;
617  int segCnt = 0; // Count number of segments at x->shortest
618  do {
619    // TODO : Only count segment traversable by 'Vehicle'
620    // Except for the case where a cyclist passes a motorway_link.
621    // TODO : Don't count oneways entering the roundabout
622    if (nd->other[0] >= 0) segCnt++;
623    if (nd->other[1] >= 0) segCnt++;
624    if (StyleNr (Way (nd)) == highway_traffic_signals) {
625      ret = 't';
626    }
627    if (StyleNr (Way (nd)) == highway_mini_roundabout) {
628      ret = 'm';
629    }   
630  } while (++nd < ndBase + hashTable[bucketsMin1 + 1] &&
631           nd->lon == nd[-1].lon && nd->lat == nd[-1].lat);
632  return segCnt > 2 ? toupper (ret) : ret;
633}
634
635void CalculateMaxSpeeds(/* in */ const styleStruct* srec, int styleCnt, 
636                        /* out */ float* maxspeeds) {
637  //calculate maxspeeds for vehicles from styles
638  for (int i = 0; i < layerBit1; i++) {
639    // first calculate the maximum specified speed for each vehicle
640    // over all styles
641    maxspeeds[i] = 0;
642    // for style
643    for (int j = 0; j < styleCnt; j++) {
644      if (srec[j].aveSpeed[i] > maxspeeds[i]) {
645        maxspeeds[i] = srec[j].aveSpeed[i];
646      }
647    }
648  }
649}
650
651int GosmInit (void *d, long size)
652{
653  if (!d) return FALSE;
654  gosmData = (char*) d;
655  bucketsMin1 = ((int *) (gosmData + size))[-2];
656  hashTable = (int *) (gosmData + size) - bucketsMin1 - (bucketsMin1 >> 7)
657                      - 5;
658  ndBase = (ndType *)(gosmData + hashTable[bucketsMin1 + (bucketsMin1 >> 7)
659     + 4]);
660 
661  // load styleCnt and style rec
662  styleCnt = *((int *) (gosmData + sizeof(pakHead)));
663  style = (struct styleStruct *)
664    (gosmData + sizeof(pakHead) + sizeof(styleCnt));
665
666  memset (gosmSway, 0, sizeof (gosmSway));
667
668  // calculate the maximum specified speed for each vehicle over all styles
669  // (used for routing later)
670  CalculateMaxSpeeds(style, styleCnt, maxspeeds);
671 
672  return ndBase && hashTable && *(int*) gosmData == pakHead;
673}
674
675// *** EVERYTHING AFTER THIS POINT IS NOT IN THE WINDOWS BUILDS ***
676
677#ifndef _WIN32
678
679void GosmLoadAltStyle(const char* elemstylefile, const char* iconscsvfile) {
680  elemstyleMapping map[2 << STYLE_BITS]; // this is needed for
681                                         // LoadElemstyles but ignored
682  memset (&srec, 0, sizeof (srec)); // defined globally
683  memset (&map, 0, sizeof (map));
684  LoadElemstyles(elemstylefile, iconscsvfile, firstElemStyle, 
685                 srec, map, maxspeeds);
686  // over-ride style record loaded from pakfile with alternative
687  style = &(srec[0]);
688}
689
690/*--------------------------------- Rebuild code ---------------------------*/
691// These defines are only used during rebuild
692
693#include <sys/mman.h>
694#include <libxml/xmlreader.h>
695
696#define MAX_BUCKETS (1<<26)
697#define IDXGROUPS 676
698#define NGROUPS 60
699#define MAX_NODES 9000000 /* Max in a group */
700#define S2GROUPS 129 // Last group is reserved for lowzoom halfSegs
701#define NGROUP(x)  ((x) / MAX_NODES % NGROUPS + IDXGROUPS)
702#define S1GROUPS NGROUPS
703#define S1GROUP(x) ((x) / MAX_NODES % NGROUPS + IDXGROUPS + NGROUPS)
704#define S2GROUP(x) ((x) / (MAX_BUCKETS / (S2GROUPS - 1)) + IDXGROUPS + NGROUPS * 2)
705#define PAIRS (16 * 1024 * 1024)
706#define PAIRGROUPS 120
707#define PAIRGROUP(x) ((x) / PAIRS + S2GROUP (0) + S2GROUPS)
708#define PAIRGROUPS2 120
709#define PAIRGROUP2(x) ((x) / PAIRS + PAIRGROUP (0) + PAIRGROUPS)
710#define FIRST_LOWZ_OTHER (PAIRS * (PAIRGROUPS - 1))
711
712#define REBUILDWATCH(x) fprintf (stderr, "%3d %s\n", ++rebuildCnt, #x); x
713
714#define TO_HALFSEG -1 // Rebuild only
715
716struct halfSegType { // Rebuild only
717  int lon, lat, other, wayPtr;
718};
719
720struct nodeType {
721  int id, lon, lat;
722};
723
724char *data;
725
726inline nodeType *FindNode (nodeType *table, int id)
727{
728  unsigned hash = id;
729  for (;;) {
730    nodeType *n = &table[hash % MAX_NODES];
731    if (n->id < 0 || n->id == id) return n;
732    hash = hash * (__int64) 1664525 + 1013904223;
733  }
734}
735
736int HalfSegCmp (const halfSegType *a, const halfSegType *b)
737{
738  int lowz = a->other < -2 || FIRST_LOWZ_OTHER <= a->other;
739  int hasha = Hash (a->lon, a->lat, lowz), hashb = Hash (b->lon, b->lat, lowz);
740  return hasha != hashb ? hasha - hashb : a->lon != b->lon ? a->lon - b->lon :
741    a->lat != b->lat ? a->lat - b->lat :
742    (b->other < 0 && b[1].other < 0 ? 1 : 0) -
743    (a->other < 0 && a[1].other < 0 ? 1 : 0);
744} // First sort by hash bucket, then by lon, then by lat.
745// If they are all the same, the nodes goes in the front where so that it's
746// easy to iterate through the turn restrictions.
747
748int IdxCmp (const void *aptr, const void *bptr)
749{
750  char *ta = data + *(unsigned *)aptr, *tb = data + *(unsigned *)bptr;
751  int tag = TagCmp (ta, tb);
752  while (*--ta) {}
753  while (*--tb) {}
754  unsigned a = ZEnc ((unsigned)((wayType *)ta)[-1].clat >> 16, 
755                     (unsigned)((wayType *)ta)[-1].clon >> 16);
756  unsigned b = ZEnc ((unsigned)((wayType *)tb)[-1].clat >> 16, 
757                     (unsigned)((wayType *)tb)[-1].clon >> 16);
758  return tag ? tag : a < b ? -1 : 1;
759}
760
761/* To reduce the number of cache misses and disk seeks we need to construct
762 the pack file so that waysTypes that are physically close to each other, are
763 also close to each other in the file. We only know where ways are physically
764 after the first pass, so the reordering is one done during a bbox rebuild.
765 
766 Finding an optimal solution is quite similar to find a soluting to the
767 traveling salesman problem. Instead we just place them in 2-D Hilbert curve
768 order using a qsort. */
769typedef struct {
770  wayType *w;
771  int idx;
772} masterWayType;
773
774int MasterWayCmp (const void *a, const void *b)
775{
776  int r[2], t, s, i, lead;
777  for (i = 0; i < 2; i++) {
778    t = ZEnc (((masterWayType *)(i ? b : a))->w->clon >> 16,
779      ((unsigned)((masterWayType *)(i ? b : a))->w->clat) >> 16);
780    s = ((((unsigned)t & 0xaaaaaaaa) >> 1) | ((t & 0x55555555) << 1)) ^ ~t;
781    for (lead = 1 << 30; lead; lead >>= 2) {
782      if (!(t & lead)) t ^= ((t & (lead << 1)) ? s : ~s) & (lead - 1);
783    }
784    r[i] = ((t & 0xaaaaaaaa) >> 1) ^ t;
785  }
786  return r[0] < r[1] ? 1 : r[0] > r[1] ? -1 : 0;
787}
788
789int LoadElemstyles(/* in */ const char *elemstylesfname, 
790                   const char *iconsfname, int styleCnt,
791                   /* out */ styleStruct *srec, elemstyleMapping *map, 
792                   float* maxspeeds)
793{
794   //------------------------- elemstyle.xml : --------------------------
795    int ruleCnt = 0;
796    // zero-out elemstyle-to-stylestruct mappings
797    FILE *icons_csv = fopen (iconsfname, "r");
798    xmlTextReaderPtr sXml = xmlNewTextReaderFilename (elemstylesfname);
799    if (!sXml || !icons_csv) {
800      fprintf (stderr, "Either icons.csv or elemstyles.xml not found\n");
801      return 3;
802    }
803    for (int i = 0; i < (2 << STYLE_BITS); i++) {
804      srec[i].lineColour = -1;
805      srec[i].areaColour = -1;
806    }
807    /* If elemstyles contain these, we can delete these assignments : */
808    for (int i = restriction_no_right_turn;
809            i <= restriction_only_straight_on; i++) {
810      strcpy(map[i].style_k,"restriction");
811      srec[i].scaleMax = 1;
812      srec[i].lineColour = 0; // Make it match.
813    }
814    strcpy(map[restriction_no_right_turn].style_v,"no_right_turn");
815    strcpy(map[restriction_no_left_turn].style_v,"no_left_turn");
816    strcpy(map[restriction_no_u_turn].style_v,"no_u_turn");
817    strcpy(map[restriction_no_straight_on].style_v,"no_straight_on");
818    strcpy(map[restriction_only_right_turn].style_v,"only_right_turn");
819    strcpy(map[restriction_only_left_turn].style_v,"only_left_turn");
820    strcpy(map[restriction_only_straight_on].style_v,"only_straight_on");
821
822    while (xmlTextReaderRead (sXml)) {
823      char *name = (char*) xmlTextReaderName (sXml);
824      //xmlChar *val = xmlTextReaderValue (sXml);
825      if (xmlTextReaderNodeType (sXml) == XML_READER_TYPE_ELEMENT) {
826        if (strcasecmp (name, "scale_max") == 0) {
827          while (xmlTextReaderRead (sXml) && // memory leak :
828            xmlStrcmp (xmlTextReaderName (sXml), BAD_CAST "#text") != 0) {}
829          srec[styleCnt].scaleMax = atoi ((char *) xmlTextReaderValue (sXml));
830        }
831        while (xmlTextReaderMoveToNextAttribute (sXml)) {
832          char *n = (char *) xmlTextReaderName (sXml);
833          char *v = (char *) xmlTextReaderValue (sXml);
834          if (strcasecmp (name, "condition") == 0) {
835            if (strcasecmp (n, "k") == 0) strcpy(map[styleCnt].style_k, v);
836            if (strcasecmp (n, "v") == 0) strcpy(map[styleCnt].style_v, v);
837          }
838          if (strcasecmp (name, "line") == 0) {
839            if (strcasecmp (n, "width") == 0) {
840              srec[styleCnt].lineWidth = atoi (v);
841            }
842            if (strcasecmp (n, "realwidth") == 0) {
843              srec[styleCnt].lineRWidth = atoi (v);
844            }
845            if (strcasecmp (n, "colour") == 0) {
846              sscanf (v, "#%x", &srec[styleCnt].lineColour);
847            }
848            if (strcasecmp (n, "colour_bg") == 0) {
849              sscanf (v, "#%x", &srec[styleCnt].lineColourBg);
850            }
851            srec[styleCnt].dashed = srec[styleCnt].dashed ||
852              (strcasecmp (n, "dashed") == 0 && strcasecmp (v, "true") == 0);
853          }
854          if (strcasecmp (name, "area") == 0) {
855            if (strcasecmp (n, "colour") == 0) {
856              sscanf (v, "#%x", &srec[styleCnt].areaColour);
857            }
858          }
859          if (strcasecmp (name, "icon") == 0) {
860            if (strcasecmp (n, "src") == 0) {
861              while (v[strcspn ((char *) v, "/ ")]) {
862                v[strcspn ((char *) v, "/ ")] = '_';
863              }
864              char line[80], fnd = FALSE;
865              static const char *set[] = { "classic.big_", "classic.small_",
866                "square.big_", "square.small_" };
867              for (int i = 0; i < 4; i++) {
868                srec[styleCnt].x[i * 4 + 2] = srec[styleCnt].x[i * 4 + 3] = 1;
869              // Default to 1x1 dummys
870                int slen = strlen (set[i]), vlen = strlen (v);
871                rewind (icons_csv);
872                while (fgets (line, sizeof (line) - 1, icons_csv)) {
873                  if (strncmp (line, set[i], slen) == 0 &&
874                      strncmp (line + slen, v, vlen - 1) == 0) {
875                    sscanf (line + slen + vlen, ":%d:%d:%d:%d",
876                      srec[styleCnt].x + i * 4, srec[styleCnt].x + i * 4 + 1,
877                      srec[styleCnt].x + i * 4 + 2,
878                      srec[styleCnt].x + i * 4 + 3);
879                    fnd = TRUE;
880                  }
881                }
882              }
883              if (!fnd) fprintf (stderr, "Icon %s not found\n", v);
884            }
885          }
886          if (strcasecmp (name, "routing") == 0 && atoi (v) > 0) {
887            #define M(field) if (strcasecmp (n, #field) == 0) {\
888              map[styleCnt].defaultRestrict |= 1 << field ## R; \
889              srec[styleCnt].aveSpeed[field ## R] = atof (v); \
890            }
891            RESTRICTIONS
892            #undef M
893          }
894         
895          xmlFree (v);
896          xmlFree (n);
897        }
898      }
899      else if (xmlTextReaderNodeType (sXml) == XML_READER_TYPE_END_ELEMENT
900                  && strcasecmp ((char *) name, "rule") == 0) {
901        int ipos;
902        #define s(k,v,shortname,extraTags) { #k, #v },
903        static const char *stylet[][2] = { STYLES };
904        #undef s
905        for (ipos = 0; ipos < firstElemStyle; ipos++) {
906          if (strcmp (stylet[ipos][0], map[styleCnt].style_k) == 0 && 
907              strcmp (stylet[ipos][1], map[styleCnt].style_v) == 0) break;
908        }
909        map[ipos < firstElemStyle ? ipos : styleCnt].ruleNr = ruleCnt++;
910        if (ipos < firstElemStyle) {
911          memcpy (&srec[ipos], &srec[styleCnt], sizeof (srec[ipos]));
912          memcpy (&srec[styleCnt], &srec[styleCnt + 1], sizeof (srec[0]));
913          map[ipos].defaultRestrict = map[styleCnt].defaultRestrict;
914          map[styleCnt].defaultRestrict = 0;
915          strcpy(map[ipos].style_k,map[styleCnt].style_k);
916          strcpy(map[ipos].style_v,map[styleCnt].style_v);
917        }
918        else if (styleCnt < (2 << STYLE_BITS) - 2) styleCnt++;
919        else fprintf (stderr, "Too many rules. Increase STYLE_BITS\n");
920      }
921      xmlFree (name);
922      //xmlFree (val);     
923    }
924
925    // calculate the maximum specified speed for each vehicle over all
926    // styles
927    CalculateMaxSpeeds(srec, styleCnt, maxspeeds);
928
929    // for vehicle
930    for (int i = 0; i < layerBit1; i++) {
931      // for style
932      for (int j = 0; j < styleCnt; j++) {
933        // if no speed is defined for a vehicle on this style, then
934        // set the aveSpeed to be the maximum of any other
935        // vehicles. This speed will only be used if vehicle=yes is
936        // defined on the way. (e.g. highway=foot motorcar=yes)
937        if (srec[j].aveSpeed[i] == 0) { 
938          for (int k = 0; k < layerBit1; k++) {
939            if (srec[j].aveSpeed[i] < srec[j].aveSpeed[k]) {
940              srec[j].aveSpeed[i] = srec[j].aveSpeed[k];
941            } 
942          } // without breaking the normal maximum speed for this vehicle
943          if (srec[j].aveSpeed[i] > maxspeeds[i]) {
944            srec[j].aveSpeed[i] = maxspeeds[i];
945          }
946        }
947        // store the proportion of maxspeed for routing
948        srec[j].invSpeed[i] = maxspeeds[i] / srec[j].aveSpeed[i];
949      }
950    }
951    xmlFreeTextReader (sXml);
952
953    return styleCnt;
954}
955
956int RebuildPak(const char* pakfile, const char* elemstylefile, 
957               const char* iconscsvfile, const char* masterpakfile, 
958               const int bbox[4]) {
959  assert (layerBit3 < 32);
960
961  int rebuildCnt = 0;
962  FILE *pak, *masterf;
963  int ndStart;
964  wayType *master = NULL;
965  if (strcmp(masterpakfile,"")) {
966    if (!(masterf = fopen64 (masterpakfile, "r")) ||
967        fseek (masterf, -sizeof (ndStart), SEEK_END) != 0 ||
968        fread (&ndStart, sizeof (ndStart), 1, masterf) != 1 ||
969        (long)(master = (wayType *)mmap (NULL, ndStart, PROT_READ,
970                                         MAP_SHARED, fileno (masterf), 
971                                         0)) == -1) {
972      fprintf (stderr, "Unable to open %s for bbox rebuild\n",masterpakfile);
973      return 4;
974    }
975  }
976 
977  if (!(pak = fopen64 (pakfile, "w+"))) {
978    fprintf (stderr, "Cannot create %s\n",pakfile);
979    return 2;
980  }
981  fwrite (&pakHead, sizeof (pakHead), 1, pak);
982
983  //------------------------ elemstylesfile : -----------------------------
984  styleStruct srec[2 << STYLE_BITS];
985  elemstyleMapping map[2 << STYLE_BITS];
986  float maxspeeds[layerBit1];
987  memset (&srec, 0, sizeof (srec));
988  memset (&map, 0, sizeof (map));
989 
990  int styleCnt = LoadElemstyles(elemstylefile, iconscsvfile, firstElemStyle, 
991                                srec, map, maxspeeds);
992  // write number of styles
993  fwrite (&styleCnt, sizeof(styleCnt), 1, pak); 
994  // followed by styleStruct
995  fwrite (&srec, sizeof (srec[0]), styleCnt + 1, pak);   
996
997  //------------------ OSM Data File (/dev/stdin) : ------------------------
998  xmlTextReaderPtr xml = xmlReaderForFd (STDIN_FILENO, "", NULL, 0);
999  FILE *groupf[PAIRGROUP2 (0) + PAIRGROUPS2];
1000  char groupName[PAIRGROUP2 (0) + PAIRGROUPS2][9];
1001  for (int i = 0; i < PAIRGROUP2 (0) + PAIRGROUPS2; i++) {
1002    sprintf (groupName[i], "%c%c%d.tmp", i / 26 % 26 + 'a', i % 26 + 'a',
1003             i / 26 / 26);
1004    if (i < S2GROUP (0) && !(groupf[i] = fopen64 (groupName[i], "w+"))) {
1005      fprintf (stderr, "Cannot create temporary file.\n"
1006               "Possibly too many open files, in which case you must run "
1007               "ulimit -n or recompile\n");
1008      return 9;
1009     
1010    }
1011  }
1012 
1013#if 0 // For making sure we have a Hilbert curve
1014  bucketsMin1 = MAX_BUCKETS - 1;
1015  for (int x = 0; x < 16; x++) {
1016    for (int y = 0; y < 16; y++) {
1017      printf ("%7d ", Hash (x << TILEBITS, y << TILEBITS));
1018    }
1019    printf ("\n");
1020  }
1021#endif
1022   
1023  nodeType nd;
1024  halfSegType s[2];
1025  int nOther = 0, lowzOther = FIRST_LOWZ_OTHER, isNode = 0;
1026  int yesMask = 0, noMask = 0, *wayFseek = NULL;
1027  int lowzList[1000], lowzListCnt = 0, wStyle = styleCnt, ref = 0, role = 0;
1028  int member[2], relationType = 0;
1029  vector<int> wayId, wayMember, cycleNet;
1030  s[0].lat = 0; // Should be -1 ?
1031  s[0].other = -2;
1032  s[1].other = -1;
1033  wayType w;
1034  w.clat = 0;
1035  w.clon = 0;
1036  w.dlat = INT_MIN;
1037  w.dlon = INT_MIN;
1038  w.bits = 0;
1039  w.destination = 0;
1040  w.maxspeed = FLT_MAX;
1041 
1042  // if we are doing a second pass bbox rebuild
1043  if (master) {
1044    masterWayType *masterWay = (masterWayType *) 
1045      malloc (sizeof (*masterWay) * (ndStart / (sizeof (wayType) + 4)));
1046   
1047    unsigned i = 0, offset = ftell (pak), wcnt;
1048    wayType *m = (wayType *)(((char *)master) + offset);
1049    for (wcnt = 0; (char*) m < (char*) master + ndStart; wcnt++) {
1050      if (bbox[0] <= m->clat + m->dlat && bbox[1] <= m->clon + m->dlon &&
1051          m->clat - m->dlat <= bbox[2] && m->clon - m->dlon <= bbox[3] &&
1052          StyleNr (m) < styleCnt) {
1053        masterWay[i].idx = wcnt;
1054        masterWay[i++].w = m;
1055      }
1056      m = (wayType*)((char*)m +
1057                     ((1 + strlen ((char*)(m + 1) + 1) + 1 + 3) & ~3)) + 1;
1058    }
1059    qsort (masterWay, i, sizeof (*masterWay), MasterWayCmp);
1060    assert (wayFseek = (int*) calloc (sizeof (*wayFseek),
1061                                      ndStart / (sizeof (wayType) + 4)));
1062    for (unsigned j = 0; j < i; j++) {
1063      wayFseek[masterWay[j].idx] = offset;
1064      offset += sizeof (*masterWay[j].w) +
1065        ((1 + strlen ((char*)(masterWay[j].w + 1) + 1) + 1 + 3) & ~3);
1066    }
1067    wayFseek[wcnt] = offset;
1068    fflush (pak);
1069    ftruncate (fileno (pak), offset); // fflush first ?
1070    free (masterWay);
1071    fseek (pak, *wayFseek, SEEK_SET);
1072  }
1073 
1074  char *tag_k = NULL, *tags = (char *) BAD_CAST xmlStrdup (BAD_CAST "");
1075  char *nameTag = NULL;
1076  REBUILDWATCH (while (xmlTextReaderRead (xml))) {
1077    char *name = (char *) BAD_CAST xmlTextReaderName (xml);
1078    //xmlChar *value = xmlTextReaderValue (xml); // always empty
1079    if (xmlTextReaderNodeType (xml) == XML_READER_TYPE_ELEMENT) {
1080      isNode = stricmp (name, "way") != 0 && stricmp (name, "relation") != 0
1081        && (stricmp (name, "node") == 0 || isNode);
1082      while (xmlTextReaderMoveToNextAttribute (xml)) {
1083        char *aname = (char *) BAD_CAST xmlTextReaderName (xml);
1084        char *avalue = (char *) BAD_CAST xmlTextReaderValue (xml);
1085        //        if (xmlStrcasecmp (name, "node") == 0)
1086        if (stricmp (aname, "id") == 0) nd.id = atoi (avalue);
1087        if (stricmp (aname, "lat") == 0) nd.lat = Latitude (atof (avalue));
1088        if (stricmp (aname, "lon") == 0) nd.lon = Longitude (atof (avalue));
1089        if (stricmp (aname, "ref") == 0) ref = atoi (avalue);
1090        if (stricmp (aname, "type") == 0) relationType = avalue[0];
1091        if (stricmp (aname, "role") == 0) role = avalue[0];
1092
1093#define K_IS(x) (stricmp (tag_k, x) == 0)
1094#define V_IS(x) (stricmp (avalue, x) == 0)
1095
1096        if (stricmp (aname, "v") == 0) {
1097          if (K_IS ("route") && V_IS ("bicycle")) {
1098            cycleNet.insert (cycleNet.end (), wayMember.begin (), 
1099                             wayMember.end ());
1100          }
1101          if ((!wayFseek || *wayFseek) &&
1102              (K_IS ("lcn_ref") || K_IS ("rcn_ref") || K_IS ("ncn_ref"))) {
1103            cycleNet.push_back (ftell (pak));
1104          }
1105         
1106          int newStyle = 0;
1107          // TODO: this for loop could be clearer as a while
1108          for (; newStyle < styleCnt && !(K_IS (map[newStyle].style_k) &&
1109                                          (map[newStyle].style_v[0] == '\0' || V_IS (map[newStyle].style_v)) &&
1110                                          (isNode ? srec[newStyle].x[2] :
1111                                           srec[newStyle].lineColour != -1 ||
1112                                           srec[newStyle].areaColour != -1)); newStyle++) {}
1113          // elemstyles rules are from most important to least important
1114          // Ulf has placed rules at the beginning that will highlight
1115          // errors, like oneway=true -> icon=deprecated. So they must only
1116          // match nodes when no line or area colour was given and only
1117          // match ways when no icon was given.
1118          if (K_IS ("junction") && V_IS ("roundabout")) {
1119            yesMask |= (1 << onewayR) | (1 << roundaboutR);
1120          }
1121          else if (newStyle < styleCnt && 
1122                   (wStyle == styleCnt || 
1123                    map[wStyle].ruleNr > map[newStyle].ruleNr)) {
1124            wStyle = newStyle;
1125          }
1126         
1127          if (K_IS ("name")) {
1128            nameTag = avalue;
1129            avalue = (char*) xmlStrdup (BAD_CAST "");
1130          }
1131          else if (K_IS ("ref")) {
1132            xmlChar *tmp = xmlStrdup (BAD_CAST "\n");
1133            tmp = xmlStrcat (BAD_CAST tmp, BAD_CAST avalue);
1134            avalue = tags; // Old 'tags' will be freed
1135            tags = (char*) xmlStrcat (tmp, BAD_CAST tags);
1136            // name always first tag.
1137          }
1138          else if (K_IS ("maxspeed")) {
1139            char units[80] = "";
1140            sscanf(avalue,"%f%s",&(w.maxspeed),units);
1141            // check for mph and variants and convert to kph
1142            if (strlen(units) > 0) {
1143              if (units[0] == 'm' || units[0] == 'M' ) {
1144                w.maxspeed *= 1.609344;
1145              }
1146            }
1147          }
1148          else if (K_IS ("layer")) w.bits |= atoi (avalue) << 29;
1149         
1150#define M(field) else if (K_IS (#field)) {                              \
1151            if (V_IS ("yes") || V_IS ("1") || V_IS ("permissive") ||    \
1152                V_IS ("true")) {                                        \
1153              yesMask |= 1 << field ## R;                               \
1154            } else if (V_IS ("no") || V_IS ("0") || V_IS ("private")) { \
1155              noMask |= 1 << field ## R;                                \
1156            }                                                           \
1157            else if (V_IS ("destination")) {                            \
1158              yesMask |= 1 << field ## R;                               \
1159              w.destination |= 1 << field ## R;                         \
1160            }                                                           \
1161          }
1162          RESTRICTIONS
1163#undef M
1164           
1165          else if (!V_IS ("no") && !V_IS ("false") && 
1166                   !K_IS ("sagns_id") && !K_IS ("sangs_id") && 
1167                   !K_IS ("is_in") && !V_IS ("residential") &&
1168                   !V_IS ("unclassified") && !V_IS ("tertiary") &&
1169                   !V_IS ("secondary") && !V_IS ("primary") && // Esp. ValidateMode
1170                   !V_IS ("junction") && /* Not approved and when it isn't obvious
1171                                            from the ways that it's a junction, the tag will
1172                                            often be something ridiculous like
1173                                            junction=junction ! */
1174                   // blocked as highway:  !V_IS ("mini_roundabout") && !V_IS ("roundabout") &&
1175                   !V_IS ("traffic_signals") && !K_IS ("editor") &&
1176                   !K_IS ("class") /* esp. class=node */ &&
1177                   !K_IS ("type") /* This is only for boules, but we drop it
1178                                     because it's often misused */ &&
1179                   !V_IS ("National-Land Numerical Information (Railway) 2007, MLIT Japan") &&
1180                   !V_IS ("National-Land Numerical Information (Lake and Pond) 2005, MLIT Japan") &&
1181                   !V_IS ("National-Land Numerical Information (Administrative area) 2007, MLIT Japan") &&
1182                   !V_IS ("coastline_old") &&
1183                   !K_IS ("upload_tag") && !K_IS ("admin_level") &&
1184                   (!isNode || (!K_IS ("highway") && !V_IS ("water") &&
1185                                !K_IS ("abutters") && !V_IS ("coastline")))) {
1186            // First block out tags that will bloat the index, will not make
1187            // sense or are implied.
1188           
1189            // tags = xmlStrcat (tags, tag_k); // with this it's
1190            // tags = xmlStrcat (tags, "="); // it's amenity=fuel
1191            tags = (char *) xmlStrcat (BAD_CAST tags, BAD_CAST "\n");
1192            tags = (char *) BAD_CAST xmlStrcat (BAD_CAST tags, 
1193                                                V_IS ("yes") || V_IS ("1") || V_IS ("true")
1194                                                ? BAD_CAST tag_k : BAD_CAST avalue);
1195          }
1196        }
1197        if (stricmp (aname, "k") == 0) { /* Prevent useless tags from ending up in the pak file */
1198          xmlFree (tag_k);
1199          tag_k = avalue;
1200          if (strncasecmp (tag_k, "tiger:", 6) == 0 ||
1201              K_IS ("created_by") || K_IS ("converted_by") ||
1202              strncasecmp (tag_k, "source", 6) == 0 ||
1203              strncasecmp (tag_k, "AND_", 4) == 0 ||
1204              strncasecmp (tag_k, "AND:", 4) == 0 ||
1205              strncasecmp (tag_k, "KSJ2:", 5) == 0 || 
1206                  strncasecmp (tag_k, "geobase:", 8) == 0 ||
1207                  strncasecmp (tag_k, "kms:", 4) == 0 ||
1208                  strncasecmp (tag_k, "openGeoDB:", 10) == 0 ||
1209                  strncasecmp (tag_k, "gnis:", 5) == 0 ||
1210                  K_IS ("note:ja") ||
1211              K_IS ("attribution") /* Mostly MassGIS */ ||
1212              K_IS ("time") || K_IS ("ele") || K_IS ("hdop") ||
1213              K_IS ("sat") || K_IS ("pdop") || K_IS ("speed") ||
1214              K_IS ("course") || K_IS ("fix") || K_IS ("vdop")) {
1215            xmlFree (aname);
1216            break;
1217          }
1218        }
1219        else xmlFree (avalue);
1220        xmlFree (aname);
1221      } /* While it's an attribute */
1222      if (relationType == 'w' && stricmp (name, "member") == 0) {
1223        for (unsigned i = 0; i < wayId.size (); i += 2) {
1224          if (ref == wayId[i]) wayMember.push_back (wayId[i + 1]);
1225        }
1226      }
1227      if (!wayFseek || *wayFseek) {
1228        if (stricmp (name, "member") == 0 && role != 'v') {
1229          for (unsigned i = 0; i < wayId.size (); i += 2) {
1230            if (ref == wayId[i]) member[role == 'f' ? 0 : 1] = wayId[i + 1];
1231          }
1232        }
1233        else if (stricmp (name, "nd") == 0 ||
1234                 stricmp (name, "member") == 0) {
1235          if (s[0].lat) {
1236            fwrite (s, sizeof (s), 1, groupf[S1GROUP (s[0].lat)]);
1237          }
1238          s[0].wayPtr = ftell (pak);
1239          s[1].wayPtr = TO_HALFSEG;
1240          s[1].other = s[0].other + 1;
1241          s[0].other = nOther++ * 2;
1242          s[0].lat = ref;
1243          if (lowzListCnt >=
1244              int (sizeof (lowzList) / sizeof (lowzList[0]))) lowzListCnt--;
1245          lowzList[lowzListCnt++] = ref;
1246        }
1247      }
1248      if (stricmp (name, "node") == 0 && bbox[0] <= nd.lat &&
1249          bbox[1] <= nd.lon && nd.lat <= bbox[2] && nd.lon <= bbox[3]) {
1250        fwrite (&nd, sizeof (nd), 1, groupf[NGROUP (nd.id)]);
1251      }
1252    }
1253    if (xmlTextReaderNodeType (xml) == XML_READER_TYPE_END_ELEMENT) {
1254      int nameIsNode = stricmp (name, "node") == 0;
1255      int nameIsRelation = stricmp (name, "relation") == 0;
1256      if (nameIsRelation) wayMember.clear ();
1257      if (stricmp (name, "way") == 0 || nameIsNode || nameIsRelation) {
1258        w.bits += wStyle;
1259        if (!nameIsRelation && !nameIsNode) {
1260          wayId.push_back (nd.id);
1261          wayId.push_back (ftell (pak));
1262        }
1263        if (nameIsRelation) {
1264          xmlFree (nameTag);
1265          char str[21];
1266          sprintf (str, "%d %d", member[0], member[1]);
1267          nameTag = (char *) xmlStrdup (BAD_CAST str);
1268        }
1269        if (nameTag) {
1270          char *oldTags = tags;
1271          tags = (char *) xmlStrdup (BAD_CAST "\n");
1272          tags = (char *) xmlStrcat (BAD_CAST tags, BAD_CAST nameTag);
1273          tags = (char *) xmlStrcat (BAD_CAST tags, BAD_CAST oldTags);
1274          xmlFree (oldTags);
1275          xmlFree (nameTag);
1276          nameTag = NULL;
1277        }
1278        if (!nameIsNode || strlen (tags) > 8 || wStyle != styleCnt) {
1279          if (nameIsNode && (!wayFseek || *wayFseek)) {
1280            if (s[0].lat) { // Flush s
1281              fwrite (s, sizeof (s), 1, groupf[S1GROUP (s[0].lat)]);
1282            }
1283            s[0].lat = nd.id; // Create 2 fake halfSegs
1284            s[0].wayPtr = ftell (pak);
1285            s[1].wayPtr = TO_HALFSEG;
1286            s[0].other = -2; // No next
1287            s[1].other = -1; // No prev
1288            lowzList[lowzListCnt++] = nd.id;
1289          }
1290          if (s[0].other > -2) { // Not lowz
1291            if (s[0].other >= 0) nOther--; // Reclaim unused 'other' number
1292            s[0].other = -2;
1293          }
1294         
1295          if (srec[StyleNr (&w)].scaleMax > 10000000 &&
1296              (!wayFseek || *wayFseek)) {
1297            for (int i = 0; i < lowzListCnt; i++) {
1298              if (i % 10 && i < lowzListCnt - 1) continue; // Skip some
1299              if (s[0].lat) { // Flush s
1300                fwrite (s, sizeof (s), 1, groupf[S1GROUP (s[0].lat)]);
1301              }
1302              s[0].lat = lowzList[i];
1303              s[0].wayPtr = ftell (pak);
1304              s[1].wayPtr = TO_HALFSEG;
1305              s[1].other = i == 0 ? -4 : lowzOther++;
1306              s[0].other = i == lowzListCnt -1 ? -4 : lowzOther++;
1307            }
1308          }
1309          lowzListCnt = 0;
1310         
1311          if (StyleNr (&w) < styleCnt && stricmp (map[StyleNr (&w)].style_v,
1312                                                  "city") == 0 && tags[0] == '\n') {
1313            int nlen = strcspn (tags + 1, "\n");
1314            char *n = (char *) xmlMalloc (strlen (tags) + 1 + nlen + 5 + 1);
1315            strcpy (n, tags);
1316            memcpy (n + strlen (tags), tags, 1 + nlen);
1317            strcpy (n + strlen (tags) + 1 + nlen, " City");
1318            //fprintf (stderr, "Mark : %s\n", n + strlen (tags) + 1);
1319            xmlFree (tags);
1320            tags = n; 
1321          }
1322          w.bits |= ~noMask & (yesMask | (map[StyleNr (&w)].defaultRestrict &
1323                                          ((noMask & (1 << accessR)) ? (1 << onewayR) : ~0)));
1324          if (w.destination & (1 << accessR)) w.destination = ~0;
1325          char *compact = tags[0] == '\n' ? tags + 1 : tags;
1326          if (!wayFseek || *wayFseek) {
1327            fwrite (&w, sizeof (w), 1, pak);
1328            fwrite (tags + strlen (tags), 1, 1, pak); // '\0' at the front
1329            for (char *ptr = tags; *ptr != '\0'; ) {
1330              if (*ptr++ == '\n') {
1331                unsigned idx = ftell (pak) + ptr - 1 - tags, grp;
1332                for (grp = 0; grp < IDXGROUPS - 1 &&
1333                       TagCmp (groupName[grp], ptr) < 0; grp++) {}
1334                fwrite (&idx, sizeof (idx), 1, groupf[grp]);
1335              }
1336            }
1337            fwrite (compact, strlen (compact) + 1, 1, pak);
1338           
1339            // Write variable length tags and align on 4 bytes
1340            if (ftell (pak) & 3) {
1341              fwrite (tags, 4 - (ftell (pak) & 3), 1, pak);
1342            }
1343          }
1344          if (wayFseek) fseek (pak, *++wayFseek, SEEK_SET);
1345          //xmlFree (tags); // Just set tags[0] = '\0'
1346          //tags = (char *) xmlStrdup (BAD_CAST "");
1347        }
1348        tags[0] = '\0'; // Erase nodes with short names
1349        yesMask = noMask = 0;
1350        w.bits = 0;
1351        w.destination = 0;
1352        w.maxspeed = FLT_MAX;
1353        wStyle = styleCnt;
1354      }
1355    } // if it was </...>
1356    xmlFree (name);
1357  } // While reading xml
1358  wayId.clear ();
1359  if (s[0].lat && (!wayFseek || *wayFseek)) {
1360    fwrite (s, sizeof (s), 1, groupf[S1GROUP (s[0].lat)]);
1361  }
1362  assert (nOther * 2 < FIRST_LOWZ_OTHER);
1363  bucketsMin1 = (nOther >> 5) | (nOther >> 4);
1364  bucketsMin1 |= bucketsMin1 >> 2;
1365  bucketsMin1 |= bucketsMin1 >> 4;
1366  bucketsMin1 |= bucketsMin1 >> 8;
1367  bucketsMin1 |= bucketsMin1 >> 16;
1368  assert (bucketsMin1 < MAX_BUCKETS);
1369 
1370  for (int i = 0; i < IDXGROUPS; i++) fclose (groupf[i]);
1371  for (int i = S2GROUP (0); i < PAIRGROUP2 (0) + PAIRGROUPS2; i++) {
1372    assert (groupf[i] = fopen64 (groupName[i], "w+"));
1373  } // Avoid exceeding ulimit
1374 
1375  nodeType *nodes = (nodeType *) malloc (sizeof (*nodes) * MAX_NODES);
1376  if (!nodes) {
1377    fprintf (stderr, "Out of memory. Reduce MAX_NODES and increase GRPs\n");
1378    return 3;
1379  }
1380  for (int i = NGROUP (0); i < NGROUP (0) + NGROUPS; i++) {
1381    rewind (groupf[i]);
1382    memset (nodes, -1, sizeof (*nodes) * MAX_NODES);
1383    REBUILDWATCH (while (fread (&nd, sizeof (nd), 1, groupf[i]) == 1)) {
1384      memcpy (FindNode (nodes, nd.id), &nd, sizeof (nd));
1385    }
1386    fclose (groupf[i]);
1387    unlink (groupName[i]);
1388    rewind (groupf[i + NGROUPS]);
1389    REBUILDWATCH (while (fread (s, sizeof (s), 1, groupf[i + NGROUPS])
1390                         == 1)) {
1391      nodeType *n = FindNode (nodes, s[0].lat);
1392      //if (n->id == -1) printf ("** Undefined node %d\n", s[0].lat);
1393      s[0].lat = s[1].lat = n->id != -1 ? n->lat : INT_MIN;
1394      s[0].lon = s[1].lon = n->id != -1 ? n->lon : INT_MIN;
1395      fwrite (s, sizeof (s), 1,
1396              groupf[-2 <= s[0].other && s[0].other < FIRST_LOWZ_OTHER
1397                     ? S2GROUP (Hash (s[0].lon, s[0].lat)) : PAIRGROUP (0) - 1]);
1398    }
1399    fclose (groupf[i + NGROUPS]);
1400    unlink (groupName[i + NGROUPS]);
1401  }
1402  free (nodes);
1403 
1404  struct {
1405    int nOther1, final;
1406  } offsetpair;
1407  offsetpair.final = 0;
1408 
1409  hashTable = (int *) malloc (sizeof (*hashTable) *
1410                              (bucketsMin1 + (bucketsMin1 >> 7) + 3));
1411  int bucket = -1;
1412  for (int i = S2GROUP (0); i < S2GROUP (0) + S2GROUPS; i++) {
1413    fflush (groupf[i]);
1414    size_t size = ftell (groupf[i]);
1415    rewind (groupf[i]);
1416    REBUILDWATCH (halfSegType *seg = (halfSegType *) mmap (NULL, size,
1417                                                           PROT_READ | PROT_WRITE, MAP_SHARED, fileno (groupf[i]), 0));
1418    qsort (seg, size / sizeof (s), sizeof (s),
1419           (int (*)(const void *, const void *))HalfSegCmp);
1420    for (int j = 0; j < int (size / sizeof (seg[0])); j++) {
1421      if (!(j & 1)) {
1422        while (bucket < Hash (seg[j].lon, seg[j].lat,
1423                              i >= S2GROUP (0) + S2GROUPS - 1)) {
1424          hashTable[++bucket] = offsetpair.final / 2;
1425        }
1426      }
1427      offsetpair.nOther1 = seg[j].other;
1428      if (seg[j].other >= 0) fwrite (&offsetpair, sizeof (offsetpair), 1,
1429                                     groupf[PAIRGROUP (offsetpair.nOther1)]);
1430      offsetpair.final++;
1431    }
1432    munmap (seg, size);
1433  }
1434  while (bucket < bucketsMin1 + (bucketsMin1 >> 7) + 2) {
1435    hashTable[++bucket] = offsetpair.final / 2;
1436  }
1437 
1438  ndStart = ftell (pak);
1439 
1440  int *pairing = (int *) malloc (sizeof (*pairing) * PAIRS);
1441  for (int i = PAIRGROUP (0); i < PAIRGROUP (0) + PAIRGROUPS; i++) {
1442    REBUILDWATCH (rewind (groupf[i]));
1443    while (fread (&offsetpair, sizeof (offsetpair), 1, groupf[i]) == 1) {
1444      pairing[offsetpair.nOther1 % PAIRS] = offsetpair.final;
1445    }
1446    int pairs = ftell (groupf[i]) / sizeof (offsetpair);
1447    for (int j = 0; j < pairs; j++) {
1448      offsetpair.final = pairing[j ^ 1];
1449      offsetpair.nOther1 = pairing[j];
1450      fwrite (&offsetpair, sizeof (offsetpair), 1,
1451              groupf[PAIRGROUP2 (offsetpair.nOther1)]);
1452    }
1453    fclose (groupf[i]);
1454    unlink (groupName[i]);
1455  }
1456  free (pairing);
1457 
1458  int s2grp = S2GROUP (0), pairs;
1459  halfSegType *seg = (halfSegType *) malloc (PAIRS * sizeof (*seg));
1460  assert (seg /* Out of memory. Reduce PAIRS for small scale rebuilds. */);
1461  ndType ndWrite;
1462  for (int i = PAIRGROUP2 (0); i < PAIRGROUP2 (0) + PAIRGROUPS2; i++) {
1463    REBUILDWATCH (for (pairs = 0; pairs < PAIRS &&
1464                         s2grp < S2GROUP (0) + S2GROUPS; )) {
1465      if (fread (&seg[pairs], sizeof (seg[0]), 2, groupf [s2grp]) == 2) {
1466        pairs += 2;
1467      }
1468      else {
1469        fclose (groupf[s2grp]);
1470        unlink (groupName[s2grp]);
1471        s2grp++;
1472      }
1473    }
1474    rewind (groupf[i]);
1475    while (fread (&offsetpair, sizeof (offsetpair), 1, groupf[i]) == 1) {
1476      seg[offsetpair.nOther1 % PAIRS].other = offsetpair.final;
1477    }
1478    for (int j = 0; j < pairs; j += 2) {
1479      ndWrite.wayPtr = seg[j].wayPtr;
1480      ndWrite.lat = seg[j].lat;
1481      ndWrite.lon = seg[j].lon;
1482      ndWrite.other[0] = seg[j].other >> 1; // Right shift handles -1 the
1483      ndWrite.other[1] = seg[j + 1].other >> 1; // way we want.
1484      fwrite (&ndWrite, sizeof (ndWrite), 1, pak);
1485    }
1486    fclose (groupf[i]);
1487    unlink (groupName[i]);
1488  }
1489  free (seg);
1490 
1491  fflush (pak);
1492  data = (char *) mmap (NULL, ndStart,
1493                        PROT_READ | PROT_WRITE, MAP_SHARED, fileno (pak), 0);
1494  fseek (pak, ndStart, SEEK_SET);
1495  REBUILDWATCH (for (unsigned i = 0; i < cycleNet.size (); i++)) {
1496    wayType *way = (wayType*) (data + cycleNet[i]);
1497    for (int j = StyleNr (way) + 1; j < styleCnt; j++) {
1498      if (strncasecmp (map[j].style_k, "cyclenet", 8) == 0 &&
1499          stricmp (map[j].style_k + 8, map[StyleNr (way)].style_k) == 0 &&
1500          stricmp (map[j].style_v, map[StyleNr (way)].style_v) == 0) {
1501        way->bits = (way->bits & ~((2 << STYLE_BITS) - 1)) | j;
1502      }
1503    }
1504  }
1505  REBUILDWATCH (while (fread (&ndWrite, sizeof (ndWrite), 1, pak) == 1)) {
1506    //if (bucket > Hash (ndWrite.lon, ndWrite.lat)) printf ("unsorted !\n");
1507    wayType *way = (wayType*) (data + ndWrite.wayPtr);
1508   
1509    /* The difficult way of calculating bounding boxes,
1510       namely to adjust the centerpoint (it does save us a pass) : */
1511    // Block lost nodes with if (ndWrite.lat == INT_MIN) continue;
1512    if (way->clat + way->dlat < ndWrite.lat) {
1513      way->dlat = way->dlat < 0 ? 0 : // Bootstrap
1514        (way->dlat - way->clat + ndWrite.lat) / 2;
1515      way->clat = ndWrite.lat - way->dlat;
1516    }
1517    if (way->clat - way->dlat > ndWrite.lat) {
1518      way->dlat = (way->dlat + way->clat - ndWrite.lat) / 2;
1519      way->clat = ndWrite.lat + way->dlat;
1520    }
1521    if (way->clon + way->dlon < ndWrite.lon) {
1522      way->dlon = way->dlon < 0 ? 0 : // Bootstrap
1523        (way->dlon - way->clon + ndWrite.lon) / 2;
1524      way->clon = ndWrite.lon - way->dlon;
1525    }
1526    if (way->clon - way->dlon > ndWrite.lon) {
1527      way->dlon = (way->dlon + way->clon - ndWrite.lon) / 2;
1528      way->clon = ndWrite.lon + way->dlon;
1529    }
1530  }
1531#ifndef LAMBERTUS
1532  REBUILDWATCH (for (int i = 0; i < IDXGROUPS; i++)) {
1533    assert (groupf[i] = fopen64 (groupName[i], "r+"));
1534    fseek (groupf[i], 0, SEEK_END);
1535    int fsize = ftell (groupf[i]);
1536    fflush (groupf[i]);
1537    unsigned *idx = (unsigned *) mmap (NULL, fsize,
1538                                       PROT_READ | PROT_WRITE, MAP_SHARED, fileno (groupf[i]), 0);
1539    qsort (idx, fsize / sizeof (*idx), sizeof (*idx), IdxCmp);
1540    fwrite (idx, fsize, 1, pak);
1541#if 0
1542    for (int j = 0; j < fsize / (int) sizeof (*idx); j++) {
1543      printf ("%.*s\n", strcspn (data + idx[j], "\n"), data + idx[j]);
1544    }
1545#endif
1546    munmap (idx, fsize);
1547    fclose (groupf[i]);
1548    unlink (groupName[i]);
1549  }
1550#endif // LAMBERTUS
1551  //    printf ("ndCount=%d\n", ndCount);
1552  munmap (data, ndStart);
1553  fwrite (hashTable, sizeof (*hashTable),
1554          bucketsMin1 + (bucketsMin1 >> 7) + 3, pak);
1555  fwrite (&bucketsMin1, sizeof (bucketsMin1), 1, pak);
1556  fwrite (&ndStart, sizeof (ndStart), 1, pak); /* for ndBase */
1557
1558  fclose (pak);
1559  free (hashTable);
1560
1561  return 0;
1562}
1563
1564#endif
Note: See TracBrowser for help on using the repository browser.