src/Navaids/NavDataCache.cxx

   1 // NavDataCache.cxx - defines a unified binary cache for navigation
   2 // data, parsed from various text / XML sources.
   3
   4 // Written by James Turner, started 2012.
   5 //
   6 // Copyright (C) 2012  James Turner
   7 //
   8 // This program is free software; you can redistribute it and/or
   9 // modify it under the terms of the GNU General Public License as
  10 // published by the Free Software Foundation; either version 2 of the
  11 // License, or (at your option) any later version.
  12 //
  13 // This program is distributed in the hope that it will be useful, but
  14 // WITHOUT ANY WARRANTY; without even the implied warranty of
  15 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  16 // General Public License for more details.
  17 //
  18 // You should have received a copy of the GNU General Public License
  19 // along with this program; if not, write to the Free Software
  20 // Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
  21
  22 #ifdef HAVE_CONFIG_H
  23 # include "config.h"
  24 #endif
  25
  26 // to ensure compatability between sqlite3_int64 and PositionedID,
  27 // force the type used by sqlite to match PositionedID explicitly
  28 #define SQLITE_INT64_TYPE int64_t
  29 #define SQLITE_UINT64_TYPE uint64_t
  30
  31 #include "NavDataCache.hxx"
  32
  33 // std
  34 #include <map>
  35 #include <cassert>
  36 #include <stdint.h> // for int64_t
  37 // boost
  38 #include <boost/foreach.hpp>
  39
  40 #include "sqlite3.h"
  41
  42 // SimGear
  43 #include <simgear/structure/exception.hxx>
  44 #include <simgear/debug/logstream.hxx>
  45 #include <simgear/bucket/newbucket.hxx>
  46 #include <simgear/misc/sg_path.hxx>
  47 #include <simgear/misc/strutils.hxx>
  48 #include <simgear/threads/SGThread.hxx>
  49 #include <simgear/threads/SGGuard.hxx>
  50
  51 #include <Main/globals.hxx>
  52 #include "markerbeacon.hxx"
  53 #include "navrecord.hxx"
  54 #include <Airports/airport.hxx>
  55 #include <Airports/runways.hxx>
  56 #include <ATC/CommStation.hxx>
  57 #include "fix.hxx"
  58 #include <Navaids/fixlist.hxx>
  59 #include <Navaids/navdb.hxx>
  60 #include "PositionedOctree.hxx"
  61 #include <Airports/apt_loader.hxx>
  62 #include <Navaids/airways.hxx>
  63 #include <Airports/parking.hxx>
  64 #include <Airports/gnnode.hxx>
  65
  66 using std::string;
  67
  68 #define SG_NAVCACHE SG_NAVAID
  69 //#define LAZY_OCTREE_UPDATES 1
  70
  71 namespace {
  72
  73 const int MAX_RETRIES = 10;
  74 const int SCHEMA_VERSION = 7;
  75 const int CACHE_SIZE_KBYTES= 16000;
  76
  77 // bind a std::string to a sqlite statement. The std::string must live the
  78 // entire duration of the statement execution - do not pass a temporary
  79 // std::string, or the compiler may delete it, freeing the C-string storage,
  80 // and causing subtle memory corruption bugs!
  81 void sqlite_bind_stdstring(sqlite3_stmt* stmt, int value, const std::string& s)
  82 {
  83   sqlite3_bind_text(stmt, value, s.c_str(), s.length(), SQLITE_STATIC);
  84 }
  85
  86 // variant of the above, which does not care about the lifetime of the
  87 // passed std::string
  88 void sqlite_bind_temp_stdstring(sqlite3_stmt* stmt, int value, const std::string& s)
  89 {
  90   sqlite3_bind_text(stmt, value, s.c_str(), s.length(), SQLITE_TRANSIENT);
  91 }
  92
  93 typedef sqlite3_stmt* sqlite3_stmt_ptr;
  94
  95 void f_distanceCartSqrFunction(sqlite3_context* ctx, int argc, sqlite3_value* argv[])
  96 {
  97   if (argc != 6) {
  98     return;
  99   }
 100
 101   SGVec3d posA(sqlite3_value_double(argv[0]),
 102                sqlite3_value_double(argv[1]),
 103                sqlite3_value_double(argv[2]));
 104
 105   SGVec3d posB(sqlite3_value_double(argv[3]),
 106                sqlite3_value_double(argv[4]),
 107                sqlite3_value_double(argv[5]));
 108   sqlite3_result_double(ctx, distSqr(posA, posB));
 109 }
 110
 111
 112 static string cleanRunwayNo(const string& aRwyNo)
 113 {
 114   if (aRwyNo[0] == 'x') {
 115     return string(); // no ident for taxiways
 116   }
 117
 118   string result(aRwyNo);
 119   // canonicalise runway ident
 120   if ((aRwyNo.size() == 1) || !isdigit(aRwyNo[1])) {
 121     result = "0" + aRwyNo;
 122   }
 123
 124   // trim off trailing garbage
 125   if (result.size() > 2) {
 126     char suffix = toupper(result[2]);
 127     if (suffix == 'X') {
 128       result = result.substr(0, 2);
 129     }
 130   }
 131
 132   return result;
 133 }
 134
 135 } // anonymous namespace
 136
 137 namespace flightgear
 138 {
 139
 140 /**
 141  * Thread encapsulating a cache rebuild. This is not used to parallelise
 142  * the rebuild - we must still wait until completion before doing other
 143  * startup, since many things rely on a complete cache. The thread is used
 144  * so we don't block the main event loop for an unacceptable duration,
 145  * which causes 'not responding' / spinning beachballs on Windows & Mac
 146  */
 147 class RebuildThread : public SGThread
 148 {
 149 public:
 150   RebuildThread(NavDataCache* cache) :
 151   _cache(cache),
 152   _isFinished(false)
 153   {
 154
 155   }
 156
 157   bool isFinished() const
 158   {
 159     SGGuard<SGMutex> g(_lock);
 160     return _isFinished;
 161   }
 162
 163   virtual void run()
 164   {
 165     SGTimeStamp st;
 166     st.stamp();
 167     _cache->doRebuild();
 168     SG_LOG(SG_NAVCACHE, SG_INFO, "cache rebuild took:" << st.elapsedMSec() << "msec");
 169
 170     SGGuard<SGMutex> g(_lock);
 171     _isFinished = true;
 172   }
 173 private:
 174   NavDataCache* _cache;
 175   mutable SGMutex _lock;
 176   bool _isFinished;
 177 };
 178
 179 ////////////////////////////////////////////////////////////////////////////
 180
 181 typedef std::map<PositionedID, FGPositionedRef> PositionedCache;
 182
 183 class AirportTower : public FGPositioned
 184 {
 185 public:
 186   AirportTower(PositionedID& guid, PositionedID airport,
 187                const string& ident, const SGGeod& pos) :
 188     FGPositioned(guid, FGPositioned::TOWER, ident, pos)
 189   {
 190   }
 191 };
 192
 193 class NavDataCache::NavDataCachePrivate
 194 {
 195 public:
 196   NavDataCachePrivate(const SGPath& p, NavDataCache* o) :
 197     outer(o),
 198     db(NULL),
 199     path(p),
 200     cacheHits(0),
 201     cacheMisses(0),
 202     transactionLevel(0),
 203     transactionAborted(false)
 204   {
 205   }
 206
 207   ~NavDataCachePrivate()
 208   {
 209     close();
 210   }
 211
 212   void init()
 213   {
 214     SG_LOG(SG_NAVCACHE, SG_INFO, "NavCache at:" << path);
 215     sqlite3_open_v2(path.c_str(), &db,
 216                     SQLITE_OPEN_READWRITE | SQLITE_OPEN_CREATE, NULL);
 217
 218
 219     sqlite3_stmt_ptr checkTables =
 220       prepare("SELECT count(*) FROM sqlite_master WHERE name='properties'");
 221
 222     sqlite3_create_function(db, "distanceCartSqr", 6, SQLITE_ANY, NULL,
 223                             f_distanceCartSqrFunction, NULL, NULL);
 224
 225     execSelect(checkTables);
 226     bool didCreate = false;
 227     if (sqlite3_column_int(checkTables, 0) == 0) {
 228       SG_LOG(SG_NAVCACHE, SG_INFO, "will create tables");
 229       initTables();
 230       didCreate = true;
 231     }
 232
 233     readPropertyQuery = prepare("SELECT value FROM properties WHERE key=?");
 234     writePropertyQuery = prepare("INSERT INTO properties (key, value) VALUES (?,?)");
 235     clearProperty = prepare("DELETE FROM properties WHERE key=?1");
 236
 237     if (didCreate) {
 238       writeIntProperty("schema-version", SCHEMA_VERSION);
 239     } else {
 240       int schemaVersion = outer->readIntProperty("schema-version");
 241       if (schemaVersion != SCHEMA_VERSION) {
 242         SG_LOG(SG_NAVCACHE, SG_INFO, "Navcache schema mismatch, will rebuild");
 243         throw sg_exception("Navcache schema has changed");
 244       }
 245     }
 246
 247     // see http://www.sqlite.org/pragma.html#pragma_cache_size
 248     // for the details, small cache would cause thrashing.
 249     std::ostringstream q;
 250     q << "PRAGMA cache_size=-" << CACHE_SIZE_KBYTES << ";";
 251     runSQL(q.str());
 252     prepareQueries();
 253   }
 254
 255   void close()
 256   {
 257     BOOST_FOREACH(sqlite3_stmt_ptr stmt, prepared) {
 258       sqlite3_finalize(stmt);
 259     }
 260     prepared.clear();
 261     sqlite3_close(db);
 262   }
 263
 264   void checkCacheFile()
 265   {
 266     SG_LOG(SG_NAVCACHE, SG_INFO, "running DB integrity check");
 267     SGTimeStamp st;
 268     st.stamp();
 269
 270     sqlite3_stmt_ptr stmt = prepare("PRAGMA quick_check(1)");
 271     if (!execSelect(stmt)) {
 272       throw sg_exception("DB integrity check failed to run");
 273     }
 274
 275     string v = (char*) sqlite3_column_text(stmt, 0);
 276     if (v != "ok") {
 277       throw sg_exception("DB integrity check returned:" + v);
 278     }
 279
 280     SG_LOG(SG_NAVCACHE, SG_INFO, "NavDataCache integrity check took:" << st.elapsedMSec());
 281     finalize(stmt);
 282   }
 283
 284   void callSqlite(int result, const string& sql)
 285   {
 286     if (result == SQLITE_OK)
 287       return; // all good
 288
 289     string errMsg;
 290     if (result == SQLITE_MISUSE) {
 291       errMsg = "Sqlite API abuse";
 292       SG_LOG(SG_NAVCACHE, SG_ALERT, "Sqlite API abuse");
 293     } else {
 294       errMsg = sqlite3_errmsg(db);
 295       SG_LOG(SG_NAVCACHE, SG_ALERT, "Sqlite error:" << errMsg << " running:\n\t" << sql);
 296     }
 297
 298     throw sg_exception("Sqlite error:" + errMsg, sql);
 299   }
 300
 301   void runSQL(const string& sql)
 302   {
 303     sqlite3_stmt_ptr stmt;
 304     callSqlite(sqlite3_prepare_v2(db, sql.c_str(), sql.length(), &stmt, NULL), sql);
 305
 306     try {
 307       execSelect(stmt);
 308     } catch (sg_exception&) {
 309       sqlite3_finalize(stmt);
 310       throw; // re-throw
 311     }
 312
 313     sqlite3_finalize(stmt);
 314   }
 315
 316   sqlite3_stmt_ptr prepare(const string& sql)
 317   {
 318     sqlite3_stmt_ptr stmt;
 319     callSqlite(sqlite3_prepare_v2(db, sql.c_str(), sql.length(), &stmt, NULL), sql);
 320     prepared.push_back(stmt);
 321     return stmt;
 322   }
 323
 324   void finalize(sqlite3_stmt_ptr s)
 325   {
 326     StmtVec::iterator it = std::find(prepared.begin(), prepared.end(), s);
 327     if (it == prepared.end()) {
 328       throw sg_exception("Finalising statement that was not prepared");
 329     }
 330
 331     prepared.erase(it);
 332     sqlite3_finalize(s);
 333   }
 334
 335   void reset(sqlite3_stmt_ptr stmt)
 336   {
 337     assert(stmt);
 338     if (sqlite3_reset(stmt) != SQLITE_OK) {
 339       string errMsg = sqlite3_errmsg(db);
 340       SG_LOG(SG_NAVCACHE, SG_ALERT, "Sqlite error resetting:" << errMsg);
 341       throw sg_exception("Sqlite error resetting:" + errMsg, sqlite3_sql(stmt));
 342     }
 343   }
 344
 345   bool execSelect(sqlite3_stmt_ptr stmt)
 346   {
 347     return stepSelect(stmt);
 348   }
 349
 350   bool stepSelect(sqlite3_stmt_ptr stmt)
 351   {
 352     int retries = 0;
 353     int result;
 354     while (retries < MAX_RETRIES) {
 355       result = sqlite3_step(stmt);
 356       if (result == SQLITE_ROW) {
 357         return true; // at least one result row
 358       }
 359
 360       if (result == SQLITE_DONE) {
 361         return false; // no result rows
 362       }
 363
 364       if (result != SQLITE_BUSY) {
 365         break;
 366       }
 367
 368       SG_LOG(SG_NAVCACHE, SG_ALERT, "NavCache contention on select, will retry:" << retries);
 369       SGTimeStamp::sleepForMSec(++retries * 10);
 370     } // of retry loop for DB locked
 371
 372     if (retries >= MAX_RETRIES) {
 373       SG_LOG(SG_NAVCACHE, SG_ALERT, "exceeded maximum number of SQLITE_BUSY retries");
 374       return false;
 375     }
 376
 377     string errMsg;
 378     if (result == SQLITE_MISUSE) {
 379       errMsg = "Sqlite API abuse";
 380       SG_LOG(SG_NAVCACHE, SG_ALERT, "Sqlite API abuse");
 381     } else {
 382       errMsg = sqlite3_errmsg(db);
 383       SG_LOG(SG_NAVCACHE, SG_ALERT, "Sqlite error:" << errMsg << " (" << result
 384              << ") while running:\n\t" << sqlite3_sql(stmt));
 385     }
 386
 387     throw sg_exception("Sqlite error:" + errMsg, sqlite3_sql(stmt));
 388   }
 389
 390   void execSelect1(sqlite3_stmt_ptr stmt)
 391   {
 392     if (!execSelect(stmt)) {
 393       SG_LOG(SG_NAVCACHE, SG_WARN, "empty SELECT running:\n\t" << sqlite3_sql(stmt));
 394       throw sg_exception("no results returned for select", sqlite3_sql(stmt));
 395     }
 396   }
 397
 398   sqlite3_int64 execInsert(sqlite3_stmt_ptr stmt)
 399   {
 400     execSelect(stmt);
 401     sqlite3_int64 rowid = sqlite3_last_insert_rowid(db);
 402     reset(stmt);
 403     return rowid;
 404   }
 405
 406   void execUpdate(sqlite3_stmt_ptr stmt)
 407   {
 408     execSelect(stmt);
 409     reset(stmt);
 410   }
 411
 412   void initTables()
 413   {
 414     runSQL("CREATE TABLE properties ("
 415            "key VARCHAR,"
 416            "value VARCHAR"
 417            ")");
 418
 419     runSQL("CREATE TABLE stat_cache ("
 420            "path VARCHAR unique,"
 421            "stamp INT"
 422            ")");
 423
 424     runSQL("CREATE TABLE positioned ("
 425            "type INT,"
 426            "ident VARCHAR collate nocase,"
 427            "name VARCHAR collate nocase,"
 428            "airport INT64,"
 429            "lon FLOAT,"
 430            "lat FLOAT,"
 431            "elev_m FLOAT,"
 432            "octree_node INT,"
 433            "cart_x FLOAT,"
 434            "cart_y FLOAT,"
 435            "cart_z FLOAT"
 436            ")");
 437
 438     runSQL("CREATE INDEX pos_octree ON positioned(octree_node)");
 439     runSQL("CREATE INDEX pos_ident ON positioned(ident collate nocase)");
 440     runSQL("CREATE INDEX pos_name ON positioned(name collate nocase)");
 441     // allow efficient querying of 'all ATIS at this airport' or
 442     // 'all towers at this airport'
 443     runSQL("CREATE INDEX pos_apt_type ON positioned(airport, type)");
 444
 445     runSQL("CREATE TABLE airport ("
 446            "has_metar BOOL"
 447            ")"
 448            );
 449
 450     runSQL("CREATE TABLE comm ("
 451            "freq_khz INT,"
 452            "range_nm INT"
 453            ")"
 454            );
 455
 456     runSQL("CREATE INDEX comm_freq ON comm(freq_khz)");
 457
 458     runSQL("CREATE TABLE runway ("
 459            "heading FLOAT,"
 460            "length_ft FLOAT,"
 461            "width_m FLOAT,"
 462            "surface INT,"
 463            "displaced_threshold FLOAT,"
 464            "stopway FLOAT,"
 465            "reciprocal INT64,"
 466            "ils INT64"
 467            ")"
 468            );
 469
 470     runSQL("CREATE TABLE navaid ("
 471            "freq INT,"
 472            "range_nm INT,"
 473            "multiuse FLOAT,"
 474            "runway INT64,"
 475            "colocated INT64"
 476            ")"
 477            );
 478
 479     runSQL("CREATE INDEX navaid_freq ON navaid(freq)");
 480
 481     runSQL("CREATE TABLE octree (children INT)");
 482
 483     runSQL("CREATE TABLE airway ("
 484            "ident VARCHAR collate nocase,"
 485            "network INT" // high-level or low-level
 486            ")");
 487
 488     runSQL("CREATE INDEX airway_ident ON airway(ident)");
 489
 490     runSQL("CREATE TABLE airway_edge ("
 491            "network INT,"
 492            "airway INT64,"
 493            "a INT64,"
 494            "b INT64"
 495            ")");
 496
 497     runSQL("CREATE INDEX airway_edge_from ON airway_edge(a)");
 498
 499     runSQL("CREATE TABLE taxi_node ("
 500            "hold_type INT,"
 501            "on_runway BOOL,"
 502            "pushback BOOL"
 503            ")");
 504
 505     runSQL("CREATE TABLE parking ("
 506            "heading FLOAT,"
 507            "radius INT,"
 508            "gate_type VARCHAR,"
 509            "airlines VARCHAR,"
 510            "pushback INT64"
 511            ")");
 512
 513     runSQL("CREATE TABLE groundnet_edge ("
 514            "airport INT64,"
 515            "a INT64,"
 516            "b INT64"
 517            ")");
 518
 519     runSQL("CREATE INDEX groundnet_edge_airport ON groundnet_edge(airport)");
 520     runSQL("CREATE INDEX groundnet_edge_from ON groundnet_edge(a)");
 521   }
 522
 523   void prepareQueries()
 524   {
 525     writePropertyMulti = prepare("INSERT INTO properties (key, value) VALUES(?1,?2)");
 526
 527     beginTransactionStmt = prepare("BEGIN");
 528     commitTransactionStmt = prepare("COMMIT");
 529     rollbackTransactionStmt = prepare("ROLLBACK");
 530
 531
 532 #define POSITIONED_COLS "rowid, type, ident, name, airport, lon, lat, elev_m, octree_node"
 533 #define AND_TYPED "AND type>=?2 AND type <=?3"
 534     statCacheCheck = prepare("SELECT stamp FROM stat_cache WHERE path=?");
 535     stampFileCache = prepare("INSERT OR REPLACE INTO stat_cache "
 536                              "(path, stamp) VALUES (?,?)");
 537
 538     loadPositioned = prepare("SELECT " POSITIONED_COLS " FROM positioned WHERE rowid=?");
 539     loadAirportStmt = prepare("SELECT has_metar FROM airport WHERE rowid=?");
 540     loadNavaid = prepare("SELECT range_nm, freq, multiuse, runway, colocated FROM navaid WHERE rowid=?");
 541     loadCommStation = prepare("SELECT freq_khz, range_nm FROM comm WHERE rowid=?");
 542     loadRunwayStmt = prepare("SELECT heading, length_ft, width_m, surface, displaced_threshold,"
 543                              "stopway, reciprocal, ils FROM runway WHERE rowid=?1");
 544
 545     getAirportItems = prepare("SELECT rowid FROM positioned WHERE airport=?1 " AND_TYPED);
 546
 547
 548     setAirportMetar = prepare("UPDATE airport SET has_metar=?2 WHERE rowid="
 549                               "(SELECT rowid FROM positioned WHERE ident=?1 AND type>=?3 AND type <=?4)");
 550     sqlite3_bind_int(setAirportMetar, 3, FGPositioned::AIRPORT);
 551     sqlite3_bind_int(setAirportMetar, 4, FGPositioned::SEAPORT);
 552
 553     setRunwayReciprocal = prepare("UPDATE runway SET reciprocal=?2 WHERE rowid=?1");
 554     setRunwayILS = prepare("UPDATE runway SET ils=?2 WHERE rowid=?1");
 555     updateRunwayThreshold = prepare("UPDATE runway SET heading=?2, displaced_threshold=?3, stopway=?4 WHERE rowid=?1");
 556
 557     insertPositionedQuery = prepare("INSERT INTO positioned "
 558                                     "(type, ident, name, airport, lon, lat, elev_m, octree_node, "
 559                                     "cart_x, cart_y, cart_z)"
 560                                     " VALUES (?1, ?2, ?3, ?4, ?5, ?6, ?7, ?8, ?9, ?10, ?11)");
 561
 562     setAirportPos = prepare("UPDATE positioned SET lon=?2, lat=?3, elev_m=?4, octree_node=?5, "
 563                             "cart_x=?6, cart_y=?7, cart_z=?8 WHERE rowid=?1");
 564     insertAirport = prepare("INSERT INTO airport (rowid, has_metar) VALUES (?, ?)");
 565     insertNavaid = prepare("INSERT INTO navaid (rowid, freq, range_nm, multiuse, runway, colocated)"
 566                            " VALUES (?1, ?2, ?3, ?4, ?5, ?6)");
 567     updateILS = prepare("UPDATE navaid SET multiuse=?2 WHERE rowid=?1");
 568
 569     insertCommStation = prepare("INSERT INTO comm (rowid, freq_khz, range_nm)"
 570                                 " VALUES (?, ?, ?)");
 571     insertRunway = prepare("INSERT INTO runway "
 572                            "(rowid, heading, length_ft, width_m, surface, displaced_threshold, stopway, reciprocal)"
 573                            " VALUES (?1, ?2, ?3, ?4, ?5, ?6, ?7, ?8)");
 574     runwayLengthFtQuery = prepare("SELECT length_ft FROM runway WHERE rowid=?1");
 575
 576   // query statement
 577     findClosestWithIdent = prepare("SELECT rowid FROM positioned WHERE ident=?1 "
 578                                    AND_TYPED " ORDER BY distanceCartSqr(cart_x, cart_y, cart_z, ?4, ?5, ?6)");
 579
 580     findCommByFreq = prepare("SELECT positioned.rowid FROM positioned, comm WHERE "
 581                              "positioned.rowid=comm.rowid AND freq_khz=?1 "
 582                              AND_TYPED " ORDER BY distanceCartSqr(cart_x, cart_y, cart_z, ?4, ?5, ?6)");
 583
 584     findNavsByFreq = prepare("SELECT positioned.rowid FROM positioned, navaid WHERE "
 585                              "positioned.rowid=navaid.rowid "
 586                              "AND navaid.freq=?1 " AND_TYPED
 587                              " ORDER BY distanceCartSqr(cart_x, cart_y, cart_z, ?4, ?5, ?6)");
 588
 589     findNavsByFreqNoPos = prepare("SELECT positioned.rowid FROM positioned, navaid WHERE "
 590                                   "positioned.rowid=navaid.rowid AND freq=?1 " AND_TYPED);
 591
 592     findNavaidForRunway = prepare("SELECT positioned.rowid FROM positioned, navaid WHERE "
 593                                   "positioned.rowid=navaid.rowid AND runway=?1 AND type=?2");
 594
 595   // for an octree branch, return the child octree nodes which exist,
 596   // described as a bit-mask
 597     getOctreeChildren = prepare("SELECT children FROM octree WHERE rowid=?1");
 598
 599 #ifdef LAZY_OCTREE_UPDATES
 600     updateOctreeChildren = prepare("UPDATE octree SET children=?2 WHERE rowid=?1");
 601 #else
 602   // mask the new child value into the existing one
 603     updateOctreeChildren = prepare("UPDATE octree SET children=(?2 | children) WHERE rowid=?1");
 604 #endif
 605
 606   // define a new octree node (with no children)
 607     insertOctree = prepare("INSERT INTO octree (rowid, children) VALUES (?1, 0)");
 608
 609     getOctreeLeafChildren = prepare("SELECT rowid, type FROM positioned WHERE octree_node=?1");
 610
 611     searchAirports = prepare("SELECT ident, name FROM positioned WHERE (name LIKE ?1 OR ident LIKE ?1) " AND_TYPED);
 612     sqlite3_bind_int(searchAirports, 2, FGPositioned::AIRPORT);
 613     sqlite3_bind_int(searchAirports, 3, FGPositioned::SEAPORT);
 614
 615     getAirportItemByIdent = prepare("SELECT rowid FROM positioned WHERE airport=?1 AND ident=?2 AND type=?3");
 616
 617     findAirportRunway = prepare("SELECT airport, rowid FROM positioned WHERE ident=?2 AND type=?3 AND airport="
 618                                 "(SELECT rowid FROM positioned WHERE type=?4 AND ident=?1)");
 619     sqlite3_bind_int(findAirportRunway, 3, FGPositioned::RUNWAY);
 620     sqlite3_bind_int(findAirportRunway, 4, FGPositioned::AIRPORT);
 621
 622     // three-way join to get the navaid ident and runway ident in a single select.
 623     // we're joining positioned to itself by the navaid runway, with the complication
 624     // that we need to join the navaids table to get the runway ID.
 625     // we also need to filter by type to excluse glideslope (GS) matches
 626     findILS = prepare("SELECT nav.rowid FROM positioned AS nav, positioned AS rwy, navaid WHERE "
 627                       "nav.ident=?1 AND nav.airport=?2 AND rwy.ident=?3 "
 628                       "AND rwy.rowid = navaid.runway AND navaid.rowid=nav.rowid "
 629                       "AND (nav.type=?4 OR nav.type=?5)");
 630
 631     sqlite3_bind_int(findILS, 4, FGPositioned::ILS);
 632     sqlite3_bind_int(findILS, 5, FGPositioned::LOC);
 633
 634   // airways
 635     findAirway = prepare("SELECT rowid FROM airway WHERE network=?1 AND ident=?2");
 636     insertAirway = prepare("INSERT INTO airway (ident, network) "
 637                            "VALUES (?1, ?2)");
 638
 639     insertAirwayEdge = prepare("INSERT INTO airway_edge (network, airway, a, b) "
 640                                "VALUES (?1, ?2, ?3, ?4)");
 641
 642     isPosInAirway = prepare("SELECT rowid FROM airway_edge WHERE network=?1 AND a=?2");
 643
 644     airwayEdgesFrom = prepare("SELECT airway, b FROM airway_edge WHERE network=?1 AND a=?2");
 645
 646   // parking / taxi-node graph
 647     insertTaxiNode = prepare("INSERT INTO taxi_node (rowid, hold_type, on_runway, pushback) VALUES(?1, ?2, ?3, 0)");
 648     insertParkingPos = prepare("INSERT INTO parking (rowid, heading, radius, gate_type, airlines) "
 649                                "VALUES (?1, ?2, ?3, ?4, ?5)");
 650     setParkingPushBack = prepare("UPDATE parking SET pushback=?2 WHERE rowid=?1");
 651
 652     loadTaxiNodeStmt = prepare("SELECT hold_type, on_runway FROM taxi_node WHERE rowid=?1");
 653     loadParkingPos = prepare("SELECT heading, radius, gate_type, airlines, pushback FROM parking WHERE rowid=?1");
 654     taxiEdgesFrom = prepare("SELECT b FROM groundnet_edge WHERE a=?1");
 655     pushbackEdgesFrom = prepare("SELECT b FROM groundnet_edge, taxi_node WHERE "
 656                                 "a=?1 AND groundnet_edge.b = taxi_node.rowid AND pushback=1");
 657
 658     insertTaxiEdge = prepare("INSERT INTO groundnet_edge (airport, a,b) VALUES(?1, ?2, ?3)");
 659
 660     markTaxiNodeAsPushback = prepare("UPDATE taxi_node SET pushback=1 WHERE rowid=?1");
 661     airportTaxiNodes = prepare("SELECT rowid FROM positioned WHERE (type=?2 OR type=?3) AND airport=?1");
 662     sqlite3_bind_int(airportTaxiNodes, 2, FGPositioned::PARKING);
 663     sqlite3_bind_int(airportTaxiNodes, 3, FGPositioned::TAXI_NODE);
 664
 665     airportPushbackNodes = prepare("SELECT positioned.rowid FROM positioned, taxi_node WHERE "\
 666                                    "airport=?1 AND positioned.rowid=taxi_node.rowid AND pushback=1 "
 667                                    "AND (type=?2 OR type=?3)");
 668     sqlite3_bind_int(airportPushbackNodes, 2, FGPositioned::PARKING);
 669     sqlite3_bind_int(airportPushbackNodes, 3, FGPositioned::TAXI_NODE);
 670
 671     findNearestTaxiNode = prepare("SELECT positioned.rowid FROM positioned, taxi_node WHERE "
 672                                   "positioned.rowid = taxi_node.rowid AND airport=?1 "
 673                                   "ORDER BY distanceCartSqr(cart_x, cart_y, cart_z, ?2, ?3, ?4) "
 674                                   "LIMIT 1");
 675
 676     findNearestRunwayTaxiNode = prepare("SELECT positioned.rowid FROM positioned, taxi_node WHERE "
 677                                         "positioned.rowid = taxi_node.rowid AND airport=?1 "
 678                                         "AND on_runway=1 "
 679                                         "ORDER BY distanceCartSqr(cart_x, cart_y, cart_z, ?2, ?3, ?4) ");
 680
 681     findAirportParking = prepare("SELECT positioned.rowid FROM positioned, parking WHERE "
 682                                  "airport=?1 AND type=?4 AND "
 683                                  "radius >= ?2 AND gate_type = ?3 AND "
 684                                  "parking.rowid=positioned.rowid");
 685     sqlite3_bind_int(findAirportParking, 4, FGPositioned::PARKING);
 686   }
 687
 688   void writeIntProperty(const string& key, int value)
 689   {
 690     sqlite_bind_stdstring(clearProperty, 1, key);
 691     execUpdate(clearProperty);
 692
 693     sqlite_bind_stdstring(writePropertyQuery, 1, key);
 694     sqlite3_bind_int(writePropertyQuery, 2, value);
 695     execUpdate(writePropertyQuery);
 696   }
 697
 698
 699   FGPositioned* loadById(sqlite_int64 rowId);
 700
 701   FGAirport* loadAirport(sqlite_int64 rowId,
 702                          FGPositioned::Type ty,
 703                          const string& id, const string& name, const SGGeod& pos)
 704   {
 705     sqlite3_bind_int64(loadAirportStmt, 1, rowId);
 706     execSelect1(loadAirportStmt);
 707     bool hasMetar = (sqlite3_column_int(loadAirportStmt, 0) > 0);
 708     reset(loadAirportStmt);
 709
 710     return new FGAirport(rowId, id, pos, name, hasMetar, ty);
 711   }
 712
 713   FGRunwayBase* loadRunway(sqlite3_int64 rowId, FGPositioned::Type ty,
 714                            const string& id, const SGGeod& pos, PositionedID apt)
 715   {
 716     sqlite3_bind_int(loadRunwayStmt, 1, rowId);
 717     execSelect1(loadRunwayStmt);
 718
 719     double heading = sqlite3_column_double(loadRunwayStmt, 0);
 720     double lengthM = sqlite3_column_int(loadRunwayStmt, 1);
 721     double widthM = sqlite3_column_double(loadRunwayStmt, 2);
 722     int surface = sqlite3_column_int(loadRunwayStmt, 3);
 723
 724     if (ty == FGPositioned::TAXIWAY) {
 725       reset(loadRunwayStmt);
 726       return new FGTaxiway(rowId, id, pos, heading, lengthM, widthM, surface);
 727     } else if (ty == FGPositioned::HELIPAD) {
 728         reset(loadRunwayStmt);
 729         return new FGHelipad(rowId, apt, id, pos, heading, lengthM, widthM, surface);
 730     } else {
 731       double displacedThreshold = sqlite3_column_double(loadRunwayStmt, 4);
 732       double stopway = sqlite3_column_double(loadRunwayStmt, 5);
 733       PositionedID reciprocal = sqlite3_column_int64(loadRunwayStmt, 6);
 734       PositionedID ils = sqlite3_column_int64(loadRunwayStmt, 7);
 735       FGRunway* r = new FGRunway(rowId, apt, id, pos, heading, lengthM, widthM,
 736                           displacedThreshold, stopway, surface, false);
 737
 738       if (reciprocal > 0) {
 739         r->setReciprocalRunway(reciprocal);
 740       }
 741
 742       if (ils > 0) {
 743         r->setILS(ils);
 744       }
 745
 746       reset(loadRunwayStmt);
 747       return r;
 748     }
 749   }
 750
 751   CommStation* loadComm(sqlite3_int64 rowId, FGPositioned::Type ty,
 752                         const string& id, const string& name,
 753                         const SGGeod& pos,
 754                         PositionedID airport)
 755   {
 756     sqlite3_bind_int64(loadCommStation, 1, rowId);
 757     execSelect1(loadCommStation);
 758
 759     int range = sqlite3_column_int(loadCommStation, 0);
 760     int freqKhz = sqlite3_column_int(loadCommStation, 1);
 761     reset(loadCommStation);
 762
 763     CommStation* c = new CommStation(rowId, name, ty, pos, freqKhz, range);
 764     c->setAirport(airport);
 765     return c;
 766   }
 767
 768   FGPositioned* loadNav(sqlite3_int64 rowId,
 769                        FGPositioned::Type ty, const string& id,
 770                        const string& name, const SGGeod& pos)
 771   {
 772     sqlite3_bind_int64(loadNavaid, 1, rowId);
 773     execSelect1(loadNavaid);
 774
 775     PositionedID runway = sqlite3_column_int64(loadNavaid, 3);
 776     // marker beacons are light-weight
 777     if ((ty == FGPositioned::OM) || (ty == FGPositioned::IM) ||
 778         (ty == FGPositioned::MM))
 779     {
 780       reset(loadNavaid);
 781       return new FGMarkerBeaconRecord(rowId, ty, runway, pos);
 782     }
 783
 784     int rangeNm = sqlite3_column_int(loadNavaid, 0),
 785       freq = sqlite3_column_int(loadNavaid, 1);
 786     double mulituse = sqlite3_column_double(loadNavaid, 2);
 787     //sqlite3_int64 colocated = sqlite3_column_int64(loadNavaid, 4);
 788     reset(loadNavaid);
 789
 790     return new FGNavRecord(rowId, ty, id, name, pos, freq, rangeNm, mulituse, runway);
 791   }
 792
 793   FGPositioned* loadParking(sqlite3_int64 rowId,
 794                             const string& name, const SGGeod& pos,
 795                             PositionedID airport)
 796   {
 797     sqlite3_bind_int64(loadParkingPos, 1, rowId);
 798     execSelect1(loadParkingPos);
 799
 800     double heading = sqlite3_column_double(loadParkingPos, 0);
 801     int radius = sqlite3_column_int(loadParkingPos, 1);
 802     string aircraftType((char*) sqlite3_column_text(loadParkingPos, 2));
 803     string airlines((char*) sqlite3_column_text(loadParkingPos, 3));
 804     PositionedID pushBack = sqlite3_column_int64(loadParkingPos, 4);
 805     reset(loadParkingPos);
 806
 807     return new FGParking(rowId, pos, heading, radius, name, aircraftType, airlines, pushBack);
 808   }
 809
 810   FGPositioned* loadTaxiNode(sqlite3_int64 rowId, const SGGeod& pos,
 811                              PositionedID airport)
 812   {
 813     sqlite3_bind_int64(loadTaxiNodeStmt, 1, rowId);
 814     execSelect1(loadTaxiNodeStmt);
 815
 816     int hold_type = sqlite3_column_int(loadTaxiNodeStmt, 0);
 817     bool onRunway = sqlite3_column_int(loadTaxiNodeStmt, 1);
 818     reset(loadTaxiNodeStmt);
 819
 820     return new FGTaxiNode(rowId, pos, onRunway, hold_type);
 821   }
 822
 823   PositionedID insertPositioned(FGPositioned::Type ty, const string& ident,
 824                                 const string& name, const SGGeod& pos, PositionedID apt,
 825                                 bool spatialIndex)
 826   {
 827     SGVec3d cartPos(SGVec3d::fromGeod(pos));
 828
 829     sqlite3_bind_int(insertPositionedQuery, 1, ty);
 830     sqlite_bind_stdstring(insertPositionedQuery, 2, ident);
 831     sqlite_bind_stdstring(insertPositionedQuery, 3, name);
 832     sqlite3_bind_int64(insertPositionedQuery, 4, apt);
 833     sqlite3_bind_double(insertPositionedQuery, 5, pos.getLongitudeDeg());
 834     sqlite3_bind_double(insertPositionedQuery, 6, pos.getLatitudeDeg());
 835     sqlite3_bind_double(insertPositionedQuery, 7, pos.getElevationM());
 836
 837     if (spatialIndex) {
 838       Octree::Leaf* octreeLeaf = Octree::global_spatialOctree->findLeafForPos(cartPos);
 839       assert(intersects(octreeLeaf->bbox(), cartPos));
 840       sqlite3_bind_int64(insertPositionedQuery, 8, octreeLeaf->guid());
 841     } else {
 842       sqlite3_bind_null(insertPositionedQuery, 8);
 843     }
 844
 845     sqlite3_bind_double(insertPositionedQuery, 9, cartPos.x());
 846     sqlite3_bind_double(insertPositionedQuery, 10, cartPos.y());
 847     sqlite3_bind_double(insertPositionedQuery, 11, cartPos.z());
 848
 849     PositionedID r = execInsert(insertPositionedQuery);
 850     return r;
 851   }
 852
 853   FGPositioned::List findAllByString(const string& s, const string& column,
 854                                      FGPositioned::Filter* filter, bool exact)
 855   {
 856     string query = s;
 857     if (!exact) query += "%";
 858
 859   // build up SQL query text
 860     string matchTerm = exact ? "=?1" : " LIKE ?1";
 861     string sql = "SELECT rowid FROM positioned WHERE " + column + matchTerm;
 862     if (filter) {
 863       sql += " " AND_TYPED;
 864     }
 865
 866   // find or prepare a suitable statement frrm the SQL
 867     sqlite3_stmt_ptr stmt = findByStringDict[sql];
 868     if (!stmt) {
 869       stmt = prepare(sql);
 870       findByStringDict[sql] = stmt;
 871     }
 872
 873     sqlite_bind_stdstring(stmt, 1, query);
 874     if (filter) {
 875       sqlite3_bind_int(stmt, 2, filter->minType());
 876       sqlite3_bind_int(stmt, 3, filter->maxType());
 877     }
 878
 879     FGPositioned::List result;
 880   // run the prepared SQL
 881     while (stepSelect(stmt))
 882     {
 883       FGPositioned* pos = outer->loadById(sqlite3_column_int64(stmt, 0));
 884       if (filter && !filter->pass(pos)) {
 885         continue;
 886       }
 887
 888       result.push_back(pos);
 889     }
 890
 891     reset(stmt);
 892     return result;
 893   }
 894
 895   PositionedIDVec selectIds(sqlite3_stmt_ptr query)
 896   {
 897     PositionedIDVec result;
 898     while (stepSelect(query)) {
 899       result.push_back(sqlite3_column_int64(query, 0));
 900     }
 901     reset(query);
 902     return result;
 903   }
 904
 905   double runwayLengthFt(PositionedID rwy)
 906   {
 907     sqlite3_bind_int64(runwayLengthFtQuery, 1, rwy);
 908     execSelect1(runwayLengthFtQuery);
 909     double length = sqlite3_column_double(runwayLengthFtQuery, 0);
 910     reset(runwayLengthFtQuery);
 911     return length;
 912   }
 913
 914   void flushDeferredOctreeUpdates()
 915   {
 916     BOOST_FOREACH(Octree::Branch* nd, deferredOctreeUpdates) {
 917       sqlite3_bind_int64(updateOctreeChildren, 1, nd->guid());
 918       sqlite3_bind_int(updateOctreeChildren, 2, nd->childMask());
 919       execUpdate(updateOctreeChildren);
 920     }
 921
 922     deferredOctreeUpdates.clear();
 923   }
 924
 925   NavDataCache* outer;
 926   sqlite3* db;
 927   SGPath path;
 928
 929   /// the actual cache of ID -> instances. This holds an owning reference,
 930   /// so once items are in the cache they will never be deleted until
 931   /// the cache drops its reference
 932   PositionedCache cache;
 933   unsigned int cacheHits, cacheMisses;
 934
 935   /**
 936    * record the levels of open transaction objects we have
 937    */
 938   unsigned int transactionLevel;
 939   bool transactionAborted;
 940   sqlite3_stmt_ptr beginTransactionStmt, commitTransactionStmt, rollbackTransactionStmt;
 941
 942   SGPath aptDatPath, metarDatPath, navDatPath, fixDatPath,
 943   carrierDatPath, airwayDatPath;
 944
 945   sqlite3_stmt_ptr readPropertyQuery, writePropertyQuery,
 946     stampFileCache, statCacheCheck,
 947     loadAirportStmt, loadCommStation, loadPositioned, loadNavaid,
 948     loadRunwayStmt;
 949   sqlite3_stmt_ptr writePropertyMulti, clearProperty;
 950
 951   sqlite3_stmt_ptr insertPositionedQuery, insertAirport, insertTower, insertRunway,
 952   insertCommStation, insertNavaid;
 953   sqlite3_stmt_ptr setAirportMetar, setRunwayReciprocal, setRunwayILS,
 954     setAirportPos, updateRunwayThreshold, updateILS;
 955
 956   sqlite3_stmt_ptr findClosestWithIdent;
 957 // octree (spatial index) related queries
 958   sqlite3_stmt_ptr getOctreeChildren, insertOctree, updateOctreeChildren,
 959     getOctreeLeafChildren;
 960
 961   sqlite3_stmt_ptr searchAirports;
 962   sqlite3_stmt_ptr findCommByFreq, findNavsByFreq,
 963   findNavsByFreqNoPos, findNavaidForRunway;
 964   sqlite3_stmt_ptr getAirportItems, getAirportItemByIdent;
 965   sqlite3_stmt_ptr findAirportRunway,
 966     findILS;
 967
 968   sqlite3_stmt_ptr runwayLengthFtQuery;
 969
 970 // airways
 971   sqlite3_stmt_ptr findAirway, insertAirwayEdge, isPosInAirway, airwayEdgesFrom,
 972   insertAirway;
 973
 974 // groundnet (parking, taxi node graph)
 975   sqlite3_stmt_ptr loadTaxiNodeStmt, loadParkingPos, insertTaxiNode, insertParkingPos;
 976   sqlite3_stmt_ptr taxiEdgesFrom, pushbackEdgesFrom, insertTaxiEdge, markTaxiNodeAsPushback,
 977     airportTaxiNodes, airportPushbackNodes, findNearestTaxiNode, findAirportParking,
 978     setParkingPushBack, findNearestRunwayTaxiNode;
 979
 980 // since there's many permutations of ident/name queries, we create
 981 // them programtically, but cache the exact query by its raw SQL once
 982 // used.
 983   std::map<string, sqlite3_stmt_ptr> findByStringDict;
 984
 985   typedef std::vector<sqlite3_stmt_ptr> StmtVec;
 986   StmtVec prepared;
 987
 988   std::set<Octree::Branch*> deferredOctreeUpdates;
 989
 990   // if we're performing a rebuild, the thread that is doing the work.
 991   // otherwise, NULL
 992   std::auto_ptr<RebuildThread> rebuilder;
 993 };
 994
 995   //////////////////////////////////////////////////////////////////////
 996
 997 FGPositioned* NavDataCache::NavDataCachePrivate::loadById(sqlite3_int64 rowid)
 998 {
 999
1000   sqlite3_bind_int64(loadPositioned, 1, rowid);
1001   execSelect1(loadPositioned);
1002
1003   assert(rowid == sqlite3_column_int64(loadPositioned, 0));
1004   FGPositioned::Type ty = (FGPositioned::Type) sqlite3_column_int(loadPositioned, 1);
1005
1006   string ident = (char*) sqlite3_column_text(loadPositioned, 2);
1007   string name = (char*) sqlite3_column_text(loadPositioned, 3);
1008   sqlite3_int64 aptId = sqlite3_column_int64(loadPositioned, 4);
1009   double lon = sqlite3_column_double(loadPositioned, 5);
1010   double lat = sqlite3_column_double(loadPositioned, 6);
1011   double elev = sqlite3_column_double(loadPositioned, 7);
1012   SGGeod pos = SGGeod::fromDegM(lon, lat, elev);
1013
1014   reset(loadPositioned);
1015
1016   switch (ty) {
1017     case FGPositioned::AIRPORT:
1018     case FGPositioned::SEAPORT:
1019     case FGPositioned::HELIPORT:
1020       return loadAirport(rowid, ty, ident, name, pos);
1021
1022     case FGPositioned::TOWER:
1023       return new AirportTower(rowid, aptId, ident, pos);
1024
1025     case FGPositioned::RUNWAY:
1026     case FGPositioned::HELIPAD:
1027     case FGPositioned::TAXIWAY:
1028       return loadRunway(rowid, ty, ident, pos, aptId);
1029
1030     case FGPositioned::LOC:
1031     case FGPositioned::VOR:
1032     case FGPositioned::GS:
1033     case FGPositioned::ILS:
1034     case FGPositioned::NDB:
1035     case FGPositioned::OM:
1036     case FGPositioned::MM:
1037     case FGPositioned::IM:
1038     case FGPositioned::DME:
1039     case FGPositioned::TACAN:
1040     case FGPositioned::MOBILE_TACAN:
1041     {
1042       if (aptId > 0) {
1043         FGAirport* apt = (FGAirport*) outer->loadById(aptId);
1044         if (apt->validateILSData()) {
1045           SG_LOG(SG_NAVCACHE, SG_INFO, "re-loaded ILS data for " << apt->ident());
1046           // queried data above is probably invalid, force us to go around again
1047           // (the next time through, validateILSData will return false)
1048           return outer->loadById(rowid);
1049         }
1050       }
1051
1052       return loadNav(rowid, ty, ident, name, pos);
1053     }
1054
1055     case FGPositioned::FIX:
1056       return new FGFix(rowid, ident, pos);
1057
1058     case FGPositioned::WAYPOINT:
1059     {
1060       FGPositioned* wpt = new FGPositioned(rowid, FGPositioned::WAYPOINT, ident, pos);
1061       return wpt;
1062     }
1063
1064     case FGPositioned::FREQ_GROUND:
1065     case FGPositioned::FREQ_TOWER:
1066     case FGPositioned::FREQ_ATIS:
1067     case FGPositioned::FREQ_AWOS:
1068     case FGPositioned::FREQ_APP_DEP:
1069     case FGPositioned::FREQ_ENROUTE:
1070     case FGPositioned::FREQ_CLEARANCE:
1071     case FGPositioned::FREQ_UNICOM:
1072       return loadComm(rowid, ty, ident, name, pos, aptId);
1073
1074     case FGPositioned::TAXI_NODE:
1075       return loadTaxiNode(rowid, pos, aptId);
1076
1077     case FGPositioned::PARKING:
1078       return loadParking(rowid, ident, pos, aptId);
1079
1080     default:
1081       return NULL;
1082   }
1083 }
1084
1085
1086 static NavDataCache* static_instance = NULL;
1087
1088 NavDataCache::NavDataCache()
1089 {
1090   const int MAX_TRIES = 3;
1091   SGPath homePath(globals->get_fg_home());
1092
1093   std::ostringstream os;
1094   string_list versionParts = simgear::strutils::split(VERSION, ".");
1095   if (versionParts.size() < 2) {
1096     os << "navdata.cache";
1097   } else {
1098     os << "navdata_" << versionParts[0] << "_" << versionParts[1] << ".cache";
1099   }
1100
1101   homePath.append(os.str());
1102
1103   for (int t=0; t < MAX_TRIES; ++t) {
1104     try {
1105       d.reset(new NavDataCachePrivate(homePath, this));
1106       d->init();
1107       //d->checkCacheFile();
1108     // reached this point with no exception, success
1109       break;
1110     } catch (sg_exception& e) {
1111       SG_LOG(SG_NAVCACHE, t == 0 ? SG_WARN : SG_ALERT, "NavCache: init failed:" << e.what()
1112              << " (attempt " << t << ")");
1113       d.reset();
1114       homePath.remove();
1115     }
1116   } // of retry loop
1117
1118   double RADIUS_EARTH_M = 7000 * 1000.0; // 7000km is plenty
1119   SGVec3d earthExtent(RADIUS_EARTH_M, RADIUS_EARTH_M, RADIUS_EARTH_M);
1120   Octree::global_spatialOctree =
1121     new Octree::Branch(SGBox<double>(-earthExtent, earthExtent), 1);
1122
1123   d->aptDatPath = SGPath(globals->get_fg_root());
1124   d->aptDatPath.append("Airports/apt.dat.gz");
1125
1126   d->metarDatPath = SGPath(globals->get_fg_root());
1127   d->metarDatPath.append("Airports/metar.dat.gz");
1128
1129   d->navDatPath = SGPath(globals->get_fg_root());
1130   d->navDatPath.append("Navaids/nav.dat.gz");
1131
1132   d->fixDatPath = SGPath(globals->get_fg_root());
1133   d->fixDatPath.append("Navaids/fix.dat.gz");
1134
1135   d->carrierDatPath = SGPath(globals->get_fg_root());
1136   d->carrierDatPath.append("Navaids/carrier_nav.dat.gz");
1137
1138   d->airwayDatPath = SGPath(globals->get_fg_root());
1139   d->airwayDatPath.append("Navaids/awy.dat.gz");
1140 }
1141
1142 NavDataCache::~NavDataCache()
1143 {
1144   assert(static_instance == this);
1145   static_instance = NULL;
1146   SG_LOG(SG_NAVCACHE, SG_INFO, "closing the navcache");
1147   d.reset();
1148 }
1149
1150 NavDataCache* NavDataCache::instance()
1151 {
1152   if (!static_instance) {
1153     static_instance = new NavDataCache;
1154   }
1155
1156   return static_instance;
1157 }
1158
1159 bool NavDataCache::isRebuildRequired()
1160 {
1161   if (isCachedFileModified(d->aptDatPath) ||
1162       isCachedFileModified(d->metarDatPath) ||
1163       isCachedFileModified(d->navDatPath) ||
1164       isCachedFileModified(d->fixDatPath) ||
1165       isCachedFileModified(d->airwayDatPath))
1166   {
1167     SG_LOG(SG_NAVCACHE, SG_INFO, "NavCache: main cache rebuild required");
1168     return true;
1169   }
1170
1171   string sceneryPaths = simgear::strutils::join(globals->get_fg_scenery(), ";");
1172   if (readStringProperty("scenery_paths") != sceneryPaths) {
1173     SG_LOG(SG_NAVCACHE, SG_INFO, "NavCache: scenery paths changed, main cache rebuild required");
1174     return true;
1175   }
1176
1177   SG_LOG(SG_NAVCACHE, SG_INFO, "NavCache: no main cache rebuild required");
1178   return false;
1179 }
1180
1181 bool NavDataCache::rebuild()
1182 {
1183   if (!d->rebuilder.get()) {
1184     d->rebuilder.reset(new RebuildThread(this));
1185     d->rebuilder->start();
1186   }
1187
1188 // poll the rebuild thread
1189   bool fin = d->rebuilder->isFinished();
1190   if (fin) {
1191     d->rebuilder.reset(); // all done!
1192   }
1193   return fin;
1194 }
1195
1196 void NavDataCache::doRebuild()
1197 {
1198   try {
1199     d->close(); // completely close the sqlite object
1200     d->path.remove(); // remove the file on disk
1201     d->init(); // star again from scratch
1202
1203     Transaction txn(this);
1204   // initialise the root octree node
1205     d->runSQL("INSERT INTO octree (rowid, children) VALUES (1, 0)");
1206
1207     SGTimeStamp st;
1208     st.stamp();
1209
1210     airportDBLoad(d->aptDatPath);
1211     SG_LOG(SG_NAVCACHE, SG_INFO, "apt.dat load took:" << st.elapsedMSec());
1212
1213     metarDataLoad(d->metarDatPath);
1214     stampCacheFile(d->aptDatPath);
1215     stampCacheFile(d->metarDatPath);
1216
1217     st.stamp();
1218     loadFixes(d->fixDatPath);
1219     stampCacheFile(d->fixDatPath);
1220     SG_LOG(SG_NAVCACHE, SG_INFO, "fix.dat load took:" << st.elapsedMSec());
1221
1222     st.stamp();
1223     navDBInit(d->navDatPath);
1224     stampCacheFile(d->navDatPath);
1225     SG_LOG(SG_NAVCACHE, SG_INFO, "nav.dat load took:" << st.elapsedMSec());
1226
1227     loadCarrierNav(d->carrierDatPath);
1228     stampCacheFile(d->carrierDatPath);
1229
1230     st.stamp();
1231     Airway::load(d->airwayDatPath);
1232     stampCacheFile(d->airwayDatPath);
1233     SG_LOG(SG_NAVCACHE, SG_INFO, "awy.dat load took:" << st.elapsedMSec());
1234
1235     d->flushDeferredOctreeUpdates();
1236
1237     string sceneryPaths = simgear::strutils::join(globals->get_fg_scenery(), ";");
1238     writeStringProperty("scenery_paths", sceneryPaths);
1239
1240     txn.commit();
1241   } catch (sg_exception& e) {
1242     SG_LOG(SG_NAVCACHE, SG_ALERT, "caught exception rebuilding navCache:" << e.what());
1243   }
1244 }
1245
1246 int NavDataCache::readIntProperty(const string& key)
1247 {
1248   sqlite_bind_stdstring(d->readPropertyQuery, 1, key);
1249   int result = 0;
1250
1251   if (d->execSelect(d->readPropertyQuery)) {
1252     result = sqlite3_column_int(d->readPropertyQuery, 0);
1253   } else {
1254     SG_LOG(SG_NAVCACHE, SG_WARN, "readIntProperty: unknown:" << key);
1255   }
1256
1257   d->reset(d->readPropertyQuery);
1258   return result;
1259 }
1260
1261 double NavDataCache::readDoubleProperty(const string& key)
1262 {
1263   sqlite_bind_stdstring(d->readPropertyQuery, 1, key);
1264   double result = 0.0;
1265   if (d->execSelect(d->readPropertyQuery)) {
1266     result = sqlite3_column_double(d->readPropertyQuery, 0);
1267   } else {
1268     SG_LOG(SG_NAVCACHE, SG_WARN, "readDoubleProperty: unknown:" << key);
1269   }
1270
1271   d->reset(d->readPropertyQuery);
1272   return result;
1273 }
1274
1275 string NavDataCache::readStringProperty(const string& key)
1276 {
1277   sqlite_bind_stdstring(d->readPropertyQuery, 1, key);
1278   string result;
1279   if (d->execSelect(d->readPropertyQuery)) {
1280     result = (char*) sqlite3_column_text(d->readPropertyQuery, 0);
1281   } else {
1282     SG_LOG(SG_NAVCACHE, SG_WARN, "readStringProperty: unknown:" << key);
1283   }
1284
1285   d->reset(d->readPropertyQuery);
1286   return result;
1287 }
1288
1289 void NavDataCache::writeIntProperty(const string& key, int value)
1290 {
1291   d->writeIntProperty(key, value);
1292 }
1293
1294 void NavDataCache::writeStringProperty(const string& key, const string& value)
1295 {
1296   sqlite_bind_stdstring(d->clearProperty, 1, key);
1297   d->execUpdate(d->clearProperty);
1298
1299   sqlite_bind_stdstring(d->writePropertyQuery, 1, key);
1300   sqlite_bind_stdstring(d->writePropertyQuery, 2, value);
1301   d->execUpdate(d->writePropertyQuery);
1302 }
1303
1304 void NavDataCache::writeDoubleProperty(const string& key, const double& value)
1305 {
1306   sqlite_bind_stdstring(d->clearProperty, 1, key);
1307   d->execUpdate(d->clearProperty);
1308
1309   sqlite_bind_stdstring(d->writePropertyQuery, 1, key);
1310   sqlite3_bind_double(d->writePropertyQuery, 2, value);
1311   d->execUpdate(d->writePropertyQuery);
1312 }
1313
1314 string_list NavDataCache::readStringListProperty(const string& key)
1315 {
1316   sqlite_bind_stdstring(d->readPropertyQuery, 1, key);
1317   string_list result;
1318   while (d->stepSelect(d->readPropertyQuery)) {
1319     result.push_back((char*) sqlite3_column_text(d->readPropertyQuery, 0));
1320   }
1321   d->reset(d->readPropertyQuery);
1322
1323   return result;
1324 }
1325
1326 void NavDataCache::writeStringListProperty(const string& key, const string_list& values)
1327 {
1328   sqlite_bind_stdstring(d->clearProperty, 1, key);
1329   d->execUpdate(d->clearProperty);
1330
1331   BOOST_FOREACH(string value, values) {
1332     sqlite_bind_stdstring(d->writePropertyMulti, 1, key);
1333     sqlite_bind_stdstring(d->writePropertyMulti, 2, value);
1334     d->execInsert(d->writePropertyMulti);
1335   }
1336 }
1337
1338 bool NavDataCache::isCachedFileModified(const SGPath& path) const
1339 {
1340   if (!path.exists()) {
1341     throw sg_io_exception("isCachedFileModified: Missing file:" + path.str());
1342   }
1343
1344   sqlite_bind_temp_stdstring(d->statCacheCheck, 1, path.str());
1345   bool isModified = true;
1346
1347   if (d->execSelect(d->statCacheCheck)) {
1348     time_t modtime = sqlite3_column_int64(d->statCacheCheck, 0);
1349     time_t delta = std::labs(modtime - path.modTime());
1350     if (delta != 0)
1351     {
1352       SG_LOG(SG_NAVCACHE, SG_DEBUG, "NavCache: rebuild required for " << path << ". Timestamps: " << modtime << " != " << path.modTime());
1353       if (delta < 30)
1354       {
1355           // File system time stamp has slightly changed. It's unlikely that the user has managed to change a file, start fgfs,
1356           // and then changed file again within x seconds - so it's suspicious...
1357           SG_LOG(SG_NAVCACHE, SG_ALERT, "NavCache: suspicious file timestamp change. Please report this to FlightGear. "
1358                   << "Delta: " << delta << ", Timestamps: " << modtime << ", " << path.modTime() << ", path: " << path);
1359       }
1360     }
1361     else
1362     {
1363       SG_LOG(SG_NAVCACHE, SG_DEBUG, "NavCache: no rebuild required for " << path);
1364     }
1365
1366     isModified = (delta != 0);
1367   } else {
1368     SG_LOG(SG_NAVCACHE, SG_DEBUG, "NavCache: initial build required for " << path);
1369   }
1370
1371   d->reset(d->statCacheCheck);
1372   return isModified;
1373 }
1374
1375 void NavDataCache::stampCacheFile(const SGPath& path)
1376 {
1377   sqlite_bind_temp_stdstring(d->stampFileCache, 1, path.str());
1378   sqlite3_bind_int64(d->stampFileCache, 2, path.modTime());
1379   d->execInsert(d->stampFileCache);
1380 }
1381
1382 void NavDataCache::beginTransaction()
1383 {
1384   if (d->transactionLevel == 0) {
1385     d->transactionAborted = false;
1386     d->stepSelect(d->beginTransactionStmt);
1387     sqlite3_reset(d->beginTransactionStmt);
1388   }
1389
1390   ++d->transactionLevel;
1391 }
1392
1393 void NavDataCache::commitTransaction()
1394 {
1395   assert(d->transactionLevel > 0);
1396   if (--d->transactionLevel == 0) {
1397     // if a nested transaction aborted, we might end up here, but must
1398     // still abort the entire transaction. That's bad, but safer than
1399     // committing.
1400     sqlite3_stmt_ptr q = d->transactionAborted ? d->rollbackTransactionStmt : d->commitTransactionStmt;
1401
1402     int retries = 0;
1403     int result;
1404     while (retries < MAX_RETRIES) {
1405       result = sqlite3_step(q);
1406       if (result == SQLITE_DONE) {
1407         break;
1408       }
1409
1410       // see http://www.sqlite.org/c3ref/get_autocommit.html for a hint
1411       // what's going on here: autocommit in inactive inside BEGIN, so if
1412       // it's active, the DB was rolled-back
1413       if (sqlite3_get_autocommit(d->db)) {
1414         SG_LOG(SG_NAVCACHE, SG_ALERT, "commit: was rolled back!" << retries);
1415         d->transactionAborted = true;
1416         break;
1417       }
1418
1419       if (result != SQLITE_BUSY) {
1420         break;
1421       }
1422
1423       SGTimeStamp::sleepForMSec(++retries * 10);
1424       SG_LOG(SG_NAVCACHE, SG_ALERT, "NavCache contention on commit, will retry:" << retries);
1425     } // of retry loop for DB busy
1426
1427     string errMsg;
1428     if (result != SQLITE_DONE) {
1429       errMsg = sqlite3_errmsg(d->db);
1430       SG_LOG(SG_NAVCACHE, SG_ALERT, "Sqlite error:" << errMsg << " for  " << result
1431              << " while running:\n\t" << sqlite3_sql(q));
1432     }
1433
1434     sqlite3_reset(q);
1435   }
1436 }
1437
1438 void NavDataCache::abortTransaction()
1439 {
1440   SG_LOG(SG_NAVCACHE, SG_WARN, "NavCache: aborting transaction");
1441
1442   assert(d->transactionLevel > 0);
1443   if (--d->transactionLevel == 0) {
1444     d->stepSelect(d->rollbackTransactionStmt);
1445     sqlite3_reset(d->rollbackTransactionStmt);
1446   }
1447
1448   d->transactionAborted = true;
1449 }
1450
1451 FGPositioned* NavDataCache::loadById(PositionedID rowid)
1452 {
1453   if (rowid == 0) {
1454     return NULL;
1455   }
1456
1457   PositionedCache::iterator it = d->cache.find(rowid);
1458   if (it != d->cache.end()) {
1459     d->cacheHits++;
1460     return it->second; // cache it
1461   }
1462
1463   FGPositioned* pos = d->loadById(rowid);
1464   d->cache.insert(it, PositionedCache::value_type(rowid, pos));
1465   d->cacheMisses++;
1466   return pos;
1467 }
1468
1469 PositionedID NavDataCache::insertAirport(FGPositioned::Type ty, const string& ident,
1470                                          const string& name)
1471 {
1472   // airports have their pos computed based on the avergae runway centres
1473   // so the pos isn't available immediately. Pass a dummy pos and avoid
1474   // doing spatial indexing until later
1475   sqlite3_int64 rowId = d->insertPositioned(ty, ident, name, SGGeod(),
1476                                             0 /* airport */,
1477                                             false /* spatial index */);
1478
1479   sqlite3_bind_int64(d->insertAirport, 1, rowId);
1480   d->execInsert(d->insertAirport);
1481
1482   return rowId;
1483 }
1484
1485 void NavDataCache::updatePosition(PositionedID item, const SGGeod &pos)
1486 {
1487   if (d->cache.find(item) != d->cache.end()) {
1488     SG_LOG(SG_NAVCACHE, SG_DEBUG, "updating position of an item in the cache");
1489     d->cache[item]->modifyPosition(pos);
1490   }
1491
1492   SGVec3d cartPos(SGVec3d::fromGeod(pos));
1493
1494   sqlite3_bind_int(d->setAirportPos, 1, item);
1495   sqlite3_bind_double(d->setAirportPos, 2, pos.getLongitudeDeg());
1496   sqlite3_bind_double(d->setAirportPos, 3, pos.getLatitudeDeg());
1497   sqlite3_bind_double(d->setAirportPos, 4, pos.getElevationM());
1498
1499 // bug 905; the octree leaf may change here, but the leaf may already be
1500 // loaded, and caching its children. (Either the old or new leaf!). Worse,
1501 // we may be called here as a result of loading one of those leaf's children.
1502 // instead of dealing with all those possibilites, such as modifying
1503 // the in-memory leaf's STL child container, we simply leave the runtime
1504 // structures alone. This is fine providing items do no move very far, since
1505 // all the spatial searches ultimately use the items' real cartesian position,
1506 // which was updated above.
1507   Octree::Leaf* octreeLeaf = Octree::global_spatialOctree->findLeafForPos(cartPos);
1508   sqlite3_bind_int64(d->setAirportPos, 5, octreeLeaf->guid());
1509
1510   sqlite3_bind_double(d->setAirportPos, 6, cartPos.x());
1511   sqlite3_bind_double(d->setAirportPos, 7, cartPos.y());
1512   sqlite3_bind_double(d->setAirportPos, 8, cartPos.z());
1513
1514
1515   d->execUpdate(d->setAirportPos);
1516 }
1517
1518 void NavDataCache::insertTower(PositionedID airportId, const SGGeod& pos)
1519 {
1520   d->insertPositioned(FGPositioned::TOWER, string(), string(),
1521                       pos, airportId, true /* spatial index */);
1522 }
1523
1524 PositionedID
1525 NavDataCache::insertRunway(FGPositioned::Type ty, const string& ident,
1526                            const SGGeod& pos, PositionedID apt,
1527                            double heading, double length, double width, double displacedThreshold,
1528                            double stopway, int surfaceCode)
1529 {
1530   // only runways are spatially indexed; don't bother indexing taxiways
1531   // or pavements
1532   bool spatialIndex = ( ty == FGPositioned::RUNWAY || ty == FGPositioned::HELIPAD);
1533
1534   sqlite3_int64 rowId = d->insertPositioned(ty, cleanRunwayNo(ident), "", pos, apt,
1535                                             spatialIndex);
1536   sqlite3_bind_int64(d->insertRunway, 1, rowId);
1537   sqlite3_bind_double(d->insertRunway, 2, heading);
1538   sqlite3_bind_double(d->insertRunway, 3, length);
1539   sqlite3_bind_double(d->insertRunway, 4, width);
1540   sqlite3_bind_int(d->insertRunway, 5, surfaceCode);
1541   sqlite3_bind_double(d->insertRunway, 6, displacedThreshold);
1542   sqlite3_bind_double(d->insertRunway, 7, stopway);
1543
1544   return d->execInsert(d->insertRunway);
1545 }
1546
1547 void NavDataCache::setRunwayReciprocal(PositionedID runway, PositionedID recip)
1548 {
1549   sqlite3_bind_int64(d->setRunwayReciprocal, 1, runway);
1550   sqlite3_bind_int64(d->setRunwayReciprocal, 2, recip);
1551   d->execUpdate(d->setRunwayReciprocal);
1552
1553 // and the opposite direction too!
1554   sqlite3_bind_int64(d->setRunwayReciprocal, 2, runway);
1555   sqlite3_bind_int64(d->setRunwayReciprocal, 1, recip);
1556   d->execUpdate(d->setRunwayReciprocal);
1557 }
1558
1559 void NavDataCache::setRunwayILS(PositionedID runway, PositionedID ils)
1560 {
1561   sqlite3_bind_int64(d->setRunwayILS, 1, runway);
1562   sqlite3_bind_int64(d->setRunwayILS, 2, ils);
1563   d->execUpdate(d->setRunwayILS);
1564
1565   // and the in-memory one
1566   if (d->cache.find(runway) != d->cache.end()) {
1567     FGRunway* instance = (FGRunway*) d->cache[runway].ptr();
1568     instance->setILS(ils);
1569   }
1570 }
1571
1572 void NavDataCache::updateRunwayThreshold(PositionedID runwayID, const SGGeod &aThreshold,
1573                                   double aHeading, double aDisplacedThreshold,
1574                                   double aStopway)
1575 {
1576 // update the runway information
1577   sqlite3_bind_int64(d->updateRunwayThreshold, 1, runwayID);
1578   sqlite3_bind_double(d->updateRunwayThreshold, 2, aHeading);
1579   sqlite3_bind_double(d->updateRunwayThreshold, 3, aDisplacedThreshold);
1580   sqlite3_bind_double(d->updateRunwayThreshold, 4, aStopway);
1581   d->execUpdate(d->updateRunwayThreshold);
1582
1583 // compute the new runway center, based on the threshold lat/lon and length,
1584   double offsetFt = (0.5 * d->runwayLengthFt(runwayID));
1585   SGGeod newCenter= SGGeodesy::direct(aThreshold, aHeading, offsetFt * SG_FEET_TO_METER);
1586   newCenter.setElevationM(aThreshold.getElevationM());
1587
1588 // now update the positional data
1589   updatePosition(runwayID, newCenter);
1590 }
1591
1592 PositionedID
1593 NavDataCache::insertNavaid(FGPositioned::Type ty, const string& ident,
1594                           const string& name, const SGGeod& pos,
1595                            int freq, int range, double multiuse,
1596                            PositionedID apt, PositionedID runway)
1597 {
1598   bool spatialIndex = true;
1599   if (ty == FGPositioned::MOBILE_TACAN) {
1600     spatialIndex = false;
1601   }
1602
1603   sqlite3_int64 rowId = d->insertPositioned(ty, ident, name, pos, apt,
1604                                             spatialIndex);
1605   sqlite3_bind_int64(d->insertNavaid, 1, rowId);
1606   sqlite3_bind_int(d->insertNavaid, 2, freq);
1607   sqlite3_bind_int(d->insertNavaid, 3, range);
1608   sqlite3_bind_double(d->insertNavaid, 4, multiuse);
1609   sqlite3_bind_int64(d->insertNavaid, 5, runway);
1610   return d->execInsert(d->insertNavaid);
1611 }
1612
1613 void NavDataCache::updateILS(PositionedID ils, const SGGeod& newPos, double aHdg)
1614 {
1615   sqlite3_bind_int64(d->updateILS, 1, ils);
1616   sqlite3_bind_double(d->updateILS, 2, aHdg);
1617   d->execUpdate(d->updateILS);
1618   updatePosition(ils, newPos);
1619 }
1620
1621 PositionedID NavDataCache::insertCommStation(FGPositioned::Type ty,
1622                                              const string& name, const SGGeod& pos, int freq, int range,
1623                                              PositionedID apt)
1624 {
1625   sqlite3_int64 rowId = d->insertPositioned(ty, "", name, pos, apt, true);
1626   sqlite3_bind_int64(d->insertCommStation, 1, rowId);
1627   sqlite3_bind_int(d->insertCommStation, 2, freq);
1628   sqlite3_bind_int(d->insertCommStation, 3, range);
1629   return d->execInsert(d->insertCommStation);
1630 }
1631
1632 PositionedID NavDataCache::insertFix(const std::string& ident, const SGGeod& aPos)
1633 {
1634   return d->insertPositioned(FGPositioned::FIX, ident, string(), aPos, 0, true);
1635 }
1636
1637 PositionedID NavDataCache::createUserWaypoint(const std::string& ident, const SGGeod& aPos)
1638 {
1639   return d->insertPositioned(FGPositioned::WAYPOINT, ident, string(), aPos, 0,
1640                              true /* spatial index */);
1641 }
1642
1643 void NavDataCache::setAirportMetar(const string& icao, bool hasMetar)
1644 {
1645   sqlite_bind_stdstring(d->setAirportMetar, 1, icao);
1646   sqlite3_bind_int(d->setAirportMetar, 2, hasMetar);
1647   d->execUpdate(d->setAirportMetar);
1648 }
1649
1650 FGPositioned::List NavDataCache::findAllWithIdent(const string& s,
1651                                                   FGPositioned::Filter* filter, bool exact)
1652 {
1653   return d->findAllByString(s, "ident", filter, exact);
1654 }
1655
1656 FGPositioned::List NavDataCache::findAllWithName(const string& s,
1657                                                   FGPositioned::Filter* filter, bool exact)
1658 {
1659   return d->findAllByString(s, "name", filter, exact);
1660 }
1661
1662 FGPositionedRef NavDataCache::findClosestWithIdent(const string& aIdent,
1663                                                    const SGGeod& aPos, FGPositioned::Filter* aFilter)
1664 {
1665   sqlite_bind_stdstring(d->findClosestWithIdent, 1, aIdent);
1666   if (aFilter) {
1667     sqlite3_bind_int(d->findClosestWithIdent, 2, aFilter->minType());
1668     sqlite3_bind_int(d->findClosestWithIdent, 3, aFilter->maxType());
1669   } else { // full type range
1670     sqlite3_bind_int(d->findClosestWithIdent, 2, FGPositioned::INVALID);
1671     sqlite3_bind_int(d->findClosestWithIdent, 3, FGPositioned::LAST_TYPE);
1672   }
1673
1674   SGVec3d cartPos(SGVec3d::fromGeod(aPos));
1675   sqlite3_bind_double(d->findClosestWithIdent, 4, cartPos.x());
1676   sqlite3_bind_double(d->findClosestWithIdent, 5, cartPos.y());
1677   sqlite3_bind_double(d->findClosestWithIdent, 6, cartPos.z());
1678
1679   FGPositionedRef result;
1680
1681   while (d->stepSelect(d->findClosestWithIdent)) {
1682     FGPositioned* pos = loadById(sqlite3_column_int64(d->findClosestWithIdent, 0));
1683     if (aFilter && !aFilter->pass(pos)) {
1684       continue;
1685     }
1686
1687     result = pos;
1688     break;
1689   }
1690
1691   d->reset(d->findClosestWithIdent);
1692   return result;
1693 }
1694
1695
1696 int NavDataCache::getOctreeBranchChildren(int64_t octreeNodeId)
1697 {
1698   sqlite3_bind_int64(d->getOctreeChildren, 1, octreeNodeId);
1699   d->execSelect1(d->getOctreeChildren);
1700   int children = sqlite3_column_int(d->getOctreeChildren, 0);
1701   d->reset(d->getOctreeChildren);
1702   return children;
1703 }
1704
1705 void NavDataCache::defineOctreeNode(Octree::Branch* pr, Octree::Node* nd)
1706 {
1707   sqlite3_bind_int64(d->insertOctree, 1, nd->guid());
1708   d->execInsert(d->insertOctree);
1709
1710 #ifdef LAZY_OCTREE_UPDATES
1711   d->deferredOctreeUpdates.insert(pr);
1712 #else
1713   // lowest three bits of node ID are 0..7 index of the child in the parent
1714   int childIndex = nd->guid() & 0x07;
1715
1716   sqlite3_bind_int64(d->updateOctreeChildren, 1, pr->guid());
1717 // mask has bit N set where child N exists
1718   int childMask = 1 << childIndex;
1719   sqlite3_bind_int(d->updateOctreeChildren, 2, childMask);
1720   d->execUpdate(d->updateOctreeChildren);
1721 #endif
1722 }
1723
1724 TypedPositionedVec
1725 NavDataCache::getOctreeLeafChildren(int64_t octreeNodeId)
1726 {
1727   sqlite3_bind_int64(d->getOctreeLeafChildren, 1, octreeNodeId);
1728
1729   TypedPositionedVec r;
1730   while (d->stepSelect(d->getOctreeLeafChildren)) {
1731     FGPositioned::Type ty = static_cast<FGPositioned::Type>
1732       (sqlite3_column_int(d->getOctreeLeafChildren, 1));
1733     r.push_back(std::make_pair(ty,
1734                 sqlite3_column_int64(d->getOctreeLeafChildren, 0)));
1735   }
1736
1737   d->reset(d->getOctreeLeafChildren);
1738   return r;
1739 }
1740
1741
1742 /**
1743  * A special purpose helper (used by FGAirport::searchNamesAndIdents) to
1744  * implement the AirportList dialog. It's unfortunate that it needs to reside
1745  * here, but for now it's least ugly solution.
1746  */
1747 char** NavDataCache::searchAirportNamesAndIdents(const std::string& aFilter)
1748 {
1749   string s = "%" + aFilter + "%";
1750   sqlite_bind_stdstring(d->searchAirports, 1, s);
1751
1752   unsigned int numMatches = 0, numAllocated = 16;
1753   char** result = (char**) malloc(sizeof(char*) * numAllocated);
1754
1755   while (d->stepSelect(d->searchAirports)) {
1756     if ((numMatches + 1) >= numAllocated) {
1757       numAllocated <<= 1; // double in size!
1758     // reallocate results array
1759       char** nresult = (char**) malloc(sizeof(char*) * numAllocated);
1760       memcpy(nresult, result, sizeof(char*) * numMatches);
1761       free(result);
1762       result = nresult;
1763     }
1764
1765     // nasty code to avoid excessive string copying and allocations.
1766     // We format results as follows (note whitespace!):
1767     //   ' name-of-airport-chars   (ident)'
1768     // so the total length is:
1769     //    1 + strlen(name) + 4 + strlen(icao) + 1 + 1 (for the null)
1770     // which gives a grand total of 7 + name-length + icao-length.
1771     // note the ident can be three letters (non-ICAO local strip), four
1772     // (default ICAO) or more (extended format ICAO)
1773     int nameLength = sqlite3_column_bytes(d->searchAirports, 1);
1774     int icaoLength = sqlite3_column_bytes(d->searchAirports, 0);
1775     char* entry = (char*) malloc(7 + nameLength + icaoLength);
1776     char* dst = entry;
1777     *dst++ = ' ';
1778     memcpy(dst, sqlite3_column_text(d->searchAirports, 1), nameLength);
1779     dst += nameLength;
1780     *dst++ = ' ';
1781     *dst++ = ' ';
1782     *dst++ = ' ';
1783     *dst++ = '(';
1784     memcpy(dst, sqlite3_column_text(d->searchAirports, 0), icaoLength);
1785     dst += icaoLength;
1786     *dst++ = ')';
1787     *dst++ = 0;
1788
1789     result[numMatches++] = entry;
1790   }
1791
1792   result[numMatches] = NULL; // end of list marker
1793   d->reset(d->searchAirports);
1794   return result;
1795 }
1796
1797 FGPositionedRef
1798 NavDataCache::findCommByFreq(int freqKhz, const SGGeod& aPos, FGPositioned::Filter* aFilter)
1799 {
1800   sqlite3_bind_int(d->findCommByFreq, 1, freqKhz);
1801   if (aFilter) {
1802     sqlite3_bind_int(d->findCommByFreq, 2, aFilter->minType());
1803     sqlite3_bind_int(d->findCommByFreq, 3, aFilter->maxType());
1804   } else { // full type range
1805     sqlite3_bind_int(d->findCommByFreq, 2, FGPositioned::FREQ_GROUND);
1806     sqlite3_bind_int(d->findCommByFreq, 3, FGPositioned::FREQ_UNICOM);
1807   }
1808
1809   SGVec3d cartPos(SGVec3d::fromGeod(aPos));
1810   sqlite3_bind_double(d->findCommByFreq, 4, cartPos.x());
1811   sqlite3_bind_double(d->findCommByFreq, 5, cartPos.y());
1812   sqlite3_bind_double(d->findCommByFreq, 6, cartPos.z());
1813   FGPositionedRef result;
1814
1815   while (d->execSelect(d->findCommByFreq)) {
1816     FGPositioned* p = loadById(sqlite3_column_int64(d->findCommByFreq, 0));
1817     if (aFilter && !aFilter->pass(p)) {
1818       continue;
1819     }
1820
1821     result = p;
1822     break;
1823   }
1824
1825   d->reset(d->findCommByFreq);
1826   return result;
1827 }
1828
1829 PositionedIDVec
1830 NavDataCache::findNavaidsByFreq(int freqKhz, const SGGeod& aPos, FGPositioned::Filter* aFilter)
1831 {
1832   sqlite3_bind_int(d->findNavsByFreq, 1, freqKhz);
1833   if (aFilter) {
1834     sqlite3_bind_int(d->findNavsByFreq, 2, aFilter->minType());
1835     sqlite3_bind_int(d->findNavsByFreq, 3, aFilter->maxType());
1836   } else { // full type range
1837     sqlite3_bind_int(d->findNavsByFreq, 2, FGPositioned::NDB);
1838     sqlite3_bind_int(d->findNavsByFreq, 3, FGPositioned::GS);
1839   }
1840
1841   SGVec3d cartPos(SGVec3d::fromGeod(aPos));
1842   sqlite3_bind_double(d->findNavsByFreq, 4, cartPos.x());
1843   sqlite3_bind_double(d->findNavsByFreq, 5, cartPos.y());
1844   sqlite3_bind_double(d->findNavsByFreq, 6, cartPos.z());
1845
1846   return d->selectIds(d->findNavsByFreq);
1847 }
1848
1849 PositionedIDVec
1850 NavDataCache::findNavaidsByFreq(int freqKhz, FGPositioned::Filter* aFilter)
1851 {
1852   sqlite3_bind_int(d->findNavsByFreqNoPos, 1, freqKhz);
1853   if (aFilter) {
1854     sqlite3_bind_int(d->findNavsByFreqNoPos, 2, aFilter->minType());
1855     sqlite3_bind_int(d->findNavsByFreqNoPos, 3, aFilter->maxType());
1856   } else { // full type range
1857     sqlite3_bind_int(d->findNavsByFreqNoPos, 2, FGPositioned::NDB);
1858     sqlite3_bind_int(d->findNavsByFreqNoPos, 3, FGPositioned::GS);
1859   }
1860
1861   return d->selectIds(d->findNavsByFreqNoPos);
1862 }
1863
1864 PositionedIDVec
1865 NavDataCache::airportItemsOfType(PositionedID apt,FGPositioned::Type ty,
1866                                  FGPositioned::Type maxTy)
1867 {
1868   if (maxTy == FGPositioned::INVALID) {
1869     maxTy = ty; // single-type range
1870   }
1871
1872   sqlite3_bind_int64(d->getAirportItems, 1, apt);
1873   sqlite3_bind_int(d->getAirportItems, 2, ty);
1874   sqlite3_bind_int(d->getAirportItems, 3, maxTy);
1875
1876   return d->selectIds(d->getAirportItems);
1877 }
1878
1879 PositionedID
1880 NavDataCache::airportItemWithIdent(PositionedID apt, FGPositioned::Type ty,
1881                                    const std::string& ident)
1882 {
1883   sqlite3_bind_int64(d->getAirportItemByIdent, 1, apt);
1884   sqlite_bind_stdstring(d->getAirportItemByIdent, 2, ident);
1885   sqlite3_bind_int(d->getAirportItemByIdent, 3, ty);
1886   PositionedID result = 0;
1887
1888   if (d->execSelect(d->getAirportItemByIdent)) {
1889     result = sqlite3_column_int64(d->getAirportItemByIdent, 0);
1890   }
1891
1892   d->reset(d->getAirportItemByIdent);
1893   return result;
1894 }
1895
1896 AirportRunwayPair
1897 NavDataCache::findAirportRunway(const std::string& aName)
1898 {
1899   if (aName.empty()) {
1900     return AirportRunwayPair();
1901   }
1902
1903   string_list parts = simgear::strutils::split(aName);
1904   if (parts.size() < 2) {
1905     SG_LOG(SG_NAVCACHE, SG_WARN, "findAirportRunway: malformed name:" << aName);
1906     return AirportRunwayPair();
1907   }
1908
1909   AirportRunwayPair result;
1910   sqlite_bind_stdstring(d->findAirportRunway, 1, parts[0]);
1911   sqlite_bind_stdstring(d->findAirportRunway, 2, parts[1]);
1912
1913   if (d->execSelect(d->findAirportRunway)) {
1914     result = AirportRunwayPair(sqlite3_column_int64(d->findAirportRunway, 0),
1915                       sqlite3_column_int64(d->findAirportRunway, 1));
1916
1917   } else {
1918     SG_LOG(SG_NAVCACHE, SG_WARN, "findAirportRunway: unknown airport/runway:" << aName);
1919   }
1920
1921   d->reset(d->findAirportRunway);
1922   return result;
1923 }
1924
1925 PositionedID
1926 NavDataCache::findILS(PositionedID airport, const string& runway, const string& navIdent)
1927 {
1928   sqlite_bind_stdstring(d->findILS, 1, navIdent);
1929   sqlite3_bind_int64(d->findILS, 2, airport);
1930   sqlite_bind_stdstring(d->findILS, 3, runway);
1931   PositionedID result = 0;
1932   if (d->execSelect(d->findILS)) {
1933     result = sqlite3_column_int64(d->findILS, 0);
1934   }
1935
1936   d->reset(d->findILS);
1937   return result;
1938 }
1939
1940 int NavDataCache::findAirway(int network, const string& aName)
1941 {
1942   sqlite3_bind_int(d->findAirway, 1, network);
1943   sqlite_bind_stdstring(d->findAirway, 2, aName);
1944
1945   int airway = 0;
1946   if (d->execSelect(d->findAirway)) {
1947     // already exists
1948     airway = sqlite3_column_int(d->findAirway, 0);
1949   } else {
1950     sqlite_bind_stdstring(d->insertAirway, 1, aName);
1951     sqlite3_bind_int(d->insertAirway, 2, network);
1952     airway = d->execInsert(d->insertAirway);
1953   }
1954
1955   d->reset(d->findAirway);
1956   return airway;
1957 }
1958
1959 void NavDataCache::insertEdge(int network, int airwayID, PositionedID from, PositionedID to)
1960 {
1961   // assume all edges are bidirectional for the moment
1962   for (int i=0; i<2; ++i) {
1963     sqlite3_bind_int(d->insertAirwayEdge, 1, network);
1964     sqlite3_bind_int(d->insertAirwayEdge, 2, airwayID);
1965     sqlite3_bind_int64(d->insertAirwayEdge, 3, from);
1966     sqlite3_bind_int64(d->insertAirwayEdge, 4, to);
1967     d->execInsert(d->insertAirwayEdge);
1968
1969     std::swap(from, to);
1970   }
1971 }
1972
1973 bool NavDataCache::isInAirwayNetwork(int network, PositionedID pos)
1974 {
1975   sqlite3_bind_int(d->isPosInAirway, 1, network);
1976   sqlite3_bind_int64(d->isPosInAirway, 2, pos);
1977   bool ok = d->execSelect(d->isPosInAirway);
1978   d->reset(d->isPosInAirway);
1979
1980   return ok;
1981 }
1982
1983 AirwayEdgeVec NavDataCache::airwayEdgesFrom(int network, PositionedID pos)
1984 {
1985   sqlite3_bind_int(d->airwayEdgesFrom, 1, network);
1986   sqlite3_bind_int64(d->airwayEdgesFrom, 2, pos);
1987
1988   AirwayEdgeVec result;
1989   while (d->stepSelect(d->airwayEdgesFrom)) {
1990     result.push_back(AirwayEdge(
1991                      sqlite3_column_int(d->airwayEdgesFrom, 0),
1992                      sqlite3_column_int64(d->airwayEdgesFrom, 1)
1993                      ));
1994   }
1995
1996   d->reset(d->airwayEdgesFrom);
1997   return result;
1998 }
1999
2000 PositionedID NavDataCache::findNavaidForRunway(PositionedID runway, FGPositioned::Type ty)
2001 {
2002   sqlite3_bind_int64(d->findNavaidForRunway, 1, runway);
2003   sqlite3_bind_int(d->findNavaidForRunway, 2, ty);
2004
2005   PositionedID result = 0;
2006   if (d->execSelect(d->findNavaidForRunway)) {
2007     result = sqlite3_column_int64(d->findNavaidForRunway, 0);
2008   }
2009
2010   d->reset(d->findNavaidForRunway);
2011   return result;
2012 }
2013
2014 PositionedID
2015 NavDataCache::insertParking(const std::string& name, const SGGeod& aPos,
2016                             PositionedID aAirport,
2017                            double aHeading, int aRadius, const std::string& aAircraftType,
2018                            const std::string& aAirlines)
2019 {
2020   sqlite3_int64 rowId = d->insertPositioned(FGPositioned::PARKING, name, "", aPos, aAirport, false);
2021
2022 // we need to insert a row into the taxi_node table, otherwise we can't maintain
2023 // the appropriate pushback flag.
2024   sqlite3_bind_int64(d->insertTaxiNode, 1, rowId);
2025   sqlite3_bind_int(d->insertTaxiNode, 2, 0);
2026   sqlite3_bind_int(d->insertTaxiNode, 3, 0);
2027   d->execInsert(d->insertTaxiNode);
2028
2029   sqlite3_bind_int64(d->insertParkingPos, 1, rowId);
2030   sqlite3_bind_double(d->insertParkingPos, 2, aHeading);
2031   sqlite3_bind_int(d->insertParkingPos, 3, aRadius);
2032   sqlite_bind_stdstring(d->insertParkingPos, 4, aAircraftType);
2033   sqlite_bind_stdstring(d->insertParkingPos, 5, aAirlines);
2034   return d->execInsert(d->insertParkingPos);
2035 }
2036
2037 void NavDataCache::setParkingPushBackRoute(PositionedID parking, PositionedID pushBackNode)
2038 {
2039   sqlite3_bind_int64(d->setParkingPushBack, 1, parking);
2040   sqlite3_bind_int64(d->setParkingPushBack, 2, pushBackNode);
2041   d->execUpdate(d->setParkingPushBack);
2042 }
2043
2044 PositionedID
2045 NavDataCache::insertTaxiNode(const SGGeod& aPos, PositionedID aAirport, int aHoldType, bool aOnRunway)
2046 {
2047   sqlite3_int64 rowId = d->insertPositioned(FGPositioned::TAXI_NODE, string(), string(), aPos, aAirport, false);
2048   sqlite3_bind_int64(d->insertTaxiNode, 1, rowId);
2049   sqlite3_bind_int(d->insertTaxiNode, 2, aHoldType);
2050   sqlite3_bind_int(d->insertTaxiNode, 3, aOnRunway);
2051   return d->execInsert(d->insertTaxiNode);
2052 }
2053
2054 void NavDataCache::insertGroundnetEdge(PositionedID aAirport, PositionedID from, PositionedID to)
2055 {
2056   sqlite3_bind_int64(d->insertTaxiEdge, 1, aAirport);
2057   sqlite3_bind_int64(d->insertTaxiEdge, 2, from);
2058   sqlite3_bind_int64(d->insertTaxiEdge, 3, to);
2059   d->execInsert(d->insertTaxiEdge);
2060 }
2061
2062 PositionedIDVec NavDataCache::groundNetNodes(PositionedID aAirport, bool onlyPushback)
2063 {
2064   sqlite3_stmt_ptr q = onlyPushback ? d->airportPushbackNodes : d->airportTaxiNodes;
2065   sqlite3_bind_int64(q, 1, aAirport);
2066   return d->selectIds(q);
2067 }
2068
2069 void NavDataCache::markGroundnetAsPushback(PositionedID nodeId)
2070 {
2071   sqlite3_bind_int64(d->markTaxiNodeAsPushback, 1, nodeId);
2072   d->execUpdate(d->markTaxiNodeAsPushback);
2073 }
2074
2075 static double headingDifferenceDeg(double crs1, double crs2)
2076 {
2077   double diff =  crs2 - crs1;
2078   SG_NORMALIZE_RANGE(diff, -180.0, 180.0);
2079   return diff;
2080 }
2081
2082 PositionedID NavDataCache::findGroundNetNode(PositionedID airport, const SGGeod& aPos,
2083                                              bool onRunway, FGRunway* aRunway)
2084 {
2085   sqlite3_stmt_ptr q = onRunway ? d->findNearestRunwayTaxiNode : d->findNearestTaxiNode;
2086   sqlite3_bind_int64(q, 1, airport);
2087
2088   SGVec3d cartPos(SGVec3d::fromGeod(aPos));
2089   sqlite3_bind_double(q, 2, cartPos.x());
2090   sqlite3_bind_double(q, 3, cartPos.y());
2091   sqlite3_bind_double(q, 4, cartPos.z());
2092
2093   PositionedID result = 0;
2094   while (d->execSelect(q)) {
2095     PositionedID id = sqlite3_column_int64(q, 0);
2096     if (!aRunway) {
2097       result = id;
2098       break;
2099     }
2100
2101   // ensure found node lies on the runway
2102     FGPositionedRef node = loadById(id);
2103     double course = SGGeodesy::courseDeg(node->geod(), aRunway->end());
2104     if (fabs(headingDifferenceDeg(course, aRunway->headingDeg())) < 3.0 ) {
2105       result = id;
2106       break;
2107     }
2108   }
2109
2110   d->reset(q);
2111   return result;
2112 }
2113
2114 PositionedIDVec NavDataCache::groundNetEdgesFrom(PositionedID pos, bool onlyPushback)
2115 {
2116   sqlite3_stmt_ptr q = onlyPushback ? d->pushbackEdgesFrom : d->taxiEdgesFrom;
2117   sqlite3_bind_int64(q, 1, pos);
2118   return d->selectIds(q);
2119 }
2120
2121 PositionedIDVec NavDataCache::findAirportParking(PositionedID airport, const std::string& flightType,
2122                                    int radius)
2123 {
2124   sqlite3_bind_int64(d->findAirportParking, 1, airport);
2125   sqlite3_bind_int(d->findAirportParking, 2, radius);
2126   sqlite_bind_stdstring(d->findAirportParking, 3, flightType);
2127
2128   return d->selectIds(d->findAirportParking);
2129 }
2130
2131 void NavDataCache::dropGroundnetFor(PositionedID aAirport)
2132 {
2133   sqlite3_stmt_ptr q = d->prepare("DELETE FROM parking WHERE rowid IN (SELECT rowid FROM positioned WHERE type=?1 AND airport=?2)");
2134   sqlite3_bind_int(q, 1, FGPositioned::PARKING);
2135   sqlite3_bind_int64(q, 2, aAirport);
2136   d->execUpdate(q);
2137
2138   q = d->prepare("DELETE FROM taxi_node WHERE rowid IN (SELECT rowid FROM positioned WHERE (type=?1 OR type=?2) AND airport=?3)");
2139   sqlite3_bind_int(q, 1, FGPositioned::TAXI_NODE);
2140   sqlite3_bind_int(q, 2, FGPositioned::PARKING);
2141   sqlite3_bind_int64(q, 3, aAirport);
2142   d->execUpdate(q);
2143
2144   q = d->prepare("DELETE FROM positioned WHERE (type=?1 OR type=?2) AND airport=?3");
2145   sqlite3_bind_int(q, 1, FGPositioned::TAXI_NODE);
2146   sqlite3_bind_int(q, 2, FGPositioned::PARKING);
2147   sqlite3_bind_int64(q, 3, aAirport);
2148   d->execUpdate(q);
2149
2150   q = d->prepare("DELETE FROM groundnet_edge WHERE airport=?1");
2151   sqlite3_bind_int64(q, 1, aAirport);
2152   d->execUpdate(q);
2153 }
2154
2155 /////////////////////////////////////////////////////////////////////////////////////////
2156 // Transaction RAII object
2157
2158 NavDataCache::Transaction::Transaction(NavDataCache* cache) :
2159     _instance(cache),
2160     _committed(false)
2161 {
2162     assert(cache);
2163     _instance->beginTransaction();
2164 }
2165
2166 NavDataCache::Transaction::~Transaction()
2167 {
2168     if (!_committed) {
2169         SG_LOG(SG_NAVCACHE, SG_INFO, "aborting cache transaction!");
2170         _instance->abortTransaction();
2171     }
2172 }
2173
2174 void NavDataCache::Transaction::commit()
2175 {
2176     assert(!_committed);
2177     _committed = true;
2178     _instance->commitTransaction();
2179 }
2180
2181 } // of namespace flightgear
2182