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