AceTime  1.7.2
Date and time classes for Arduino that support timezones from the TZ Database, and a system clock that can synchronize from an NTP server or an RTC chip.
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 "../common/compat.h" // ACE_TIME_USE_PROGMEM
12 #include "ZoneInfo.h"
13 #include "BasicBrokers.h"
14 #include "ExtendedBrokers.h"
15 
16 // AutoBenchmark.ino
17 void runIndexForZoneIdBinary();
18 void runIndexForZoneIdLinear();
19 
20 // Tests
21 class ZoneRegistrarTest_Sorted_isSorted;
22 class ZoneRegistrarTest_Unsorted_isSorted;
23 class ZoneRegistrarTest_Sorted_linearSearchById;
24 class ZoneRegistrarTest_Sorted_linearSearchById_not_found;
25 class ZoneRegistrarTest_Sorted_binarySearchById_zeroEntries;
26 class ZoneRegistrarTest_Sorted_binarySearchById;
27 class ZoneRegistrarTest_Sorted_binarySearchById_not_found;
28 class ZoneRegistrarTest_Unsorted_linearSearchById;
29 class ZoneRegistrarTest_Unsorted_linearSearchById_not_found;
30 
31 namespace ace_time {
32 namespace internal {
33 
43 template<typename ZI, typename ZIB, typename ZRGB>
45  public:
47  static const uint16_t kInvalidIndex = 0xffff;
48 
51  uint16_t zoneRegistrySize,
52  const ZI* const* zoneRegistry
53  ):
54  mZoneRegistrySize(zoneRegistrySize),
55  mIsSorted(isSorted(zoneRegistry, zoneRegistrySize)),
56  mZoneRegistry(zoneRegistry)
57  {}
58 
60  uint16_t zoneRegistrySize() const { return mZoneRegistrySize; }
61 
63  const ZI* getZoneInfoForIndex(uint16_t i) const {
64  return (i < mZoneRegistrySize)
65  ? ZRGB(mZoneRegistry).zoneInfo(i)
66  : nullptr;
67  }
68 
73  const ZI* getZoneInfoForName(const char* name) const {
74  uint16_t index = findIndexForName(name);
75  if (index == kInvalidIndex) return nullptr;
76  return ZRGB(mZoneRegistry).zoneInfo(index);
77  }
78 
80  const ZI* getZoneInfoForId(uint32_t zoneId) const {
81  uint16_t index = findIndexForId(zoneId);
82  if (index == kInvalidIndex) return nullptr;
83  return ZRGB(mZoneRegistry).zoneInfo(index);
84  }
85 
87  uint16_t findIndexForName(const char* name) const {
88  uint32_t zoneId = ace_common::hashDjb2(name);
89  uint16_t index = findIndexForId(zoneId);
90  if (index == kInvalidIndex) return kInvalidIndex;
91 
92  // Verify that the zoneName actually matches, in case of hash collision.
93  ZIB zoneInfoBroker(ZRGB(mZoneRegistry).zoneInfo(index));
94  ace_common::KString kname(
95  zoneInfoBroker.name(),
96  zoneInfoBroker.zoneContext()->fragments,
97  zoneInfoBroker.zoneContext()->numFragments
98  );
99  return (kname.compareTo(name) == 0) ? index : kInvalidIndex;
100  }
101 
103  uint16_t findIndexForId(uint32_t zoneId) const {
104  if (mIsSorted && mZoneRegistrySize >= kBinarySearchThreshold) {
105  return binarySearchById(mZoneRegistry, mZoneRegistrySize, zoneId);
106  } else {
107  return linearSearchById(mZoneRegistry, mZoneRegistrySize, zoneId);
108  }
109  }
110 
111  protected:
112  friend void ::runIndexForZoneIdBinary();
113  friend void ::runIndexForZoneIdLinear();
114  friend class ::ZoneRegistrarTest_Sorted_isSorted;
115  friend class ::ZoneRegistrarTest_Unsorted_isSorted;
116  friend class ::ZoneRegistrarTest_Sorted_linearSearchById;
117  friend class ::ZoneRegistrarTest_Sorted_linearSearchById_not_found;
118  friend class ::ZoneRegistrarTest_Sorted_binarySearchById_zeroEntries;
119  friend class ::ZoneRegistrarTest_Sorted_binarySearchById;
120  friend class ::ZoneRegistrarTest_Sorted_binarySearchById_not_found;
121  friend class ::ZoneRegistrarTest_Unsorted_linearSearchById;
122  friend class ::ZoneRegistrarTest_Unsorted_linearSearchById_not_found;
123 
125  static const uint8_t kBinarySearchThreshold = 8;
126 
128  static bool isSorted(const ZI* const* registry, uint16_t registrySize) {
129  const ZRGB zoneRegistry(registry);
130  return ace_common::isSortedByKey(
131  (size_t) registrySize,
132  [&zoneRegistry](size_t i) {
133  const ZI* zoneInfo = zoneRegistry.zoneInfo(i);
134  return ZIB(zoneInfo).zoneId();
135  } // lambda expression returns zoneId at index i
136  );
137  }
138 
143  static uint16_t linearSearchById(const ZI* const* registry,
144  uint16_t registrySize, uint32_t zoneId) {
145  const ZRGB zoneRegistry(registry);
146  for (uint16_t i = 0; i < registrySize; ++i) {
147  const ZI* zoneInfo = zoneRegistry.zoneInfo(i);
148  if (zoneId == ZIB(zoneInfo).zoneId()) {
149  return i;
150  }
151  }
152  return kInvalidIndex;
153 
154  // The templatized version is 20-40% slower on some compilers (but not
155  // all), so let's use the hand-rolled version above.
156  /*
157  return (uint16_t) ace_common::linearSearchByKey(
158  (size_t) registrySize,
159  zoneId,
160  [&zoneRegistry](size_t i) {
161  const ZI* zoneInfo = zoneRegistry.zoneInfo(i);
162  return ZIB(zoneInfo).zoneId();
163  } // lambda expression returns zoneId at index i
164  );
165  */
166  }
167 
176  static uint16_t binarySearchById(const ZI* const* registry,
177  uint16_t registrySize, uint32_t zoneId) {
178  const ZRGB zoneRegistry(registry);
179  return (uint16_t) ace_common::binarySearchByKey(
180  (size_t) registrySize,
181  zoneId,
182  [&zoneRegistry](size_t i) -> uint32_t {
183  const ZI* zoneInfo = zoneRegistry.zoneInfo(i);
184  return ZIB(zoneInfo).zoneId();
185  } // lambda expression returns zoneId at index i
186  );
187  }
188 
190  uint16_t findIndexForIdLinear(uint32_t zoneId) const {
191  return linearSearchById(mZoneRegistry, mZoneRegistrySize, zoneId);
192  }
193 
195  uint16_t findIndexForIdBinary(uint32_t zoneId) const {
196  return binarySearchById(mZoneRegistry, mZoneRegistrySize, zoneId);
197  }
198 
199  private:
200  // Ordering of fields optimized for 32-bit alignment.
201  uint16_t const mZoneRegistrySize;
202  bool const mIsSorted;
203  const ZI* const* const mZoneRegistry; // not nullable
204 };
205 
206 } // internal
207 
208 namespace basic {
209 
210 #if 1
211 
217  basic::ZoneInfo,
218  basic::ZoneInfoBroker,
219  basic::ZoneRegistryBroker
220 > {
221  public:
223  uint16_t zoneRegistrySize,
224  const basic::ZoneInfo* const* zoneRegistry
225  ) :
227  basic::ZoneInfo,
230  >(zoneRegistrySize, zoneRegistry)
231  {}
232 };
233 
234 #else
235 
236 namespace basic {
237 
238 // Use subclassing instead of template typedef so that error messages are
239 // understandable. The compiler seems to optimize away the subclass overhead.
240 
242  basic::ZoneInfo,
245 >
247 
248 #endif
249 
250 } // basic
251 
252 namespace extended {
253 
254 #if 1
255 
261  extended::ZoneInfo,
262  extended::ZoneInfoBroker,
263  extended::ZoneRegistryBroker
264 > {
265  public:
267  uint16_t zoneRegistrySize,
268  const extended::ZoneInfo* const* zoneRegistry
269  ) :
271  extended::ZoneInfo,
274  >(zoneRegistrySize, zoneRegistry)
275  {}
276 };
277 
278 #else
279 
280 // Use subclassing instead of template typedef so that error messages are
281 // understandable. The compiler seems to optimize away the subclass overhead.
282 
284  extended::ZoneInfo,
287 >
289 
290 #endif
291 
292 } // extended
293 
294 } // ace_time
295 
296 #endif // ACE_TIME_ZONE_REGISTRAR_H
ace_time::internal::ZoneRegistrarTemplate::getZoneInfoForIndex
const ZI * getZoneInfoForIndex(uint16_t i) const
Return the ZoneInfo at index i.
Definition: ZoneRegistrar.h:63
ace_time::internal::ZoneRegistrarTemplate::zoneRegistrySize
uint16_t zoneRegistrySize() const
Return the number of zones and (fat) links.
Definition: ZoneRegistrar.h:60
ace_time::internal::ZoneRegistrarTemplate::kInvalidIndex
static const uint16_t kInvalidIndex
Invalid index to indicate error or not found.
Definition: ZoneRegistrar.h:47
ace_time::internal::ZoneRegistrarTemplate::binarySearchById
static uint16_t binarySearchById(const ZI *const *registry, uint16_t registrySize, uint32_t zoneId)
Find the registry index corresponding to zoneId using a binary search.
Definition: ZoneRegistrar.h:176
ace_time::basic::ZoneRegistrar
Concrete template instantiation of ZoneRegistrarTemplate for basic::ZoneInfo, which can be used with ...
Definition: ZoneRegistrar.h:216
ace_time::internal::ZoneRegistrarTemplate::ZoneRegistrarTemplate
ZoneRegistrarTemplate(uint16_t zoneRegistrySize, const ZI *const *zoneRegistry)
Constructor.
Definition: ZoneRegistrar.h:50
ace_time::internal::ZoneRegistrarTemplate::linearSearchById
static uint16_t linearSearchById(const ZI *const *registry, uint16_t registrySize, uint32_t zoneId)
Find the registry index corresponding to zoneId using linear search.
Definition: ZoneRegistrar.h:143
BasicBrokers.h
ace_time::internal::ZoneRegistrarTemplate::findIndexForName
uint16_t findIndexForName(const char *name) const
Find the index for zone name.
Definition: ZoneRegistrar.h:87
ace_time::extended::ZoneRegistrar
Concrete template instantiation of ZoneRegistrarTemplate for extended::ZoneInfo, which can be used wi...
Definition: ZoneRegistrar.h:260
ace_time::internal::ZoneRegistrarTemplate::findIndexForIdLinear
uint16_t findIndexForIdLinear(uint32_t zoneId) const
Exposed only for benchmarking purposes.
Definition: ZoneRegistrar.h:190
ace_time::basic::ZoneInfoBroker
Data broker for accessing ZoneInfo.
Definition: BasicBrokers.h:286
ace_time::extended::ZoneRegistryBroker
Data broker for accessing the ZoneRegistry.
Definition: ExtendedBrokers.h:393
ace_time::extended::ZoneInfoBroker
Data broker for accessing ZoneInfo.
Definition: ExtendedBrokers.h:318
ace_time::internal::ZoneRegistrarTemplate::isSorted
static bool isSorted(const ZI *const *registry, uint16_t registrySize)
Determine if the given zone registry is sorted by id.
Definition: ZoneRegistrar.h:128
ace_time::basic::ZoneRegistryBroker
Data broker for accessing the ZoneRegistry.
Definition: BasicBrokers.h:361
ace_time::internal::ZoneRegistrarTemplate::getZoneInfoForId
const ZI * getZoneInfoForId(uint32_t zoneId) const
Return the ZoneInfo using the zoneId.
Definition: ZoneRegistrar.h:80
ace_time::internal::ZoneRegistrarTemplate::findIndexForIdBinary
uint16_t findIndexForIdBinary(uint32_t zoneId) const
Exposed only for benchmarking purposes.
Definition: ZoneRegistrar.h:195
ace_time::internal::ZoneRegistrarTemplate::kBinarySearchThreshold
static const uint8_t kBinarySearchThreshold
Use binarySearchById() if zoneRegistrySize >= threshold.
Definition: ZoneRegistrar.h:125
ExtendedBrokers.h
ace_time::internal::ZoneRegistrarTemplate::getZoneInfoForName
const ZI * getZoneInfoForName(const char *name) const
Return the ZoneInfo corresponding to the given zone name.
Definition: ZoneRegistrar.h:73
ace_time::internal::ZoneRegistrarTemplate
Class that allows looking up the ZoneInfo (ZI) from its TZDB identifier (e.g.
Definition: ZoneRegistrar.h:44
ace_time::internal::ZoneRegistrarTemplate::findIndexForId
uint16_t findIndexForId(uint32_t zoneId) const
Find the index for zone id.
Definition: ZoneRegistrar.h:103