                         Routino : Numerical Limits
                         ==========================


32/64-bit Data IDs
------------------

   The OpenStreetMap data uses a numerical identifier (ID) for each node,
   way and relation. These IDs started at 1 and increase for every new
   item of each type that is added. When an object is deleted the ID is
   not re-used so the highest ID will always be higher than the number of
   objects.

   The ID needs to be handled carefully to ensure that it does not
   overflow the data type allocated for it. Depending on the data type
   used to store the ID there are are a number of numerical limits as
   described below:

    1. If a signed 32-bit integer is used to store the ID then the maximum
       value that can be handled is 2147483647 (2^31-1) before overflow.
    2. If an unsigned 32-bit integer is used to store the ID then the
       maximum value that can be handled is 4294967295 (2^32-1) before
       overflow.
    3. If a signed 64-bit integer is used to store the ID then the maximum
       value that can be handled is 9223372036854775807 (2^63-1) before
       overflow.

   For the purposes of this document the possibility of overflow of a
   64-bit integer is ignored.

   The part of Routino that handles the node, way and relation IDs is the
   planetsplitter program.

ID Above 31-bits
- - - - - - - -

   The first ID using 31-bits (for a node) was created in the
   OpenStreetMap database in February 2013.

   The earliest versions of Routino used unsigned 32-bit integers to store
   the ID. Therefore all versions of Routino will have worked correctly
   when node number 2147483648 (2^31) was created and through until node
   number 4294967295 (2^32-1).

ID Above 32-bits
- - - - - - - -

   The ability of Routino to handle IDs larger than 32-bits does not
   depend on having a 64-bit operating system.

   Before version 2.0.1 of Routino there was no check that the ID read
   from the input data would fit within an unsigned 32-bit integer.
   Earlier versions of Routino will therefore fail to report an error and
   will process data incorrectly when node number 4294967296 (2^32) or
   higher is present.

   From version 2.0.2 of Routino the code is written to allow the node,
   way and relation ID data type to be changed to 64-bits. This means that
   a consistent data type is used for handling IDs and the format used for
   printing them is consistent with the variable type. The binary format
   of the database will be unchanged by the use of 64-bit IDs for parsing
   OSM files (since the IDs are not stored in the database) but file
   parsing will take more memory and therefore time.

   From version 3.1 of Routino the OSM node ID was changed to use 64-bit
   integers instead of 32-bit integers.

   A similar change can also be made for way or relation IDs. At the time
   of writing (July 2026) the highest ID for a way will fit in a 32-bit
   number (currently ~30.5 bits) and at the current rate of increase will
   take around 5 years to reach 32 bits. The highest ID for a relation is
   much lower (currently ~24 bits) so will not reach 32 bits for a very
   long time.

   To recompile with 64-bit way IDs the file src/typesx.h should be edited
   and the two lines below changed from:

typedef uint32_t way_t;

#define Pway_t PRIu32

   to:

typedef uint64_t way_t;

#define Pway_t PRIu64

   Between version 2.0.2 and version 2.4 of Routino a bug means that route
   relations will ignore the way or relation ID if it is equal to
   4294967295 (2^32-1).

   From version 2.4 of Routino onwards when a numerical limit is reached
   the planetsplitter program will exit with an error message that
   describes which limit was reached and which data type needs to be
   changed.

Database Format
---------------

   The other limitation in Routino is the number of objects stored in the
   database that is generated by the planetsplitter data processing. This
   number may be significantly different from the highest ID in the input
   data set for two reasons. Firstly any nodes, ways or relations that
   have been deleted will not be present in the data. Secondly when a
   partial planet database (continent, country or smaller) is processed
   there will be only a fraction of the total number of nodes, ways and
   relations.

   The limiting factor is the largest of the following.

    1. The number of nodes in the input data files.
    2. The number of segments in the input data files.
    3. The number of highways in the input data files.
    4. The number of relations in the input data files.

   Normally the number of nodes will be the limiting factor.

32-bit Indexes
- - - - - - -

   Before version 1.2 of Routino the database could hold up to 4294967295
   (2^32-1) items of each type (node, segment, way) since an unsigned
   32-bit integer is used.

   Versions 1.3 to 1.4.1 of Routino have a limit of 2147483647 (2^31-1)
   items since half of the 32-bit integer range is reserved for fake nodes
   and segments that are inserted if a waypoint is not close to a node.

   From version 1.5 of Routino the limit is 4294901760 (2^32-2^16) for the
   number of items of each type that can be stored. The small remaining
   part of the 32-bit unsigned integer range is reserved for fake nodes
   and segments.

64-bit Indexes
- - - - - - -

   When using a 32-bit operating system it is not possible to create a
   database that exceeds about 2GB in total. This will be far fewer than
   2^32 objects in the database in total. The use of 64-bit indexes will
   require a 64-bit operating system.

   From version 2.0.2 of Routino onwards it is possible to make a simple
   change to the code to index the database objects with 64-bit integers
   instead of 32-bit integers.

   To recompile with 64-bit indexes the file src/types.h should be edited
   and the two lines below changed from:

typedef uint32_t index_t;

#define Pindex_t PRIu32

   to:

typedef uint64_t index_t;

#define Pindex_t PRIu64

   This change will affect nodes, segments, ways and relations together.
   The database that is generated will no longer be compatible with
   Routino that has been compiled with 32-bit indexes. The size of the
   database will also grow by about 50% when this change is made and the
   time to generate the database and calculate a route will also increase.

--------

Copyright 2026 Andrew M. Bishop.
