AceTime  3.0.0
Date and time classes for Arduino that support timezones from the TZ Database.
ZoneRegistrar.h
1 /*
2  * MIT License
3  * Copyright (c) 2019 Brian T. Park
4  */
5 
6 #ifndef ACE_TIME_ZONE_REGISTRAR_H
7 #define ACE_TIME_ZONE_REGISTRAR_H
8 
9 #include <stdint.h>
10 #include <AceCommon.h> // KString, binarySearchByKey(), isSortedByKey()
11 #include "../zoneinfo/infos.h"
12 
13 // AutoBenchmark.ino
14 void runBasicRegistrarFindIndexForName();
15 void runBasicRegistrarFindIndexForIdBinary();
16 void runBasicRegistrarFindIndexForIdLinear();
17 void runExtendedRegistrarFindIndexForName();
18 void runExtendedRegistrarFindIndexForIdBinary();
19 void runExtendedRegistrarFindIndexForIdLinear();
20 void runCompleteRegistrarFindIndexForName();
21 void runCompleteRegistrarFindIndexForIdBinary();
22 void runCompleteRegistrarFindIndexForIdLinear();
23 
24 // Tests
25 class ZoneRegistrarTest_Sorted_isSorted;
26 class ZoneRegistrarTest_Unsorted_isSorted;
27 class ZoneRegistrarTest_Sorted_linearSearchById;
28 class ZoneRegistrarTest_Sorted_linearSearchById_not_found;
29 class ZoneRegistrarTest_Sorted_binarySearchById_zeroEntries;
30 class ZoneRegistrarTest_Sorted_binarySearchById;
31 class ZoneRegistrarTest_Sorted_binarySearchById_not_found;
32 class ZoneRegistrarTest_Unsorted_linearSearchById;
33 class ZoneRegistrarTest_Unsorted_linearSearchById_not_found;
34 
35 namespace ace_time {
36 
45 template<typename D>
47  public:
49  static const uint16_t kInvalidIndex = 0xffff;
50 
53  uint16_t zoneRegistrySize,
54  const typename D::ZoneInfo* const* zoneRegistry
55  ):
56  mZoneRegistrySize(zoneRegistrySize),
57  mIsSorted(isSorted(zoneRegistry, zoneRegistrySize)),
58  mZoneRegistry(zoneRegistry)
59  {}
60 
62  uint16_t zoneRegistrySize() const { return mZoneRegistrySize; }
63 
65  const typename D::ZoneInfo* getZoneInfoForIndex(uint16_t i) const {
66  return (i < mZoneRegistrySize)
67  ? typename D::ZoneRegistryBroker(mZoneRegistry).zoneInfo(i)
68  : nullptr;
69  }
70 
75  const typename D::ZoneInfo* getZoneInfoForName(const char* name) const {
76  uint16_t index = findIndexForName(name);
77  if (index == kInvalidIndex) return nullptr;
78  return typename D::ZoneRegistryBroker(mZoneRegistry).zoneInfo(index);
79  }
80 
82  const typename D::ZoneInfo* getZoneInfoForId(uint32_t zoneId) const {
83  uint16_t index = findIndexForId(zoneId);
84  if (index == kInvalidIndex) return nullptr;
85  return typename D::ZoneRegistryBroker(mZoneRegistry).zoneInfo(index);
86  }
87 
89  uint16_t findIndexForName(const char* name) const {
90  uint32_t zoneId = ace_common::hashDjb2(name);
91  uint16_t index = findIndexForId(zoneId);
92  if (index == kInvalidIndex) return kInvalidIndex;
93 
94  // Verify that the zoneName actually matches, in case of hash collision.
95  typename D::ZoneInfoBroker zoneInfoBroker(
96  typename D::ZoneRegistryBroker(mZoneRegistry).zoneInfo(index));
97  ace_common::KString kname(
98  zoneInfoBroker.name(),
99  zoneInfoBroker.zoneContext().fragments(),
100  zoneInfoBroker.zoneContext().numFragments()
101  );
102  return (kname.compareTo(name) == 0) ? index : kInvalidIndex;
103  }
104 
106  uint16_t findIndexForId(uint32_t zoneId) const {
107  if (mIsSorted && mZoneRegistrySize >= kBinarySearchThreshold) {
108  return binarySearchById(mZoneRegistry, mZoneRegistrySize, zoneId);
109  } else {
110  return linearSearchById(mZoneRegistry, mZoneRegistrySize, zoneId);
111  }
112  }
113 
114  protected:
115  friend void ::runBasicRegistrarFindIndexForName();
116  friend void ::runBasicRegistrarFindIndexForIdBinary();
117  friend void ::runBasicRegistrarFindIndexForIdLinear();
118  friend void ::runExtendedRegistrarFindIndexForName();
119  friend void ::runExtendedRegistrarFindIndexForIdBinary();
120  friend void ::runExtendedRegistrarFindIndexForIdLinear();
121  friend void ::runCompleteRegistrarFindIndexForName();
122  friend void ::runCompleteRegistrarFindIndexForIdBinary();
123  friend void ::runCompleteRegistrarFindIndexForIdLinear();
124  friend class ::ZoneRegistrarTest_Sorted_isSorted;
125  friend class ::ZoneRegistrarTest_Unsorted_isSorted;
126  friend class ::ZoneRegistrarTest_Sorted_linearSearchById;
127  friend class ::ZoneRegistrarTest_Sorted_linearSearchById_not_found;
128  friend class ::ZoneRegistrarTest_Sorted_binarySearchById_zeroEntries;
129  friend class ::ZoneRegistrarTest_Sorted_binarySearchById;
130  friend class ::ZoneRegistrarTest_Sorted_binarySearchById_not_found;
131  friend class ::ZoneRegistrarTest_Unsorted_linearSearchById;
132  friend class ::ZoneRegistrarTest_Unsorted_linearSearchById_not_found;
133 
135  static const uint8_t kBinarySearchThreshold = 8;
136 
138  static bool isSorted(
139  const typename D::ZoneInfo* const* registry,
140  uint16_t registrySize) {
141 
142  const typename D::ZoneRegistryBroker zoneRegistry(registry);
143  return ace_common::isSortedByKey(
144  (size_t) registrySize,
145  [&zoneRegistry](size_t i) {
146  const typename D::ZoneInfo* zoneInfo = zoneRegistry.zoneInfo(i);
147  return typename D::ZoneInfoBroker(zoneInfo).zoneId();
148  } // lambda expression returns zoneId at index i
149  );
150  }
151 
156  static uint16_t linearSearchById(
157  const typename D::ZoneInfo* const* registry,
158  uint16_t registrySize,
159  uint32_t zoneId) {
160  const typename D::ZoneRegistryBroker zoneRegistry(registry);
161  for (uint16_t i = 0; i < registrySize; ++i) {
162  const typename D::ZoneInfo* zoneInfo = zoneRegistry.zoneInfo(i);
163  if (zoneId == typename D::ZoneInfoBroker(zoneInfo).zoneId()) {
164  return i;
165  }
166  }
167  return kInvalidIndex;
168 
169  // The templatized version is 20-40% slower on some compilers (but not
170  // all), so let's use the hand-rolled version above.
171  /*
172  return (uint16_t) ace_common::linearSearchByKey(
173  (size_t) registrySize,
174  zoneId,
175  [&zoneRegistry](size_t i) {
176  const typename D::ZoneInfo* zoneInfo = zoneRegistry.zoneInfo(i);
177  return typename D::ZoneInfoBroker(zoneInfo).zoneId();
178  } // lambda expression returns zoneId at index i
179  );
180  */
181  }
182 
191  static uint16_t binarySearchById(
192  const typename D::ZoneInfo* const* registry,
193  uint16_t registrySize,
194  uint32_t zoneId) {
195  const typename D::ZoneRegistryBroker zoneRegistry(registry);
196  return (uint16_t) ace_common::binarySearchByKey(
197  (size_t) registrySize,
198  zoneId,
199  [&zoneRegistry](size_t i) -> uint32_t {
200  const typename D::ZoneInfo* zoneInfo = zoneRegistry.zoneInfo(i);
201  return typename D::ZoneInfoBroker(zoneInfo).zoneId();
202  } // lambda expression returns zoneId at index i
203  );
204  }
205 
207  uint16_t findIndexForIdLinear(uint32_t zoneId) const {
208  return linearSearchById(mZoneRegistry, mZoneRegistrySize, zoneId);
209  }
210 
212  uint16_t findIndexForIdBinary(uint32_t zoneId) const {
213  return binarySearchById(mZoneRegistry, mZoneRegistrySize, zoneId);
214  }
215 
216  private:
217  // Ordering of fields optimized for 32-bit alignment.
218  uint16_t const mZoneRegistrySize;
219  bool const mIsSorted;
220  const typename D::ZoneInfo* const* const mZoneRegistry; // not nullable
221 };
222 
223 namespace basic {
224 using ZoneRegistrar = ZoneRegistrarTemplate<basic::Info>;
225 }
226 
227 namespace extended {
228 using ZoneRegistrar = ZoneRegistrarTemplate<extended::Info>;
229 }
230 
231 namespace complete {
232 using ZoneRegistrar = ZoneRegistrarTemplate<complete::Info>;
233 }
234 
235 } // ace_time
236 
237 #endif // ACE_TIME_ZONE_REGISTRAR_H
Class that allows looking up the ZoneInfo from its TZDB identifier (e.g.
Definition: ZoneRegistrar.h:46
static uint16_t linearSearchById(const typename D::ZoneInfo *const *registry, uint16_t registrySize, uint32_t zoneId)
Find the registry index corresponding to zoneId using linear search.
uint16_t findIndexForIdBinary(uint32_t zoneId) const
Exposed only for benchmarking purposes.
uint16_t findIndexForId(uint32_t zoneId) const
Find the index for zone id.
const D::ZoneInfo * getZoneInfoForName(const char *name) const
Return the ZoneInfo corresponding to the given zone name.
Definition: ZoneRegistrar.h:75
static const uint16_t kInvalidIndex
Invalid index to indicate error or not found.
Definition: ZoneRegistrar.h:49
uint16_t findIndexForName(const char *name) const
Find the index for zone name.
Definition: ZoneRegistrar.h:89
uint16_t zoneRegistrySize() const
Return the number of zones and (fat) links.
Definition: ZoneRegistrar.h:62
const D::ZoneInfo * getZoneInfoForId(uint32_t zoneId) const
Return the ZoneInfo using the zoneId.
Definition: ZoneRegistrar.h:82
ZoneRegistrarTemplate(uint16_t zoneRegistrySize, const typename D::ZoneInfo *const *zoneRegistry)
Constructor.
Definition: ZoneRegistrar.h:52
uint16_t findIndexForIdLinear(uint32_t zoneId) const
Exposed only for benchmarking purposes.
const D::ZoneInfo * getZoneInfoForIndex(uint16_t i) const
Return the ZoneInfo at index i.
Definition: ZoneRegistrar.h:65
static uint16_t binarySearchById(const typename D::ZoneInfo *const *registry, uint16_t registrySize, uint32_t zoneId)
Find the registry index corresponding to zoneId using a binary search.
static const uint8_t kBinarySearchThreshold
Use binarySearchById() if zoneRegistrySize >= threshold.
static bool isSorted(const typename D::ZoneInfo *const *registry, uint16_t registrySize)
Determine if the given zone registry is sorted by id.