src/signalbuffer.cpp

   1 /* $Id$ */
   2
   3 /*
   4  * This file is part of OpenTTD.
   5  * OpenTTD is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, version 2.
   6  * OpenTTD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
   7  * See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with OpenTTD. If not, see <http://www.gnu.org/licenses/>.
   8  */
   9
  10 /** @file signalbuffer.cpp functions related to rail signals updating */
  11
  12 #include "stdafx.h"
  13 #include "debug.h"
  14 #include "map/road.h"
  15 #include "map/bridge.h"
  16 #include "vehicle_func.h"
  17 #include "viewport_func.h"
  18 #include "train.h"
  19 #include "company_base.h"
  20 #include "signalbuffer.h"
  21 #include "station_func.h"
  22
  23
  24 /** these are the maximums used for updating signal blocks */
  25 static const uint SIG_TBU_SIZE    =  64; ///< number of signals entering to block
  26 static const uint SIG_TBD_SIZE    = 256; ///< number of intersections - open nodes in current block
  27 static const uint SIG_GLOB_SIZE   = 128; ///< number of open blocks (block can be opened more times until detected)
  28 static const uint SIG_GLOB_UPDATE =  64; ///< how many items need to be in _globset to force update
  29
  30 assert_compile(SIG_GLOB_UPDATE <= SIG_GLOB_SIZE);
  31
  32 /** incidating trackbits with given enterdir */
  33 static const TrackBits _enterdir_to_trackbits[DIAGDIR_END] = {
  34         TRACK_BIT_3WAY_NE,
  35         TRACK_BIT_3WAY_SE,
  36         TRACK_BIT_3WAY_SW,
  37         TRACK_BIT_3WAY_NW
  38 };
  39
  40 /** incidating trackdirbits with given enterdir */
  41 static const TrackdirBits _enterdir_to_trackdirbits[DIAGDIR_END] = {
  42         TRACKDIR_BIT_X_SW | TRACKDIR_BIT_UPPER_W | TRACKDIR_BIT_RIGHT_S,
  43         TRACKDIR_BIT_Y_NW | TRACKDIR_BIT_LOWER_W | TRACKDIR_BIT_RIGHT_N,
  44         TRACKDIR_BIT_X_NE | TRACKDIR_BIT_LOWER_E | TRACKDIR_BIT_LEFT_N,
  45         TRACKDIR_BIT_Y_SE | TRACKDIR_BIT_UPPER_E | TRACKDIR_BIT_LEFT_S
  46 };
  47
  48 /**
  49  * Set containing up to 'maxitems' items of 'T'
  50  * No tree structure is used because it would cause
  51  * slowdowns in most usual cases
  52  */
  53 template <typename T, uint maxitems>
  54 struct SmallSet {
  55 private:
  56         uint n;           // actual number of units
  57         bool overflowed;  // did we try to overflow the set?
  58         const char *name; // name, used for debugging purposes...
  59         T data[maxitems]; // elements of set
  60
  61 public:
  62         /** Constructor - just set default values and 'name' */
  63         SmallSet(const char *name) : n(0), overflowed(false), name(name) { }
  64
  65         /** Reset variables to default values */
  66         void Reset()
  67         {
  68                 this->n = 0;
  69                 this->overflowed = false;
  70         }
  71
  72         /**
  73          * Returns value of 'overflowed'
  74          * @return did we try to overflow the set?
  75          */
  76         bool Overflowed()
  77         {
  78                 return this->overflowed;
  79         }
  80
  81         /**
  82          * Checks for empty set
  83          * @return is the set empty?
  84          */
  85         bool IsEmpty()
  86         {
  87                 return this->n == 0;
  88         }
  89
  90         /**
  91          * Checks for full set
  92          * @return is the set full?
  93          */
  94         bool IsFull()
  95         {
  96                 return this->n == lengthof(data);
  97         }
  98
  99         /**
 100          * Reads the number of items
 101          * @return current number of items
 102          */
 103         uint Items()
 104         {
 105                 return this->n;
 106         }
 107
 108
 109         /**
 110          * Tries to remove first instance of given item
 111          * @param item item to remove
 112          * @return element was found and removed
 113          */
 114         bool Remove(const T &item)
 115         {
 116                 for (uint i = 0; i < this->n; i++) {
 117                         if (this->data[i] == item) {
 118                                 this->data[i] = this->data[--this->n];
 119                                 return true;
 120                         }
 121                 }
 122
 123                 return false;
 124         }
 125
 126         /**
 127          * Tries to find given item in the set
 128          * @param item item to find
 129          * @return true iff the item was found
 130          */
 131         bool IsIn(const T &item)
 132         {
 133                 for (uint i = 0; i < this->n; i++) {
 134                         if (this->data[i] == item) return true;
 135                 }
 136
 137                 return false;
 138         }
 139
 140         /**
 141          * Adds item into the set, checks for full set
 142          * Sets the 'overflowed' flag if the set was full
 143          * @param item item to add
 144          * @return true iff the item could be added (set wasn't full)
 145          */
 146         bool Add(const T &item)
 147         {
 148                 if (this->IsFull()) {
 149                         overflowed = true;
 150                         DEBUG(misc, 0, "SignalSegment too complex. Set %s is full (maximum %d)", name, maxitems);
 151                         return false; // set is full
 152                 }
 153
 154                 this->data[this->n] = item;
 155                 this->n++;
 156
 157                 return true;
 158         }
 159
 160         /**
 161          * Reads the last added element into the set
 162          * @param item pointer where the item is written to
 163          * @return false iff the set was empty
 164          */
 165         bool Get(T *item)
 166         {
 167                 if (this->n == 0) return false;
 168
 169                 this->n--;
 170                 *item = this->data[this->n];
 171
 172                 return true;
 173         }
 174 };
 175
 176
 177 struct SignalPos {
 178         TileIndex tile;
 179         Trackdir td;
 180
 181         bool operator == (const SignalPos &other) const {
 182                 return (tile == other.tile) && (td == other.td);
 183         }
 184 };
 185
 186 static SignalPos SignalPosFrom(TileIndex tile, Trackdir td)
 187 {
 188         SignalPos pos = { tile, td };
 189         return pos;
 190 }
 191
 192 enum SignalSideEnum {
 193         SIDE_NE = DIAGDIR_NE,
 194         SIDE_SE = DIAGDIR_SE,
 195         SIDE_SW = DIAGDIR_SW,
 196         SIDE_NW = DIAGDIR_NW,
 197         SIDE_INTO_BRIDGE,
 198         SIDE_FROM_BRIDGE,
 199         SIDE_INTO_TUNNEL,
 200         SIDE_FROM_TUNNEL,
 201         SIDE_DEPOT,
 202 };
 203
 204 /** Allow incrementing of SignalSideEnum variables */
 205 DECLARE_POSTFIX_INCREMENT(SignalSideEnum)
 206
 207 struct SignalSide {
 208         TileIndex tile;
 209         SignalSideEnum side;
 210
 211         bool operator == (const SignalSide &other) const {
 212                 return (tile == other.tile) && (side == other.side);
 213         }
 214 };
 215
 216 static SignalSide SignalSideFrom(TileIndex tile, SignalSideEnum side)
 217 {
 218         SignalSide ss = { tile, side };
 219         return ss;
 220 }
 221
 222 static SmallSet<SignalPos,  SIG_TBU_SIZE>  _tbuset("_tbuset");   ///< set of signals that will be updated
 223 static SmallSet<SignalSide, SIG_TBD_SIZE>  _tbdset("_tbdset");   ///< set of open nodes in current signal block
 224 static SmallSet<SignalSide, SIG_GLOB_SIZE> _globset("_globset"); ///< set of places to be updated in following runs
 225 static Owner _owner = INVALID_OWNER; ///< owner of tracks in _globset, or INVALID_OWNER if empty
 226
 227
 228 /** Check if there is a train on a tile, not in a depot. */
 229 static bool HasTrainOnTile (TileIndex tile)
 230 {
 231         VehicleTileFinder iter (tile);
 232         while (!iter.finished()) {
 233                 Vehicle *v = iter.next();
 234                 if (v->type == VEH_TRAIN && Train::From(v)->trackdir != TRACKDIR_DEPOT) {
 235                         iter.set_found();
 236                 }
 237         }
 238         return iter.was_found();
 239 }
 240
 241
 242 /**
 243  * Perform some operations before adding data into Todo set
 244  * The new and reverse direction is removed from Global set, because we are sure
 245  * it doesn't need to be checked again
 246  * Also, remove reverse direction from Todo set
 247  * This is the 'core' part so the graph searching won't enter any tile twice
 248  *
 249  * @param ss1 tile and side we are entering
 250  * @param ss2 tile and side we are leaving
 251  * @return false iff the Todo buffer would be overrun
 252  */
 253 static inline bool MaybeAddToTodoSet(const SignalSide &ss1, const SignalSide &ss2)
 254 {
 255         _globset.Remove(ss1); // it can be in Global but not in Todo
 256         _globset.Remove(ss2); // remove in all cases
 257
 258         assert(!_tbdset.IsIn(ss1)); // it really shouldn't be there already
 259
 260         if (_tbdset.Remove(ss2)) return true;
 261
 262         return _tbdset.Add(ss1);
 263 }
 264
 265
 266 /** Current signal block state flags */
 267 enum SigFlags {
 268         SF_NONE   = 0,
 269         SF_TRAIN  = 1 << 0, ///< train found in segment
 270         SF_EXIT   = 1 << 1, ///< exitsignal found
 271         SF_EXIT2  = 1 << 2, ///< two or more exits found
 272         SF_GREEN  = 1 << 3, ///< green exitsignal found
 273         SF_GREEN2 = 1 << 4, ///< two or more green exits found
 274         SF_FULL   = 1 << 5, ///< some of buffers was full, do not continue
 275         SF_PBS    = 1 << 6, ///< pbs signal found
 276 };
 277
 278 DECLARE_ENUM_AS_BIT_SET(SigFlags)
 279
 280
 281 /**
 282  * Search signal block
 283  *
 284  * @param owner owner whose signals we are updating
 285  * @return SigFlags
 286  */
 287 static SigFlags ExploreSegment(Owner owner)
 288 {
 289         SigFlags flags = SF_NONE;
 290
 291         SignalSide ss;
 292
 293         while (_tbdset.Get(&ss)) {
 294                 SignalSide newss;
 295                 newss.tile = ss.tile; // tile we will enter
 296
 297                 switch (GetTileType(ss.tile)) {
 298                         case TT_RAILWAY: {
 299                                 if (GetTileOwner(ss.tile) != owner) continue; // do not propagate signals on others' tiles (remove for tracksharing)
 300
 301                                 if (IsTileSubtype(ss.tile, TT_BRIDGE)) {
 302                                         DiagDirection dir = GetTunnelBridgeDirection(ss.tile);
 303                                         if (ss.side == (SignalSideEnum)dir) continue;
 304                                         if (ss.side == SIDE_INTO_BRIDGE) {
 305                                                 newss.tile = GetOtherBridgeEnd(ss.tile); // skip to exit tile
 306                                                 if (!(flags & SF_TRAIN) && EnsureNoTrainOnTunnelBridgeMiddle(ss.tile, newss.tile).Failed()) flags |= SF_TRAIN;
 307                                                 newss.side = SIDE_FROM_BRIDGE;
 308                                                 ss.tile = newss.tile;
 309                                                 ss.side = SIDE_INTO_BRIDGE;
 310                                                 break;
 311                                         }
 312                                         if (ss.side == SIDE_FROM_BRIDGE) ss.side = (SignalSideEnum)dir;
 313                                 }
 314
 315                                 assert(IsValidDiagDirection((DiagDirection)ss.side));
 316
 317                                 TrackBits tracks = GetTrackBits(ss.tile); // trackbits of tile
 318                                 TrackBits tracks_masked = (TrackBits)(tracks & _enterdir_to_trackbits[ss.side]); // only incidating trackbits
 319
 320                                 if (tracks == TRACK_BIT_HORZ || tracks == TRACK_BIT_VERT) { // there is exactly one incidating track, no need to check
 321                                         tracks = tracks_masked;
 322                                 } else {
 323                                         if (tracks_masked == TRACK_BIT_NONE) continue; // no incidating track
 324                                 }
 325
 326                                 assert((tracks_masked & ~tracks) == TRACK_BIT_NONE); // tracks_masked must be a subset of tracks
 327                                 assert(tracks_masked != TRACK_BIT_NONE);
 328                                 assert(tracks_masked != TRACK_BIT_HORZ);
 329                                 assert(tracks_masked != TRACK_BIT_VERT);
 330                                 assert(tracks != TRACK_BIT_HORZ);
 331                                 assert(tracks != TRACK_BIT_VERT);
 332
 333                                 if (HasAtMostOneBit(tracks)) { // only one track
 334                                         Track track = TrackBitsToTrack(tracks); // get the only track
 335                                         if (!(flags & SF_TRAIN) && EnsureNoTrainOnTrackBits(ss.tile, tracks).Failed()) flags |= SF_TRAIN;
 336
 337                                         // tile can only have signals if it only has one bit
 338                                         if (HasSignalOnTrack(ss.tile, track)) { // now check whole track, not trackdir
 339                                                 SignalType sig = GetSignalType(ss.tile, track);
 340                                                 Trackdir trackdir = FindFirstTrackdir(TrackBitsToTrackdirBits(tracks) & _enterdir_to_trackdirbits[ss.side]);
 341                                                 Trackdir reversedir = ReverseTrackdir(trackdir);
 342                                                 /* add (tile, reversetrackdir) to 'to-be-updated' set when there is
 343                                                  * ANY conventional signal in REVERSE direction
 344                                                  * (if it is a presignal EXIT and it changes, it will be added to 'to-be-done' set later) */
 345                                                 if (HasSignalOnTrackdir(ss.tile, reversedir)) {
 346                                                         if (IsPbsSignal(sig)) {
 347                                                                 flags |= SF_PBS;
 348                                                         } else if (!_tbuset.Add(SignalPosFrom(ss.tile, reversedir))) {
 349                                                                 return flags | SF_FULL;
 350                                                         }
 351                                                 }
 352                                                 if (HasSignalOnTrackdir(ss.tile, trackdir) && !IsOnewaySignal(sig)) flags |= SF_PBS;
 353
 354                                                 /* if it is a presignal EXIT in OUR direction and we haven't found 2 green exits yes, do special check */
 355                                                 if (!(flags & SF_GREEN2) && IsPresignalExit(sig) && HasSignalOnTrackdir(ss.tile, trackdir)) { // found presignal exit
 356                                                         if (flags & SF_EXIT) flags |= SF_EXIT2; // found two (or more) exits
 357                                                         flags |= SF_EXIT; // found at least one exit - allow for compiler optimizations
 358                                                         if (GetSignalStateByTrackdir(ss.tile, trackdir) == SIGNAL_STATE_GREEN) { // found green presignal exit
 359                                                                 if (flags & SF_GREEN) flags |= SF_GREEN2;
 360                                                                 flags |= SF_GREEN;
 361                                                         }
 362                                                 }
 363
 364                                                 continue;
 365                                         }
 366                                 } else { // tile has overlapping tracks
 367                                         if (!(flags & SF_TRAIN) && HasTrainOnTile(ss.tile)) flags |= SF_TRAIN;
 368                                 }
 369
 370                                 SignalSideEnum enterdir = ss.side;
 371                                 for (ss.side = (SignalSideEnum)DIAGDIR_BEGIN; ss.side < (SignalSideEnum)DIAGDIR_END; ss.side++) { // test all possible exit directions
 372                                         if (ss.side != enterdir && (tracks & _enterdir_to_trackbits[ss.side])) { // any track incidating?
 373                                                 if (IsTileSubtype(ss.tile, TT_BRIDGE) && (ss.side == (SignalSideEnum)GetTunnelBridgeDirection(ss.tile))) {
 374                                                         newss.tile = ss.tile;
 375                                                         newss.side = SIDE_INTO_BRIDGE;
 376                                                         if (!MaybeAddToTodoSet(newss, SignalSideFrom(ss.tile, SIDE_FROM_BRIDGE))) return flags | SF_FULL;
 377                                                 } else {
 378                                                         newss.tile = ss.tile + TileOffsByDiagDir((DiagDirection)ss.side);  // new tile to check
 379                                                         newss.side = (SignalSideEnum)ReverseDiagDir((DiagDirection)ss.side); // direction we are entering from
 380                                                         if (!MaybeAddToTodoSet(newss, ss)) return flags | SF_FULL;
 381                                                 }
 382                                         }
 383                                 }
 384
 385                                 continue; // continue the while() loop
 386                         }
 387
 388                         case TT_MISC:
 389                                 if (GetTileOwner(ss.tile) != owner) continue;
 390
 391                                 switch (GetTileSubtype(ss.tile)) {
 392                                         default: continue;
 393
 394                                         case TT_MISC_CROSSING:
 395                                                 assert(IsValidDiagDirection((DiagDirection)ss.side));
 396                                                 if (DiagDirToAxis((DiagDirection)ss.side) == GetCrossingRoadAxis(ss.tile)) continue; // different axis
 397                                                 if (!(flags & SF_TRAIN) && HasTrainOnTile(ss.tile)) flags |= SF_TRAIN;
 398                                                 newss.side = ss.side;
 399                                                 ss.side = (SignalSideEnum)ReverseDiagDir((DiagDirection)ss.side); // exitdir
 400                                                 newss.tile += TileOffsByDiagDir((DiagDirection)ss.side);
 401                                                 break;
 402
 403                                         case TT_MISC_TUNNEL: {
 404                                                 if (GetTunnelTransportType(ss.tile) != TRANSPORT_RAIL) continue;
 405                                                 DiagDirection dir = GetTunnelBridgeDirection(ss.tile);
 406
 407                                                 if (ss.side == SIDE_INTO_TUNNEL) { // going into the wormhole
 408                                                         newss.tile = GetOtherTunnelEnd(ss.tile); // skip to exit tile
 409                                                         if (!(flags & SF_TRAIN) && EnsureNoTrainOnTunnelBridgeMiddle(ss.tile, newss.tile).Failed()) flags |= SF_TRAIN;
 410                                                         newss.side = SIDE_FROM_TUNNEL;
 411                                                         ss.tile = newss.tile;
 412                                                         ss.side = SIDE_INTO_TUNNEL;
 413                                                 } else if (ss.side == SIDE_FROM_TUNNEL) { // incoming from the wormhole
 414                                                         if (!(flags & SF_TRAIN) && EnsureNoTrainOnTrackBits(ss.tile, TRACK_BIT_ALL).Failed()) flags |= SF_TRAIN;
 415                                                         if (maptile_has_tunnel_signals(ss.tile)) {
 416                                                                 /* Only one-way signals supported in tunnels. */
 417                                                                 assert(maptile_has_tunnel_signal(ss.tile, true) != maptile_has_tunnel_signal(ss.tile, false));
 418                                                                 if (maptile_has_tunnel_signal(ss.tile, true)) {
 419                                                                         /* Only normal signals supported into tunnels. */
 420                                                                         assert(maptile_get_tunnel_signal_type(ss.tile) == SIGTYPE_NORMAL);
 421                                                                         if (!_tbuset.Add(SignalPosFrom(ss.tile, DiagDirToDiagTrackdir(dir)))) {
 422                                                                                 return flags | SF_FULL;
 423                                                                         }
 424                                                                 }
 425                                                                 continue;
 426                                                         }
 427                                                         ss.side = (SignalSideEnum)ReverseDiagDir(dir); // exitdir
 428                                                         newss.tile += TileOffsByDiagDir((DiagDirection)ss.side); // just skip to next tile
 429                                                         newss.side = (SignalSideEnum)dir;
 430                                                 } else { // neither into nor from the wormhole
 431                                                         assert(IsValidDiagDirection((DiagDirection)ss.side));
 432                                                         if (ss.side != (SignalSideEnum)ReverseDiagDir(dir)) continue;
 433                                                         if (!(flags & SF_TRAIN) && EnsureNoTrainOnTrackBits(ss.tile, TRACK_BIT_ALL).Failed()) flags |= SF_TRAIN;
 434                                                         if (maptile_has_tunnel_signals(ss.tile)) {
 435                                                                 /* Only one-way signals supported in tunnels. */
 436                                                                 assert(maptile_has_tunnel_signal(ss.tile, true) != maptile_has_tunnel_signal(ss.tile, false));
 437                                                                 if (maptile_has_tunnel_signal(ss.tile, false)) {
 438                                                                         SignalType sig = maptile_get_tunnel_signal_type(ss.tile);
 439                                                                         /* Only normal and one-way path signals supported in tunnels. */
 440                                                                         assert(sig == SIGTYPE_NORMAL || sig == SIGTYPE_PBS_ONEWAY);
 441                                                                         if (sig != SIGTYPE_NORMAL) {
 442                                                                                 flags |= SF_PBS;
 443                                                                         } else if (!_tbuset.Add(SignalPosFrom(ss.tile, DiagDirToDiagTrackdir(ReverseDiagDir(dir))))) {
 444                                                                                 return flags | SF_FULL;
 445                                                                         }
 446                                                                 }
 447                                                                 continue;
 448                                                         }
 449                                                         ss.side = SIDE_FROM_TUNNEL;
 450                                                         newss.tile = ss.tile;
 451                                                         newss.side = SIDE_INTO_TUNNEL;
 452                                                 }
 453                                                 break;
 454                                         }
 455
 456                                         case TT_MISC_DEPOT:
 457                                                 if (!IsRailDepot(ss.tile)) continue;
 458                                                 if (ss.side == SIDE_DEPOT) { // from 'inside' - train just entered or left the depot
 459                                                         if (!(flags & SF_TRAIN) && HasTrainOnTile(ss.tile)) flags |= SF_TRAIN;
 460                                                         ss.side = (SignalSideEnum)GetGroundDepotDirection(ss.tile); // exitdir
 461                                                         newss.tile += TileOffsByDiagDir((DiagDirection)ss.side);
 462                                                         newss.side = (SignalSideEnum)ReverseDiagDir((DiagDirection)ss.side);
 463                                                         break;
 464                                                 } else if (ss.side == (SignalSideEnum)GetGroundDepotDirection(ss.tile)) { // entered a depot
 465                                                         if (!(flags & SF_TRAIN) && HasTrainOnTile(ss.tile)) flags |= SF_TRAIN;
 466                                                 }
 467                                                 continue;
 468                                 }
 469                                 break;
 470
 471                         case TT_STATION:
 472                                 assert(IsValidDiagDirection((DiagDirection)ss.side));
 473
 474                                 if (!HasStationRail(ss.tile)) continue;
 475                                 if (GetTileOwner(ss.tile) != owner) continue;
 476                                 if (DiagDirToAxis((DiagDirection)ss.side) != GetRailStationAxis(ss.tile)) continue; // different axis
 477                                 if (IsStationTileBlocked(ss.tile)) continue; // 'eye-candy' station tile
 478
 479                                 if (!(flags & SF_TRAIN) && HasTrainOnTile(ss.tile)) flags |= SF_TRAIN;
 480                                 newss.side = ss.side;
 481                                 ss.side = (SignalSideEnum)ReverseDiagDir((DiagDirection)ss.side); // exitdir
 482                                 newss.tile += TileOffsByDiagDir((DiagDirection)ss.side);
 483                                 break;
 484
 485                         default:
 486                                 continue; // continue the while() loop
 487                 }
 488
 489                 if (!MaybeAddToTodoSet(newss, ss)) return flags | SF_FULL;
 490         }
 491
 492         return flags;
 493 }
 494
 495
 496 /**
 497  * Determine the state for a signal heading into a tunnel when there is a train in it
 498  * @param tile the tunnel tile
 499  * @return the signal state to set
 500  */
 501 static SignalState GetTunnelSignalState(TileIndex tile)
 502 {
 503         assert(maptile_is_rail_tunnel(tile));
 504
 505         /* signal is red if there is a train on the initial tile */
 506         if (HasTrainOnTile(tile)) return SIGNAL_STATE_RED;
 507
 508         /* otherwise, signal is red iff there is a train near the entry */
 509         TileIndex tile2 = TileAddByDiagDir(tile, GetTunnelBridgeDirection(tile));
 510         VehicleTileFinder iter (GetOtherTunnelEnd(tile));
 511         while (!iter.finished()) {
 512                 Vehicle *v = iter.next();
 513                 if (v->type == VEH_TRAIN && TileVirtXY(v->x_pos, v->y_pos) == tile2) iter.set_found();
 514         }
 515         return iter.was_found() ? SIGNAL_STATE_RED : SIGNAL_STATE_GREEN;
 516 }
 517
 518 /**
 519  * Update signals around segment in _tbuset
 520  *
 521  * @param flags info about segment
 522  */
 523 static void UpdateSignalsAroundSegment(SigFlags flags)
 524 {
 525         SignalPos pos;
 526
 527         while (_tbuset.Get(&pos)) {
 528                 if (!IsRailwayTile(pos.tile)) {
 529                         /* Special signals */
 530                         assert(maptile_is_rail_tunnel(pos.tile));
 531                         assert(maptile_get_tunnel_signal_type(pos.tile) == SIGTYPE_NORMAL);
 532
 533                         bool inwards = pos.td == DiagDirToDiagTrackdir(GetTunnelBridgeDirection(pos.tile));
 534                         SignalState newstate = !(flags & SF_TRAIN) ? SIGNAL_STATE_GREEN :
 535                                 inwards ? GetTunnelSignalState(pos.tile) : SIGNAL_STATE_RED;
 536
 537                         if (newstate != maptile_get_tunnel_signal_state(pos.tile, inwards)) {
 538                                 maptile_set_tunnel_signal_state(pos.tile, inwards, newstate);
 539                                 MarkTileDirtyByTile(pos.tile);
 540                         }
 541
 542                         continue;
 543                 }
 544
 545                 assert(HasSignalOnTrackdir(pos.tile, pos.td));
 546
 547                 SignalType sig = GetSignalType(pos.tile, TrackdirToTrack(pos.td));
 548                 SignalState newstate = SIGNAL_STATE_GREEN;
 549
 550                 /* determine whether the new state is red */
 551                 if (flags & SF_TRAIN) {
 552                         /* train in the segment */
 553                         newstate = SIGNAL_STATE_RED;
 554                 } else {
 555                         /* is it a bidir combo? - then do not count its other signal direction as exit */
 556                         if (sig == SIGTYPE_COMBO && HasSignalOnTrackdir(pos.tile, ReverseTrackdir(pos.td))) {
 557                                 /* at least one more exit */
 558                                 if ((flags & SF_EXIT2) &&
 559                                                 /* no green exit */
 560                                                 (!(flags & SF_GREEN) ||
 561                                                 /* only one green exit, and it is this one - so all other exits are red */
 562                                                 (!(flags & SF_GREEN2) && GetSignalStateByTrackdir(pos.tile, ReverseTrackdir(pos.td)) == SIGNAL_STATE_GREEN))) {
 563                                         newstate = SIGNAL_STATE_RED;
 564                                 }
 565                         } else { // entry, at least one exit, no green exit
 566                                 if (IsPresignalEntry(sig) && (flags & SF_EXIT) && !(flags & SF_GREEN)) newstate = SIGNAL_STATE_RED;
 567                         }
 568                 }
 569
 570                 /* only when the state changes */
 571                 if (newstate != GetSignalStateByTrackdir(pos.tile, pos.td)) {
 572                         if (IsPresignalExit(sig)) {
 573                                 /* for pre-signal exits, add block to the global set */
 574                                 DiagDirection exitdir = TrackdirToExitdir(ReverseTrackdir(pos.td));
 575                                 SignalSideEnum side;
 576                                 if (IsRailBridgeTile(pos.tile)) {
 577                                         side = (exitdir == GetTunnelBridgeDirection(pos.tile)) ? SIDE_FROM_BRIDGE : (SignalSideEnum)exitdir;
 578                                 } else if (IsTunnelTile(pos.tile)) {
 579                                         side = (exitdir == GetTunnelBridgeDirection(pos.tile)) ? SIDE_FROM_TUNNEL : (SignalSideEnum)exitdir;
 580                                 } else {
 581                                         side = (SignalSideEnum)exitdir;
 582                                 }
 583                                 _globset.Add(SignalSideFrom(pos.tile, side)); // do not check for full global set, first update all signals
 584                         }
 585                         SetSignalStateByTrackdir(pos.tile, pos.td, newstate);
 586                         MarkTileDirtyByTile(pos.tile);
 587                 }
 588         }
 589
 590 }
 591
 592
 593 /** Reset all sets after one set overflowed */
 594 static inline void ResetSets()
 595 {
 596         _tbuset.Reset();
 597         _tbdset.Reset();
 598         _globset.Reset();
 599 }
 600
 601
 602 /**
 603  * Updates blocks in _globset buffer
 604  *
 605  * @param owner company whose signals we are updating
 606  * @return state of the first block from _globset
 607  * @pre _globset.IsEmpty() || Company::IsValidID(_owner)
 608  */
 609 SigSegState UpdateSignalsInBuffer()
 610 {
 611         assert(_globset.IsEmpty() || Company::IsValidID(_owner));
 612
 613         SigSegState state = SIGSEG_NONE; // value to return
 614
 615         SignalSide ss;
 616
 617         while (_globset.Get(&ss)) {
 618                 assert(_tbuset.IsEmpty());
 619                 assert(_tbdset.IsEmpty());
 620
 621                 /* After updating signal, data stored are always railway with signals.
 622                  * Other situations happen when data are from outside functions -
 623                  * modification of railbits (including both rail building and removal),
 624                  * train entering/leaving block, train leaving depot...
 625                  */
 626                 switch (GetTileType(ss.tile)) {
 627                         case TT_RAILWAY:
 628                                 if (IsTileSubtype(ss.tile, TT_TRACK)) {
 629                                         /* check if there was something here that got deleted */
 630                                         if (!IsValidDiagDirection((DiagDirection)ss.side)) continue;
 631                                         goto check_track;
 632                                 }
 633                                 assert(ss.side != (SignalSideEnum)GetTunnelBridgeDirection(ss.tile));
 634                                 if (IsValidDiagDirection((DiagDirection)ss.side)) goto check_track;
 635                                 assert(ss.side == SIDE_INTO_BRIDGE || ss.side == SIDE_FROM_BRIDGE);
 636                                 _tbdset.Add(SignalSideFrom(ss.tile, SIDE_INTO_BRIDGE));
 637                                 _tbdset.Add(SignalSideFrom(ss.tile, SIDE_FROM_BRIDGE));
 638                                 break;
 639
 640                         case TT_MISC:
 641                                 if (IsTunnelTile(ss.tile)) {
 642                                         /* 'optimization assert' - do not try to update signals when it is not needed */
 643                                         assert(GetTunnelTransportType(ss.tile) == TRANSPORT_RAIL);
 644                                         if (IsValidDiagDirection((DiagDirection)ss.side)) {
 645                                                 assert(ss.side == (SignalSideEnum)ReverseDiagDir(GetTunnelBridgeDirection(ss.tile)));
 646                                                 goto check_track;
 647                                         } else {
 648                                                 assert(ss.side == SIDE_INTO_TUNNEL || SIDE_FROM_TUNNEL);
 649                                                 _tbdset.Add(SignalSideFrom(ss.tile, SIDE_INTO_TUNNEL));
 650                                                 _tbdset.Add(SignalSideFrom(ss.tile, SIDE_FROM_TUNNEL));
 651                                         }
 652                                         break;
 653                                 }
 654                                 if (IsRailDepotTile(ss.tile)) {
 655                                         /* 'optimization assert' do not try to update signals in other cases */
 656                                         assert(ss.side == SIDE_DEPOT || ss.side == (SignalSideEnum)GetGroundDepotDirection(ss.tile));
 657                                         _tbdset.Add(SignalSideFrom(ss.tile, SIDE_DEPOT)); // start from depot inside
 658                                         break;
 659                                 }
 660                                 if (!IsLevelCrossingTile(ss.tile)) goto next_tile;
 661                                 /* fall through */
 662                         case TT_STATION:
 663                         check_track:
 664                                 assert(IsValidDiagDirection((DiagDirection)ss.side));
 665                                 if ((TrackStatusToTrackBits(GetTileRailwayStatus(ss.tile)) & _enterdir_to_trackbits[ss.side]) != TRACK_BIT_NONE) {
 666                                         /* only add to set when there is some 'interesting' track */
 667                                         _tbdset.Add(ss);
 668                                         _tbdset.Add(SignalSideFrom(ss.tile + TileOffsByDiagDir((DiagDirection)ss.side), (SignalSideEnum)ReverseDiagDir((DiagDirection)ss.side)));
 669                                         break;
 670                                 }
 671                                 /* FALL THROUGH */
 672                         default:
 673                                 /* jump to next tile */
 674                         next_tile:
 675                                 /* check if there was a bridge here but got deleted */
 676                                 if (!IsValidDiagDirection((DiagDirection)ss.side)) continue;
 677                                 ss.tile = ss.tile + TileOffsByDiagDir((DiagDirection)ss.side);
 678                                 ss.side = (SignalSideEnum)ReverseDiagDir((DiagDirection)ss.side);
 679                                 if ((TrackStatusToTrackBits(GetTileRailwayStatus(ss.tile)) & _enterdir_to_trackbits[ss.side]) != TRACK_BIT_NONE) {
 680                                         _tbdset.Add(ss);
 681                                         break;
 682                                 }
 683                                 /* happens when removing a rail that wasn't connected at one or both sides */
 684                                 continue; // continue the while() loop
 685                 }
 686
 687                 assert(!_tbdset.Overflowed()); // it really shouldn't overflow by these one or two items
 688                 assert(!_tbdset.IsEmpty()); // it wouldn't hurt anyone, but shouldn't happen too
 689
 690                 SigFlags flags = ExploreSegment(_owner);
 691
 692                 if (state == SIGSEG_NONE) {
 693                         if (flags & SF_PBS) {
 694                                 state = SIGSEG_PBS;
 695                         } else if ((flags & SF_TRAIN) || ((flags & SF_EXIT) && !(flags & SF_GREEN)) || (flags & SF_FULL)) {
 696                                 state = SIGSEG_FULL;
 697                         } else {
 698                                 state = SIGSEG_FREE;
 699                         }
 700                 }
 701
 702                 /* do not do anything when some buffer was full */
 703                 if (flags & SF_FULL) {
 704                         ResetSets(); // free all sets
 705                         break;
 706                 }
 707
 708                 UpdateSignalsAroundSegment(flags);
 709         }
 710
 711         _owner = INVALID_OWNER;
 712
 713         return state;
 714 }
 715
 716
 717 /**
 718  * Check if signal buffer is empty
 719  * @returns whether the signal buffer is empty
 720  */
 721 bool IsSignalBufferEmpty()
 722 {
 723         return _globset.IsEmpty();
 724 }
 725
 726 /**
 727  * Set signal buffer owner
 728  */
 729 static inline void SetBufferOwner(Owner owner)
 730 {
 731         /* do not allow signal updates for two companies in one run */
 732         assert(_globset.IsEmpty() || owner == _owner);
 733         _owner = owner;
 734 }
 735
 736 /**
 737  * Update signals in buffer if it has too many items
 738  */
 739 static inline void UpdateSignalsInBufferAuto()
 740 {
 741         if (_globset.Items() >= SIG_GLOB_UPDATE) {
 742                 /* too many items, force update */
 743                 UpdateSignalsInBuffer();
 744         }
 745 }
 746
 747
 748 /**
 749  * Add track to signal update buffer
 750  *
 751  * @param tile tile where we start
 752  * @param track track at which ends we will update signals
 753  * @param owner owner whose signals we will update
 754  */
 755 void AddTrackToSignalBuffer(TileIndex tile, Track track, Owner owner)
 756 {
 757         SetBufferOwner(owner);
 758
 759         if (IsRailBridgeTile(tile)) {
 760                 DiagDirection dir = GetTunnelBridgeDirection(tile);
 761                 DiagDirection side;
 762                 side = TrackdirToExitdir(TrackToTrackdir(track));
 763                 _globset.Add(SignalSideFrom(tile, (side == dir) ? SIDE_FROM_BRIDGE : (SignalSideEnum)side));
 764                 side = TrackdirToExitdir(ReverseTrackdir(TrackToTrackdir(track)));
 765                 _globset.Add(SignalSideFrom(tile, (side == dir) ? SIDE_FROM_BRIDGE : (SignalSideEnum)side));
 766         } else if (IsTunnelTile(tile)) {
 767                 DiagDirection dir = GetTunnelBridgeDirection(tile);
 768                 assert(track == DiagDirToDiagTrack(dir));
 769                 _globset.Add(SignalSideFrom(tile, (SignalSideEnum)ReverseDiagDir(dir)));
 770                 _globset.Add(SignalSideFrom(tile, SIDE_FROM_TUNNEL));
 771         } else {
 772                 _globset.Add(SignalSideFrom(tile, (SignalSideEnum)TrackdirToExitdir(TrackToTrackdir(track))));
 773                 _globset.Add(SignalSideFrom(tile, (SignalSideEnum)TrackdirToExitdir(ReverseTrackdir(TrackToTrackdir(track)))));
 774         }
 775
 776         UpdateSignalsInBufferAuto();
 777 }
 778
 779
 780 /**
 781  * Add side of tile to signal update buffer
 782  *
 783  * @param tile tile where we start
 784  * @param side side of tile
 785  * @param owner owner whose signals we will update
 786  */
 787 void AddSideToSignalBuffer(TileIndex tile, DiagDirection side, Owner owner)
 788 {
 789         SetBufferOwner(owner);
 790
 791         assert(IsValidDiagDirection(side));
 792         _globset.Add(SignalSideFrom(tile, (SignalSideEnum)side));
 793
 794         UpdateSignalsInBufferAuto();
 795 }
 796
 797 /**
 798  * Add depot tile to signal update buffer
 799  *
 800  * @param tile tile to add
 801  * @param owner owner whose signals we will update
 802  */
 803 void AddDepotToSignalBuffer(TileIndex tile, Owner owner)
 804 {
 805         SetBufferOwner(owner);
 806
 807         assert(IsDepotTile(tile));
 808         _globset.Add(SignalSideFrom(tile, SIDE_DEPOT));
 809
 810         UpdateSignalsInBufferAuto();
 811 }
 812
 813 /**
 814  * Add bridge tile to signal update buffer
 815  *
 816  * @param tile tile to add
 817  * @param owner owner whose signals we will update
 818  */
 819 void AddBridgeToSignalBuffer(TileIndex tile, Owner owner)
 820 {
 821         SetBufferOwner(owner);
 822
 823         assert(IsRailBridgeTile(tile));
 824         _globset.Add(SignalSideFrom(tile, SIDE_FROM_BRIDGE));
 825
 826         UpdateSignalsInBufferAuto();
 827 }
 828
 829 /**
 830  * Add tunnel tile to signal update buffer
 831  *
 832  * @param tile tile to add
 833  * @param owner owner whose signals we will update
 834  */
 835 void AddTunnelToSignalBuffer(TileIndex tile, Owner owner)
 836 {
 837         SetBufferOwner(owner);
 838
 839         assert(maptile_is_rail_tunnel(tile));
 840         _globset.Add(SignalSideFrom(tile, SIDE_FROM_TUNNEL));
 841
 842         UpdateSignalsInBufferAuto();
 843 }
 844
 845
 846 /**
 847  * Add a pathfinder position to signal update buffer
 848  *
 849  * @param pos position to add
 850  * @param owner owner whose signals we will update
 851  */
 852 void AddPosToSignalBuffer(const RailPathPos &pos, Owner owner)
 853 {
 854         SetBufferOwner(owner);
 855
 856         if (pos.in_wormhole()) {
 857                 _globset.Add(SignalSideFrom(pos.wormhole, IsRailwayTile(pos.wormhole) ? SIDE_INTO_BRIDGE : SIDE_INTO_TUNNEL));
 858         } else if (IsRailDepotTile(pos.tile)) {
 859                 _globset.Add(SignalSideFrom(pos.tile, SIDE_DEPOT));
 860         } else {
 861                 DiagDirection exitdir = TrackdirToExitdir(pos.td);
 862                 SignalSideEnum side;
 863                 if (IsRailBridgeTile(pos.tile)) {
 864                         side = (exitdir == GetTunnelBridgeDirection(pos.tile)) ? SIDE_FROM_BRIDGE : (SignalSideEnum)exitdir;
 865                 } else if (IsTunnelTile(pos.tile)) {
 866                         side = (exitdir == GetTunnelBridgeDirection(pos.tile)) ? SIDE_FROM_TUNNEL : (SignalSideEnum)exitdir;
 867                 } else {
 868                         side = (SignalSideEnum)exitdir;
 869                 }
 870                 _globset.Add(SignalSideFrom(pos.tile, side));
 871         }
 872
 873         UpdateSignalsInBufferAuto();
 874 }