AceTime  2.2.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  int16_t offsetMinutes;
186 
188  int16_t deltaMinutes;
189 
191  char abbrev[internal::kAbbrevSize];
192 
194  const char* letter;
195 
196  union {
204 
209  CompareStatus compareStatus;
210  };
211 
212  const char* format() const {
213  return match->era.format();
214  }
215 
217  void log() const {
218  logging::printf("Transition(");
219  if (sizeof(acetime_t) <= sizeof(int)) {
220  logging::printf("start=%d", startEpochSeconds);
221  } else {
222  logging::printf("start=%ld", startEpochSeconds);
223  }
224  logging::printf("; status=%d", compareStatus);
225  logging::printf("; UTC");
228  logging::printf("; tt="); transitionTime.log();
229  logging::printf("; tts="); transitionTimeS.log();
230  logging::printf("; ttu="); transitionTimeU.log();
231  #if ACE_TIME_EXTENDED_ZONE_PROCESSOR_DEBUG
232  if (rule.isNull()) {
233  logging::printf("; rule=-");
234  } else {
235  logging::printf("; rule=");
236  logging::printf("[%d,%d]", rule.fromYear(), rule.toYear());
237  }
238  #endif
239  }
240 
242  static void logHourMinute(int16_t minutes) {
243  char sign;
244  if (minutes < 0) {
245  sign = '-';
246  minutes = -minutes;
247  } else {
248  sign = '+';
249  }
250  uint8_t hour = minutes / 60;
251  uint8_t minute = minutes - hour * 60;
252  logging::printf("%c%02u:%02u", sign, (unsigned) hour, (unsigned) minute);
253  }
254 
255 #ifdef ACE_TIME_EXTENDED_ZONE_PROCESSOR_DEBUG
257  static void printTransitions(
258  const char* prefix,
259  const TransitionTemplate* const* begin,
260  const TransitionTemplate* const* end) {
261  for (const TransitionTemplate* const* iter = begin; iter != end; ++iter) {
262  logging::printf(prefix);
263  (*iter)->log();
264  logging::printf("\n");
265  }
266  }
267 #endif
268 };
269 
277 template <typename ZEB, typename ZPB, typename ZRB>
281 
283  uint8_t fold;
284 
291  uint8_t num;
292 };
293 
307 template <typename ZEB, typename ZPB, typename ZRB>
315 
317  uint8_t num;
318 };
319 
351 template<uint8_t SIZE, typename ZEB, typename ZPB, typename ZRB>
353  public:
359 
366 
373 
376 
383  void init() {
384  for (uint8_t i = 0; i < SIZE; i++) {
385  mTransitions[i] = &mPool[i];
386  }
387  mIndexPrior = 0;
388  mIndexCandidates = 0;
389  mIndexFree = 0;
390  }
391 
394  return mTransitions[mIndexPrior];
395  }
396 
406  mIndexCandidates = mIndexPrior;
407  mIndexFree = mIndexPrior;
408  }
409 
410  Transition** getCandidatePoolBegin() {
411  return &mTransitions[mIndexCandidates];
412  }
413  Transition** getCandidatePoolEnd() {
414  return &mTransitions[mIndexFree];
415  }
416 
417  Transition** getActivePoolBegin() {
418  return &mTransitions[0];
419  }
420  Transition** getActivePoolEnd() {
421  return &mTransitions[mIndexFree];
422  }
423 
430  if (mIndexFree < SIZE) {
431  // Allocate a free transition.
432  if (mIndexFree >= mAllocSize) {
433  mAllocSize = mIndexFree + 1;
434  }
435  return mTransitions[mIndexFree];
436  } else {
437  // No more transition available in the buffer, so just return the last
438  // one. This will probably cause a bug in the timezone calculations, but
439  // I think this is better than triggering undefined behavior by running
440  // off the end of the mTransitions buffer.
441  return mTransitions[SIZE - 1];
442  }
443  }
444 
453  if (mIndexFree >= SIZE) return;
454  mIndexFree++;
455  mIndexPrior = mIndexFree;
456  mIndexCandidates = mIndexFree;
457  }
458 
468  getFreeAgent(); // allocate a new Transition
469 
470  mIndexCandidates++;
471  mIndexFree++;
472  return &mTransitions[mIndexPrior];
473  }
474 
477  Transition* ft = mTransitions[mIndexFree];
478  Transition* prior = mTransitions[mIndexPrior];
479  if ((prior->isValidPrior && prior->transitionTime < ft->transitionTime)
480  || !prior->isValidPrior) {
481  ft->isValidPrior = true;
482  prior->isValidPrior = false;
483  internal::swap(mTransitions[mIndexPrior], mTransitions[mIndexFree]);
484  }
485  }
486 
493  mIndexCandidates--;
494  }
495 
503  if (mIndexFree >= SIZE) return;
504 
505  // This implementation makes pair-wise swaps to shift the current
506  // Transition leftwards into its correctly sorted position. At first
507  // glance, this seem inefficient compared to the alternative
508  // implementation where we save the current Transition, then slide all the
509  // elements to the left by one position rightwards. However,
510  // MemoryBenchmark shows that this implementation is 46 bytes smaller on
511  // an AVR processor.
512  for (uint8_t i = mIndexFree; i > mIndexCandidates; i--) {
513  Transition* curr = mTransitions[i];
514  Transition* prev = mTransitions[i - 1];
515  if (curr->transitionTime >= prev->transitionTime) break;
516  mTransitions[i] = prev;
517  mTransitions[i - 1] = curr;
518  }
519  mIndexFree++;
520  }
521 
529  if (ACE_TIME_EXTENDED_ZONE_PROCESSOR_DEBUG) {
530  logging::printf("addActiveCandidatesToActivePool()\n");
531  }
532 
533  // Shift active candidates to the left into the Active pool.
534  uint8_t iActive = mIndexPrior;
535  uint8_t iCandidate = mIndexCandidates;
536  for (; iCandidate < mIndexFree; iCandidate++) {
537  if (isCompareStatusActive(mTransitions[iCandidate]->compareStatus)) {
538  if (iActive != iCandidate) {
539  // Must use swap(), because we are moving pointers instead of the
540  // actual Transition objects.
541  internal::swap(mTransitions[iActive], mTransitions[iCandidate]);
542  }
543  ++iActive;
544  }
545  }
546 
547  mIndexPrior = iActive;
548  mIndexCandidates = iActive;
549  mIndexFree = iActive;
550 
551  return mTransitions[iActive - 1];
552  }
553 
563  const {
564  if (ACE_TIME_EXTENDED_ZONE_PROCESSOR_DEBUG) {
565  logging::printf(
566  "findTransitionForSeconds(): mIndexFree: %d\n", mIndexFree);
567  }
568 
569  const Transition* prev = nullptr;
570  const Transition* curr = nullptr;
571  const Transition* next = nullptr;
572  for (uint8_t i = 0; i < mIndexFree; i++) {
573  next = mTransitions[i];
574  if (next->startEpochSeconds > epochSeconds) break;
575  prev = curr;
576  curr = next;
577  next = nullptr;
578  }
579 
580  uint8_t fold;
581  uint8_t num;
582  calcFoldAndOverlap(&fold, &num, prev, curr, next, epochSeconds);
583  //fprintf(stderr, "prev=%p;curr=%p;next=%p;fold=%d;num=%d\n",
584  // prev, curr, next, fold, num);
585  return TransitionForSeconds{curr, fold, num};
586  }
587 
589  static void calcFoldAndOverlap(
590  uint8_t* fold,
591  uint8_t* num,
592  const Transition* prev,
593  const Transition* curr,
594  const Transition* next,
595  acetime_t epochSeconds) {
596 
597  if (curr == nullptr) {
598  *fold = 0;
599  *num = 0;
600  return;
601  }
602 
603  // Check if within forward overlap shadow from prev
604  bool isOverlap;
605  if (prev == nullptr) {
606  isOverlap = false;
607  } else {
608  // Extract the shift from prev transition. Can be 0 in some cases where
609  // the zone changed from DST of one zone to the STD into another zone,
610  // causing the overall UTC offset to remain unchanged.
611  acetime_t shiftSeconds = subtractDateTuple(
612  curr->startDateTime, prev->untilDateTime);
613  if (shiftSeconds >= 0) {
614  // spring forward, or unchanged
615  isOverlap = false;
616  } else {
617  // Check if within the forward overlap shadow from prev
618  isOverlap = epochSeconds - curr->startEpochSeconds < -shiftSeconds;
619  }
620  }
621  if (isOverlap) {
622  *fold = 1; // epochSeconds selects the second match
623  *num = 2;
624  return;
625  }
626 
627  // Check if within backward overlap shawdow from next
628  if (next == nullptr) {
629  isOverlap = false;
630  } else {
631  // Extract the shift to next transition. Can be 0 in some cases where
632  // the zone changed from DST of one zone to the STD into another zone,
633  // causing the overall UTC offset to remain unchanged.
634  acetime_t shiftSeconds = subtractDateTuple(
635  next->startDateTime, curr->untilDateTime);
636  if (shiftSeconds >= 0) {
637  // spring forward, or unchanged
638  isOverlap = false;
639  } else {
640  // Check if within the backward overlap shadow from next
641  isOverlap = next->startEpochSeconds - epochSeconds <= -shiftSeconds;
642  }
643  }
644  if (isOverlap) {
645  *fold = 0; // epochSeconds selects the first match
646  *num = 2;
647  return;
648  }
649 
650  // Normal single match, no overlap.
651  *fold = 0;
652  *num = 1;
653  }
654 
661  const LocalDateTime& ldt) const {
662  // Convert LocalDateTime to DateTuple.
663  DateTuple localDate{
664  ldt.year(),
665  ldt.month(),
666  ldt.day(),
667  (int16_t) (ldt.hour() * 60 + ldt.minute()),
669  };
670 
671  // Examine adjacent pairs of Transitions, looking for an exact match, gap,
672  // or overlap.
673  const Transition* prev = nullptr;
674  const Transition* curr = nullptr;
675  uint8_t num = 0;
676  for (uint8_t i = 0; i < mIndexFree; i++) {
677  curr = mTransitions[i];
678 
679  const DateTuple& startDateTime = curr->startDateTime;
680  const DateTuple& untilDateTime = curr->untilDateTime;
681  bool isExactMatch = (startDateTime <= localDate)
682  && (localDate < untilDateTime);
683 
684  if (isExactMatch) {
685  // Check for a previous exact match to detect an overlap.
686  if (num == 1) {
687  num++;
688  break;
689  }
690 
691  // Loop again to detect an overlap.
692  num = 1;
693  } else if (startDateTime > localDate) {
694  // Exit loop since no more candidate transition.
695  break;
696  }
697 
698  prev = curr;
699 
700  // Set the curr to nullptr so that if the loop runs off the end of the
701  // list of Transitions, the curr is marked as nullptr.
702  curr = nullptr;
703  }
704 
705  // Check if the prev was an exact match, and set the curr to be identical.
706  // avoid confusion.
707  if (num == 1) {
708  curr = prev;
709  }
710 
711  // This should get optimized by RVO.
712  return TransitionForDateTime{prev, curr, num};
713  }
714 
716  void log() const {
717  logging::printf("TransitionStorage: ");
718  logging::printf("SIZE=%d, mAllocSize=%d\n", SIZE, mAllocSize);
719  int nActives = mIndexPrior;
720  int nPrior = mIndexCandidates - mIndexPrior;
721  int nCandidates = mIndexFree - mIndexCandidates;
722  int nAllocFree = mAllocSize - mIndexFree;
723  int nVirginFree = SIZE - mAllocSize;
724 
725  logging::printf(" Actives: %d\n", nActives);
727  " ", &mTransitions[0], &mTransitions[mIndexPrior]);
728 
729  logging::printf(" Prior: %d\n", nPrior);
731  " ", &mTransitions[mIndexPrior], &mTransitions[mIndexCandidates]);
732 
733  logging::printf(" Candidates: %d\n", nCandidates);
735  " ", &mTransitions[mIndexCandidates], &mTransitions[mIndexFree]);
736 
737  logging::printf(" Allocated Free: %d\n", nAllocFree);
738  logging::printf(" Virgin Free: %d\n", nVirginFree);
739  }
740 
742  void resetAllocSize() { mAllocSize = 0; }
743 
749  uint8_t getAllocSize() const { return mAllocSize; }
750 
751  private:
752  friend class ::TransitionStorageTest_getFreeAgent;
753  friend class ::TransitionStorageTest_getFreeAgent2;
754  friend class ::TransitionStorageTest_addFreeAgentToActivePool;
755  friend class ::TransitionStorageTest_reservePrior;
756  friend class ::TransitionStorageTest_addPriorToCandidatePool;
757  friend class ::TransitionStorageTest_addFreeAgentToCandidatePool;
758  friend class ::TransitionStorageTest_setFreeAgentAsPriorIfValid;
759  friend class ::TransitionStorageTest_addActiveCandidatesToActivePool;
760  friend class ::TransitionStorageTest_findTransitionForDateTime;
761  friend class ::TransitionStorageTest_resetCandidatePool;
762 
764  Transition* getTransition(uint8_t i) {
765  return mTransitions[i];
766  }
767 
768  Transition mPool[SIZE];
769  Transition* mTransitions[SIZE];
770  uint8_t mIndexPrior;
771  uint8_t mIndexCandidates;
772  uint8_t mIndexFree;
773 
775  uint8_t mAllocSize = 0;
776 };
777 
778 } // namespace extended
779 } // namespace ace_time
780 
781 #endif
Class that holds the date-time as the components (year, month, day, hour, minute, second) without reg...
Definition: LocalDateTime.h:31
uint8_t day() const
Return the day of the month.
uint8_t month() const
Return the month with January=1, December=12.
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:352
void resetAllocSize()
Reset the current allocation size.
Definition: Transition.h:742
void addFreeAgentToActivePool()
Immediately add the free agent Transition at index mIndexFree to the Active pool.
Definition: Transition.h:452
TransitionForSecondsTemplate< ZEB, ZPB, ZRB > TransitionForSeconds
Template instantiation of TransitionForSecondsTemplate used by this class.
Definition: Transition.h:365
TransitionForDateTimeTemplate< ZEB, ZPB, ZRB > TransitionForDateTime
Template instantiation of TransitionForDateTimeTemplate used by this class.
Definition: Transition.h:372
void init()
Initialize all pools to 0 size, usually when a new year is initialized.
Definition: Transition.h:383
void setFreeAgentAsPriorIfValid()
Set the free agent transition as the most recent prior.
Definition: Transition.h:476
Transition * getFreeAgent()
Return a pointer to the first Transition in the free pool.
Definition: Transition.h:429
TransitionTemplate< ZEB, ZPB, ZRB > Transition
Template instantiation of TransitionTemplate used by this class.
Definition: Transition.h:358
void resetCandidatePool()
Empty the Candidate pool by resetting the various indexes.
Definition: Transition.h:405
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:589
uint8_t getAllocSize() const
Return the maximum number of transitions which was allocated.
Definition: Transition.h:749
void addFreeAgentToCandidatePool()
Add the free agent Transition at index mIndexFree to the Candidate pool, sorted by transitionTime.
Definition: Transition.h:502
Transition * getPrior()
Return the current prior transition.
Definition: Transition.h:393
TransitionForDateTime findTransitionForDateTime(const LocalDateTime &ldt) const
Return the candidate Transitions matching the given dateTime.
Definition: Transition.h:660
Transition * addActiveCandidatesToActivePool()
Add active candidates into the Active pool, and collapse the Candidate pool.
Definition: Transition.h:528
void addPriorToCandidatePool()
Add the current prior into the Candidates pool.
Definition: Transition.h:492
TransitionForSeconds findTransitionForSeconds(acetime_t epochSeconds) const
Return the Transition matching the given epochSeconds.
Definition: Transition.h:562
Transition ** reservePrior()
Allocate a free Transition then add it to the Prior pool.
Definition: Transition.h:467
void log() const
Verify that the indexes are valid.
Definition: Transition.h:716
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:49
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
int16_t lastDeltaMinutes
The DST offset of the last Transition in this MatchingEra.
Definition: Transition.h:67
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
DateTuple startDateTime
The effective start time of the matching ZoneEra, which uses the UTC offsets of the previous matching...
Definition: Transition.h:52
int16_t lastOffsetMinutes
The STD offset of the last Transition in this MatchingEra.
Definition: Transition.h:64
The result of the findTransitionForDateTime(const LocalDatetime& ldt) method which can return 0,...
Definition: Transition.h:308
uint8_t num
Number of matches: 0, 1, 2.
Definition: Transition.h:317
const TransitionTemplate< ZEB, ZPB, ZRB > * prev
The previous transition.
Definition: Transition.h:311
const TransitionTemplate< ZEB, ZPB, ZRB > * curr
The matching transition, or null if not found or in gap.
Definition: Transition.h:314
Tuple of a matching Transition and its 'fold'.
Definition: Transition.h:278
uint8_t fold
1 if corresponding datetime occurred the second time
Definition: Transition.h:283
const TransitionTemplate< ZEB, ZPB, ZRB > * curr
The matching transition, or null if not found.
Definition: Transition.h:280
uint8_t num
Number of occurrences of the resulting LocalDateTime: 0, 1, or 2.
Definition: Transition.h:291
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:257
bool isValidPrior
During findCandidateTransitions(), this flag indicates whether the current transition is a valid "pri...
Definition: Transition.h:203
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
const char * letter
Storage for the 'letter' field if 'rule' is not null.
Definition: Transition.h:194
int16_t offsetMinutes
The base offset minutes, not the total effective UTC offset.
Definition: Transition.h:185
void log() const
Used only for debugging.
Definition: Transition.h:217
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:209
static void logHourMinute(int16_t minutes)
Print minutes as [+/-]hh:mm.
Definition: Transition.h:242
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:191
int16_t deltaMinutes
The DST delta minutes.
Definition: Transition.h:188
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: ZoneContext.h:44