AceTime  2.3.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 #include "../zoneinfo/brokers.h"
13 
14 // AutoBenchmark.ino
15 void runBasicRegistrarFindIndexForName();
16 void runBasicRegistrarFindIndexForIdBinary();
17 void runBasicRegistrarFindIndexForIdLinear();
18 void runExtendedRegistrarFindIndexForName();
19 void runExtendedRegistrarFindIndexForIdBinary();
20 void runExtendedRegistrarFindIndexForIdLinear();
21 void runCompleteRegistrarFindIndexForName();
22 void runCompleteRegistrarFindIndexForIdBinary();
23 void runCompleteRegistrarFindIndexForIdLinear();
24 
25 // Tests
26 class ZoneRegistrarTest_Sorted_isSorted;
27 class ZoneRegistrarTest_Unsorted_isSorted;
28 class ZoneRegistrarTest_Sorted_linearSearchById;
29 class ZoneRegistrarTest_Sorted_linearSearchById_not_found;
30 class ZoneRegistrarTest_Sorted_binarySearchById_zeroEntries;
31 class ZoneRegistrarTest_Sorted_binarySearchById;
32 class ZoneRegistrarTest_Sorted_binarySearchById_not_found;
33 class ZoneRegistrarTest_Unsorted_linearSearchById;
34 class ZoneRegistrarTest_Unsorted_linearSearchById_not_found;
35 
36 namespace ace_time {
37 namespace internal {
38 
48 template<typename ZI, typename ZIB, typename ZRGB>
50  public:
52  static const uint16_t kInvalidIndex = 0xffff;
53 
56  uint16_t zoneRegistrySize,
57  const ZI* const* zoneRegistry
58  ):
59  mZoneRegistrySize(zoneRegistrySize),
60  mIsSorted(isSorted(zoneRegistry, zoneRegistrySize)),
61  mZoneRegistry(zoneRegistry)
62  {}
63 
65  uint16_t zoneRegistrySize() const { return mZoneRegistrySize; }
66 
68  const ZI* getZoneInfoForIndex(uint16_t i) const {
69  return (i < mZoneRegistrySize)
70  ? ZRGB(mZoneRegistry).zoneInfo(i)
71  : nullptr;
72  }
73 
78  const ZI* getZoneInfoForName(const char* name) const {
79  uint16_t index = findIndexForName(name);
80  if (index == kInvalidIndex) return nullptr;
81  return ZRGB(mZoneRegistry).zoneInfo(index);
82  }
83 
85  const ZI* getZoneInfoForId(uint32_t zoneId) const {
86  uint16_t index = findIndexForId(zoneId);
87  if (index == kInvalidIndex) return nullptr;
88  return ZRGB(mZoneRegistry).zoneInfo(index);
89  }
90 
92  uint16_t findIndexForName(const char* name) const {
93  uint32_t zoneId = ace_common::hashDjb2(name);
94  uint16_t index = findIndexForId(zoneId);
95  if (index == kInvalidIndex) return kInvalidIndex;
96 
97  // Verify that the zoneName actually matches, in case of hash collision.
98  ZIB zoneInfoBroker(ZRGB(mZoneRegistry).zoneInfo(index));
99  ace_common::KString kname(
100  zoneInfoBroker.name(),
101  zoneInfoBroker.zoneContext().fragments(),
102  zoneInfoBroker.zoneContext().numFragments()
103  );
104  return (kname.compareTo(name) == 0) ? index : kInvalidIndex;
105  }
106 
108  uint16_t findIndexForId(uint32_t zoneId) const {
109  if (mIsSorted && mZoneRegistrySize >= kBinarySearchThreshold) {
110  return binarySearchById(mZoneRegistry, mZoneRegistrySize, zoneId);
111  } else {
112  return linearSearchById(mZoneRegistry, mZoneRegistrySize, zoneId);
113  }
114  }
115 
116  protected:
117  friend void ::runBasicRegistrarFindIndexForName();
118  friend void ::runBasicRegistrarFindIndexForIdBinary();
119  friend void ::runBasicRegistrarFindIndexForIdLinear();
120  friend void ::runExtendedRegistrarFindIndexForName();
121  friend void ::runExtendedRegistrarFindIndexForIdBinary();
122  friend void ::runExtendedRegistrarFindIndexForIdLinear();
123  friend void ::runCompleteRegistrarFindIndexForName();
124  friend void ::runCompleteRegistrarFindIndexForIdBinary();
125  friend void ::runCompleteRegistrarFindIndexForIdLinear();
126  friend class ::ZoneRegistrarTest_Sorted_isSorted;
127  friend class ::ZoneRegistrarTest_Unsorted_isSorted;
128  friend class ::ZoneRegistrarTest_Sorted_linearSearchById;
129  friend class ::ZoneRegistrarTest_Sorted_linearSearchById_not_found;
130  friend class ::ZoneRegistrarTest_Sorted_binarySearchById_zeroEntries;
131  friend class ::ZoneRegistrarTest_Sorted_binarySearchById;
132  friend class ::ZoneRegistrarTest_Sorted_binarySearchById_not_found;
133  friend class ::ZoneRegistrarTest_Unsorted_linearSearchById;
134  friend class ::ZoneRegistrarTest_Unsorted_linearSearchById_not_found;
135 
137  static const uint8_t kBinarySearchThreshold = 8;
138 
140  static bool isSorted(const ZI* const* registry, uint16_t registrySize) {
141  const ZRGB zoneRegistry(registry);
142  return ace_common::isSortedByKey(
143  (size_t) registrySize,
144  [&zoneRegistry](size_t i) {
145  const ZI* zoneInfo = zoneRegistry.zoneInfo(i);
146  return ZIB(zoneInfo).zoneId();
147  } // lambda expression returns zoneId at index i
148  );
149  }
150 
155  static uint16_t linearSearchById(const ZI* const* registry,
156  uint16_t registrySize, uint32_t zoneId) {
157  const ZRGB zoneRegistry(registry);
158  for (uint16_t i = 0; i < registrySize; ++i) {
159  const ZI* zoneInfo = zoneRegistry.zoneInfo(i);
160  if (zoneId == ZIB(zoneInfo).zoneId()) {
161  return i;
162  }
163  }
164  return kInvalidIndex;
165 
166  // The templatized version is 20-40% slower on some compilers (but not
167  // all), so let's use the hand-rolled version above.
168  /*
169  return (uint16_t) ace_common::linearSearchByKey(
170  (size_t) registrySize,
171  zoneId,
172  [&zoneRegistry](size_t i) {
173  const ZI* zoneInfo = zoneRegistry.zoneInfo(i);
174  return ZIB(zoneInfo).zoneId();
175  } // lambda expression returns zoneId at index i
176  );
177  */
178  }
179 
188  static uint16_t binarySearchById(const ZI* const* registry,
189  uint16_t registrySize, uint32_t zoneId) {
190  const ZRGB zoneRegistry(registry);
191  return (uint16_t) ace_common::binarySearchByKey(
192  (size_t) registrySize,
193  zoneId,
194  [&zoneRegistry](size_t i) -> uint32_t {
195  const ZI* zoneInfo = zoneRegistry.zoneInfo(i);
196  return ZIB(zoneInfo).zoneId();
197  } // lambda expression returns zoneId at index i
198  );
199  }
200 
202  uint16_t findIndexForIdLinear(uint32_t zoneId) const {
203  return linearSearchById(mZoneRegistry, mZoneRegistrySize, zoneId);
204  }
205 
207  uint16_t findIndexForIdBinary(uint32_t zoneId) const {
208  return binarySearchById(mZoneRegistry, mZoneRegistrySize, zoneId);
209  }
210 
211  private:
212  // Ordering of fields optimized for 32-bit alignment.
213  uint16_t const mZoneRegistrySize;
214  bool const mIsSorted;
215  const ZI* const* const mZoneRegistry; // not nullable
216 };
217 
218 } // internal
219 
220 namespace basic {
221 
226 using ZoneRegistrar = internal::ZoneRegistrarTemplate<
227  basic::ZoneInfo,
228  basic::ZoneInfoBroker,
229  basic::ZoneRegistryBroker
230 >;
231 
232 } // basic
233 
234 namespace extended {
235 
240 using ZoneRegistrar = internal::ZoneRegistrarTemplate<
241  extended::ZoneInfo,
242  extended::ZoneInfoBroker,
243  extended::ZoneRegistryBroker
244 >;
245 
246 } // extended
247 
248 namespace complete {
249 
254 using ZoneRegistrar = internal::ZoneRegistrarTemplate<
255  complete::ZoneInfo,
256  complete::ZoneInfoBroker,
257  complete::ZoneRegistryBroker
258 >;
259 
260 } // complete
261 
262 } // ace_time
263 
264 #endif // ACE_TIME_ZONE_REGISTRAR_H
Class that allows looking up the ZoneInfo (ZI) from its TZDB identifier (e.g.
Definition: ZoneRegistrar.h:49
const ZI * getZoneInfoForId(uint32_t zoneId) const
Return the ZoneInfo using the zoneId.
Definition: ZoneRegistrar.h:85
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:68
static const uint16_t kInvalidIndex
Invalid index to indicate error or not found.
Definition: ZoneRegistrar.h:52
uint16_t zoneRegistrySize() const
Return the number of zones and (fat) links.
Definition: ZoneRegistrar.h:65
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:92
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:78
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:55
static bool isSorted(const ZI *const *registry, uint16_t registrySize)
Determine if the given zone registry is sorted by id.