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

Last change on this file since 15090 was 13906, checked in by daviddean, 11 years ago

Maxspeed now converts maxspeed=N m/hr and variants into km/hr for routing calculations. This is basically done based on the first non-space character after the number.

  • Property svn:executable set to *
File size: 61.7 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 (dhashSize) * 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) {
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:", 4) == 0 || K_IS ("note:ja") ||
1206              K_IS ("attribution") /* Mostly MassGIS */ ||
1207              K_IS ("time") || K_IS ("ele") || K_IS ("hdop") ||
1208              K_IS ("sat") || K_IS ("pdop") || K_IS ("speed") ||
1209              K_IS ("course") || K_IS ("fix") || K_IS ("vdop")) {
1210            xmlFree (aname);
1211            break;
1212          }
1213        }
1214        else xmlFree (avalue);
1215        xmlFree (aname);
1216      } /* While it's an attribute */
1217      if (relationType == 'w' && stricmp (name, "member") == 0) {
1218        for (unsigned i = 0; i < wayId.size (); i += 2) {
1219          if (ref == wayId[i]) wayMember.push_back (wayId[i + 1]);
1220        }
1221      }
1222      if (!wayFseek || *wayFseek) {
1223        if (stricmp (name, "member") == 0 && role != 'v') {
1224          for (unsigned i = 0; i < wayId.size (); i += 2) {
1225            if (ref == wayId[i]) member[role == 'f' ? 0 : 1] = wayId[i + 1];
1226          }
1227        }
1228        else if (stricmp (name, "nd") == 0 ||
1229                 stricmp (name, "member") == 0) {
1230          if (s[0].lat) {
1231            fwrite (s, sizeof (s), 1, groupf[S1GROUP (s[0].lat)]);
1232          }
1233          s[0].wayPtr = ftell (pak);
1234          s[1].wayPtr = TO_HALFSEG;
1235          s[1].other = s[0].other + 1;
1236          s[0].other = nOther++ * 2;
1237          s[0].lat = ref;
1238          if (lowzListCnt >=
1239              int (sizeof (lowzList) / sizeof (lowzList[0]))) lowzListCnt--;
1240          lowzList[lowzListCnt++] = ref;
1241        }
1242      }
1243      if (stricmp (name, "node") == 0 && bbox[0] <= nd.lat &&
1244          bbox[1] <= nd.lon && nd.lat <= bbox[2] && nd.lon <= bbox[3]) {
1245        fwrite (&nd, sizeof (nd), 1, groupf[NGROUP (nd.id)]);
1246      }
1247    }
1248    if (xmlTextReaderNodeType (xml) == XML_READER_TYPE_END_ELEMENT) {
1249      int nameIsNode = stricmp (name, "node") == 0;
1250      int nameIsRelation = stricmp (name, "relation") == 0;
1251      if (nameIsRelation) wayMember.clear ();
1252      if (stricmp (name, "way") == 0 || nameIsNode || nameIsRelation) {
1253        w.bits += wStyle;
1254        if (!nameIsRelation && !nameIsNode) {
1255          wayId.push_back (nd.id);
1256          wayId.push_back (ftell (pak));
1257        }
1258        if (nameIsRelation) {
1259          xmlFree (nameTag);
1260          char str[21];
1261          sprintf (str, "%d %d", member[0], member[1]);
1262          nameTag = (char *) xmlStrdup (BAD_CAST str);
1263        }
1264        if (nameTag) {
1265          char *oldTags = tags;
1266          tags = (char *) xmlStrdup (BAD_CAST "\n");
1267          tags = (char *) xmlStrcat (BAD_CAST tags, BAD_CAST nameTag);
1268          tags = (char *) xmlStrcat (BAD_CAST tags, BAD_CAST oldTags);
1269          xmlFree (oldTags);
1270          xmlFree (nameTag);
1271          nameTag = NULL;
1272        }
1273        if (!nameIsNode || strlen (tags) > 8 || wStyle != styleCnt) {
1274          if (nameIsNode && (!wayFseek || *wayFseek)) {
1275            if (s[0].lat) { // Flush s
1276              fwrite (s, sizeof (s), 1, groupf[S1GROUP (s[0].lat)]);
1277            }
1278            s[0].lat = nd.id; // Create 2 fake halfSegs
1279            s[0].wayPtr = ftell (pak);
1280            s[1].wayPtr = TO_HALFSEG;
1281            s[0].other = -2; // No next
1282            s[1].other = -1; // No prev
1283            lowzList[lowzListCnt++] = nd.id;
1284          }
1285          if (s[0].other > -2) { // Not lowz
1286            if (s[0].other >= 0) nOther--; // Reclaim unused 'other' number
1287            s[0].other = -2;
1288          }
1289         
1290          if (srec[StyleNr (&w)].scaleMax > 10000000 &&
1291              (!wayFseek || *wayFseek)) {
1292            for (int i = 0; i < lowzListCnt; i++) {
1293              if (i % 10 && i < lowzListCnt - 1) continue; // Skip some
1294              if (s[0].lat) { // Flush s
1295                fwrite (s, sizeof (s), 1, groupf[S1GROUP (s[0].lat)]);
1296              }
1297              s[0].lat = lowzList[i];
1298              s[0].wayPtr = ftell (pak);
1299              s[1].wayPtr = TO_HALFSEG;
1300              s[1].other = i == 0 ? -4 : lowzOther++;
1301              s[0].other = i == lowzListCnt -1 ? -4 : lowzOther++;
1302            }
1303          }
1304          lowzListCnt = 0;
1305         
1306          if (StyleNr (&w) < styleCnt && stricmp (map[StyleNr (&w)].style_v,
1307                                                  "city") == 0 && tags[0] == '\n') {
1308            int nlen = strcspn (tags + 1, "\n");
1309            char *n = (char *) xmlMalloc (strlen (tags) + 1 + nlen + 5 + 1);
1310            strcpy (n, tags);
1311            memcpy (n + strlen (tags), tags, 1 + nlen);
1312            strcpy (n + strlen (tags) + 1 + nlen, " City");
1313            //fprintf (stderr, "Mark : %s\n", n + strlen (tags) + 1);
1314            xmlFree (tags);
1315            tags = n; 
1316          }
1317          w.bits |= ~noMask & (yesMask | (map[StyleNr (&w)].defaultRestrict &
1318                                          ((noMask & (1 << accessR)) ? (1 << onewayR) : ~0)));
1319          if (w.destination & (1 << accessR)) w.destination = ~0;
1320          char *compact = tags[0] == '\n' ? tags + 1 : tags;
1321          if (!wayFseek || *wayFseek) {
1322            fwrite (&w, sizeof (w), 1, pak);
1323            fwrite (tags + strlen (tags), 1, 1, pak); // '\0' at the front
1324            for (char *ptr = tags; *ptr != '\0'; ) {
1325              if (*ptr++ == '\n') {
1326                unsigned idx = ftell (pak) + ptr - 1 - tags, grp;
1327                for (grp = 0; grp < IDXGROUPS - 1 &&
1328                       TagCmp (groupName[grp], ptr) < 0; grp++) {}
1329                fwrite (&idx, sizeof (idx), 1, groupf[grp]);
1330              }
1331            }
1332            fwrite (compact, strlen (compact) + 1, 1, pak);
1333           
1334            // Write variable length tags and align on 4 bytes
1335            if (ftell (pak) & 3) {
1336              fwrite (tags, 4 - (ftell (pak) & 3), 1, pak);
1337            }
1338          }
1339          if (wayFseek) fseek (pak, *++wayFseek, SEEK_SET);
1340          //xmlFree (tags); // Just set tags[0] = '\0'
1341          //tags = (char *) xmlStrdup (BAD_CAST "");
1342        }
1343        tags[0] = '\0'; // Erase nodes with short names
1344        yesMask = noMask = 0;
1345        w.bits = 0;
1346        w.destination = 0;
1347        w.maxspeed = FLT_MAX;
1348        wStyle = styleCnt;
1349      }
1350    } // if it was </...>
1351    xmlFree (name);
1352  } // While reading xml
1353  wayId.clear ();
1354  if (s[0].lat && (!wayFseek || *wayFseek)) {
1355    fwrite (s, sizeof (s), 1, groupf[S1GROUP (s[0].lat)]);
1356  }
1357  assert (nOther * 2 < FIRST_LOWZ_OTHER);
1358  bucketsMin1 = (nOther >> 5) | (nOther >> 4);
1359  bucketsMin1 |= bucketsMin1 >> 2;
1360  bucketsMin1 |= bucketsMin1 >> 4;
1361  bucketsMin1 |= bucketsMin1 >> 8;
1362  bucketsMin1 |= bucketsMin1 >> 16;
1363  assert (bucketsMin1 < MAX_BUCKETS);
1364 
1365  for (int i = 0; i < IDXGROUPS; i++) fclose (groupf[i]);
1366  for (int i = S2GROUP (0); i < PAIRGROUP2 (0) + PAIRGROUPS2; i++) {
1367    assert (groupf[i] = fopen64 (groupName[i], "w+"));
1368  } // Avoid exceeding ulimit
1369 
1370  nodeType *nodes = (nodeType *) malloc (sizeof (*nodes) * MAX_NODES);
1371  if (!nodes) {
1372    fprintf (stderr, "Out of memory. Reduce MAX_NODES and increase GRPs\n");
1373    return 3;
1374  }
1375  for (int i = NGROUP (0); i < NGROUP (0) + NGROUPS; i++) {
1376    rewind (groupf[i]);
1377    memset (nodes, -1, sizeof (*nodes) * MAX_NODES);
1378    REBUILDWATCH (while (fread (&nd, sizeof (nd), 1, groupf[i]) == 1)) {
1379      memcpy (FindNode (nodes, nd.id), &nd, sizeof (nd));
1380    }
1381    fclose (groupf[i]);
1382    unlink (groupName[i]);
1383    rewind (groupf[i + NGROUPS]);
1384    REBUILDWATCH (while (fread (s, sizeof (s), 1, groupf[i + NGROUPS])
1385                         == 1)) {
1386      nodeType *n = FindNode (nodes, s[0].lat);
1387      //if (n->id == -1) printf ("** Undefined node %d\n", s[0].lat);
1388      s[0].lat = s[1].lat = n->id != -1 ? n->lat : INT_MIN;
1389      s[0].lon = s[1].lon = n->id != -1 ? n->lon : INT_MIN;
1390      fwrite (s, sizeof (s), 1,
1391              groupf[-2 <= s[0].other && s[0].other < FIRST_LOWZ_OTHER
1392                     ? S2GROUP (Hash (s[0].lon, s[0].lat)) : PAIRGROUP (0) - 1]);
1393    }
1394    fclose (groupf[i + NGROUPS]);
1395    unlink (groupName[i + NGROUPS]);
1396  }
1397  free (nodes);
1398 
1399  struct {
1400    int nOther1, final;
1401  } offsetpair;
1402  offsetpair.final = 0;
1403 
1404  hashTable = (int *) malloc (sizeof (*hashTable) *
1405                              (bucketsMin1 + (bucketsMin1 >> 7) + 3));
1406  int bucket = -1;
1407  for (int i = S2GROUP (0); i < S2GROUP (0) + S2GROUPS; i++) {
1408    fflush (groupf[i]);
1409    size_t size = ftell (groupf[i]);
1410    rewind (groupf[i]);
1411    REBUILDWATCH (halfSegType *seg = (halfSegType *) mmap (NULL, size,
1412                                                           PROT_READ | PROT_WRITE, MAP_SHARED, fileno (groupf[i]), 0));
1413    qsort (seg, size / sizeof (s), sizeof (s),
1414           (int (*)(const void *, const void *))HalfSegCmp);
1415    for (int j = 0; j < int (size / sizeof (seg[0])); j++) {
1416      if (!(j & 1)) {
1417        while (bucket < Hash (seg[j].lon, seg[j].lat,
1418                              i >= S2GROUP (0) + S2GROUPS - 1)) {
1419          hashTable[++bucket] = offsetpair.final / 2;
1420        }
1421      }
1422      offsetpair.nOther1 = seg[j].other;
1423      if (seg[j].other >= 0) fwrite (&offsetpair, sizeof (offsetpair), 1,
1424                                     groupf[PAIRGROUP (offsetpair.nOther1)]);
1425      offsetpair.final++;
1426    }
1427    munmap (seg, size);
1428  }
1429  while (bucket < bucketsMin1 + (bucketsMin1 >> 7) + 2) {
1430    hashTable[++bucket] = offsetpair.final / 2;
1431  }
1432 
1433  ndStart = ftell (pak);
1434 
1435  int *pairing = (int *) malloc (sizeof (*pairing) * PAIRS);
1436  for (int i = PAIRGROUP (0); i < PAIRGROUP (0) + PAIRGROUPS; i++) {
1437    REBUILDWATCH (rewind (groupf[i]));
1438    while (fread (&offsetpair, sizeof (offsetpair), 1, groupf[i]) == 1) {
1439      pairing[offsetpair.nOther1 % PAIRS] = offsetpair.final;
1440    }
1441    int pairs = ftell (groupf[i]) / sizeof (offsetpair);
1442    for (int j = 0; j < pairs; j++) {
1443      offsetpair.final = pairing[j ^ 1];
1444      offsetpair.nOther1 = pairing[j];
1445      fwrite (&offsetpair, sizeof (offsetpair), 1,
1446              groupf[PAIRGROUP2 (offsetpair.nOther1)]);
1447    }
1448    fclose (groupf[i]);
1449    unlink (groupName[i]);
1450  }
1451  free (pairing);
1452 
1453  int s2grp = S2GROUP (0), pairs;
1454  halfSegType *seg = (halfSegType *) malloc (PAIRS * sizeof (*seg));
1455  assert (seg /* Out of memory. Reduce PAIRS for small scale rebuilds. */);
1456  ndType ndWrite;
1457  for (int i = PAIRGROUP2 (0); i < PAIRGROUP2 (0) + PAIRGROUPS2; i++) {
1458    REBUILDWATCH (for (pairs = 0; pairs < PAIRS &&
1459                         s2grp < S2GROUP (0) + S2GROUPS; )) {
1460      if (fread (&seg[pairs], sizeof (seg[0]), 2, groupf [s2grp]) == 2) {
1461        pairs += 2;
1462      }
1463      else {
1464        fclose (groupf[s2grp]);
1465        unlink (groupName[s2grp]);
1466        s2grp++;
1467      }
1468    }
1469    rewind (groupf[i]);
1470    while (fread (&offsetpair, sizeof (offsetpair), 1, groupf[i]) == 1) {
1471      seg[offsetpair.nOther1 % PAIRS].other = offsetpair.final;
1472    }
1473    for (int j = 0; j < pairs; j += 2) {
1474      ndWrite.wayPtr = seg[j].wayPtr;
1475      ndWrite.lat = seg[j].lat;
1476      ndWrite.lon = seg[j].lon;
1477      ndWrite.other[0] = seg[j].other >> 1; // Right shift handles -1 the
1478      ndWrite.other[1] = seg[j + 1].other >> 1; // way we want.
1479      fwrite (&ndWrite, sizeof (ndWrite), 1, pak);
1480    }
1481    fclose (groupf[i]);
1482    unlink (groupName[i]);
1483  }
1484  free (seg);
1485 
1486  fflush (pak);
1487  data = (char *) mmap (NULL, ndStart,
1488                        PROT_READ | PROT_WRITE, MAP_SHARED, fileno (pak), 0);
1489  fseek (pak, ndStart, SEEK_SET);
1490  REBUILDWATCH (for (unsigned i = 0; i < cycleNet.size (); i++)) {
1491    wayType *way = (wayType*) (data + cycleNet[i]);
1492    for (int j = StyleNr (way) + 1; j < styleCnt; j++) {
1493      if (strncasecmp (map[j].style_k, "cyclenet", 8) == 0 &&
1494          stricmp (map[j].style_k + 8, map[StyleNr (way)].style_k) == 0 &&
1495          stricmp (map[j].style_v, map[StyleNr (way)].style_v) == 0) {
1496        way->bits = (way->bits & ~((2 << STYLE_BITS) - 1)) | j;
1497      }
1498    }
1499  }
1500  REBUILDWATCH (while (fread (&ndWrite, sizeof (ndWrite), 1, pak) == 1)) {
1501    //if (bucket > Hash (ndWrite.lon, ndWrite.lat)) printf ("unsorted !\n");
1502    wayType *way = (wayType*) (data + ndWrite.wayPtr);
1503   
1504    /* The difficult way of calculating bounding boxes,
1505       namely to adjust the centerpoint (it does save us a pass) : */
1506    // Block lost nodes with if (ndWrite.lat == INT_MIN) continue;
1507    if (way->clat + way->dlat < ndWrite.lat) {
1508      way->dlat = way->dlat < 0 ? 0 : // Bootstrap
1509        (way->dlat - way->clat + ndWrite.lat) / 2;
1510      way->clat = ndWrite.lat - way->dlat;
1511    }
1512    if (way->clat - way->dlat > ndWrite.lat) {
1513      way->dlat = (way->dlat + way->clat - ndWrite.lat) / 2;
1514      way->clat = ndWrite.lat + way->dlat;
1515    }
1516    if (way->clon + way->dlon < ndWrite.lon) {
1517      way->dlon = way->dlon < 0 ? 0 : // Bootstrap
1518        (way->dlon - way->clon + ndWrite.lon) / 2;
1519      way->clon = ndWrite.lon - way->dlon;
1520    }
1521    if (way->clon - way->dlon > ndWrite.lon) {
1522      way->dlon = (way->dlon + way->clon - ndWrite.lon) / 2;
1523      way->clon = ndWrite.lon + way->dlon;
1524    }
1525  }
1526#ifndef LAMBERTUS
1527  REBUILDWATCH (for (int i = 0; i < IDXGROUPS; i++)) {
1528    assert (groupf[i] = fopen64 (groupName[i], "r+"));
1529    fseek (groupf[i], 0, SEEK_END);
1530    int fsize = ftell (groupf[i]);
1531    fflush (groupf[i]);
1532    unsigned *idx = (unsigned *) mmap (NULL, fsize,
1533                                       PROT_READ | PROT_WRITE, MAP_SHARED, fileno (groupf[i]), 0);
1534    qsort (idx, fsize / sizeof (*idx), sizeof (*idx), IdxCmp);
1535    fwrite (idx, fsize, 1, pak);
1536#if 0
1537    for (int j = 0; j < fsize / (int) sizeof (*idx); j++) {
1538      printf ("%.*s\n", strcspn (data + idx[j], "\n"), data + idx[j]);
1539    }
1540#endif
1541    munmap (idx, fsize);
1542    fclose (groupf[i]);
1543    unlink (groupName[i]);
1544  }
1545#endif // LAMBERTUS
1546  //    printf ("ndCount=%d\n", ndCount);
1547  munmap (data, ndStart);
1548  fwrite (hashTable, sizeof (*hashTable),
1549          bucketsMin1 + (bucketsMin1 >> 7) + 3, pak);
1550  fwrite (&bucketsMin1, sizeof (bucketsMin1), 1, pak);
1551  fwrite (&ndStart, sizeof (ndStart), 1, pak); /* for ndBase */
1552
1553  fclose (pak);
1554  free (hashTable);
1555
1556  return 0;
1557}
1558
1559#endif
Note: See TracBrowser for help on using the repository browser.