AceTime  2.3.0
Date and time classes for Arduino that support timezones from the TZ Database.
Transition.h
1 /*
2  * MIT License
3  * Copyright (c) 2019 Brian T. Park
4  */
5 
6 #ifndef ACE_TIME_EXTENDED_TRANSITION_H
7 #define ACE_TIME_EXTENDED_TRANSITION_H
8 
9 #include <stdint.h> // uint8_t
10 #include "common/logging.h"
11 #include "local_date_mutation.h"
12 #include "DateTuple.h"
13 
14 class TransitionStorageTest_getFreeAgent;
15 class TransitionStorageTest_getFreeAgent2;
16 class TransitionStorageTest_addFreeAgentToActivePool;
17 class TransitionStorageTest_reservePrior;
18 class TransitionStorageTest_addPriorToCandidatePool;
19 class TransitionStorageTest_addFreeAgentToCandidatePool;
20 class TransitionStorageTest_setFreeAgentAsPriorIfValid;
21 class TransitionStorageTest_addActiveCandidatesToActivePool;
22 class TransitionStorageTest_findTransitionForDateTime;
23 class TransitionStorageTest_resetCandidatePool;
24 
25 class Print;
26 
27 #ifndef ACE_TIME_EXTENDED_ZONE_PROCESSOR_DEBUG
28 #define ACE_TIME_EXTENDED_ZONE_PROCESSOR_DEBUG 0
29 #endif
30 
31 namespace ace_time {
32 namespace extended {
33 
34 inline bool isCompareStatusActive(CompareStatus status) {
35  return status == CompareStatus::kExactMatch
36  || status == CompareStatus::kWithinMatch
37  || status == CompareStatus::kPrior;
38 }
39 
46 template<typename ZEB>
53 
56 
58  ZEB era;
59 
62 
65 
68 
69  void log() const {
70  logging::printf("MatchingEra(");
71  logging::printf("start="); startDateTime.log();
72  logging::printf("; until="); untilDateTime.log();
73  logging::printf("; era=%c", (era.isNull()) ? '-' : '*');
74  logging::printf("; prevMatch=%c", (prevMatch) ? '*' : '-');
75  logging::printf(")");
76  }
77 };
78 
79 //---------------------------------------------------------------------------
80 
113 template <typename ZEB, typename ZPB, typename ZRB>
115 
118 
119 #if ACE_TIME_EXTENDED_ZONE_PROCESSOR_DEBUG
126  ZRB rule;
127 #endif
128 
136 
137  union {
144 
150  };
151 
152  union {
159 
165  };
166 
167 #if ACE_TIME_EXTENDED_ZONE_PROCESSOR_DEBUG
172  DateTuple originalTransitionTime;
173 #endif
174 
177 
185  int32_t offsetSeconds;
186 
188  int32_t deltaSeconds;
189 
196  char abbrev[internal::kAbbrevSize];
197 
198  union {
206 
211  CompareStatus compareStatus;
212  };
213 
214  const char* format() const {
215  return match->era.format();
216  }
217 
219  void log() const {
220  logging::printf("Transition(");
221  if (sizeof(acetime_t) <= sizeof(int)) {
222  logging::printf("start=%d", startEpochSeconds);
223  } else {
224  logging::printf("start=%ld", startEpochSeconds);
225  }
226  logging::printf("; status=%d", compareStatus);
227  logging::printf("; UTC");
230  logging::printf("; tt="); transitionTime.log();
231  logging::printf("; tts="); transitionTimeS.log();
232  logging::printf("; ttu="); transitionTimeU.log();
233  #if ACE_TIME_EXTENDED_ZONE_PROCESSOR_DEBUG
234  if (rule.isNull()) {
235  logging::printf("; rule=-");
236  } else {
237  logging::printf("; rule=");
238  logging::printf("[%d,%d]", rule.fromYear(), rule.toYear());
239  }
240  #endif
241  }
242 
244  static void logHourMinuteSecond(int32_t seconds) {
245  char sign;
246  if (seconds < 0) {
247  sign = '-';
248  seconds = -seconds;
249  } else {
250  sign = '+';
251  }
252  uint16_t minutes = seconds / 60;
253  uint8_t second = seconds - minutes * int32_t(60);
254  uint8_t hour = minutes / 60;
255  uint8_t minute = minutes - hour * 60;
256  if (second == 0) {
257  logging::printf("%c%02u:%02u", sign, (unsigned) hour, (unsigned) minute);
258  } else {
259  logging::printf("%c%02u:%02u:%02u",
260  sign, (unsigned) hour, (unsigned) minute, (unsigned) second);
261  }
262  }
263 
264 #ifdef ACE_TIME_EXTENDED_ZONE_PROCESSOR_DEBUG
266  static void printTransitions(
267  const char* prefix,
268  const TransitionTemplate* const* begin,
269  const TransitionTemplate* const* end) {
270  for (const TransitionTemplate* const* iter = begin; iter != end; ++iter) {
271  logging::printf(prefix);
272  (*iter)->log();
273  logging::printf("\n");
274  }
275  }
276 #endif
277 };
278 
286 template <typename ZEB, typename ZPB, typename ZRB>
290 
292  uint8_t fold;
293 
300  uint8_t num;
301 };
302 
316 template <typename ZEB, typename ZPB, typename ZRB>
324 
326  uint8_t num;
327 };
328 
360 template<uint8_t SIZE, typename ZEB, typename ZPB, typename ZRB>
362  public:
368 
375 
382 
385 
392  void init() {
393  for (uint8_t i = 0; i < SIZE; i++) {
394  mTransitions[i] = &mPool[i];
395  }
396  mIndexPrior = 0;
397  mIndexCandidates = 0;
398  mIndexFree = 0;
399  }
400 
403  return mTransitions[mIndexPrior];
404  }
405 
415  mIndexCandidates = mIndexPrior;
416  mIndexFree = mIndexPrior;
417  }
418 
419  Transition** getCandidatePoolBegin() {
420  return &mTransitions[mIndexCandidates];
421  }
422  Transition** getCandidatePoolEnd() {
423  return &mTransitions[mIndexFree];
424  }
425 
426  Transition** getActivePoolBegin() {
427  return &mTransitions[0];
428  }
429  Transition** getActivePoolEnd() {
430  return &mTransitions[mIndexFree];
431  }
432 
439  if (mIndexFree < SIZE) {
440  // Allocate a free transition.
441  if (mIndexFree >= mAllocSize) {
442  mAllocSize = mIndexFree + 1;
443  }
444  return mTransitions[mIndexFree];
445  } else {
446  // No more transition available in the buffer, so just return the last
447  // one. This will probably cause a bug in the timezone calculations, but
448  // I think this is better than triggering undefined behavior by running
449  // off the end of the mTransitions buffer.
450  return mTransitions[SIZE - 1];
451  }
452  }
453 
462  if (mIndexFree >= SIZE) return;
463  mIndexFree++;
464  mIndexPrior = mIndexFree;
465  mIndexCandidates = mIndexFree;
466  }
467 
477  getFreeAgent(); // allocate a new Transition
478 
479  mIndexCandidates++;
480  mIndexFree++;
481  return &mTransitions[mIndexPrior];
482  }
483 
486  Transition* ft = mTransitions[mIndexFree];
487  Transition* prior = mTransitions[mIndexPrior];
488  if ((prior->isValidPrior && prior->transitionTime < ft->transitionTime)
489  || !prior->isValidPrior) {
490  ft->isValidPrior = true;
491  prior->isValidPrior = false;
492  internal::swap(mTransitions[mIndexPrior], mTransitions[mIndexFree]);
493  }
494  }
495 
502  mIndexCandidates--;
503  }
504 
512  if (mIndexFree >= SIZE) return;
513 
514  // This implementation makes pair-wise swaps to shift the current
515  // Transition leftwards into its correctly sorted position. At first
516  // glance, this seem inefficient compared to the alternative
517  // implementation where we save the current Transition, then slide all the
518  // elements to the left by one position rightwards. However,
519  // MemoryBenchmark shows that this implementation is 46 bytes smaller on
520  // an AVR processor.
521  for (uint8_t i = mIndexFree; i > mIndexCandidates; i--) {
522  Transition* curr = mTransitions[i];
523  Transition* prev = mTransitions[i - 1];
524  if (curr->transitionTime >= prev->transitionTime) break;
525  mTransitions[i] = prev;
526  mTransitions[i - 1] = curr;
527  }
528  mIndexFree++;
529  }
530 
538  if (ACE_TIME_EXTENDED_ZONE_PROCESSOR_DEBUG) {
539  logging::printf("addActiveCandidatesToActivePool()\n");
540  }
541 
542  // Shift active candidates to the left into the Active pool.
543  uint8_t iActive = mIndexPrior;
544  uint8_t iCandidate = mIndexCandidates;
545  for (; iCandidate < mIndexFree; iCandidate++) {
546  if (isCompareStatusActive(mTransitions[iCandidate]->compareStatus)) {
547  if (iActive != iCandidate) {
548  // Must use swap(), because we are moving pointers instead of the
549  // actual Transition objects.
550  internal::swap(mTransitions[iActive], mTransitions[iCandidate]);
551  }
552  ++iActive;
553  }
554  }
555 
556  mIndexPrior = iActive;
557  mIndexCandidates = iActive;
558  mIndexFree = iActive;
559 
560  return mTransitions[iActive - 1];
561  }
562 
572  const {
573  if (ACE_TIME_EXTENDED_ZONE_PROCESSOR_DEBUG) {
574  logging::printf(
575  "findTransitionForSeconds(): mIndexFree: %d\n", mIndexFree);
576  }
577 
578  const Transition* prev = nullptr;
579  const Transition* curr = nullptr;
580  const Transition* next = nullptr;
581  for (uint8_t i = 0; i < mIndexFree; i++) {
582  next = mTransitions[i];
583  if (next->startEpochSeconds > epochSeconds) break;
584  prev = curr;
585  curr = next;
586  next = nullptr;
587  }
588 
589  uint8_t fold;
590  uint8_t num;
591  calcFoldAndOverlap(&fold, &num, prev, curr, next, epochSeconds);
592  //fprintf(stderr, "prev=%p;curr=%p;next=%p;fold=%d;num=%d\n",
593  // prev, curr, next, fold, num);
594  return TransitionForSeconds{curr, fold, num};
595  }
596 
598  static void calcFoldAndOverlap(
599  uint8_t* fold,
600  uint8_t* num,
601  const Transition* prev,
602  const Transition* curr,
603  const Transition* next,
604  acetime_t epochSeconds) {
605 
606  if (curr == nullptr) {
607  *fold = 0;
608  *num = 0;
609  return;
610  }
611 
612  // Check if within forward overlap shadow from prev
613  bool isOverlap;
614  if (prev == nullptr) {
615  isOverlap = false;
616  } else {
617  // Extract the shift from prev transition. Can be 0 in some cases where
618  // the zone changed from DST of one zone to the STD into another zone,
619  // causing the overall UTC offset to remain unchanged.
620  acetime_t shiftSeconds = subtractDateTuple(
621  curr->startDateTime, prev->untilDateTime);
622  if (shiftSeconds >= 0) {
623  // spring forward, or unchanged
624  isOverlap = false;
625  } else {
626  // Check if within the forward overlap shadow from prev
627  isOverlap = epochSeconds - curr->startEpochSeconds < -shiftSeconds;
628  }
629  }
630  if (isOverlap) {
631  *fold = 1; // epochSeconds selects the second match
632  *num = 2;
633  return;
634  }
635 
636  // Check if within backward overlap shawdow from next
637  if (next == nullptr) {
638  isOverlap = false;
639  } else {
640  // Extract the shift to next transition. Can be 0 in some cases where
641  // the zone changed from DST of one zone to the STD into another zone,
642  // causing the overall UTC offset to remain unchanged.
643  acetime_t shiftSeconds = subtractDateTuple(
644  next->startDateTime, curr->untilDateTime);
645  if (shiftSeconds >= 0) {
646  // spring forward, or unchanged
647  isOverlap = false;
648  } else {
649  // Check if within the backward overlap shadow from next
650  isOverlap = next->startEpochSeconds - epochSeconds <= -shiftSeconds;
651  }
652  }
653  if (isOverlap) {
654  *fold = 0; // epochSeconds selects the first match
655  *num = 2;
656  return;
657  }
658 
659  // Normal single match, no overlap.
660  *fold = 0;
661  *num = 1;
662  }
663 
670  const LocalDateTime& ldt) const {
671  // Convert LocalDateTime to DateTuple.
672  DateTuple localDate{
673  ldt.year(),
674  ldt.month(),
675  ldt.day(),
676  ((ldt.hour() * int32_t(60) + ldt.minute()) * 60 + ldt.second()),
678  };
679 
680  // Examine adjacent pairs of Transitions, looking for an exact match, gap,
681  // or overlap.
682  const Transition* prev = nullptr;
683  const Transition* curr = nullptr;
684  uint8_t num = 0;
685  for (uint8_t i = 0; i < mIndexFree; i++) {
686  curr = mTransitions[i];
687 
688  const DateTuple& startDateTime = curr->startDateTime;
689  const DateTuple& untilDateTime = curr->untilDateTime;
690  bool isExactMatch = (startDateTime <= localDate)
691  && (localDate < untilDateTime);
692 
693  if (isExactMatch) {
694  // Check for a previous exact match to detect an overlap.
695  if (num == 1) {
696  num++;
697  break;
698  }
699 
700  // Loop again to detect an overlap.
701  num = 1;
702  } else if (startDateTime > localDate) {
703  // Exit loop since no more candidate transition.
704  break;
705  }
706 
707  prev = curr;
708 
709  // Set the curr to nullptr so that if the loop runs off the end of the
710  // list of Transitions, the curr is marked as nullptr.
711  curr = nullptr;
712  }
713 
714  // Check if the prev was an exact match, and set the curr to be identical.
715  // avoid confusion.
716  if (num == 1) {
717  curr = prev;
718  }
719 
720  // This should get optimized by RVO.
721  return TransitionForDateTime{prev, curr, num};
722  }
723 
725  void log() const {
726  logging::printf("TransitionStorage: ");
727  logging::printf("SIZE=%d, mAllocSize=%d\n", SIZE, mAllocSize);
728  int nActives = mIndexPrior;
729  int nPrior = mIndexCandidates - mIndexPrior;
730  int nCandidates = mIndexFree - mIndexCandidates;
731  int nAllocFree = mAllocSize - mIndexFree;
732  int nVirginFree = SIZE - mAllocSize;
733 
734  logging::printf(" Actives: %d\n", nActives);
736  " ", &mTransitions[0], &mTransitions[mIndexPrior]);
737 
738  logging::printf(" Prior: %d\n", nPrior);
740  " ", &mTransitions[mIndexPrior], &mTransitions[mIndexCandidates]);
741 
742  logging::printf(" Candidates: %d\n", nCandidates);
744  " ", &mTransitions[mIndexCandidates], &mTransitions[mIndexFree]);
745 
746  logging::printf(" Allocated Free: %d\n", nAllocFree);
747  logging::printf(" Virgin Free: %d\n", nVirginFree);
748  }
749 
751  void resetAllocSize() { mAllocSize = 0; }
752 
758  uint8_t getAllocSize() const { return mAllocSize; }
759 
760  private:
761  friend class ::TransitionStorageTest_getFreeAgent;
762  friend class ::TransitionStorageTest_getFreeAgent2;
763  friend class ::TransitionStorageTest_addFreeAgentToActivePool;
764  friend class ::TransitionStorageTest_reservePrior;
765  friend class ::TransitionStorageTest_addPriorToCandidatePool;
766  friend class ::TransitionStorageTest_addFreeAgentToCandidatePool;
767  friend class ::TransitionStorageTest_setFreeAgentAsPriorIfValid;
768  friend class ::TransitionStorageTest_addActiveCandidatesToActivePool;
769  friend class ::TransitionStorageTest_findTransitionForDateTime;
770  friend class ::TransitionStorageTest_resetCandidatePool;
771 
773  Transition* getTransition(uint8_t i) {
774  return mTransitions[i];
775  }
776 
777  Transition mPool[SIZE];
778  Transition* mTransitions[SIZE];
779  uint8_t mIndexPrior;
780  uint8_t mIndexCandidates;
781  uint8_t mIndexFree;
782 
784  uint8_t mAllocSize = 0;
785 };
786 
787 } // namespace extended
788 } // namespace ace_time
789 
790 #endif
Class that holds the date-time as the components (year, month, day, hour, minute, second) without reg...
Definition: LocalDateTime.h:30
uint8_t day() const
Return the day of the month.
uint8_t month() const
Return the month with January=1, December=12.
uint8_t second() const
Return the second.
uint8_t minute() const
Return the minute.
uint8_t hour() const
Return the hour.
int16_t year() const
Return the year.
A heap manager which is specialized and tuned to manage a collection of Transitions,...
Definition: Transition.h:361
void resetAllocSize()
Reset the current allocation size.
Definition: Transition.h:751
void addFreeAgentToActivePool()
Immediately add the free agent Transition at index mIndexFree to the Active pool.
Definition: Transition.h:461
TransitionForSecondsTemplate< ZEB, ZPB, ZRB > TransitionForSeconds
Template instantiation of TransitionForSecondsTemplate used by this class.
Definition: Transition.h:374
TransitionForDateTimeTemplate< ZEB, ZPB, ZRB > TransitionForDateTime
Template instantiation of TransitionForDateTimeTemplate used by this class.
Definition: Transition.h:381
void init()
Initialize all pools to 0 size, usually when a new year is initialized.
Definition: Transition.h:392
void setFreeAgentAsPriorIfValid()
Set the free agent transition as the most recent prior.
Definition: Transition.h:485
Transition * getFreeAgent()
Return a pointer to the first Transition in the free pool.
Definition: Transition.h:438
TransitionTemplate< ZEB, ZPB, ZRB > Transition
Template instantiation of TransitionTemplate used by this class.
Definition: Transition.h:367
void resetCandidatePool()
Empty the Candidate pool by resetting the various indexes.
Definition: Transition.h:414
static void calcFoldAndOverlap(uint8_t *fold, uint8_t *num, const Transition *prev, const Transition *curr, const Transition *next, acetime_t epochSeconds)
Calculate the fold and num parameters of TransitionForSecond.
Definition: Transition.h:598
uint8_t getAllocSize() const
Return the maximum number of transitions which was allocated.
Definition: Transition.h:758
void addFreeAgentToCandidatePool()
Add the free agent Transition at index mIndexFree to the Candidate pool, sorted by transitionTime.
Definition: Transition.h:511
Transition * getPrior()
Return the current prior transition.
Definition: Transition.h:402
TransitionForDateTime findTransitionForDateTime(const LocalDateTime &ldt) const
Return the candidate Transitions matching the given dateTime.
Definition: Transition.h:669
Transition * addActiveCandidatesToActivePool()
Add active candidates into the Active pool, and collapse the Candidate pool.
Definition: Transition.h:537
void addPriorToCandidatePool()
Add the current prior into the Candidates pool.
Definition: Transition.h:501
TransitionForSeconds findTransitionForSeconds(acetime_t epochSeconds) const
Return the Transition matching the given epochSeconds.
Definition: Transition.h:571
Transition ** reservePrior()
Allocate a free Transition then add it to the Prior pool.
Definition: Transition.h:476
void log() const
Verify that the indexes are valid.
Definition: Transition.h:725
int32_t acetime_t
Type for the number of seconds from epoch.
Definition: common.h:24
A tuple that represents a date and time.
Definition: DateTuple.h:36
void log() const
Used only for debugging.
Definition: DateTuple.h:50
Data structure that captures the matching ZoneEra and its ZoneRule transitions for a given year.
Definition: Transition.h:47
MatchingEraTemplate * prevMatch
The previous MatchingEra, needed to interpret startDateTime.
Definition: Transition.h:61
ZEB era
The ZoneEra that matched the given year.
Definition: Transition.h:58
DateTuple untilDateTime
The effective until time of the matching ZoneEra.
Definition: Transition.h:55
int32_t lastOffsetSeconds
The STD offset of the last Transition in this MatchingEra.
Definition: Transition.h:64
DateTuple startDateTime
The effective start time of the matching ZoneEra, which uses the UTC offsets of the previous matching...
Definition: Transition.h:52
int32_t lastDeltaSeconds
The DST offset of the last Transition in this MatchingEra.
Definition: Transition.h:67
The result of the findTransitionForDateTime(const LocalDatetime& ldt) method which can return 0,...
Definition: Transition.h:317
uint8_t num
Number of matches: 0, 1, 2.
Definition: Transition.h:326
const TransitionTemplate< ZEB, ZPB, ZRB > * prev
The previous transition.
Definition: Transition.h:320
const TransitionTemplate< ZEB, ZPB, ZRB > * curr
The matching transition, or null if not found or in gap.
Definition: Transition.h:323
Tuple of a matching Transition and its 'fold'.
Definition: Transition.h:287
uint8_t fold
1 if corresponding datetime occurred the second time
Definition: Transition.h:292
const TransitionTemplate< ZEB, ZPB, ZRB > * curr
The matching transition, or null if not found.
Definition: Transition.h:289
uint8_t num
Number of occurrences of the resulting LocalDateTime: 0, 1, or 2.
Definition: Transition.h:300
Represents an interval of time where the time zone obeyed a certain UTC offset and DST delta.
Definition: Transition.h:114
static void printTransitions(const char *prefix, const TransitionTemplate *const *begin, const TransitionTemplate *const *end)
Print an iterable of Transitions from 'begin' to 'end'.
Definition: Transition.h:266
int32_t offsetSeconds
The base offset minutes, not the total effective UTC offset.
Definition: Transition.h:185
bool isValidPrior
During findCandidateTransitions(), this flag indicates whether the current transition is a valid "pri...
Definition: Transition.h:205
DateTuple transitionTime
The original transition time, usually 'w' but sometimes 's' or 'u'.
Definition: Transition.h:135
acetime_t startEpochSeconds
The calculated transition time of the given rule.
Definition: Transition.h:176
DateTuple transitionTimeS
Version of transitionTime in 's' mode, using the UTC offset of the previous Transition.
Definition: Transition.h:143
DateTuple untilDateTime
Until time expressed using the UTC offset of the current Transition.
Definition: Transition.h:164
void log() const
Used only for debugging.
Definition: Transition.h:219
DateTuple transitionTimeU
Version of transitionTime in 'u' mode, using the UTC offset of the previous transition.
Definition: Transition.h:158
CompareStatus compareStatus
During processTransitionCompareStatus(), this flag indicates how the transition falls within the time...
Definition: Transition.h:211
int32_t deltaSeconds
The DST delta seconds.
Definition: Transition.h:188
DateTuple startDateTime
Start time expressed using the UTC offset of the current Transition.
Definition: Transition.h:149
char abbrev[internal::kAbbrevSize]
The calculated effective time zone abbreviation, e.g.
Definition: Transition.h:196
static void logHourMinuteSecond(int32_t seconds)
Print seconds as [+/-]hh:mm[:ss].
Definition: Transition.h:244
const MatchingEraTemplate< ZEB > * match
The match which generated this Transition.
Definition: Transition.h:117
static const uint8_t kSuffixW
Represents 'w' or wall time.
Definition: ZoneInfoLow.h:62