ua_nodestore_default.c 13 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410
  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 "ua_nodestore_default.h"
  9. #include "ziptree.h"
  10. #ifdef UA_ENABLE_MULTITHREADING
  11. #include <pthread.h>
  12. #define BEGIN_CRITSECT(NODEMAP) pthread_mutex_lock(&(NODEMAP)->mutex)
  13. #define END_CRITSECT(NODEMAP) pthread_mutex_unlock(&(NODEMAP)->mutex)
  14. #else
  15. #define BEGIN_CRITSECT(NODEMAP)
  16. #define END_CRITSECT(NODEMAP)
  17. #endif
  18. /* container_of */
  19. #define container_of(ptr, type, member) \
  20. (type *)((uintptr_t)ptr - offsetof(type,member))
  21. struct NodeEntry;
  22. typedef struct NodeEntry NodeEntry;
  23. struct NodeEntry {
  24. ZIP_ENTRY(NodeEntry) zipfields;
  25. UA_UInt32 nodeIdHash;
  26. UA_UInt16 refCount; /* How many consumers have a reference to the node? */
  27. UA_Boolean deleted; /* Node was marked as deleted and can be deleted when refCount == 0 */
  28. NodeEntry *orig; /* If a copy is made to replace a node, track that we
  29. * replace only the node from which the copy was made.
  30. * Important for concurrent operations. */
  31. UA_NodeId nodeId; /* This is actually a UA_Node that also starts with a NodeId */
  32. };
  33. /* Absolute ordering for NodeIds */
  34. static enum ZIP_CMP
  35. cmpNodeId(const void *a, const void *b) {
  36. const NodeEntry *aa = (const NodeEntry*)a;
  37. const NodeEntry *bb = (const NodeEntry*)b;
  38. /* Compare hash */
  39. if(aa->nodeIdHash < bb->nodeIdHash)
  40. return ZIP_CMP_LESS;
  41. if(aa->nodeIdHash > bb->nodeIdHash)
  42. return ZIP_CMP_MORE;
  43. if(UA_NodeId_equal(&aa->nodeId, &bb->nodeId))
  44. return ZIP_CMP_EQ;
  45. /* Compare namespaceIndex */
  46. if(aa->nodeId.namespaceIndex < bb->nodeId.namespaceIndex)
  47. return ZIP_CMP_LESS;
  48. if(aa->nodeId.namespaceIndex > bb->nodeId.namespaceIndex)
  49. return ZIP_CMP_MORE;
  50. /* Compare identifierType */
  51. if(aa->nodeId.identifierType < bb->nodeId.identifierType)
  52. return ZIP_CMP_LESS;
  53. if(aa->nodeId.identifierType > bb->nodeId.identifierType)
  54. return ZIP_CMP_MORE;
  55. /* Compare the identifier */
  56. switch(aa->nodeId.identifierType) {
  57. case UA_NODEIDTYPE_NUMERIC:
  58. if(aa->nodeId.identifier.numeric < bb->nodeId.identifier.numeric)
  59. return ZIP_CMP_LESS;
  60. if(aa->nodeId.identifier.numeric > bb->nodeId.identifier.numeric)
  61. return ZIP_CMP_MORE;
  62. break;
  63. case UA_NODEIDTYPE_GUID:
  64. if(aa->nodeId.identifier.guid.data1 < bb->nodeId.identifier.guid.data1 ||
  65. aa->nodeId.identifier.guid.data2 < bb->nodeId.identifier.guid.data2 ||
  66. aa->nodeId.identifier.guid.data3 < bb->nodeId.identifier.guid.data3 ||
  67. strncmp((const char*)aa->nodeId.identifier.guid.data4,
  68. (const char*)bb->nodeId.identifier.guid.data4, 8) < 0)
  69. return ZIP_CMP_LESS;
  70. if(aa->nodeId.identifier.guid.data1 > bb->nodeId.identifier.guid.data1 ||
  71. aa->nodeId.identifier.guid.data2 > bb->nodeId.identifier.guid.data2 ||
  72. aa->nodeId.identifier.guid.data3 > bb->nodeId.identifier.guid.data3 ||
  73. strncmp((const char*)aa->nodeId.identifier.guid.data4,
  74. (const char*)bb->nodeId.identifier.guid.data4, 8) > 0)
  75. return ZIP_CMP_MORE;
  76. break;
  77. case UA_NODEIDTYPE_STRING:
  78. case UA_NODEIDTYPE_BYTESTRING: {
  79. if(aa->nodeId.identifier.string.length < bb->nodeId.identifier.string.length)
  80. return ZIP_CMP_LESS;
  81. if(aa->nodeId.identifier.string.length > bb->nodeId.identifier.string.length)
  82. return ZIP_CMP_MORE;
  83. int cmp = strncmp((const char*)aa->nodeId.identifier.string.data,
  84. (const char*)bb->nodeId.identifier.string.data,
  85. aa->nodeId.identifier.string.length);
  86. if(cmp < 0)
  87. return ZIP_CMP_LESS;
  88. if(cmp > 0)
  89. return ZIP_CMP_MORE;
  90. break;
  91. }
  92. default:
  93. break;
  94. }
  95. return ZIP_CMP_EQ;
  96. }
  97. ZIP_HEAD(NodeTree, NodeEntry);
  98. typedef struct NodeTree NodeTree;
  99. typedef struct {
  100. NodeTree root;
  101. #ifdef UA_ENABLE_MULTITHREADING
  102. pthread_mutex_t mutex; /* Protect access */
  103. #endif
  104. } NodeMap;
  105. ZIP_PROTTYPE(NodeTree, NodeEntry, NodeEntry)
  106. ZIP_IMPL(NodeTree, NodeEntry, zipfields, NodeEntry, zipfields, cmpNodeId)
  107. static NodeEntry *
  108. newEntry(UA_NodeClass nodeClass) {
  109. size_t size = sizeof(NodeEntry) - sizeof(UA_NodeId);
  110. switch(nodeClass) {
  111. case UA_NODECLASS_OBJECT:
  112. size += sizeof(UA_ObjectNode);
  113. break;
  114. case UA_NODECLASS_VARIABLE:
  115. size += sizeof(UA_VariableNode);
  116. break;
  117. case UA_NODECLASS_METHOD:
  118. size += sizeof(UA_MethodNode);
  119. break;
  120. case UA_NODECLASS_OBJECTTYPE:
  121. size += sizeof(UA_ObjectTypeNode);
  122. break;
  123. case UA_NODECLASS_VARIABLETYPE:
  124. size += sizeof(UA_VariableTypeNode);
  125. break;
  126. case UA_NODECLASS_REFERENCETYPE:
  127. size += sizeof(UA_ReferenceTypeNode);
  128. break;
  129. case UA_NODECLASS_DATATYPE:
  130. size += sizeof(UA_DataTypeNode);
  131. break;
  132. case UA_NODECLASS_VIEW:
  133. size += sizeof(UA_ViewNode);
  134. break;
  135. default:
  136. return NULL;
  137. }
  138. NodeEntry *entry = (NodeEntry*)UA_calloc(1, size);
  139. if(!entry)
  140. return NULL;
  141. UA_Node *node = (UA_Node*)&entry->nodeId;
  142. node->nodeClass = nodeClass;
  143. return entry;
  144. }
  145. static void
  146. deleteEntry(NodeEntry *entry) {
  147. UA_Node_deleteMembers((UA_Node*)&entry->nodeId);
  148. UA_free(entry);
  149. }
  150. static void
  151. cleanupEntry(NodeEntry *entry) {
  152. if(entry->deleted && entry->refCount == 0)
  153. deleteEntry(entry);
  154. }
  155. /***********************/
  156. /* Interface functions */
  157. /***********************/
  158. /* Not yet inserted into the NodeMap */
  159. static UA_Node *
  160. NodeMap_newNode(void *context, UA_NodeClass nodeClass) {
  161. NodeEntry *entry = newEntry(nodeClass);
  162. if(!entry)
  163. return NULL;
  164. return (UA_Node*)&entry->nodeId;
  165. }
  166. /* Not yet inserted into the NodeMap */
  167. static void
  168. NodeMap_deleteNode(void *context, UA_Node *node) {
  169. deleteEntry(container_of(node, NodeEntry, nodeId));
  170. }
  171. static const UA_Node *
  172. NodeMap_getNode(void *context, const UA_NodeId *nodeid) {
  173. NodeMap *ns = (NodeMap*)context;
  174. BEGIN_CRITSECT(ns);
  175. NodeEntry dummy;
  176. dummy.nodeIdHash = UA_NodeId_hash(nodeid);
  177. dummy.nodeId = *nodeid;
  178. NodeEntry *entry = ZIP_FIND(NodeTree, &ns->root, &dummy);
  179. if(!entry) {
  180. END_CRITSECT(ns);
  181. return NULL;
  182. }
  183. ++entry->refCount;
  184. END_CRITSECT(ns);
  185. return (const UA_Node*)&entry->nodeId;
  186. }
  187. static void
  188. NodeMap_releaseNode(void *context, const UA_Node *node) {
  189. if(!node)
  190. return;
  191. #ifdef UA_ENABLE_MULTITHREADING
  192. NodeMap *ns = (NodeMap*)context;
  193. #endif
  194. BEGIN_CRITSECT(ns);
  195. NodeEntry *entry = container_of(node, NodeEntry, nodeId);
  196. UA_assert(entry->refCount > 0);
  197. --entry->refCount;
  198. cleanupEntry(entry);
  199. END_CRITSECT(ns);
  200. }
  201. static UA_StatusCode
  202. NodeMap_getNodeCopy(void *context, const UA_NodeId *nodeid,
  203. UA_Node **outNode) {
  204. /* Find the node */
  205. const UA_Node *node = NodeMap_getNode(context, nodeid);
  206. if(!node)
  207. return UA_STATUSCODE_BADNODEIDUNKNOWN;
  208. /* Create the new entry */
  209. NodeEntry *ne = newEntry(node->nodeClass);
  210. if(!ne) {
  211. NodeMap_releaseNode(context, node);
  212. return UA_STATUSCODE_BADOUTOFMEMORY;
  213. }
  214. /* Copy the node content */
  215. UA_Node *nnode = (UA_Node*)&ne->nodeId;
  216. UA_StatusCode retval = UA_Node_copy(node, nnode);
  217. NodeMap_releaseNode(context, node);
  218. if(retval != UA_STATUSCODE_GOOD) {
  219. deleteEntry(ne);
  220. return retval;
  221. }
  222. ne->orig = container_of(node, NodeEntry, nodeId);
  223. *outNode = nnode;
  224. return UA_STATUSCODE_GOOD;
  225. }
  226. static UA_StatusCode
  227. NodeMap_removeNode(void *context, const UA_NodeId *nodeid) {
  228. NodeMap *ns = (NodeMap*)context;
  229. BEGIN_CRITSECT(ns);
  230. NodeEntry dummy;
  231. dummy.nodeIdHash = UA_NodeId_hash(nodeid);
  232. dummy.nodeId = *nodeid;
  233. NodeEntry *entry = ZIP_FIND(NodeTree, &ns->root, &dummy);
  234. if(!entry) {
  235. END_CRITSECT(ns);
  236. return UA_STATUSCODE_BADNODEIDUNKNOWN;
  237. }
  238. ZIP_REMOVE(NodeTree, &ns->root, entry);
  239. entry->deleted = true;
  240. cleanupEntry(entry);
  241. END_CRITSECT(ns);
  242. return UA_STATUSCODE_GOOD;
  243. }
  244. static UA_StatusCode
  245. NodeMap_insertNode(void *context, UA_Node *node,
  246. UA_NodeId *addedNodeId) {
  247. NodeEntry *entry = container_of(node, NodeEntry, nodeId);
  248. NodeMap *ns = (NodeMap*)context;
  249. BEGIN_CRITSECT(ns);
  250. /* Ensure that the NodeId is unique */
  251. NodeEntry dummy;
  252. dummy.nodeId = node->nodeId;
  253. if(node->nodeId.identifierType == UA_NODEIDTYPE_NUMERIC &&
  254. node->nodeId.identifier.numeric == 0) {
  255. do { /* Create a random nodeid until we find an unoccupied id */
  256. node->nodeId.identifier.numeric = UA_UInt32_random();
  257. dummy.nodeId.identifier.numeric = node->nodeId.identifier.numeric;
  258. dummy.nodeIdHash = UA_NodeId_hash(&node->nodeId);
  259. } while(ZIP_FIND(NodeTree, &ns->root, &dummy));
  260. } else {
  261. dummy.nodeIdHash = UA_NodeId_hash(&node->nodeId);
  262. if(ZIP_FIND(NodeTree, &ns->root, &dummy)) { /* The nodeid exists */
  263. deleteEntry(entry);
  264. END_CRITSECT(ns);
  265. return UA_STATUSCODE_BADNODEIDEXISTS;
  266. }
  267. }
  268. /* Copy the NodeId */
  269. if(addedNodeId) {
  270. UA_StatusCode retval = UA_NodeId_copy(&node->nodeId, addedNodeId);
  271. if(retval != UA_STATUSCODE_GOOD) {
  272. deleteEntry(entry);
  273. END_CRITSECT(ns);
  274. return retval;
  275. }
  276. }
  277. /* Insert the node */
  278. entry->nodeIdHash = dummy.nodeIdHash;
  279. ZIP_INSERT(NodeTree, &ns->root, entry, ZIP_FFS32(UA_UInt32_random()));
  280. END_CRITSECT(ns);
  281. return UA_STATUSCODE_GOOD;
  282. }
  283. static UA_StatusCode
  284. NodeMap_replaceNode(void *context, UA_Node *node) {
  285. /* Find the node */
  286. const UA_Node *oldNode = NodeMap_getNode(context, &node->nodeId);
  287. if(!oldNode)
  288. return UA_STATUSCODE_BADNODEIDUNKNOWN;
  289. /* Test if the copy is current */
  290. NodeEntry *entry = container_of(node, NodeEntry, nodeId);
  291. NodeEntry *oldEntry = container_of(oldNode, NodeEntry, nodeId);
  292. if(oldEntry != entry->orig) {
  293. /* The node was already updated since the copy was made */
  294. deleteEntry(entry);
  295. NodeMap_releaseNode(context, oldNode);
  296. return UA_STATUSCODE_BADINTERNALERROR;
  297. }
  298. /* Replace */
  299. NodeMap *ns = (NodeMap*)context;
  300. BEGIN_CRITSECT(ns);
  301. ZIP_REMOVE(NodeTree, &ns->root, oldEntry);
  302. entry->nodeIdHash = oldEntry->nodeIdHash;
  303. ZIP_INSERT(NodeTree, &ns->root, entry, ZIP_RANK(entry, zipfields));
  304. oldEntry->deleted = true;
  305. END_CRITSECT(ns);
  306. NodeMap_releaseNode(context, oldNode);
  307. return UA_STATUSCODE_GOOD;
  308. }
  309. struct VisitorData {
  310. UA_NodestoreVisitor visitor;
  311. void *visitorContext;
  312. };
  313. static void
  314. nodeVisitor(NodeEntry *entry, void *data) {
  315. struct VisitorData *d = (struct VisitorData*)data;
  316. d->visitor(d->visitorContext, (UA_Node*)&entry->nodeId);
  317. }
  318. static void
  319. NodeMap_iterate(void *context, void *visitorContext,
  320. UA_NodestoreVisitor visitor) {
  321. struct VisitorData d;
  322. d.visitor = visitor;
  323. d.visitorContext = visitorContext;
  324. NodeMap *ns = (NodeMap*)context;
  325. BEGIN_CRITSECT(ns);
  326. ZIP_ITER(NodeTree, &ns->root, nodeVisitor, &d);
  327. END_CRITSECT(ns);
  328. }
  329. static void
  330. deleteNodeVisitor(NodeEntry *entry, void *data) {
  331. deleteEntry(entry);
  332. }
  333. static void
  334. NodeMap_delete(void *context) {
  335. NodeMap *ns = (NodeMap*)context;
  336. #ifdef UA_ENABLE_MULTITHREADING
  337. pthread_mutex_destroy(&ns->mutex);
  338. #endif
  339. ZIP_ITER(NodeTree, &ns->root, deleteNodeVisitor, NULL);
  340. UA_free(ns);
  341. }
  342. UA_StatusCode
  343. UA_Nodestore_default_new(UA_Nodestore *ns) {
  344. /* Allocate and initialize the nodemap */
  345. NodeMap *nodemap = (NodeMap*)UA_malloc(sizeof(NodeMap));
  346. if(!nodemap)
  347. return UA_STATUSCODE_BADOUTOFMEMORY;
  348. #ifdef UA_ENABLE_MULTITHREADING
  349. pthread_mutex_init(&nodemap->mutex, NULL);
  350. #endif
  351. ZIP_INIT(&nodemap->root);
  352. /* Populate the nodestore */
  353. ns->context = nodemap;
  354. ns->deleteNodestore = NodeMap_delete;
  355. ns->inPlaceEditAllowed = true;
  356. ns->newNode = NodeMap_newNode;
  357. ns->deleteNode = NodeMap_deleteNode;
  358. ns->getNode = NodeMap_getNode;
  359. ns->releaseNode = NodeMap_releaseNode;
  360. ns->getNodeCopy = NodeMap_getNodeCopy;
  361. ns->insertNode = NodeMap_insertNode;
  362. ns->replaceNode = NodeMap_replaceNode;
  363. ns->removeNode = NodeMap_removeNode;
  364. ns->iterate = NodeMap_iterate;
  365. return UA_STATUSCODE_GOOD;
  366. }