AceTime  1.7.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.
LinkRegistrar.h
1 /*
2  * MIT License
3  * Copyright (c) 2021 Brian T. Park
4  */
5 
6 #ifndef ACE_TIME_LINK_REGISTRAR_H
7 #define ACE_TIME_LINK_REGISTRAR_H
8 
9 #include <stdint.h>
10 #include <AceCommon.h> // KString, binarySearchByKey(), isSortedByKey()
11 #include "../common/compat.h" // ACE_TIME_USE_PROGMEM
12 #include "LinkEntry.h"
13 #include "BasicBrokers.h"
14 #include "ExtendedBrokers.h"
15 
16 class LinkRegistrarTest_isSorted;
17 
18 namespace ace_time {
19 namespace internal {
20 
29 template<typename LE, typename LEB, typename LRGB>
31  public:
33  static const uint16_t kInvalidIndex = 0xffff;
34 
37  uint16_t linkRegistrySize,
38  const LE* linkRegistry
39  ):
40  mLinkRegistrySize(linkRegistrySize),
41  mIsSorted(isSorted(linkRegistry, linkRegistrySize)),
42  mLinkRegistry(linkRegistry)
43  {}
44 
46  uint16_t linkRegistrySize() const { return mLinkRegistrySize; }
47 
49  const LE* getLinkEntryForIndex(uint16_t i) const {
50  return (mLinkRegistry && i < mLinkRegistrySize)
51  ? LRGB(mLinkRegistry).linkEntry(i)
52  : nullptr;
53  }
54 
56  const LE* getLinkEntryForId(uint32_t linkId) const {
57  if (mLinkRegistrySize == 0 || mLinkRegistry == nullptr) {
58  return nullptr;
59  }
60  uint16_t index = findIndexForId(linkId);
61  if (index == kInvalidIndex) return nullptr;
62  return LRGB(mLinkRegistry).linkEntry(index);
63  }
64 
66  uint16_t findIndexForId(uint32_t linkId) const {
67  if (mIsSorted && mLinkRegistrySize >= kBinarySearchThreshold) {
68  return binarySearchById(mLinkRegistry, mLinkRegistrySize, linkId);
69  } else {
70  return linearSearchById(mLinkRegistry, mLinkRegistrySize, linkId);
71  }
72  }
73 
74  protected:
75  friend class ::LinkRegistrarTest_isSorted;
76 
78  static const uint8_t kBinarySearchThreshold = 8;
79 
81  static bool isSorted(const LE* registry, uint16_t registrySize) {
82  const LRGB linkRegistry(registry);
83  return ace_common::isSortedByKey(
84  (size_t) registrySize,
85  [&linkRegistry](size_t i) {
86  const LE* linkEntry = linkRegistry.linkEntry(i);
87  return LEB(linkEntry).linkId();
88  } // lambda expression returns linkId at index i
89  );
90  }
91 
96  static uint16_t linearSearchById(const LE* registry,
97  uint16_t registrySize, uint32_t linkId) {
98  const LRGB linkRegistry(registry);
99 
100  for (uint16_t i = 0; i < registrySize; ++i) {
101  const LE* linkEntry = linkRegistry.linkEntry(i);
102  if (linkId == LEB(linkEntry).linkId()) {
103  return i;
104  }
105  }
106  return kInvalidIndex;
107 
108  // The templatized version is 20-40% slower on some compilers (but not
109  // all), so let's use the hand-rolled version above.
110  /*
111  return (uint16_t) ace_common::linearSearchByKey(
112  (size_t) registrySize,
113  linkId,
114  [&linkRegistry](size_t i) {
115  const LE* linkEntry = linkRegistry.linkEntry(i);
116  return LEB(linkEntry).linkId();
117  } // lambda expression returns linkId at index i
118  );
119  */
120  }
121 
130  static uint16_t binarySearchById(const LE* registry,
131  uint16_t registrySize, uint32_t linkId) {
132  const LRGB linkRegistry(registry);
133  return (uint16_t) ace_common::binarySearchByKey(
134  (size_t) registrySize,
135  linkId,
136  [&linkRegistry](size_t i) {
137  const LE* linkEntry = linkRegistry.linkEntry(i);
138  return LEB(linkEntry).linkId();
139  } // lambda expression returns linkId at index i
140  );
141  }
142 
144  uint16_t findIndexForIdLinear(uint32_t linkId) const {
145  return linearSearchById(mLinkRegistry, mLinkRegistrySize, linkId);
146  }
147 
149  uint16_t findIndexForIdBinary(uint32_t linkId) const {
150  return binarySearchById(mLinkRegistry, mLinkRegistrySize, linkId);
151  }
152 
153  private:
154  // Ordering of fields optimized for 32-bit alignment.
155  uint16_t const mLinkRegistrySize;
156  bool const mIsSorted;
157  const LE* const mLinkRegistry; // nullable
158 };
159 
160 } // internal
161 
162 namespace basic {
163 
164 #if 1
165 
171  basic::LinkEntry,
172  basic::LinkEntryBroker,
173  basic::LinkRegistryBroker
174 > {
175  public:
177  uint16_t linkRegistrySize,
178  const basic::LinkEntry* linkRegistry
179  ) :
181  basic::LinkEntry,
184  >(linkRegistrySize, linkRegistry)
185  {}
186 };
187 
188 #else
189 
190 // Use subclassing instead of template typedef so that error messages are
191 // understandable. The compiler seems to optimize away the subclass overhead.
192 
194  basic::LinkEntry,
197 >
199 
200 #endif
201 
202 } // basic
203 
204 namespace extended {
205 
206 #if 1
207 
213  extended::LinkEntry,
214  extended::LinkEntryBroker,
215  extended::LinkRegistryBroker
216 > {
217  public:
219  uint16_t linkRegistrySize,
220  const extended::LinkEntry* linkRegistry
221  ) :
223  extended::LinkEntry,
226  >(linkRegistrySize, linkRegistry)
227  {}
228 };
229 
230 #else
231 
233  extended::LinkEntry,
236 >
238 
239 #endif
240 
241 } // extended
242 
243 } // ace_time
244 
245 #endif
ace_time::internal::LinkRegistrarTemplate::getLinkEntryForIndex
const LE * getLinkEntryForIndex(uint16_t i) const
Return the LinkEntry at index i.
Definition: LinkRegistrar.h:49
ace_time::internal::LinkRegistrarTemplate::LinkRegistrarTemplate
LinkRegistrarTemplate(uint16_t linkRegistrySize, const LE *linkRegistry)
Constructor.
Definition: LinkRegistrar.h:36
ace_time::internal::LinkRegistrarTemplate::getLinkEntryForId
const LE * getLinkEntryForId(uint32_t linkId) const
Return the LinkEntry using the linkId.
Definition: LinkRegistrar.h:56
ace_time::extended::LinkEntryBroker
Data broker for accessing a LinkEntry.
Definition: ExtendedBrokers.h:425
BasicBrokers.h
ace_time::internal::LinkRegistrarTemplate::linkRegistrySize
uint16_t linkRegistrySize() const
Return the number of (thin) links.
Definition: LinkRegistrar.h:46
ace_time::extended::LinkRegistrar
Concrete template instantiation of LinkRegistrarTemplate for extended::LinkEntry.
Definition: LinkRegistrar.h:212
ace_time::internal::LinkRegistrarTemplate::findIndexForIdLinear
uint16_t findIndexForIdLinear(uint32_t linkId) const
Exposed only for benchmarking purposes.
Definition: LinkRegistrar.h:144
ace_time::internal::LinkRegistrarTemplate::findIndexForId
uint16_t findIndexForId(uint32_t linkId) const
Find the index for linkId.
Definition: LinkRegistrar.h:66
ace_time::internal::LinkRegistrarTemplate::kBinarySearchThreshold
static const uint8_t kBinarySearchThreshold
Use binarySearchById() if linkRegistrySize >= threshold.
Definition: LinkRegistrar.h:78
ace_time::internal::LinkRegistrarTemplate::binarySearchById
static uint16_t binarySearchById(const LE *registry, uint16_t registrySize, uint32_t linkId)
Find the registry index corresponding to linkId using a binary search.
Definition: LinkRegistrar.h:130
ExtendedBrokers.h
ace_time::internal::LinkRegistrarTemplate::kInvalidIndex
static const uint16_t kInvalidIndex
Invalid index to indicate error or not found.
Definition: LinkRegistrar.h:33
ace_time::basic::LinkRegistryBroker
Data broker for a LinkRegistry composed of LinkEntry records.
Definition: BasicBrokers.h:421
ace_time::basic::LinkEntryBroker
Data broker for accessing a LinkEntry.
Definition: BasicBrokers.h:393
ace_time::internal::LinkRegistrarTemplate::findIndexForIdBinary
uint16_t findIndexForIdBinary(uint32_t linkId) const
Exposed only for benchmarking purposes.
Definition: LinkRegistrar.h:149
ace_time::basic::LinkRegistrar
Concrete template instantiation of LinkRegistrarTemplate for basic::LinkEntry.
Definition: LinkRegistrar.h:170
ace_time::extended::LinkRegistryBroker
Data broker for a LinkRegistry composed of LinkEntry records.
Definition: ExtendedBrokers.h:453
ace_time::internal::LinkRegistrarTemplate
Class that allows looking up the LinkEntry (LE) from its LinkRegistry (LRGB) using its linkId.
Definition: LinkRegistrar.h:30
ace_time::internal::LinkRegistrarTemplate::linearSearchById
static uint16_t linearSearchById(const LE *registry, uint16_t registrySize, uint32_t linkId)
Find the registry index corresponding to linkId using linear search.
Definition: LinkRegistrar.h:96
ace_time::internal::LinkRegistrarTemplate::isSorted
static bool isSorted(const LE *registry, uint16_t registrySize)
Determine if the given link registry is sorted by id.
Definition: LinkRegistrar.h:81