src/fvid2_graph.c

   1 /*
   2  *  Copyright (c) Texas Instruments Incorporated 2018
   3  *
   4  *  Redistribution and use in source and binary forms, with or without
   5  *  modification, are permitted provided that the following conditions
   6  *  are met:
   7  *
   8  *    Redistributions of source code must retain the above copyright
   9  *    notice, this list of conditions and the following disclaimer.
  10  *
  11  *    Redistributions in binary form must reproduce the above copyright
  12  *    notice, this list of conditions and the following disclaimer in the
  13  *    documentation and/or other materials provided with the
  14  *    distribution.
  15  *
  16  *    Neither the name of Texas Instruments Incorporated nor the names of
  17  *    its contributors may be used to endorse or promote products derived
  18  *    from this software without specific prior written permission.
  19  *
  20  *  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  21  *  "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  22  *  LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  23  *  A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  24  *  OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  25  *  SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  26  *  LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  27  *  DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  28  *  THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  29  *  (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  30  *  OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  31  */
  32
  33 /**
  34  *  \file fvid2_graph.c
  35  *
  36  *  \brief File containing the graph functions for resource management.
  37  *
  38  */
  39
  40 /* ========================================================================== */
  41 /*                             Include Files                                  */
  42 /* ========================================================================== */
  43
  44 #include <stdint.h>
  45 #include <ti/drv/fvid2/fvid2.h>
  46
  47 /* ========================================================================== */
  48 /*                           Macros & Typedefs                                */
  49 /* ========================================================================== */
  50
  51 /* None */
  52
  53 /* ========================================================================== */
  54 /*                         Structure Declarations                             */
  55 /* ========================================================================== */
  56
  57 /* None */
  58
  59 /* ========================================================================== */
  60 /*                         Internal Function Declarations                     */
  61 /* ========================================================================== */
  62
  63 static int32_t Fvid2_graphConnect(const Fvid2_GraphNodeList *inNodeList,
  64                                   const Fvid2_GraphEdgeList *inEdgeList);
  65
  66 /* ========================================================================== */
  67 /*                            Global Variables                                */
  68 /* ========================================================================== */
  69
  70 /* None */
  71
  72 /* ========================================================================== */
  73 /*                          Function Definitions                              */
  74 /* ========================================================================== */
  75
  76 Fvid2_GraphInfo *Fvid2_graphInit(const Fvid2_GraphNodeList *inNodeList,
  77                                  const Fvid2_GraphEdgeList *inEdgeList,
  78                                  Fvid2_GraphInfo *graphHandle)
  79 {
  80     GT_assert(Fvid2Trace, (graphHandle != NULL));
  81     GT_assert(Fvid2Trace, (graphHandle->nodeList != NULL));
  82     GT_assert(Fvid2Trace, (graphHandle->edgeList != NULL));
  83
  84     GT_assert(Fvid2Trace, (inNodeList != NULL));
  85     GT_assert(Fvid2Trace, (inEdgeList != NULL));
  86
  87     graphHandle->nodeList->numNodes = inNodeList->numNodes;
  88     graphHandle->edgeList->numEdges = inEdgeList->numEdges;
  89     graphHandle->nodeList->list = inNodeList->list;
  90     graphHandle->edgeList->list = inEdgeList->list;
  91
  92     Fvid2_graphConnect(inNodeList, inEdgeList);
  93     return graphHandle;
  94 }
  95
  96 int32_t Fvid2_graphDeInit(Fvid2_GraphInfo *graphHandle)
  97 {
  98     return FVID2_SOK;
  99 }
 100
 101 Fvid2_GraphNodeInfo *Fvid2_graphGetNodeInfo(
 102                             const Fvid2_GraphNodeList *nodeList,
 103                             uint32_t nodeIndex)
 104 {
 105     Fvid2_GraphNodeInfo *node = NULL;
 106     if (nodeIndex < nodeList->numNodes)
 107     {
 108         node = &nodeList->list[nodeIndex];
 109     }
 110     return (node);
 111 }
 112
 113 uint32_t Fvid2_graphIsNodeInputAvailable(
 114                             const Fvid2_GraphNodeList *nodeList,
 115                             uint32_t nodeId)
 116 {
 117     uint32_t j;
 118     uint32_t retVal  = TRUE;
 119     Fvid2_GraphNodeInfo *curNode = Fvid2_graphGetNodeInfo(nodeList, nodeId);
 120     if (NULL == curNode)
 121     {
 122         retVal = FALSE;
 123     }
 124     else
 125     {
 126         for (j = 0; j < curNode->inputNodeSet.numNodes; j++)
 127         {
 128             if (FVID2_GRAPH_NODE_MODE_ENABLE ==
 129                                             curNode->inputNodeSet.isEnabled[j])
 130             {
 131                 retVal = FALSE;
 132                 break;
 133             }
 134         }
 135     }
 136     return retVal;
 137 }
 138
 139 uint32_t Fvid2_graphIsNodeOutputAvailable(
 140                             const Fvid2_GraphNodeList *nodeList,
 141                             uint32_t nodeId)
 142 {
 143     uint32_t j;
 144     uint32_t retVal  = TRUE;
 145     Fvid2_GraphNodeInfo *curNode = Fvid2_graphGetNodeInfo(nodeList, nodeId);
 146     if (NULL == curNode)
 147     {
 148         retVal = FALSE;
 149     }
 150     else
 151     {
 152         for (j = 0; j < curNode->outputNodeSet.numNodes; j++)
 153         {
 154             if (FVID2_GRAPH_NODE_MODE_ENABLE ==
 155                                             curNode->outputNodeSet.isEnabled[j])
 156             {
 157                 retVal = FALSE;
 158                 break;
 159             }
 160         }
 161     }
 162     return retVal;
 163 }
 164
 165 int32_t Fvid2_graphAllocNodes(const Fvid2_GraphNodeList *nodeList,
 166                               const Fvid2_GraphEdgeList *edgeList,
 167                               uint32_t graphNodeMode)
 168 {
 169     uint32_t i, j;
 170     int32_t retVal = FVID2_SOK;
 171     Fvid2_GraphEdgeInfo *inputEdgeList = edgeList->list;
 172     for (i = 0; i < edgeList->numEdges; i++)
 173     {
 174         Fvid2_GraphNodeInfo *startNode = Fvid2_graphGetNodeInfo(
 175             nodeList, inputEdgeList[i].startNode);
 176         GT_assert(Fvid2Trace, (startNode != NULL));
 177         Fvid2_GraphNodeInfo *endNode = Fvid2_graphGetNodeInfo(
 178             nodeList, inputEdgeList[i].endNode);
 179         GT_assert(Fvid2Trace, (endNode != NULL));
 180         if ((startNode->nodeId == FVID2_GRAPH_INVALID_NODE_ID) &&
 181             (endNode->nodeId == FVID2_GRAPH_INVALID_NODE_ID))
 182         {
 183             break;
 184         }
 185
 186         /* Multiple connections from different path does not work */
 187         if (FVID2_GRAPH_NODE_OUT_SINGLE == startNode->nodeOutNum)
 188         {
 189             uint32_t inUse = FALSE;
 190             for (j = 0; j < startNode->outputNodeSet.numNodes; j++)
 191             {
 192                 if (FVID2_GRAPH_NODE_MODE_ENABLE ==
 193                                         startNode->outputNodeSet.isEnabled[j])
 194                 {
 195                     inUse = TRUE;
 196                     break;
 197                 }
 198             }
 199             if ((FALSE == inUse) ||
 200                 (FVID2_GRAPH_NODE_MODE_DISABLE == graphNodeMode))
 201             {
 202                 for (j = 0; j < startNode->outputNodeSet.numNodes; j++)
 203                 {
 204                     if (startNode->outputNodeSet.node[j] == endNode)
 205                     {
 206                         startNode->outputNodeSet.isEnabled[j] = graphNodeMode;
 207                         break;
 208                     }
 209                 }
 210                 if (j == startNode->outputNodeSet.numNodes)
 211                 {
 212                     retVal = FVID2_EFAIL;
 213                 }
 214             }
 215         }
 216         else if (FVID2_GRAPH_NODE_OUT_MULTI == startNode->nodeOutNum)
 217         {
 218             for (j = 0; j < startNode->outputNodeSet.numNodes; j++)
 219             {
 220                 if (startNode->outputNodeSet.node[j] == endNode)
 221                 {
 222                     startNode->outputNodeSet.isEnabled[j] = graphNodeMode;
 223                     break;
 224                 }
 225             }
 226             if (j == startNode->outputNodeSet.numNodes)
 227             {
 228                 retVal = FVID2_EFAIL;
 229             }
 230         }
 231         else
 232         {
 233             /*Do nothing */
 234         }
 235
 236         if (FVID2_GRAPH_NODE_IN_SINGLE == endNode->nodeInNum)
 237         {
 238             uint32_t inUse = FALSE;
 239             for (j = 0; j < endNode->inputNodeSet.numNodes; j++)
 240             {
 241                 if (FVID2_GRAPH_NODE_MODE_ENABLE == endNode->inputNodeSet.isEnabled[j])
 242                 {
 243                     inUse = TRUE;
 244                     break;
 245                 }
 246             }
 247             if ((FALSE == inUse) ||
 248                 (FVID2_GRAPH_NODE_MODE_DISABLE == graphNodeMode))
 249             {
 250                 for (j = 0; j < endNode->inputNodeSet.numNodes; j++)
 251                 {
 252                     if (endNode->inputNodeSet.node[j] == startNode)
 253                     {
 254                         endNode->inputNodeSet.isEnabled[j] = graphNodeMode;
 255                         break;
 256                     }
 257                 }
 258                 if (j == endNode->inputNodeSet.numNodes)
 259                 {
 260                     retVal = FVID2_EFAIL;
 261                 }
 262             }
 263         }
 264         else if (FVID2_GRAPH_NODE_IN_MULTI == endNode->nodeInNum)
 265         {
 266             for (j = 0; j < endNode->inputNodeSet.numNodes; j++)
 267             {
 268                 if (endNode->inputNodeSet.node[j] == startNode)
 269                 {
 270                     endNode->inputNodeSet.isEnabled[j] = graphNodeMode;
 271                     break;
 272                 }
 273             }
 274             if (j == endNode->inputNodeSet.numNodes)
 275             {
 276                 retVal = FVID2_EFAIL;
 277             }
 278         }
 279         else
 280         {
 281             /*Do nothing */
 282         }
 283     }
 284
 285     return retVal;
 286 }
 287
 288 int32_t Fvid2_graphGetPath(const Fvid2_GraphNodeList *inNodeList,
 289                            const Fvid2_GraphEdgeList *inEdgeList,
 290                            Fvid2_GraphNodeList *outNodeList,
 291                            Fvid2_GraphEdgeList *outEdgeList,
 292                            uint32_t maxOutNodeCnt,
 293                            uint32_t maxOutEdgeCnt)
 294 {
 295     uint32_t i, j;
 296     uint32_t pathEdgeCount = inEdgeList->numEdges;
 297     uint32_t pathNodeCount = 0U;
 298     uint32_t numInNodes = inNodeList->numNodes;
 299     uint32_t nodes[FVID2_GRAPH_MAX_NODES] = {0U};
 300
 301     for (i = 0; i < inEdgeList->numEdges; i++)
 302     {
 303         j = inEdgeList->list[i].startNode;
 304         nodes[j] = 1U;
 305         j = inEdgeList->list[i].endNode;
 306         nodes[j] = 1U;
 307     }
 308
 309     for (i = 0; i < numInNodes; i++)
 310     {
 311         if (nodes[i] == 1U)
 312         {
 313             pathNodeCount++;
 314         }
 315     }
 316
 317     GT_assert(Fvid2Trace, (pathNodeCount < maxOutNodeCnt));
 318     outNodeList->numNodes = pathNodeCount;
 319
 320     GT_assert(Fvid2Trace, (outNodeList->list != NULL));
 321
 322     GT_assert(Fvid2Trace, (pathEdgeCount < maxOutEdgeCnt));
 323     outEdgeList->numEdges = pathEdgeCount;
 324     GT_assert(Fvid2Trace, (outEdgeList->list != NULL));
 325
 326     for (i = 0U; i < pathEdgeCount; i++)
 327     {
 328         outEdgeList->list[i].startNode = inEdgeList->list[i].startNode;
 329         outEdgeList->list[i].endNode = inEdgeList->list[i].endNode;
 330     }
 331
 332     j = 0U;
 333     for (i = 0U; i < numInNodes; i++)
 334     {
 335         if (nodes[i] == 1U)
 336         {
 337             Fvid2Utils_memcpy((void *) &outNodeList->list[j],
 338                               (void *) &inNodeList->list[i],
 339                               sizeof (Fvid2_GraphNodeInfo));
 340
 341             /* Reset connection info from the original graph */
 342             Fvid2Utils_memset((void *)(outNodeList->list[j].inputNodeSet.node),
 343                               0,
 344                               sizeof (Fvid2_GraphNodeInfo *)
 345                                                    * FVID2_GRAPH_MAX_NUM_PATHS);
 346             Fvid2Utils_memset((void *)(outNodeList->list[j].outputNodeSet.node),
 347                               0,
 348                               sizeof (Fvid2_GraphNodeInfo *)
 349                                                    * FVID2_GRAPH_MAX_NUM_PATHS);
 350             j++;
 351         }
 352     }
 353
 354     return FVID2_SOK;
 355 }
 356
 357 int32_t Fvid2_graphFreePath(Fvid2_GraphNodeList *nodeList,
 358                             Fvid2_GraphEdgeList *edgeList)
 359 {
 360     if (NULL != nodeList->list)
 361     {
 362         nodeList->numNodes = 0U;
 363         nodeList->list = NULL;
 364     }
 365     if (NULL != edgeList->list)
 366     {
 367         edgeList->numEdges = 0U;
 368         edgeList->list = NULL;
 369     }
 370     return FVID2_SOK;
 371 }
 372
 373 int32_t Fvid2_graphGetEnabledIndex(const uint32_t *array, uint32_t size)
 374 {
 375     uint32_t i;
 376     int32_t  retVal = FVID2_EFAIL;
 377
 378     for (i = 0; i < size; i++)
 379     {
 380         if ((uint32_t) 0 != array[i])
 381         {
 382             retVal = (int32_t) i;
 383             break;
 384         }
 385     }
 386     return retVal;
 387 }
 388
 389 void Fvid2_graphAddEdge(Fvid2_GraphEdgeInfo *edge,
 390                         uint32_t startNode,
 391                         uint32_t endNode)
 392 {
 393     if (startNode != endNode)
 394     {
 395         edge->startNode = startNode;
 396         edge->endNode = endNode;
 397     }
 398 }
 399
 400 static int32_t Fvid2_graphConnect(const Fvid2_GraphNodeList *inNodeList,
 401                                   const Fvid2_GraphEdgeList *inEdgeList)
 402 {
 403     Fvid2_GraphNodeInfo *nodes = inNodeList->list;
 404     Fvid2_GraphEdgeInfo *edges = inEdgeList->list;
 405     uint32_t cnt, startNode, endNode, index1, index2;
 406     for (cnt = 0; cnt < inNodeList->numNodes; cnt++)
 407     {
 408         Fvid2Utils_memset(&nodes[cnt].inputNodeSet,
 409                           0,
 410                           sizeof (Fvid2_GraphNodeSet));
 411         Fvid2Utils_memset(&nodes[cnt].outputNodeSet,
 412                           0,
 413                           sizeof (Fvid2_GraphNodeSet));
 414     }
 415
 416     for (cnt = 0U; cnt < inEdgeList->numEdges; cnt++)
 417     {
 418         startNode = edges[cnt].startNode;
 419         endNode   = edges[cnt].endNode;
 420         /* End Node is output node for the start Node so update
 421          * information in start node*/
 422         index1 = nodes[startNode].outputNodeSet.numNodes;
 423         nodes[startNode].outputNodeSet.node[index1] = &nodes[endNode];
 424         nodes[startNode].outputNodeSet.numNodes++;
 425         GT_assert(Fvid2Trace, (index1 < FVID2_GRAPH_MAX_NUM_PATHS));
 426
 427         /* Start Node is input node for the end Node so update
 428          * information in end node*/
 429         index2 = nodes[endNode].inputNodeSet.numNodes;
 430         nodes[endNode].inputNodeSet.node[index2] = &nodes[startNode];
 431         nodes[endNode].inputNodeSet.numNodes++;
 432         GT_assert(Fvid2Trace, (index2 < FVID2_GRAPH_MAX_NUM_PATHS));
 433
 434         /* Dummy node's input is always enabled */
 435         if ((TRUE == nodes[endNode].isDummy) &&
 436             (TRUE == nodes[startNode].isDummy))
 437         {
 438             nodes[startNode].outputNodeSet.isEnabled[index1] = TRUE;
 439             nodes[endNode].inputNodeSet.isEnabled[index2]    = TRUE;
 440         }
 441     }
 442
 443     return FVID2_SOK;
 444 }