AceTime  1.3
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 <string.h> // strcmp(), strcmp_P()
11 #include <AceCommon.h> // strcmp_PP()
12 #include "common/compat.h"
13 #include "internal/ZoneInfo.h"
14 #include "internal/Brokers.h"
15 
16 class BasicZoneRegistrarTest_Sorted_isSorted;
17 class BasicZoneRegistrarTest_Sorted_linearSearchByName;
18 class BasicZoneRegistrarTest_Sorted_linearSearchByName_not_found;
19 class BasicZoneRegistrarTest_Sorted_binarySearchByName;
20 class BasicZoneRegistrarTest_Sorted_binarySearchByName_not_found;
21 class BasicZoneRegistrarTest_Sorted_linearSearchById;
22 class BasicZoneRegistrarTest_Sorted_linearSearchById_not_found;
23 class BasicZoneRegistrarTest_Unsorted_isSorted;
24 class BasicZoneRegistrarTest_Unsorted_linearSearchByName;
25 class BasicZoneRegistrarTest_Unsorted_linearSearchByName_not_found;
26 class BasicZoneRegistrarTest_Unsorted_binarySearchByName;
27 class BasicZoneRegistrarTest_Unsorted_binarySearchByName_not_found;
28 class BasicZoneRegistrarTest_Unsorted_linearSearchById;
29 class BasicZoneRegistrarTest_Unsorted_linearSearchById_not_found;
30 
31 namespace ace_time {
32 
34 typedef int (*strcmp_t)(const char*, const char*);
35 
49 template<typename ZI, typename ZRB, typename ZIB, strcmp_t STRCMP_P,
50  strcmp_t STRCMP_PP>
52  public:
54  static const uint16_t kInvalidIndex = 0xffff;
55 
57  ZoneRegistrar(uint16_t registrySize, const ZI* const* zoneRegistry):
58  mRegistrySize(registrySize),
59  mZoneRegistry(zoneRegistry),
60  mIsSorted(isSorted(zoneRegistry, registrySize)) {}
61 
63  uint16_t registrySize() const { return mRegistrySize; }
64 
69  bool isSorted() const { return mIsSorted; }
70 
72  const ZI* getZoneInfoForIndex(uint16_t i) const {
73  return (i < mRegistrySize) ? ZRB(mZoneRegistry).zoneInfo(i) : nullptr;
74  }
75 
80  const ZI* getZoneInfoForName(const char* name) const {
81  uint16_t index = findIndexForName(name);
82  if (index == kInvalidIndex) return nullptr;
83  return ZRB(mZoneRegistry).zoneInfo(index);
84  }
85 
87  const ZI* getZoneInfoForId(uint32_t zoneId) const {
88  uint16_t index = findIndexForId(zoneId);
89  if (index == kInvalidIndex) return nullptr;
90  return ZRB(mZoneRegistry).zoneInfo(index);
91  }
92 
94  uint16_t findIndexForName(const char* name) const {
95  if (mIsSorted && mRegistrySize >= kBinarySearchThreshold) {
96  return binarySearchByName(mZoneRegistry, mRegistrySize, name);
97  } else {
98  return linearSearchByName(mZoneRegistry, mRegistrySize, name);
99  }
100  }
101 
103  uint16_t findIndexForId(uint32_t zoneId) const {
104  return linearSearchById(mZoneRegistry, mRegistrySize, zoneId);
105  }
106 
107  protected:
108  friend class ::BasicZoneRegistrarTest_Sorted_isSorted;
109  friend class ::BasicZoneRegistrarTest_Sorted_linearSearchByName;
110  friend class ::BasicZoneRegistrarTest_Sorted_linearSearchByName_not_found;
111  friend class ::BasicZoneRegistrarTest_Sorted_binarySearchByName;
112  friend class ::BasicZoneRegistrarTest_Sorted_binarySearchByName_not_found;
113  friend class ::BasicZoneRegistrarTest_Sorted_linearSearchById;
114  friend class ::BasicZoneRegistrarTest_Sorted_linearSearchById_not_found;
115  friend class ::BasicZoneRegistrarTest_Unsorted_isSorted;
116  friend class ::BasicZoneRegistrarTest_Unsorted_linearSearchByName;
117  friend class ::BasicZoneRegistrarTest_Unsorted_linearSearchByName_not_found;
118  friend class ::BasicZoneRegistrarTest_Unsorted_binarySearchByName;
119  friend class ::BasicZoneRegistrarTest_Unsorted_binarySearchByName_not_found;
120  friend class ::BasicZoneRegistrarTest_Unsorted_linearSearchById;
121  friend class ::BasicZoneRegistrarTest_Unsorted_linearSearchById_not_found;
122 
124  static const uint8_t kBinarySearchThreshold = 6;
125 
127  static bool isSorted(const ZI* const* registry, uint16_t registrySize) {
128  if (registrySize == 0) {
129  return false;
130  }
131 
132  const ZRB zoneRegistry(registry);
133  const char* prevName = ZIB(zoneRegistry.zoneInfo(0)).name();
134  for (uint16_t i = 1; i < registrySize; ++i) {
135  const char* currName = ZIB(zoneRegistry.zoneInfo(i)).name();
136  if (STRCMP_PP(prevName, currName) > 0) {
137  return false;
138  }
139  prevName = currName;
140  }
141  return true;
142  }
143 
148  static uint16_t linearSearchByName(const ZI* const* registry,
149  uint16_t registrySize, const char* name) {
150  const ZRB zoneRegistry(registry);
151  for (uint16_t i = 0; i < registrySize; ++i) {
152  const ZI* zoneInfo = zoneRegistry.zoneInfo(i);
153  if (STRCMP_P(name, ZIB(zoneInfo).name()) == 0) {
154  return i;
155  }
156  }
157  return kInvalidIndex;
158  }
159 
164  static uint16_t binarySearchByName(const ZI* const* registry,
165  uint16_t registrySize, const char* name) {
166  uint16_t a = 0;
167  uint16_t b = registrySize - 1;
168  const ZRB zoneRegistry(registry);
169  while (true) {
170  uint16_t c = (a + b) / 2;
171  const ZI* zoneInfo = zoneRegistry.zoneInfo(c);
172  int8_t compare = STRCMP_P(name, ZIB(zoneInfo).name());
173  if (compare == 0) return c;
174  if (a == b) return kInvalidIndex;
175  if (compare < 0) {
176  b = c - 1;
177  } else {
178  a = c + 1;
179  }
180  }
181  }
182 
184  static uint16_t linearSearchById(const ZI* const* registry,
185  uint16_t registrySize, uint32_t zoneId) {
186  const ZRB zoneRegistry(registry);
187  for (uint16_t i = 0; i < registrySize; ++i) {
188  const ZI* zoneInfo = zoneRegistry.zoneInfo(i);
189  if (zoneId == ZIB(zoneInfo).zoneId()) {
190  return i;
191  }
192  }
193  return kInvalidIndex;
194  }
195 
196  uint16_t const mRegistrySize;
197  const ZI* const* const mZoneRegistry;
198  bool const mIsSorted;
199 };
200 
205 #if ACE_TIME_USE_PROGMEM
206 typedef ZoneRegistrar<basic::ZoneInfo, basic::ZoneRegistryBroker,
207  basic::ZoneInfoBroker, acetime_strcmp_P, ace_common::strcmp_PP>
208  BasicZoneRegistrar;
209 #else
210 typedef ZoneRegistrar<basic::ZoneInfo, basic::ZoneRegistryBroker,
211  basic::ZoneInfoBroker, strcmp, strcmp> BasicZoneRegistrar;
212 #endif
213 
218 #if ACE_TIME_USE_PROGMEM
219 typedef ZoneRegistrar<extended::ZoneInfo, extended::ZoneRegistryBroker,
220  extended::ZoneInfoBroker, acetime_strcmp_P, ace_common::strcmp_PP>
221  ExtendedZoneRegistrar;
222 #else
223 typedef ZoneRegistrar<extended::ZoneInfo, extended::ZoneRegistryBroker,
224  extended::ZoneInfoBroker, strcmp, strcmp> ExtendedZoneRegistrar;
225 #endif
226 
227 }
228 
229 #endif
ace_time::ZoneRegistrar::kInvalidIndex
static const uint16_t kInvalidIndex
Invalid index to indicate error or not found.
Definition: ZoneRegistrar.h:54
ace_time::ZoneRegistrar::kBinarySearchThreshold
static const uint8_t kBinarySearchThreshold
Use binarySearch() if registrySize >= threshold.
Definition: ZoneRegistrar.h:124
ace_time::ZoneRegistrar::linearSearchById
static uint16_t linearSearchById(const ZI *const *registry, uint16_t registrySize, uint32_t zoneId)
Find the registry index corresponding to id using linear search.
Definition: ZoneRegistrar.h:184
ace_time::ZoneRegistrar::isSorted
static bool isSorted(const ZI *const *registry, uint16_t registrySize)
Determine if the given zone registry is sorted by name.
Definition: ZoneRegistrar.h:127
ace_time::ZoneRegistrar::binarySearchByName
static uint16_t binarySearchByName(const ZI *const *registry, uint16_t registrySize, const char *name)
Find the registry index corresponding to name using a binary search.
Definition: ZoneRegistrar.h:164
ace_time::ZoneRegistrar::findIndexForId
uint16_t findIndexForId(uint32_t zoneId) const
Find the index for zone id.
Definition: ZoneRegistrar.h:103
Brokers.h
ace_time::ZoneRegistrar
Class that allows looking up the ZoneInfo (ZI) from its TZDB identifier (e.g.
Definition: ZoneRegistrar.h:51
compat.h
ace_time::ZoneRegistrar::isSorted
bool isSorted() const
Return true if zoneRegistry is sorted, and eligible to use a binary search.
Definition: ZoneRegistrar.h:69
ace_time::ZoneRegistrar::ZoneRegistrar
ZoneRegistrar(uint16_t registrySize, const ZI *const *zoneRegistry)
Constructor.
Definition: ZoneRegistrar.h:57
ace_time::ZoneRegistrar::getZoneInfoForIndex
const ZI * getZoneInfoForIndex(uint16_t i) const
Return the ZoneInfo at index i.
Definition: ZoneRegistrar.h:72
ace_time::ZoneRegistrar::getZoneInfoForId
const ZI * getZoneInfoForId(uint32_t zoneId) const
Return the ZoneInfo using the zoneId.
Definition: ZoneRegistrar.h:87
ace_time::ZoneRegistrar::getZoneInfoForName
const ZI * getZoneInfoForName(const char *name) const
Return the ZoneInfo corresponding to the given zone name.
Definition: ZoneRegistrar.h:80
ace_time::ZoneRegistrar::registrySize
uint16_t registrySize() const
Return the number of zones.
Definition: ZoneRegistrar.h:63
ace_time::ZoneRegistrar::linearSearchByName
static uint16_t linearSearchByName(const ZI *const *registry, uint16_t registrySize, const char *name)
Find the registry index corresponding to name using a linear search.
Definition: ZoneRegistrar.h:148
ace_time::ZoneRegistrar::findIndexForName
uint16_t findIndexForName(const char *name) const
Find the index for zone name.
Definition: ZoneRegistrar.h:94