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>
46 class ZoneRegistrarTemplate {
47 public:
49 static const uint16_t kInvalidIndex = 0xffff;
50
52 ZoneRegistrarTemplate(
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
ace_time::ZoneRegistrarTemplate
Class that allows looking up the ZoneInfo from its TZDB identifier (e.g.
Definition: ZoneRegistrar.h:46
ace_time::ZoneRegistrarTemplate::linearSearchById
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.
Definition: ZoneRegistrar.h:156
ace_time::ZoneRegistrarTemplate::findIndexForIdBinary
uint16_t findIndexForIdBinary(uint32_t zoneId) const
Exposed only for benchmarking purposes.
Definition: ZoneRegistrar.h:212
ace_time::ZoneRegistrarTemplate::findIndexForId
uint16_t findIndexForId(uint32_t zoneId) const
Find the index for zone id.
Definition: ZoneRegistrar.h:106
ace_time::ZoneRegistrarTemplate::getZoneInfoForName
const D::ZoneInfo * getZoneInfoForName(const char *name) const
Return the ZoneInfo corresponding to the given zone name.
Definition: ZoneRegistrar.h:75
ace_time::ZoneRegistrarTemplate::kInvalidIndex
static const uint16_t kInvalidIndex
Invalid index to indicate error or not found.
Definition: ZoneRegistrar.h:49
ace_time::ZoneRegistrarTemplate::findIndexForName
uint16_t findIndexForName(const char *name) const
Find the index for zone name.
Definition: ZoneRegistrar.h:89
ace_time::ZoneRegistrarTemplate::zoneRegistrySize
uint16_t zoneRegistrySize() const
Return the number of zones and (fat) links.
Definition: ZoneRegistrar.h:62
ace_time::ZoneRegistrarTemplate::getZoneInfoForId
const D::ZoneInfo * getZoneInfoForId(uint32_t zoneId) const
Return the ZoneInfo using the zoneId.
Definition: ZoneRegistrar.h:82
ace_time::ZoneRegistrarTemplate::ZoneRegistrarTemplate
ZoneRegistrarTemplate(uint16_t zoneRegistrySize, const typename D::ZoneInfo *const *zoneRegistry)
Constructor.
Definition: ZoneRegistrar.h:52
ace_time::ZoneRegistrarTemplate::findIndexForIdLinear
uint16_t findIndexForIdLinear(uint32_t zoneId) const
Exposed only for benchmarking purposes.
Definition: ZoneRegistrar.h:207
ace_time::ZoneRegistrarTemplate::getZoneInfoForIndex
const D::ZoneInfo * getZoneInfoForIndex(uint16_t i) const
Return the ZoneInfo at index i.
Definition: ZoneRegistrar.h:65
ace_time::ZoneRegistrarTemplate::binarySearchById
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.
Definition: ZoneRegistrar.h:191
ace_time::ZoneRegistrarTemplate::kBinarySearchThreshold
static const uint8_t kBinarySearchThreshold
Use binarySearchById() if zoneRegistrySize >= threshold.
Definition: ZoneRegistrar.h:135
ace_time::ZoneRegistrarTemplate::isSorted
static bool isSorted(const typename D::ZoneInfo *const *registry, uint16_t registrySize)
Determine if the given zone registry is sorted by id.
Definition: ZoneRegistrar.h:138