AceTime  3.0.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 D>
53 
56 
58  typename D::ZoneEraBroker 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 
111 template <typename D>
113 
116 
117 #if ACE_TIME_EXTENDED_ZONE_PROCESSOR_DEBUG
124  typename D::ZoneRuleBroker rule;
125 #endif
126 
134 
135  union {
142 
148  };
149 
150  union {
157 
163  };
164 
165 #if ACE_TIME_EXTENDED_ZONE_PROCESSOR_DEBUG
170  DateTuple originalTransitionTime;
171 #endif
172 
175 
177  int32_t offsetSeconds;
178 
180  int32_t deltaSeconds;
181 
189 
190  union {
198 
203  CompareStatus compareStatus;
204  };
205 
206  const char* format() const {
207  return match->era.format();
208  }
209 
211  void log() const {
212  logging::printf("Transition(");
213  if (sizeof(acetime_t) <= sizeof(int)) {
214  logging::printf("start=%d", startEpochSeconds);
215  } else {
216  logging::printf("start=%ld", startEpochSeconds);
217  }
218  logging::printf("; status=%d", compareStatus);
219  logging::printf("; UTC");
222  logging::printf("; tt="); transitionTime.log();
223  logging::printf("; tts="); transitionTimeS.log();
224  logging::printf("; ttu="); transitionTimeU.log();
225  #if ACE_TIME_EXTENDED_ZONE_PROCESSOR_DEBUG
226  if (rule.isNull()) {
227  logging::printf("; rule=-");
228  } else {
229  logging::printf("; rule=");
230  logging::printf("[%d,%d]", rule.fromYear(), rule.toYear());
231  }
232  #endif
233  }
234 
236  static void logHourMinuteSecond(int32_t seconds) {
237  char sign;
238  if (seconds < 0) {
239  sign = '-';
240  seconds = -seconds;
241  } else {
242  sign = '+';
243  }
244  uint16_t minutes = seconds / 60;
245  uint8_t second = seconds - minutes * int32_t(60);
246  uint8_t hour = minutes / 60;
247  uint8_t minute = minutes - hour * 60;
248  if (second == 0) {
249  logging::printf("%c%02u:%02u", sign, (unsigned) hour, (unsigned) minute);
250  } else {
251  logging::printf("%c%02u:%02u:%02u",
252  sign, (unsigned) hour, (unsigned) minute, (unsigned) second);
253  }
254  }
255 
256 #ifdef ACE_TIME_EXTENDED_ZONE_PROCESSOR_DEBUG
258  static void printTransitions(
259  const char* prefix,
260  const TransitionTemplate* const* begin,
261  const TransitionTemplate* const* end) {
262  for (const TransitionTemplate* const* iter = begin; iter != end; ++iter) {
263  logging::printf(prefix);
264  (*iter)->log();
265  logging::printf("\n");
266  }
267  }
268 #endif
269 };
270 
278 template <typename D>
282 
284  uint8_t fold;
285 
292  uint8_t num;
293 };
294 
308 template <typename D>
316 
318  uint8_t num;
319 };
320 
350 template<uint8_t SIZE, typename D>
352  public:
358 
365 
372 
375 
382  void init() {
383  for (uint8_t i = 0; i < SIZE; i++) {
384  mTransitions[i] = &mPool[i];
385  }
386  mIndexPrior = 0;
387  mIndexCandidates = 0;
388  mIndexFree = 0;
389  }
390 
393  return mTransitions[mIndexPrior];
394  }
395 
405  mIndexCandidates = mIndexPrior;
406  mIndexFree = mIndexPrior;
407  }
408 
409  Transition** getCandidatePoolBegin() {
410  return &mTransitions[mIndexCandidates];
411  }
412  Transition** getCandidatePoolEnd() {
413  return &mTransitions[mIndexFree];
414  }
415 
416  Transition** getActivePoolBegin() {
417  return &mTransitions[0];
418  }
419  Transition** getActivePoolEnd() {
420  return &mTransitions[mIndexFree];
421  }
422 
429  if (mIndexFree < SIZE) {
430  // Allocate a free transition.
431  if (mIndexFree >= mAllocSize) {
432  mAllocSize = mIndexFree + 1;
433  }
434  return mTransitions[mIndexFree];
435  } else {
436  // No more transition available in the buffer, so just return the last
437  // one. This will probably cause a bug in the timezone calculations, but
438  // I think this is better than triggering undefined behavior by running
439  // off the end of the mTransitions buffer.
440  return mTransitions[SIZE - 1];
441  }
442  }
443 
452  if (mIndexFree >= SIZE) return;
453  mIndexFree++;
454  mIndexPrior = mIndexFree;
455  mIndexCandidates = mIndexFree;
456  }
457 
467  getFreeAgent(); // allocate a new Transition
468 
469  mIndexCandidates++;
470  mIndexFree++;
471  return &mTransitions[mIndexPrior];
472  }
473 
476  Transition* ft = mTransitions[mIndexFree];
477  Transition* prior = mTransitions[mIndexPrior];
478  if ((prior->isValidPrior && prior->transitionTime < ft->transitionTime)
479  || !prior->isValidPrior) {
480  ft->isValidPrior = true;
481  prior->isValidPrior = false;
482  swap(mTransitions[mIndexPrior], mTransitions[mIndexFree]);
483  }
484  }
485 
492  mIndexCandidates--;
493  }
494 
502  if (mIndexFree >= SIZE) return;
503 
504  // This implementation makes pair-wise swaps to shift the current
505  // Transition leftwards into its correctly sorted position. At first
506  // glance, this seem inefficient compared to the alternative
507  // implementation where we save the current Transition, then slide all the
508  // elements to the left by one position rightwards. However,
509  // MemoryBenchmark shows that this implementation is 46 bytes smaller on
510  // an AVR processor.
511  for (uint8_t i = mIndexFree; i > mIndexCandidates; i--) {
512  Transition* curr = mTransitions[i];
513  Transition* prev = mTransitions[i - 1];
514  if (curr->transitionTime >= prev->transitionTime) break;
515  mTransitions[i] = prev;
516  mTransitions[i - 1] = curr;
517  }
518  mIndexFree++;
519  }
520 
528  if (ACE_TIME_EXTENDED_ZONE_PROCESSOR_DEBUG) {
529  logging::printf("addActiveCandidatesToActivePool()\n");
530  }
531 
532  // Shift active candidates to the left into the Active pool.
533  uint8_t iActive = mIndexPrior;
534  uint8_t iCandidate = mIndexCandidates;
535  for (; iCandidate < mIndexFree; iCandidate++) {
536  if (isCompareStatusActive(mTransitions[iCandidate]->compareStatus)) {
537  if (iActive != iCandidate) {
538  // Must use swap(), because we are moving pointers instead of the
539  // actual Transition objects.
540  swap(mTransitions[iActive], mTransitions[iCandidate]);
541  }
542  ++iActive;
543  }
544  }
545 
546  mIndexPrior = iActive;
547  mIndexCandidates = iActive;
548  mIndexFree = iActive;
549 
550  return mTransitions[iActive - 1];
551  }
552 
562  const {
563  if (ACE_TIME_EXTENDED_ZONE_PROCESSOR_DEBUG) {
564  logging::printf(
565  "findTransitionForSeconds(): mIndexFree: %d\n", mIndexFree);
566  }
567 
568  const Transition* prev = nullptr;
569  const Transition* curr = nullptr;
570  const Transition* next = nullptr;
571  for (uint8_t i = 0; i < mIndexFree; i++) {
572  next = mTransitions[i];
573  if (next->startEpochSeconds > epochSeconds) break;
574  prev = curr;
575  curr = next;
576  next = nullptr;
577  }
578 
579  uint8_t fold;
580  uint8_t num;
581  calcFoldAndOverlap(&fold, &num, prev, curr, next, epochSeconds);
582  //fprintf(stderr, "prev=%p;curr=%p;next=%p;fold=%d;num=%d\n",
583  // prev, curr, next, fold, num);
584  return TransitionForSeconds{curr, fold, num};
585  }
586 
606  static void calcFoldAndOverlap(
607  uint8_t* fold,
608  uint8_t* num,
609  const Transition* prev,
610  const Transition* curr,
611  const Transition* next,
612  acetime_t epochSeconds) {
613 
614  if (curr == nullptr) {
615  *fold = 0;
616  *num = 0;
617  return;
618  }
619 
620  // Check if within forward overlap shadow from prev
621  bool isOverlap;
622  if (prev == nullptr) {
623  isOverlap = false;
624  } else {
625  // Extract the shift from prev transition. Can be 0 in some cases where
626  // the zone changed from DST of one zone to the STD into another zone,
627  // causing the overall UTC offset to remain unchanged.
628  acetime_t shiftSeconds = subtractDateTuple(
629  curr->startDateTime, prev->untilDateTime);
630  if (shiftSeconds >= 0) {
631  // spring forward, or unchanged
632  isOverlap = false;
633  } else {
634  // Check if within the forward overlap shadow from prev
635  isOverlap = epochSeconds - curr->startEpochSeconds < -shiftSeconds;
636  }
637  }
638  if (isOverlap) {
639  *fold = 1; // epochSeconds selects the second match
640  *num = 2;
641  return;
642  }
643 
644  // Check if within backward overlap shawdow from next
645  if (next == nullptr) {
646  isOverlap = false;
647  } else {
648  // Extract the shift to next transition. Can be 0 in some cases where
649  // the zone changed from DST of one zone to the STD into another zone,
650  // causing the overall UTC offset to remain unchanged.
651  acetime_t shiftSeconds = subtractDateTuple(
652  next->startDateTime, curr->untilDateTime);
653  if (shiftSeconds >= 0) {
654  // spring forward, or unchanged
655  isOverlap = false;
656  } else {
657  // Check if within the backward overlap shadow from next
658  isOverlap = next->startEpochSeconds - epochSeconds <= -shiftSeconds;
659  }
660  }
661  if (isOverlap) {
662  *fold = 0; // epochSeconds selects the first match
663  *num = 2;
664  return;
665  }
666 
667  // Normal single match, no overlap.
668  *fold = 0;
669  *num = 1;
670  }
671 
678  const LocalDateTime& ldt) const {
679  // Convert LocalDateTime to DateTuple.
680  DateTuple localDate{
681  ldt.year(),
682  ldt.month(),
683  ldt.day(),
684  ((ldt.hour() * int32_t(60) + ldt.minute()) * 60 + ldt.second()),
686  };
687 
688  // Examine adjacent pairs of Transitions, looking for an exact match, gap,
689  // or overlap.
690  const Transition* prev = nullptr;
691  const Transition* curr = nullptr;
692  uint8_t num = 0;
693  for (uint8_t i = 0; i < mIndexFree; i++) {
694  curr = mTransitions[i];
695 
696  const DateTuple& startDateTime = curr->startDateTime;
697  const DateTuple& untilDateTime = curr->untilDateTime;
698  bool isExactMatch = (startDateTime <= localDate)
699  && (localDate < untilDateTime);
700 
701  if (isExactMatch) {
702  // Check for a previous exact match to detect an overlap.
703  if (num == 1) {
704  num++;
705  break;
706  }
707 
708  // Loop again to detect an overlap.
709  num = 1;
710  } else if (startDateTime > localDate) {
711  // Exit loop since no more candidate transition.
712  break;
713  }
714 
715  prev = curr;
716 
717  // Set the curr to nullptr so that if the loop runs off the end of the
718  // list of Transitions, the curr is marked as nullptr.
719  curr = nullptr;
720  }
721 
722  // Check if the prev was an exact match, and set the curr to be identical.
723  // avoid confusion.
724  if (num == 1) {
725  curr = prev;
726  }
727 
728  // This should get optimized by RVO.
729  return TransitionForDateTime{prev, curr, num};
730  }
731 
733  void log() const {
734  logging::printf("TransitionStorage: ");
735  logging::printf("SIZE=%d, mAllocSize=%d\n", SIZE, mAllocSize);
736  int nActives = mIndexPrior;
737  int nPrior = mIndexCandidates - mIndexPrior;
738  int nCandidates = mIndexFree - mIndexCandidates;
739  int nAllocFree = mAllocSize - mIndexFree;
740  int nVirginFree = SIZE - mAllocSize;
741 
742  logging::printf(" Actives: %d\n", nActives);
744  " ", &mTransitions[0], &mTransitions[mIndexPrior]);
745 
746  logging::printf(" Prior: %d\n", nPrior);
748  " ", &mTransitions[mIndexPrior], &mTransitions[mIndexCandidates]);
749 
750  logging::printf(" Candidates: %d\n", nCandidates);
752  " ", &mTransitions[mIndexCandidates], &mTransitions[mIndexFree]);
753 
754  logging::printf(" Allocated Free: %d\n", nAllocFree);
755  logging::printf(" Virgin Free: %d\n", nVirginFree);
756  }
757 
759  void resetAllocSize() { mAllocSize = 0; }
760 
766  uint8_t getAllocSize() const { return mAllocSize; }
767 
768  private:
769  friend class ::TransitionStorageTest_getFreeAgent;
770  friend class ::TransitionStorageTest_getFreeAgent2;
771  friend class ::TransitionStorageTest_addFreeAgentToActivePool;
772  friend class ::TransitionStorageTest_reservePrior;
773  friend class ::TransitionStorageTest_addPriorToCandidatePool;
774  friend class ::TransitionStorageTest_addFreeAgentToCandidatePool;
775  friend class ::TransitionStorageTest_setFreeAgentAsPriorIfValid;
776  friend class ::TransitionStorageTest_addActiveCandidatesToActivePool;
777  friend class ::TransitionStorageTest_findTransitionForDateTime;
778  friend class ::TransitionStorageTest_resetCandidatePool;
779 
781  Transition* getTransition(uint8_t i) {
782  return mTransitions[i];
783  }
784 
785  Transition mPool[SIZE];
786  Transition* mTransitions[SIZE];
787  uint8_t mIndexPrior;
788  uint8_t mIndexCandidates;
789  uint8_t mIndexFree;
790 
792  uint8_t mAllocSize = 0;
793 };
794 
795 } // namespace extended
796 } // namespace ace_time
797 
798 #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:351
void setFreeAgentAsPriorIfValid()
Set the free agent transition as the most recent prior.
Definition: Transition.h:475
Transition * getFreeAgent()
Return a pointer to the first Transition in the free pool.
Definition: Transition.h:428
TransitionTemplate< D > Transition
Template instantiation of TransitionTemplate used by this class.
Definition: Transition.h:357
void addPriorToCandidatePool()
Add the current prior into the Candidates pool.
Definition: Transition.h:491
uint8_t getAllocSize() const
Return the maximum number of transitions which was allocated.
Definition: Transition.h:766
Transition * addActiveCandidatesToActivePool()
Add active candidates into the Active pool, and collapse the Candidate pool.
Definition: Transition.h:527
void resetCandidatePool()
Empty the Candidate pool by resetting the various indexes.
Definition: Transition.h:404
void resetAllocSize()
Reset the current allocation size.
Definition: Transition.h:759
void addFreeAgentToActivePool()
Immediately add the free agent Transition at index mIndexFree to the Active pool.
Definition: Transition.h:451
TransitionForSecondsTemplate< D > TransitionForSeconds
Template instantiation of TransitionForSecondsTemplate used by this class.
Definition: Transition.h:364
TransitionForDateTimeTemplate< D > TransitionForDateTime
Template instantiation of TransitionForDateTimeTemplate used by this class.
Definition: Transition.h:371
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:606
Transition * getPrior()
Return the current prior transition.
Definition: Transition.h:392
TransitionForDateTime findTransitionForDateTime(const LocalDateTime &ldt) const
Return the candidate Transitions matching the given dateTime.
Definition: Transition.h:677
void addFreeAgentToCandidatePool()
Add the free agent Transition at index mIndexFree to the Candidate pool, sorted by transitionTime.
Definition: Transition.h:501
Transition ** reservePrior()
Allocate a free Transition then add it to the Prior pool.
Definition: Transition.h:466
TransitionForSeconds findTransitionForSeconds(acetime_t epochSeconds) const
Return the Transition matching the given epochSeconds.
Definition: Transition.h:561
void init()
Initialize all pools to 0 size, usually when a new year is initialized.
Definition: Transition.h:382
void log() const
Verify that the indexes are valid.
Definition: Transition.h:733
void swap(T &a, T &b)
Swap 2 parameters.
Definition: common.h:48
const uint8_t kAbbrevSize
Size of the c-string buffer needed to hold a time zone abbreviation.
Definition: common.h:44
int32_t acetime_t
Type for the number of seconds from epoch.
Definition: common.h:24
static const uint8_t kSuffixW
Represents 'w' or wall time.
Definition: ZoneInfoLow.h:88
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
int32_t lastDeltaSeconds
The DST offset of the last Transition in this MatchingEra.
Definition: Transition.h:67
MatchingEraTemplate * prevMatch
The previous MatchingEra, needed to interpret startDateTime.
Definition: Transition.h:61
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 lastOffsetSeconds
The STD offset of the last Transition in this MatchingEra.
Definition: Transition.h:64
DateTuple untilDateTime
The effective until time of the matching ZoneEra.
Definition: Transition.h:55
D::ZoneEraBroker era
The ZoneEra that matched the given year.
Definition: Transition.h:58
The result of the findTransitionForDateTime(const LocalDatetime& ldt) method which can return 0,...
Definition: Transition.h:309
const TransitionTemplate< D > * curr
The matching transition, or null if not found or in gap.
Definition: Transition.h:315
const TransitionTemplate< D > * prev
The previous transition.
Definition: Transition.h:312
uint8_t num
Number of matches: 0, 1, 2.
Definition: Transition.h:318
Tuple of a matching Transition and its 'fold'.
Definition: Transition.h:279
const TransitionTemplate< D > * curr
The matching transition, or null if not found.
Definition: Transition.h:281
uint8_t num
Number of occurrences of the resulting LocalDateTime: 0, 1, or 2.
Definition: Transition.h:292
uint8_t fold
1 if corresponding datetime occurred the second time
Definition: Transition.h:284
Represents an interval of time where the time zone obeyed a certain UTC offset and DST delta.
Definition: Transition.h:112
static void logHourMinuteSecond(int32_t seconds)
Print seconds as [+/-]hh:mm[:ss].
Definition: Transition.h:236
DateTuple transitionTimeU
Version of transitionTime in 'u' mode, using the UTC offset of the previous transition.
Definition: Transition.h:156
void log() const
Used only for debugging.
Definition: Transition.h:211
DateTuple transitionTime
The original transition time, usually 'w' but sometimes 's' or 'u'.
Definition: Transition.h:133
const MatchingEraTemplate< D > * match
The match which generated this Transition.
Definition: Transition.h:115
DateTuple startDateTime
Start time expressed using the UTC offset of the current Transition.
Definition: Transition.h:147
CompareStatus compareStatus
During processTransitionCompareStatus(), this flag indicates how the transition falls within the time...
Definition: Transition.h:203
int32_t deltaSeconds
The DST delta seconds.
Definition: Transition.h:180
bool isValidPrior
During findCandidateTransitions(), this flag indicates whether the current transition is a valid "pri...
Definition: Transition.h:197
char abbrev[kAbbrevSize]
The calculated effective time zone abbreviation, e.g.
Definition: Transition.h:188
acetime_t startEpochSeconds
The calculated transition time of the given rule.
Definition: Transition.h:174
DateTuple untilDateTime
Until time expressed using the UTC offset of the current Transition.
Definition: Transition.h:162
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:258
DateTuple transitionTimeS
Version of transitionTime in 's' mode, using the UTC offset of the previous Transition.
Definition: Transition.h:141
int32_t offsetSeconds
The standard time offset seconds, not the total offset.
Definition: Transition.h:177