ua_nodestore_ziptree.c 10 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362
  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. *
  4. * Copyright 2014-2018 (c) Fraunhofer IOSB (Author: Julius Pfrommer)
  5. * Copyright 2017 (c) Julian Grothoff
  6. * Copyright 2017 (c) Stefan Profanter, fortiss GmbH
  7. */
  8. #include <open62541/plugin/nodestore_default.h>
  9. #include "ziptree.h"
  10. #if UA_MULTITHREADING >= 100
  11. #define BEGIN_CRITSECT(ctx) UA_LOCK(ctx->lock)
  12. #define END_CRITSECT(ctx) UA_UNLOCK(ctx->lock)
  13. #else
  14. #define BEGIN_CRITSECT(ctx) do {} while(0)
  15. #define END_CRITSECT(ctx) do {} while(0)
  16. #endif
  17. /* container_of */
  18. #define container_of(ptr, type, member) \
  19. (type *)((uintptr_t)ptr - offsetof(type,member))
  20. struct NodeEntry;
  21. typedef struct NodeEntry NodeEntry;
  22. struct NodeEntry {
  23. ZIP_ENTRY(NodeEntry) zipfields;
  24. UA_UInt32 nodeIdHash;
  25. UA_UInt16 refCount; /* How many consumers have a reference to the node? */
  26. UA_Boolean deleted; /* Node was marked as deleted and can be deleted when refCount == 0 */
  27. NodeEntry *orig; /* If a copy is made to replace a node, track that we
  28. * replace only the node from which the copy was made.
  29. * Important for concurrent operations. */
  30. UA_NodeId nodeId; /* This is actually a UA_Node that also starts with a NodeId */
  31. };
  32. /* Absolute ordering for NodeIds */
  33. static enum ZIP_CMP
  34. cmpNodeId(const void *a, const void *b) {
  35. const NodeEntry *aa = (const NodeEntry*)a;
  36. const NodeEntry *bb = (const NodeEntry*)b;
  37. /* Compare hash */
  38. if(aa->nodeIdHash < bb->nodeIdHash)
  39. return ZIP_CMP_LESS;
  40. if(aa->nodeIdHash > bb->nodeIdHash)
  41. return ZIP_CMP_MORE;
  42. /* Compore nodes in detail */
  43. return (enum ZIP_CMP)UA_NodeId_order(&aa->nodeId, &bb->nodeId);
  44. }
  45. ZIP_HEAD(NodeTree, NodeEntry);
  46. typedef struct NodeTree NodeTree;
  47. typedef struct {
  48. NodeTree root;
  49. #if UA_MULTITHREADING >= 100
  50. UA_LOCK_TYPE(lock) /* Protect access */
  51. #endif
  52. } ZipContext;
  53. ZIP_PROTTYPE(NodeTree, NodeEntry, NodeEntry)
  54. ZIP_IMPL(NodeTree, NodeEntry, zipfields, NodeEntry, zipfields, cmpNodeId)
  55. static NodeEntry *
  56. newEntry(UA_NodeClass nodeClass) {
  57. size_t size = sizeof(NodeEntry) - sizeof(UA_NodeId);
  58. switch(nodeClass) {
  59. case UA_NODECLASS_OBJECT:
  60. size += sizeof(UA_ObjectNode);
  61. break;
  62. case UA_NODECLASS_VARIABLE:
  63. size += sizeof(UA_VariableNode);
  64. break;
  65. case UA_NODECLASS_METHOD:
  66. size += sizeof(UA_MethodNode);
  67. break;
  68. case UA_NODECLASS_OBJECTTYPE:
  69. size += sizeof(UA_ObjectTypeNode);
  70. break;
  71. case UA_NODECLASS_VARIABLETYPE:
  72. size += sizeof(UA_VariableTypeNode);
  73. break;
  74. case UA_NODECLASS_REFERENCETYPE:
  75. size += sizeof(UA_ReferenceTypeNode);
  76. break;
  77. case UA_NODECLASS_DATATYPE:
  78. size += sizeof(UA_DataTypeNode);
  79. break;
  80. case UA_NODECLASS_VIEW:
  81. size += sizeof(UA_ViewNode);
  82. break;
  83. default:
  84. return NULL;
  85. }
  86. NodeEntry *entry = (NodeEntry*)UA_calloc(1, size);
  87. if(!entry)
  88. return NULL;
  89. UA_Node *node = (UA_Node*)&entry->nodeId;
  90. node->nodeClass = nodeClass;
  91. return entry;
  92. }
  93. static void
  94. deleteEntry(NodeEntry *entry) {
  95. UA_Node_clear((UA_Node*)&entry->nodeId);
  96. UA_free(entry);
  97. }
  98. static void
  99. cleanupEntry(NodeEntry *entry) {
  100. if(entry->deleted && entry->refCount == 0)
  101. deleteEntry(entry);
  102. }
  103. /***********************/
  104. /* Interface functions */
  105. /***********************/
  106. /* Not yet inserted into the ZipContext */
  107. static UA_Node *
  108. zipNsNewNode(void *nsCtx, UA_NodeClass nodeClass) {
  109. NodeEntry *entry = newEntry(nodeClass);
  110. if(!entry)
  111. return NULL;
  112. return (UA_Node*)&entry->nodeId;
  113. }
  114. /* Not yet inserted into the ZipContext */
  115. static void
  116. zipNsDeleteNode(void *nsCtx, UA_Node *node) {
  117. deleteEntry(container_of(node, NodeEntry, nodeId));
  118. }
  119. static const UA_Node *
  120. zipNsGetNode(void *nsCtx, const UA_NodeId *nodeId) {
  121. ZipContext *ns = (ZipContext*)nsCtx;
  122. BEGIN_CRITSECT(ns);
  123. NodeEntry dummy;
  124. dummy.nodeIdHash = UA_NodeId_hash(nodeId);
  125. dummy.nodeId = *nodeId;
  126. NodeEntry *entry = ZIP_FIND(NodeTree, &ns->root, &dummy);
  127. if(!entry) {
  128. END_CRITSECT(ns);
  129. return NULL;
  130. }
  131. ++entry->refCount;
  132. END_CRITSECT(ns);
  133. return (const UA_Node*)&entry->nodeId;
  134. }
  135. static void
  136. zipNsReleaseNode(void *nsCtx, const UA_Node *node) {
  137. if(!node)
  138. return;
  139. #if UA_MULTITHREADING >= 100
  140. ZipContext *ns = (ZipContext*)nsCtx;
  141. #endif
  142. BEGIN_CRITSECT(ns);
  143. NodeEntry *entry = container_of(node, NodeEntry, nodeId);
  144. UA_assert(entry->refCount > 0);
  145. --entry->refCount;
  146. cleanupEntry(entry);
  147. END_CRITSECT(ns);
  148. }
  149. static UA_StatusCode
  150. zipNsGetNodeCopy(void *nsCtx, const UA_NodeId *nodeId,
  151. UA_Node **outNode) {
  152. /* Find the node */
  153. const UA_Node *node = zipNsGetNode(nsCtx, nodeId);
  154. if(!node)
  155. return UA_STATUSCODE_BADNODEIDUNKNOWN;
  156. /* Create the new entry */
  157. NodeEntry *ne = newEntry(node->nodeClass);
  158. if(!ne) {
  159. zipNsReleaseNode(nsCtx, node);
  160. return UA_STATUSCODE_BADOUTOFMEMORY;
  161. }
  162. /* Copy the node content */
  163. UA_Node *nnode = (UA_Node*)&ne->nodeId;
  164. UA_StatusCode retval = UA_Node_copy(node, nnode);
  165. zipNsReleaseNode(nsCtx, node);
  166. if(retval != UA_STATUSCODE_GOOD) {
  167. deleteEntry(ne);
  168. return retval;
  169. }
  170. ne->orig = container_of(node, NodeEntry, nodeId);
  171. *outNode = nnode;
  172. return UA_STATUSCODE_GOOD;
  173. }
  174. static UA_StatusCode
  175. zipNsInsertNode(void *nsCtx, UA_Node *node, UA_NodeId *addedNodeId) {
  176. NodeEntry *entry = container_of(node, NodeEntry, nodeId);
  177. ZipContext *ns = (ZipContext*)nsCtx;
  178. BEGIN_CRITSECT(ns);
  179. /* Ensure that the NodeId is unique */
  180. NodeEntry dummy;
  181. dummy.nodeId = node->nodeId;
  182. if(node->nodeId.identifierType == UA_NODEIDTYPE_NUMERIC &&
  183. node->nodeId.identifier.numeric == 0) {
  184. do { /* Create a random nodeid until we find an unoccupied id */
  185. node->nodeId.identifier.numeric = UA_UInt32_random();
  186. dummy.nodeId.identifier.numeric = node->nodeId.identifier.numeric;
  187. dummy.nodeIdHash = UA_NodeId_hash(&node->nodeId);
  188. } while(ZIP_FIND(NodeTree, &ns->root, &dummy));
  189. } else {
  190. dummy.nodeIdHash = UA_NodeId_hash(&node->nodeId);
  191. if(ZIP_FIND(NodeTree, &ns->root, &dummy)) { /* The nodeid exists */
  192. deleteEntry(entry);
  193. END_CRITSECT(ns);
  194. return UA_STATUSCODE_BADNODEIDEXISTS;
  195. }
  196. }
  197. /* Copy the NodeId */
  198. if(addedNodeId) {
  199. UA_StatusCode retval = UA_NodeId_copy(&node->nodeId, addedNodeId);
  200. if(retval != UA_STATUSCODE_GOOD) {
  201. deleteEntry(entry);
  202. END_CRITSECT(ns);
  203. return retval;
  204. }
  205. }
  206. /* Insert the node */
  207. entry->nodeIdHash = dummy.nodeIdHash;
  208. ZIP_INSERT(NodeTree, &ns->root, entry, ZIP_FFS32(UA_UInt32_random()));
  209. END_CRITSECT(ns);
  210. return UA_STATUSCODE_GOOD;
  211. }
  212. static UA_StatusCode
  213. zipNsReplaceNode(void *nsCtx, UA_Node *node) {
  214. /* Find the node */
  215. const UA_Node *oldNode = zipNsGetNode(nsCtx, &node->nodeId);
  216. if(!oldNode) {
  217. deleteEntry(container_of(node, NodeEntry, nodeId));
  218. return UA_STATUSCODE_BADNODEIDUNKNOWN;
  219. }
  220. /* Test if the copy is current */
  221. NodeEntry *entry = container_of(node, NodeEntry, nodeId);
  222. NodeEntry *oldEntry = container_of(oldNode, NodeEntry, nodeId);
  223. if(oldEntry != entry->orig) {
  224. /* The node was already updated since the copy was made */
  225. deleteEntry(entry);
  226. zipNsReleaseNode(nsCtx, oldNode);
  227. return UA_STATUSCODE_BADINTERNALERROR;
  228. }
  229. /* Replace */
  230. ZipContext *ns = (ZipContext*)nsCtx;
  231. BEGIN_CRITSECT(ns);
  232. ZIP_REMOVE(NodeTree, &ns->root, oldEntry);
  233. entry->nodeIdHash = oldEntry->nodeIdHash;
  234. ZIP_INSERT(NodeTree, &ns->root, entry, ZIP_RANK(entry, zipfields));
  235. oldEntry->deleted = true;
  236. END_CRITSECT(ns);
  237. zipNsReleaseNode(nsCtx, oldNode);
  238. return UA_STATUSCODE_GOOD;
  239. }
  240. static UA_StatusCode
  241. zipNsRemoveNode(void *nsCtx, const UA_NodeId *nodeId) {
  242. ZipContext *ns = (ZipContext*)nsCtx;
  243. BEGIN_CRITSECT(ns);
  244. NodeEntry dummy;
  245. dummy.nodeIdHash = UA_NodeId_hash(nodeId);
  246. dummy.nodeId = *nodeId;
  247. NodeEntry *entry = ZIP_FIND(NodeTree, &ns->root, &dummy);
  248. if(!entry) {
  249. END_CRITSECT(ns);
  250. return UA_STATUSCODE_BADNODEIDUNKNOWN;
  251. }
  252. ZIP_REMOVE(NodeTree, &ns->root, entry);
  253. entry->deleted = true;
  254. cleanupEntry(entry);
  255. END_CRITSECT(ns);
  256. return UA_STATUSCODE_GOOD;
  257. }
  258. struct VisitorData {
  259. UA_NodestoreVisitor visitor;
  260. void *visitorContext;
  261. };
  262. static void
  263. nodeVisitor(NodeEntry *entry, void *data) {
  264. struct VisitorData *d = (struct VisitorData*)data;
  265. d->visitor(d->visitorContext, (UA_Node*)&entry->nodeId);
  266. }
  267. static void
  268. zipNsIterate(void *nsCtx, UA_NodestoreVisitor visitor,
  269. void *visitorCtx) {
  270. struct VisitorData d;
  271. d.visitor = visitor;
  272. d.visitorContext = visitorCtx;
  273. ZipContext *ns = (ZipContext*)nsCtx;
  274. BEGIN_CRITSECT(ns);
  275. ZIP_ITER(NodeTree, &ns->root, nodeVisitor, &d);
  276. END_CRITSECT(ns);
  277. }
  278. static void
  279. deleteNodeVisitor(NodeEntry *entry, void *data) {
  280. deleteEntry(entry);
  281. }
  282. /***********************/
  283. /* Nodestore Lifecycle */
  284. /***********************/
  285. static void
  286. zipNsClear(void *nsCtx) {
  287. if (!nsCtx)
  288. return;
  289. ZipContext *ns = (ZipContext*)nsCtx;
  290. #if UA_MULTITHREADING >= 100
  291. UA_LOCK_DESTROY(ns->lock);
  292. #endif
  293. ZIP_ITER(NodeTree, &ns->root, deleteNodeVisitor, NULL);
  294. UA_free(ns);
  295. }
  296. UA_StatusCode
  297. UA_Nodestore_ZipTree(UA_Nodestore *ns) {
  298. /* Allocate and initialize the context */
  299. ZipContext *ctx = (ZipContext*)UA_malloc(sizeof(ZipContext));
  300. if(!ctx)
  301. return UA_STATUSCODE_BADOUTOFMEMORY;
  302. #if UA_MULTITHREADING >= 100
  303. UA_LOCK_INIT(ctx->lock)
  304. #endif
  305. ZIP_INIT(&ctx->root);
  306. /* Populate the nodestore */
  307. ns->context = (void*)ctx;
  308. ns->clear = zipNsClear;
  309. ns->newNode = zipNsNewNode;
  310. ns->deleteNode = zipNsDeleteNode;
  311. ns->getNode = zipNsGetNode;
  312. ns->releaseNode = zipNsReleaseNode;
  313. ns->getNodeCopy = zipNsGetNodeCopy;
  314. ns->insertNode = zipNsInsertNode;
  315. ns->replaceNode = zipNsReplaceNode;
  316. ns->removeNode = zipNsRemoveNode;
  317. ns->iterate = zipNsIterate;
  318. return UA_STATUSCODE_GOOD;
  319. }