AceTime 2.4.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>
49 class ZoneRegistrarTemplate {
50 public:
52 static const uint16_t kInvalidIndex = 0xffff;
53
55 ZoneRegistrarTemplate(
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
ace_time::internal::ZoneRegistrarTemplate
Class that allows looking up the ZoneInfo (ZI) from its TZDB identifier (e.g.
Definition: ZoneRegistrar.h:49
ace_time::internal::ZoneRegistrarTemplate::getZoneInfoForId
const ZI * getZoneInfoForId(uint32_t zoneId) const
Return the ZoneInfo using the zoneId.
Definition: ZoneRegistrar.h:85
ace_time::internal::ZoneRegistrarTemplate::findIndexForIdLinear
uint16_t findIndexForIdLinear(uint32_t zoneId) const
Exposed only for benchmarking purposes.
Definition: ZoneRegistrar.h:202
ace_time::internal::ZoneRegistrarTemplate::getZoneInfoForIndex
const ZI * getZoneInfoForIndex(uint16_t i) const
Return the ZoneInfo at index i.
Definition: ZoneRegistrar.h:68
ace_time::internal::ZoneRegistrarTemplate::kInvalidIndex
static const uint16_t kInvalidIndex
Invalid index to indicate error or not found.
Definition: ZoneRegistrar.h:52
ace_time::internal::ZoneRegistrarTemplate::zoneRegistrySize
uint16_t zoneRegistrySize() const
Return the number of zones and (fat) links.
Definition: ZoneRegistrar.h:65
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:155
ace_time::internal::ZoneRegistrarTemplate::findIndexForIdBinary
uint16_t findIndexForIdBinary(uint32_t zoneId) const
Exposed only for benchmarking purposes.
Definition: ZoneRegistrar.h:207
ace_time::internal::ZoneRegistrarTemplate::findIndexForName
uint16_t findIndexForName(const char *name) const
Find the index for zone name.
Definition: ZoneRegistrar.h:92
ace_time::internal::ZoneRegistrarTemplate::kBinarySearchThreshold
static const uint8_t kBinarySearchThreshold
Use binarySearchById() if zoneRegistrySize >= threshold.
Definition: ZoneRegistrar.h:137
ace_time::internal::ZoneRegistrarTemplate::getZoneInfoForName
const ZI * getZoneInfoForName(const char *name) const
Return the ZoneInfo corresponding to the given zone name.
Definition: ZoneRegistrar.h:78
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:188
ace_time::internal::ZoneRegistrarTemplate::findIndexForId
uint16_t findIndexForId(uint32_t zoneId) const
Find the index for zone id.
Definition: ZoneRegistrar.h:108
ace_time::internal::ZoneRegistrarTemplate::ZoneRegistrarTemplate
ZoneRegistrarTemplate(uint16_t zoneRegistrySize, const ZI *const *zoneRegistry)
Constructor.
Definition: ZoneRegistrar.h:55
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:140