libpldm: add APIs to create entity associations

Add APIs to create entity associations (as described in DSP0248 v1.2.0).

The entity association hierarchy is represented as a
first-child/next-sibling n-ary tree. This commit adds APIs to create,
destroy, visit, and add to the tree.

Signed-off-by: Deepak Kodihalli <dkodihal@in.ibm.com>
Change-Id: I0d834c8cfea128a5b2586f889ccb9ddc7b5bca97
diff --git a/libpldm/pdr.c b/libpldm/pdr.c
index 5e792a5..f2d4aa1 100644
--- a/libpldm/pdr.c
+++ b/libpldm/pdr.c
@@ -301,3 +301,172 @@
 
 	return NULL;
 }
+
+typedef struct pldm_entity_association_tree {
+	pldm_entity_node *root;
+	uint16_t last_used_container_id;
+} pldm_entity_association_tree;
+
+typedef struct pldm_entity_node {
+	pldm_entity entity;
+	pldm_entity_node *first_child;
+	pldm_entity_node *next_sibling;
+	uint8_t association_type;
+} pldm_entity_node;
+
+static inline uint16_t next_container_id(pldm_entity_association_tree *tree)
+{
+	assert(tree != NULL);
+	assert(tree->last_used_container_id != UINT16_MAX);
+
+	return ++tree->last_used_container_id;
+}
+
+pldm_entity_association_tree *pldm_entity_association_tree_init()
+{
+	pldm_entity_association_tree *tree =
+	    malloc(sizeof(pldm_entity_association_tree));
+	assert(tree != NULL);
+	tree->root = NULL;
+	tree->last_used_container_id = 0;
+
+	return tree;
+}
+
+static pldm_entity_node *find_insertion_at(pldm_entity_node *start,
+					   uint16_t entity_type)
+{
+	assert(start != NULL);
+
+	/* Insert after the the last node that matches the input entity type, or
+	 * at the end if no such match occurrs
+	 */
+	while (start->next_sibling != NULL) {
+		uint16_t this_type = start->entity.entity_type;
+		pldm_entity_node *next = start->next_sibling;
+		if (this_type == entity_type &&
+		    (this_type != next->entity.entity_type)) {
+			break;
+		}
+		start = start->next_sibling;
+	}
+
+	return start;
+}
+
+pldm_entity_node *
+pldm_entity_association_tree_add(pldm_entity_association_tree *tree,
+				 pldm_entity *entity, pldm_entity_node *parent,
+				 uint8_t association_type)
+{
+	assert(tree != NULL);
+	assert(association_type == PLDM_ENTITY_ASSOCIAION_PHYSICAL ||
+	       association_type == PLDM_ENTITY_ASSOCIAION_LOGICAL);
+	pldm_entity_node *node = malloc(sizeof(pldm_entity_node));
+	assert(node != NULL);
+	node->first_child = NULL;
+	node->next_sibling = NULL;
+	node->entity.entity_type = entity->entity_type;
+	node->entity.entity_instance_num = 1;
+	node->association_type = association_type;
+
+	if (tree->root == NULL) {
+		assert(parent == NULL);
+		tree->root = node;
+		/* container_id 0 here indicates this is the top-most entry */
+		node->entity.entity_container_id = 0;
+	} else if (parent != NULL && parent->first_child == NULL) {
+		parent->first_child = node;
+		node->entity.entity_container_id = next_container_id(tree);
+	} else {
+		pldm_entity_node *start =
+		    parent == NULL ? tree->root : parent->first_child;
+		pldm_entity_node *prev =
+		    find_insertion_at(start, entity->entity_type);
+		assert(prev != NULL);
+		pldm_entity_node *next = prev->next_sibling;
+		if (prev->entity.entity_type == entity->entity_type) {
+			assert(prev->entity.entity_instance_num != UINT16_MAX);
+			node->entity.entity_instance_num =
+			    prev->entity.entity_instance_num + 1;
+		}
+		prev->next_sibling = node;
+		node->next_sibling = next;
+		node->entity.entity_container_id =
+		    prev->entity.entity_container_id;
+	}
+	entity->entity_instance_num = node->entity.entity_instance_num;
+	entity->entity_container_id = node->entity.entity_container_id;
+
+	return node;
+}
+
+static void get_num_nodes(pldm_entity_node *node, size_t *num)
+{
+	if (node == NULL) {
+		return;
+	}
+
+	++(*num);
+	get_num_nodes(node->next_sibling, num);
+	get_num_nodes(node->first_child, num);
+}
+
+static void entity_association_tree_visit(pldm_entity_node *node,
+					  pldm_entity *entities, size_t *index)
+{
+	if (node == NULL) {
+		return;
+	}
+
+	pldm_entity *entity = &entities[*index];
+	++(*index);
+	entity->entity_type = node->entity.entity_type;
+	entity->entity_instance_num = node->entity.entity_instance_num;
+	entity->entity_container_id = node->entity.entity_container_id;
+
+	entity_association_tree_visit(node->next_sibling, entities, index);
+	entity_association_tree_visit(node->first_child, entities, index);
+}
+
+void pldm_entity_association_tree_visit(pldm_entity_association_tree *tree,
+					pldm_entity **entities, size_t *size)
+{
+	assert(tree != NULL);
+
+	*size = 0;
+	if (tree->root == NULL) {
+		return;
+	}
+
+	get_num_nodes(tree->root, size);
+	*entities = malloc(*size * sizeof(pldm_entity));
+	size_t index = 0;
+	entity_association_tree_visit(tree->root, *entities, &index);
+}
+
+static void entity_association_tree_destroy(pldm_entity_node *node)
+{
+	if (node == NULL) {
+		return;
+	}
+
+	entity_association_tree_destroy(node->next_sibling);
+	entity_association_tree_destroy(node->first_child);
+	free(node);
+}
+
+void pldm_entity_association_tree_destroy(pldm_entity_association_tree *tree)
+{
+	assert(tree != NULL);
+
+	entity_association_tree_destroy(tree->root);
+	free(tree);
+}
+
+inline bool pldm_entity_is_node_parent(pldm_entity_node *node)
+{
+	assert(node != NULL);
+
+	return node->first_child != NULL;
+}
diff --git a/libpldm/pdr.h b/libpldm/pdr.h
index 7fe0f23..0e5690d 100644
--- a/libpldm/pdr.h
+++ b/libpldm/pdr.h
@@ -5,6 +5,8 @@
 extern "C" {
 #endif
 
+#include <stdbool.h>
+#include <stddef.h>
 #include <stdint.h>
 
 /** @struct pldm_pdr
@@ -174,6 +176,79 @@
     uint16_t *entity_type, uint16_t *entity_instance_num,
     uint16_t *container_id);
 
+/* =========================== */
+/* Entity Association PDR APIs */
+/* =========================== */
+
+typedef struct pldm_entity {
+	uint16_t entity_type;
+	uint16_t entity_instance_num;
+	uint16_t entity_container_id;
+} __attribute__((packed)) pldm_entity;
+
+enum entity_association_containment_type {
+	PLDM_ENTITY_ASSOCIAION_PHYSICAL = 0x0,
+	PLDM_ENTITY_ASSOCIAION_LOGICAL = 0x1
+};
+
+/** @struct pldm_entity_association_tree
+ *  opaque structure that represents the entity association hierarchy
+ */
+typedef struct pldm_entity_association_tree pldm_entity_association_tree;
+
+/** @struct pldm_entity_node
+ *  opaque structure that represents a node in the entity association hierarchy
+ */
+typedef struct pldm_entity_node pldm_entity_node;
+
+/** @brief Make a new entity association tree
+ *
+ *  @return opaque pointer that acts as a handle to the tree; NULL if no
+ *  tree could be created
+ */
+pldm_entity_association_tree *pldm_entity_association_tree_init();
+
+/** @brief Add an entity into the entity association tree
+ *
+ *  @param[in/out] tree - opaque pointer acting as a handle to the tree
+ *  @param[in/out] entity - pointer to the entity to be added. Input has the
+ *                          entity type. On output, instance number and the
+ *                          container id are populated.
+ *  @param[in] parent - pointer to the node that should be the parent of input
+ *                      entity. If this is NULL, then the entity is the root
+ *  @param[in] association_type - relation with the parent : logical or physical
+ *
+ *  @return pldm_entity_node* - opaque pointer to added entity
+ */
+pldm_entity_node *
+pldm_entity_association_tree_add(pldm_entity_association_tree *tree,
+				 pldm_entity *entity, pldm_entity_node *parent,
+				 uint8_t association_type);
+
+/** @brief Visit and note each entity in the entity association tree
+ *
+ *  @param[in] tree - opaque pointer acting as a handle to the tree
+ *  @param[out] entities - pointer to list of pldm_entity's. To be free()'d by
+ *                         the caller
+ *  @param[out] size - number of pldm_entity's
+ */
+void pldm_entity_association_tree_visit(pldm_entity_association_tree *tree,
+					pldm_entity **entities, size_t *size);
+
+/** @brief Destroy entity association tree
+ *
+ *  @param[in] tree - opaque pointer acting as a handle to the tree
+ */
+void pldm_entity_association_tree_destroy(pldm_entity_association_tree *tree);
+
+/** @brief Check if input enity node is a parent
+ *
+ *  @param[in] node - opaque pointer acting as a handle to an entity node
+ *
+ *  @return bool true if node is a parent, false otherwise
+ */
+bool pldm_entity_is_node_parent(pldm_entity_node *node);
+
 #ifdef __cplusplus
 }
 #endif
diff --git a/libpldm/tests/libpldm_pdr_test.cpp b/libpldm/tests/libpldm_pdr_test.cpp
index 1998823..cad64fc 100644
--- a/libpldm/tests/libpldm_pdr_test.cpp
+++ b/libpldm/tests/libpldm_pdr_test.cpp
@@ -318,3 +318,224 @@
 
     pldm_pdr_destroy(repo);
 }
+
+TEST(EntityAssociationPDR, testInit)
+{
+    auto tree = pldm_entity_association_tree_init();
+    EXPECT_NE(tree, nullptr);
+    pldm_entity_association_tree_destroy(tree);
+}
+
+TEST(EntityAssociationPDR, testBuild)
+{
+    //        1
+    //        |
+    //        2--3--4
+    //        |
+    //        5--6--7
+    //        |  |
+    //        9  8
+
+    pldm_entity entities[9]{};
+
+    entities[0].entity_type = 1;
+    entities[1].entity_type = 2;
+    entities[2].entity_type = 2;
+    entities[3].entity_type = 3;
+    entities[4].entity_type = 4;
+    entities[5].entity_type = 5;
+    entities[6].entity_type = 5;
+    entities[7].entity_type = 6;
+    entities[8].entity_type = 7;
+
+    auto tree = pldm_entity_association_tree_init();
+
+    auto l1 = pldm_entity_association_tree_add(tree, &entities[0], nullptr,
+                                               PLDM_ENTITY_ASSOCIAION_PHYSICAL);
+    EXPECT_NE(l1, nullptr);
+    auto l2a = pldm_entity_association_tree_add(
+        tree, &entities[1], l1, PLDM_ENTITY_ASSOCIAION_PHYSICAL);
+    EXPECT_NE(l2a, nullptr);
+    auto l2b = pldm_entity_association_tree_add(
+        tree, &entities[2], l1, PLDM_ENTITY_ASSOCIAION_PHYSICAL);
+    EXPECT_NE(l2b, nullptr);
+    auto l2c = pldm_entity_association_tree_add(
+        tree, &entities[3], l1, PLDM_ENTITY_ASSOCIAION_PHYSICAL);
+    EXPECT_NE(l2c, nullptr);
+    auto l3a = pldm_entity_association_tree_add(
+        tree, &entities[4], l2a, PLDM_ENTITY_ASSOCIAION_PHYSICAL);
+    EXPECT_NE(l3a, nullptr);
+    auto l3b = pldm_entity_association_tree_add(
+        tree, &entities[5], l2a, PLDM_ENTITY_ASSOCIAION_PHYSICAL);
+    EXPECT_NE(l3b, nullptr);
+    auto l3c = pldm_entity_association_tree_add(
+        tree, &entities[6], l2a, PLDM_ENTITY_ASSOCIAION_PHYSICAL);
+    EXPECT_NE(l3b, nullptr);
+    auto l4a = pldm_entity_association_tree_add(
+        tree, &entities[7], l3a, PLDM_ENTITY_ASSOCIAION_PHYSICAL);
+    EXPECT_NE(l4a, nullptr);
+    auto l4b = pldm_entity_association_tree_add(
+        tree, &entities[8], l3b, PLDM_ENTITY_ASSOCIAION_PHYSICAL);
+    EXPECT_NE(l4b, nullptr);
+
+    EXPECT_EQ(pldm_entity_is_node_parent(l1), true);
+    EXPECT_EQ(pldm_entity_is_node_parent(l2a), true);
+    EXPECT_EQ(pldm_entity_is_node_parent(l3a), true);
+    EXPECT_EQ(pldm_entity_is_node_parent(l3b), true);
+
+    EXPECT_EQ(pldm_entity_is_node_parent(l2b), false);
+    EXPECT_EQ(pldm_entity_is_node_parent(l2c), false);
+    EXPECT_EQ(pldm_entity_is_node_parent(l3c), false);
+    EXPECT_EQ(pldm_entity_is_node_parent(l4a), false);
+    EXPECT_EQ(pldm_entity_is_node_parent(l4b), false);
+
+    size_t num{};
+    pldm_entity* out = nullptr;
+    pldm_entity_association_tree_visit(tree, &out, &num);
+    EXPECT_EQ(num, 9);
+
+    EXPECT_EQ(out[0].entity_type, 1);
+    EXPECT_EQ(out[0].entity_instance_num, 1);
+    EXPECT_EQ(out[0].entity_container_id, 0);
+
+    EXPECT_EQ(out[1].entity_type, 2);
+    EXPECT_EQ(out[1].entity_instance_num, 1);
+    EXPECT_EQ(out[1].entity_container_id, 1);
+    EXPECT_EQ(out[2].entity_type, 2);
+    EXPECT_EQ(out[2].entity_instance_num, 2);
+    EXPECT_EQ(out[2].entity_container_id, 1);
+    EXPECT_EQ(out[3].entity_type, 3);
+    EXPECT_EQ(out[3].entity_instance_num, 1);
+    EXPECT_EQ(out[3].entity_container_id, 1);
+
+    EXPECT_EQ(out[4].entity_type, 4);
+    EXPECT_EQ(out[4].entity_instance_num, 1);
+    EXPECT_EQ(out[4].entity_container_id, 2);
+    EXPECT_EQ(out[5].entity_type, 5);
+    EXPECT_EQ(out[5].entity_instance_num, 1);
+    EXPECT_EQ(out[5].entity_container_id, 2);
+    EXPECT_EQ(out[6].entity_type, 5);
+    EXPECT_EQ(out[6].entity_instance_num, 2);
+    EXPECT_EQ(out[6].entity_container_id, 2);
+
+    EXPECT_EQ(out[7].entity_type, 7);
+    EXPECT_EQ(out[7].entity_instance_num, 1);
+    EXPECT_EQ(out[7].entity_container_id, 4);
+    EXPECT_EQ(out[8].entity_type, 6);
+    EXPECT_EQ(out[8].entity_instance_num, 1);
+    EXPECT_EQ(out[8].entity_container_id, 3);
+
+    free(out);
+    pldm_entity_association_tree_destroy(tree);
+}
+
+TEST(EntityAssociationPDR, testSpecialTrees)
+{
+    pldm_entity entities[3]{};
+
+    entities[0].entity_type = 1;
+    entities[1].entity_type = 2;
+    entities[2].entity_type = 1;
+
+    // A
+    auto tree = pldm_entity_association_tree_init();
+    auto node = pldm_entity_association_tree_add(
+        tree, &entities[0], nullptr, PLDM_ENTITY_ASSOCIAION_PHYSICAL);
+    EXPECT_NE(node, nullptr);
+    size_t num{};
+    pldm_entity* out = nullptr;
+    pldm_entity_association_tree_visit(tree, &out, &num);
+    EXPECT_EQ(num, 1);
+    EXPECT_EQ(out[0].entity_type, 1);
+    EXPECT_EQ(out[0].entity_instance_num, 1);
+    EXPECT_EQ(out[0].entity_container_id, 0);
+    free(out);
+    pldm_entity_association_tree_destroy(tree);
+
+    // A-A-A
+    tree = pldm_entity_association_tree_init();
+    node = pldm_entity_association_tree_add(tree, &entities[0], nullptr,
+                                            PLDM_ENTITY_ASSOCIAION_PHYSICAL);
+    EXPECT_NE(node, nullptr);
+    node = pldm_entity_association_tree_add(tree, &entities[1], nullptr,
+                                            PLDM_ENTITY_ASSOCIAION_PHYSICAL);
+    EXPECT_NE(node, nullptr);
+    node = pldm_entity_association_tree_add(tree, &entities[2], nullptr,
+                                            PLDM_ENTITY_ASSOCIAION_PHYSICAL);
+    EXPECT_NE(node, nullptr);
+    pldm_entity_association_tree_visit(tree, &out, &num);
+    EXPECT_EQ(num, 3);
+    EXPECT_EQ(out[0].entity_type, 1);
+    EXPECT_EQ(out[0].entity_instance_num, 1);
+    EXPECT_EQ(out[0].entity_container_id, 0);
+    EXPECT_EQ(out[1].entity_type, 1);
+    EXPECT_EQ(out[1].entity_instance_num, 2);
+    EXPECT_EQ(out[1].entity_container_id, 0);
+    EXPECT_EQ(out[2].entity_type, 2);
+    EXPECT_EQ(out[2].entity_instance_num, 1);
+    EXPECT_EQ(out[2].entity_container_id, 0);
+    free(out);
+    pldm_entity_association_tree_destroy(tree);
+
+    // A
+    // |
+    // A
+    // |
+    // A
+    tree = pldm_entity_association_tree_init();
+    node = pldm_entity_association_tree_add(tree, &entities[0], nullptr,
+                                            PLDM_ENTITY_ASSOCIAION_PHYSICAL);
+    EXPECT_NE(node, nullptr);
+    auto node1 = pldm_entity_association_tree_add(
+        tree, &entities[1], node, PLDM_ENTITY_ASSOCIAION_PHYSICAL);
+    EXPECT_NE(node1, nullptr);
+    auto node2 = pldm_entity_association_tree_add(
+        tree, &entities[2], node1, PLDM_ENTITY_ASSOCIAION_PHYSICAL);
+    EXPECT_NE(node2, nullptr);
+    pldm_entity_association_tree_visit(tree, &out, &num);
+    EXPECT_EQ(num, 3);
+    EXPECT_EQ(out[0].entity_type, 1);
+    EXPECT_EQ(out[0].entity_instance_num, 1);
+    EXPECT_EQ(out[0].entity_container_id, 0);
+    EXPECT_EQ(out[1].entity_type, 2);
+    EXPECT_EQ(out[1].entity_instance_num, 1);
+    EXPECT_EQ(out[1].entity_container_id, 1);
+    EXPECT_EQ(out[2].entity_type, 1);
+    EXPECT_EQ(out[2].entity_instance_num, 1);
+    EXPECT_EQ(out[2].entity_container_id, 2);
+    free(out);
+    pldm_entity_association_tree_destroy(tree);
+
+    // A-A
+    //   |
+    //   A-A
+    tree = pldm_entity_association_tree_init();
+    node = pldm_entity_association_tree_add(tree, &entities[0], nullptr,
+                                            PLDM_ENTITY_ASSOCIAION_PHYSICAL);
+    EXPECT_NE(node, nullptr);
+    node = pldm_entity_association_tree_add(tree, &entities[0], nullptr,
+                                            PLDM_ENTITY_ASSOCIAION_PHYSICAL);
+    EXPECT_NE(node, nullptr);
+    node1 = pldm_entity_association_tree_add(tree, &entities[1], node,
+                                             PLDM_ENTITY_ASSOCIAION_PHYSICAL);
+    EXPECT_NE(node1, nullptr);
+    node2 = pldm_entity_association_tree_add(tree, &entities[2], node,
+                                             PLDM_ENTITY_ASSOCIAION_PHYSICAL);
+    EXPECT_NE(node2, nullptr);
+    pldm_entity_association_tree_visit(tree, &out, &num);
+    EXPECT_EQ(num, 4);
+    EXPECT_EQ(out[0].entity_type, 1);
+    EXPECT_EQ(out[0].entity_instance_num, 1);
+    EXPECT_EQ(out[0].entity_container_id, 0);
+    EXPECT_EQ(out[1].entity_type, 1);
+    EXPECT_EQ(out[1].entity_instance_num, 2);
+    EXPECT_EQ(out[1].entity_container_id, 0);
+    EXPECT_EQ(out[2].entity_type, 2);
+    EXPECT_EQ(out[2].entity_instance_num, 1);
+    EXPECT_EQ(out[2].entity_container_id, 1);
+    EXPECT_EQ(out[3].entity_type, 1);
+    EXPECT_EQ(out[3].entity_instance_num, 1);
+    EXPECT_EQ(out[3].entity_container_id, 1);
+    free(out);
+    pldm_entity_association_tree_destroy(tree);
+}