ua_nodestore_default.c 14 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464
  1. /* This work is licensed under a Creative Commons CCZero 1.0 Universal License.
  2. * See http://creativecommons.org/publicdomain/zero/1.0/ for more information. */
  3. #include "ua_nodestore_default.h"
  4. #ifdef UA_ENABLE_MULTITHREADING
  5. #include <pthread.h>
  6. #define BEGIN_CRITSECT(NODEMAP) pthread_mutex_lock(&(NODEMAP)->mutex)
  7. #define END_CRITSECT(NODEMAP) pthread_mutex_unlock(&(NODEMAP)->mutex)
  8. #else
  9. #define BEGIN_CRITSECT(NODEMAP)
  10. #define END_CRITSECT(NODEMAP)
  11. #endif
  12. /* The default Nodestore is simply a hash-map from NodeIds to Nodes. To find an
  13. * entry, iterate over candidate positions according to the NodeId hash.
  14. *
  15. * - Tombstone or non-matching NodeId: continue searching
  16. * - Matching NodeId: Return the entry
  17. * - NULL: Abort the search */
  18. typedef struct UA_NodeMapEntry {
  19. struct UA_NodeMapEntry *orig; /* the version this is a copy from (or NULL) */
  20. UA_UInt16 refCount; /* How many consumers have a reference to the node? */
  21. UA_Boolean deleted; /* Node was marked as deleted and can be deleted when refCount == 0 */
  22. UA_Node node;
  23. } UA_NodeMapEntry;
  24. #define UA_NODEMAP_MINSIZE 64
  25. #define UA_NODEMAP_TOMBSTONE ((UA_NodeMapEntry*)0x01)
  26. typedef struct {
  27. UA_NodeMapEntry **entries;
  28. UA_UInt32 size;
  29. UA_UInt32 count;
  30. UA_UInt32 sizePrimeIndex;
  31. #ifdef UA_ENABLE_MULTITHREADING
  32. pthread_mutex_t mutex; /* Protect access */
  33. #endif
  34. } UA_NodeMap;
  35. /*********************/
  36. /* HashMap Utilities */
  37. /*********************/
  38. /* The size of the hash-map is always a prime number. They are chosen to be
  39. * close to the next power of 2. So the size ca. doubles with each prime. */
  40. static UA_UInt32 const primes[] = {
  41. 7, 13, 31, 61, 127, 251,
  42. 509, 1021, 2039, 4093, 8191, 16381,
  43. 32749, 65521, 131071, 262139, 524287, 1048573,
  44. 2097143, 4194301, 8388593, 16777213, 33554393, 67108859,
  45. 134217689, 268435399, 536870909, 1073741789, 2147483647, 4294967291
  46. };
  47. static UA_UInt32 mod(UA_UInt32 h, UA_UInt32 size) { return h % size; }
  48. static UA_UInt32 mod2(UA_UInt32 h, UA_UInt32 size) { return 1 + (h % (size - 2)); }
  49. static UA_UInt16
  50. higher_prime_index(UA_UInt32 n) {
  51. UA_UInt16 low = 0;
  52. UA_UInt16 high = (UA_UInt16)(sizeof(primes) / sizeof(UA_UInt32));
  53. while(low != high) {
  54. UA_UInt16 mid = (UA_UInt16)(low + ((high - low) / 2));
  55. if(n > primes[mid])
  56. low = (UA_UInt16)(mid + 1);
  57. else
  58. high = mid;
  59. }
  60. return low;
  61. }
  62. /* returns an empty slot or null if the nodeid exists */
  63. static UA_NodeMapEntry **
  64. findFreeSlot(const UA_NodeMap *ns, const UA_NodeId *nodeid) {
  65. UA_UInt32 h = UA_NodeId_hash(nodeid);
  66. UA_UInt32 size = ns->size;
  67. UA_UInt32 idx = mod(h, size);
  68. UA_UInt32 hash2 = mod2(h, size);
  69. while(true) {
  70. UA_NodeMapEntry *e = ns->entries[idx];
  71. if(e > UA_NODEMAP_TOMBSTONE &&
  72. UA_NodeId_equal(&e->node.nodeId, nodeid))
  73. return NULL;
  74. if(ns->entries[idx] <= UA_NODEMAP_TOMBSTONE)
  75. return &ns->entries[idx];
  76. idx += hash2;
  77. if(idx >= size)
  78. idx -= size;
  79. }
  80. /* NOTREACHED */
  81. return NULL;
  82. }
  83. /* The occupancy of the table after the call will be about 50% */
  84. static UA_StatusCode
  85. expand(UA_NodeMap *ns) {
  86. UA_UInt32 osize = ns->size;
  87. UA_UInt32 count = ns->count;
  88. /* Resize only when table after removal of unused elements is either too
  89. full or too empty */
  90. if(count * 2 < osize && (count * 8 > osize || osize <= UA_NODEMAP_MINSIZE))
  91. return UA_STATUSCODE_GOOD;
  92. UA_NodeMapEntry **oentries = ns->entries;
  93. UA_UInt32 nindex = higher_prime_index(count * 2);
  94. UA_UInt32 nsize = primes[nindex];
  95. UA_NodeMapEntry **nentries = (UA_NodeMapEntry **)UA_calloc(nsize, sizeof(UA_NodeMapEntry*));
  96. if(!nentries)
  97. return UA_STATUSCODE_BADOUTOFMEMORY;
  98. ns->entries = nentries;
  99. ns->size = nsize;
  100. ns->sizePrimeIndex = nindex;
  101. /* recompute the position of every entry and insert the pointer */
  102. for(size_t i = 0, j = 0; i < osize && j < count; ++i) {
  103. if(oentries[i] <= UA_NODEMAP_TOMBSTONE)
  104. continue;
  105. UA_NodeMapEntry **e = findFreeSlot(ns, &oentries[i]->node.nodeId);
  106. UA_assert(e);
  107. *e = oentries[i];
  108. ++j;
  109. }
  110. UA_free(oentries);
  111. return UA_STATUSCODE_GOOD;
  112. }
  113. static UA_NodeMapEntry *
  114. newEntry(UA_NodeClass nodeClass) {
  115. size_t size = sizeof(UA_NodeMapEntry) - sizeof(UA_Node);
  116. switch(nodeClass) {
  117. case UA_NODECLASS_OBJECT:
  118. size += sizeof(UA_ObjectNode);
  119. break;
  120. case UA_NODECLASS_VARIABLE:
  121. size += sizeof(UA_VariableNode);
  122. break;
  123. case UA_NODECLASS_METHOD:
  124. size += sizeof(UA_MethodNode);
  125. break;
  126. case UA_NODECLASS_OBJECTTYPE:
  127. size += sizeof(UA_ObjectTypeNode);
  128. break;
  129. case UA_NODECLASS_VARIABLETYPE:
  130. size += sizeof(UA_VariableTypeNode);
  131. break;
  132. case UA_NODECLASS_REFERENCETYPE:
  133. size += sizeof(UA_ReferenceTypeNode);
  134. break;
  135. case UA_NODECLASS_DATATYPE:
  136. size += sizeof(UA_DataTypeNode);
  137. break;
  138. case UA_NODECLASS_VIEW:
  139. size += sizeof(UA_ViewNode);
  140. break;
  141. default:
  142. return NULL;
  143. }
  144. UA_NodeMapEntry *entry = (UA_NodeMapEntry*)UA_calloc(1, size);
  145. if(!entry)
  146. return NULL;
  147. entry->node.nodeClass = nodeClass;
  148. return entry;
  149. }
  150. static void
  151. deleteEntry(UA_NodeMapEntry *entry) {
  152. UA_Node_deleteMembers(&entry->node);
  153. UA_free(entry);
  154. }
  155. static void
  156. cleanupEntry(UA_NodeMapEntry *entry) {
  157. if(entry->deleted && entry->refCount == 0)
  158. deleteEntry(entry);
  159. }
  160. static UA_StatusCode
  161. clearSlot(UA_NodeMap *ns, UA_NodeMapEntry **slot) {
  162. (*slot)->deleted = true;
  163. cleanupEntry(*slot);
  164. *slot = UA_NODEMAP_TOMBSTONE;
  165. --ns->count;
  166. /* Downsize the hashmap if it is very empty */
  167. if(ns->count * 8 < ns->size && ns->size > 32)
  168. expand(ns); /* Can fail. Just continue with the bigger hashmap. */
  169. return UA_STATUSCODE_GOOD;
  170. }
  171. static UA_NodeMapEntry **
  172. findOccupiedSlot(const UA_NodeMap *ns, const UA_NodeId *nodeid) {
  173. UA_UInt32 h = UA_NodeId_hash(nodeid);
  174. UA_UInt32 size = ns->size;
  175. UA_UInt32 idx = mod(h, size);
  176. UA_UInt32 hash2 = mod2(h, size);
  177. while(true) {
  178. UA_NodeMapEntry *e = ns->entries[idx];
  179. if(!e)
  180. return NULL;
  181. if(e > UA_NODEMAP_TOMBSTONE &&
  182. UA_NodeId_equal(&e->node.nodeId, nodeid))
  183. return &ns->entries[idx];
  184. idx += hash2;
  185. if(idx >= size)
  186. idx -= size;
  187. }
  188. /* NOTREACHED */
  189. return NULL;
  190. }
  191. /***********************/
  192. /* Interface functions */
  193. /***********************/
  194. static UA_Node *
  195. UA_NodeMap_newNode(void *context, UA_NodeClass nodeClass) {
  196. UA_NodeMapEntry *entry = newEntry(nodeClass);
  197. if(!entry)
  198. return NULL;
  199. return &entry->node;
  200. }
  201. static void
  202. UA_NodeMap_deleteNode(void *context, UA_Node *node) {
  203. #ifdef UA_ENABLE_MULTITHREADING
  204. UA_NodeMap *ns = (UA_NodeMap*)context;
  205. #endif
  206. BEGIN_CRITSECT(ns);
  207. UA_NodeMapEntry *entry = container_of(node, UA_NodeMapEntry, node);
  208. UA_assert(&entry->node == node);
  209. deleteEntry(entry);
  210. END_CRITSECT(ns);
  211. }
  212. static const UA_Node *
  213. UA_NodeMap_getNode(void *context, const UA_NodeId *nodeid) {
  214. UA_NodeMap *ns = (UA_NodeMap*)context;
  215. BEGIN_CRITSECT(ns);
  216. UA_NodeMapEntry **entry = findOccupiedSlot(ns, nodeid);
  217. if(!entry) {
  218. END_CRITSECT(ns);
  219. return NULL;
  220. }
  221. ++(*entry)->refCount;
  222. END_CRITSECT(ns);
  223. return (const UA_Node*)&(*entry)->node;
  224. }
  225. static void
  226. UA_NodeMap_releaseNode(void *context, const UA_Node *node) {
  227. #ifdef UA_ENABLE_MULTITHREADING
  228. UA_NodeMap *ns = (UA_NodeMap*)context;
  229. #endif
  230. BEGIN_CRITSECT(ns);
  231. UA_NodeMapEntry *entry = container_of(node, UA_NodeMapEntry, node);
  232. UA_assert(&entry->node == node);
  233. UA_assert(entry->refCount > 0);
  234. --entry->refCount;
  235. cleanupEntry(entry);
  236. END_CRITSECT(ns);
  237. }
  238. static UA_StatusCode
  239. UA_NodeMap_getNodeCopy(void *context, const UA_NodeId *nodeid,
  240. UA_Node **outNode) {
  241. UA_NodeMap *ns = (UA_NodeMap*)context;
  242. BEGIN_CRITSECT(ns);
  243. UA_NodeMapEntry **slot = findOccupiedSlot(ns, nodeid);
  244. if(!slot) {
  245. END_CRITSECT(ns);
  246. return UA_STATUSCODE_BADNODEIDUNKNOWN;
  247. }
  248. UA_NodeMapEntry *entry = *slot;
  249. UA_NodeMapEntry *newItem = newEntry(entry->node.nodeClass);
  250. if(!newItem) {
  251. END_CRITSECT(ns);
  252. return UA_STATUSCODE_BADOUTOFMEMORY;
  253. }
  254. UA_StatusCode retval = UA_Node_copy(&entry->node, &newItem->node);
  255. if(retval == UA_STATUSCODE_GOOD) {
  256. newItem->orig = entry; // store the pointer to the original
  257. *outNode = &newItem->node;
  258. } else {
  259. deleteEntry(newItem);
  260. }
  261. END_CRITSECT(ns);
  262. return retval;
  263. }
  264. static UA_StatusCode
  265. UA_NodeMap_removeNode(void *context, const UA_NodeId *nodeid) {
  266. UA_NodeMap *ns = (UA_NodeMap*)context;
  267. BEGIN_CRITSECT(ns);
  268. UA_NodeMapEntry **slot = findOccupiedSlot(ns, nodeid);
  269. UA_StatusCode retval = UA_STATUSCODE_GOOD;
  270. if(slot)
  271. retval = clearSlot(ns, slot);
  272. else
  273. retval = UA_STATUSCODE_BADNODEIDUNKNOWN;
  274. END_CRITSECT(ns);
  275. return retval;
  276. }
  277. static UA_StatusCode
  278. UA_NodeMap_insertNode(void *context, UA_Node *node,
  279. UA_NodeId *addedNodeId) {
  280. UA_NodeMap *ns = (UA_NodeMap*)context;
  281. BEGIN_CRITSECT(ns);
  282. if(ns->size * 3 <= ns->count * 4) {
  283. if(expand(ns) != UA_STATUSCODE_GOOD) {
  284. END_CRITSECT(ns);
  285. return UA_STATUSCODE_BADINTERNALERROR;
  286. }
  287. }
  288. UA_NodeId tempNodeid;
  289. tempNodeid = node->nodeId;
  290. tempNodeid.namespaceIndex = 0;
  291. UA_NodeMapEntry **slot;
  292. if(tempNodeid.identifierType == UA_NODEIDTYPE_NUMERIC &&
  293. tempNodeid.identifier.numeric == 0) {
  294. /* create a random nodeid */
  295. if(node->nodeId.namespaceIndex == 0)
  296. node->nodeId.namespaceIndex = 1;
  297. UA_UInt32 identifier = ns->count+1; // start value
  298. UA_UInt32 size = ns->size;
  299. UA_UInt32 increase = mod2(identifier, size);
  300. while(true) {
  301. node->nodeId.identifier.numeric = identifier;
  302. slot = findFreeSlot(ns, &node->nodeId);
  303. if(slot)
  304. break;
  305. identifier += increase;
  306. if(identifier >= size)
  307. identifier -= size;
  308. }
  309. } else {
  310. slot = findFreeSlot(ns, &node->nodeId);
  311. if(!slot) {
  312. deleteEntry(container_of(node, UA_NodeMapEntry, node));
  313. END_CRITSECT(ns);
  314. return UA_STATUSCODE_BADNODEIDEXISTS;
  315. }
  316. }
  317. *slot = container_of(node, UA_NodeMapEntry, node);
  318. ++ns->count;
  319. UA_assert(&(*slot)->node == node);
  320. UA_StatusCode retval = UA_STATUSCODE_GOOD;
  321. if(addedNodeId) {
  322. retval = UA_NodeId_copy(&node->nodeId, addedNodeId);
  323. if(retval != UA_STATUSCODE_GOOD)
  324. clearSlot(ns, slot);
  325. }
  326. END_CRITSECT(ns);
  327. return retval;
  328. }
  329. static UA_StatusCode
  330. UA_NodeMap_replaceNode(void *context, UA_Node *node) {
  331. UA_NodeMap *ns = (UA_NodeMap*)context;
  332. BEGIN_CRITSECT(ns);
  333. UA_NodeMapEntry **slot = findOccupiedSlot(ns, &node->nodeId);
  334. if(!slot) {
  335. END_CRITSECT(ns);
  336. return UA_STATUSCODE_BADNODEIDUNKNOWN;
  337. }
  338. UA_NodeMapEntry *newEntry = container_of(node, UA_NodeMapEntry, node);
  339. if(*slot != newEntry->orig) {
  340. /* The node was updated since the copy was made */
  341. deleteEntry(newEntry);
  342. END_CRITSECT(ns);
  343. return UA_STATUSCODE_BADINTERNALERROR;
  344. }
  345. (*slot)->deleted = true;
  346. cleanupEntry(*slot);
  347. *slot = newEntry;
  348. END_CRITSECT(ns);
  349. return UA_STATUSCODE_GOOD;
  350. }
  351. static void
  352. UA_NodeMap_iterate(void *context, void *visitorContext,
  353. UA_NodestoreVisitor visitor) {
  354. UA_NodeMap *ns = (UA_NodeMap*)context;
  355. BEGIN_CRITSECT(ns);
  356. for(UA_UInt32 i = 0; i < ns->size; ++i) {
  357. if(ns->entries[i] > UA_NODEMAP_TOMBSTONE) {
  358. END_CRITSECT(ns);
  359. UA_NodeMapEntry *entry = ns->entries[i];
  360. entry->refCount++;
  361. visitor(visitorContext, &entry->node);
  362. entry->refCount--;
  363. cleanupEntry(entry);
  364. BEGIN_CRITSECT(ns);
  365. }
  366. }
  367. END_CRITSECT(ns);
  368. }
  369. static void
  370. UA_NodeMap_delete(void *context) {
  371. UA_NodeMap *ns = (UA_NodeMap*)context;
  372. #ifdef UA_ENABLE_MULTITHREADING
  373. pthread_mutex_destroy(&ns->mutex);
  374. #endif
  375. UA_UInt32 size = ns->size;
  376. UA_NodeMapEntry **entries = ns->entries;
  377. for(UA_UInt32 i = 0; i < size; ++i) {
  378. if(entries[i] > UA_NODEMAP_TOMBSTONE) {
  379. /* On debugging builds, check that all nodes were release */
  380. UA_assert(entries[i]->refCount == 0);
  381. /* Delete the node */
  382. deleteEntry(entries[i]);
  383. }
  384. }
  385. UA_free(ns->entries);
  386. UA_free(ns);
  387. }
  388. UA_StatusCode
  389. UA_Nodestore_default_new(UA_Nodestore *ns) {
  390. /* Allocate and initialize the nodemap */
  391. UA_NodeMap *nodemap = (UA_NodeMap*)UA_malloc(sizeof(UA_NodeMap));
  392. if(!nodemap)
  393. return UA_STATUSCODE_BADOUTOFMEMORY;
  394. nodemap->sizePrimeIndex = higher_prime_index(UA_NODEMAP_MINSIZE);
  395. nodemap->size = primes[nodemap->sizePrimeIndex];
  396. nodemap->count = 0;
  397. nodemap->entries = (UA_NodeMapEntry**)
  398. UA_calloc(nodemap->size, sizeof(UA_NodeMapEntry*));
  399. if(!nodemap->entries) {
  400. UA_free(nodemap);
  401. return UA_STATUSCODE_BADOUTOFMEMORY;
  402. }
  403. #ifdef UA_ENABLE_MULTITHREADING
  404. pthread_mutex_init(&nodemap->mutex, NULL);
  405. #endif
  406. /* Populate the nodestore */
  407. ns->context = nodemap;
  408. ns->deleteNodestore = UA_NodeMap_delete;
  409. ns->inPlaceEditAllowed = true;
  410. ns->newNode = UA_NodeMap_newNode;
  411. ns->deleteNode = UA_NodeMap_deleteNode;
  412. ns->getNode = UA_NodeMap_getNode;
  413. ns->releaseNode = UA_NodeMap_releaseNode;
  414. ns->getNodeCopy = UA_NodeMap_getNodeCopy;
  415. ns->insertNode = UA_NodeMap_insertNode;
  416. ns->replaceNode = UA_NodeMap_replaceNode;
  417. ns->removeNode = UA_NodeMap_removeNode;
  418. ns->iterate = UA_NodeMap_iterate;
  419. return UA_STATUSCODE_GOOD;
  420. }