fork download
copy 
  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <stdlib.h>
  4.  
  5. typedef struct
  6. {
  7.   void* pElements;
  8.   size_t ElementSize;
  9.   size_t Count; // how many elements exist
  10.   size_t TotalCount; // for how many elements space allocated
  11. } tArray;
  12.  
  13. void ArrayInit(tArray* pArray, size_t ElementSize)
  14. {
  15.   pArray->pElements = NULL;
  16.   pArray->ElementSize = ElementSize;
  17.   pArray->TotalCount = pArray->Count = 0;
  18. }
  19.  
  20. void ArrayDestroy(tArray* pArray)
  21. {
  22.   free(pArray->pElements);
  23.   ArrayInit(pArray, 0);
  24. }
  25.  
  26. int ArrayGrowByOne(tArray* pArray)
  27. {
  28.   if (pArray->Count == pArray->TotalCount) // used up all allocated space
  29.   {
  30.     size_t newTotalCount, newTotalSize;
  31.     void* p;
  32.  
  33.     if (pArray->TotalCount == 0)
  34.     {
  35.       newTotalCount = 1;
  36.     }
  37.     else
  38.     {
  39.       newTotalCount = 2 * pArray->TotalCount; // double the allocated count
  40.       if (newTotalCount / 2 != pArray->TotalCount) // count overflow
  41.         return 0;
  42.     }
  43.  
  44.     newTotalSize = newTotalCount * pArray->ElementSize;
  45.     if (newTotalSize / pArray->ElementSize != newTotalCount) // size overflow
  46.       return 0;
  47.  
  48.     p = realloc(pArray->pElements, newTotalSize);
  49.     if (p == NULL) // out of memory
  50.       return 0;
  51.  
  52.     pArray->pElements = p;
  53.     pArray->TotalCount = newTotalCount;
  54.   }
  55.  
  56.   pArray->Count++;
  57.   return 1;
  58. }
  59.  
  60. int ArrayInsertElement(tArray* pArray, size_t pos, void* pElement)
  61. {
  62.   if (pos > pArray->Count) // bad position
  63.     return 0;
  64.  
  65.   if (!ArrayGrowByOne(pArray)) // couldn't grow
  66.     return 0;
  67.  
  68.   if (pos < pArray->Count - 1)
  69.     memmove((char*)pArray->pElements + (pos + 1) * pArray->ElementSize,
  70.            (char*)pArray->pElements + pos * pArray->ElementSize,
  71.            (pArray->Count - 1 - pos) * pArray->ElementSize);
  72.  
  73.   memcpy((char*)pArray->pElements + pos * pArray->ElementSize,
  74.          pElement,
  75.          pArray->ElementSize);
  76.  
  77.   return 1;
  78. }
  79.  
  80. typedef struct
  81. {
  82.   int Id;
  83.  
  84.   int Data;
  85.  
  86.   tArray LinksTo; // links from this node to other nodes (array of Id's)
  87.   tArray LinksFrom; // back links from other nodes to this node (array of Id's)
  88. } tNode;
  89.  
  90. typedef struct
  91. {
  92.   tArray Nodes;
  93. } tGraph;
  94.  
  95. void GraphInit(tGraph* pGraph)
  96. {
  97.   ArrayInit(&pGraph->Nodes, sizeof(tNode));
  98. }
  99.  
  100. void GraphPrintNodes(tGraph* pGraph)
  101. {
  102.   size_t i, j;
  103.  
  104.   if (pGraph->Nodes.Count == 0)
  105.   {
  106.     printf("Empty graph.\n");
  107.   }
  108.  
  109.   for (i = 0; i < pGraph->Nodes.Count; i++)
  110.   {
  111.     tNode* pNode = (tNode*)pGraph->Nodes.pElements + i;
  112.  
  113.     printf("Node %d:\n  Data: %d\n", pNode->Id, pNode->Data);
  114.  
  115.     if (pNode->LinksTo.Count)
  116.     {
  117.       printf("  Links to:\n");
  118.  
  119.       for (j = 0; j < pNode->LinksTo.Count; j++)
  120.       {
  121.         int* p = (int*)pNode->LinksTo.pElements + j;
  122.         printf("    Node %d\n", *p);
  123.       }
  124.     }
  125.   }
  126. }
  127.  
  128. void GraphDestroy(tGraph* pGraph)
  129. {
  130.   size_t i;
  131.  
  132.   for (i = 0; i < pGraph->Nodes.Count; i++)
  133.   {
  134.     tNode* pNode = (tNode*)pGraph->Nodes.pElements + i;
  135.     ArrayDestroy(&pNode->LinksTo);
  136.     ArrayDestroy(&pNode->LinksFrom);
  137.   }
  138.  
  139.   ArrayDestroy(&pGraph->Nodes);
  140. }
  141.  
  142. int NodeIdComparator(const void* p1, const void* p2)
  143. {
  144.   const tNode* pa = p1;
  145.   const tNode* pb = p2;
  146.  
  147.   if (pa->Id < pb->Id)
  148.     return -1;
  149.   if (pa->Id > pb->Id)
  150.     return 1;
  151.   return 0;
  152. }
  153.  
  154. int IntComparator(const void* p1, const void* p2)
  155. {
  156.   const int* pa = p1;
  157.   const int* pb = p2;
  158.  
  159.   if (*pa < *pb)
  160.     return -1;
  161.   if (*pa > *pb)
  162.     return 1;
  163.   return 0;
  164. }
  165.  
  166. size_t GraphFindNodeIndexById(tGraph* pGraph, int Id)
  167. {
  168.   tNode* pNode = bsearch(&Id,
  169.                          pGraph->Nodes.pElements,
  170.                          pGraph->Nodes.Count,
  171.                          pGraph->Nodes.ElementSize,
  172.                          &NodeIdComparator);
  173.  
  174.   if (pNode == NULL)
  175.     return (size_t)-1;
  176.  
  177.   return pNode - (tNode*)pGraph->Nodes.pElements;
  178. }
  179.  
  180. int GraphInsertNode(tGraph* pGraph, int Id, int Data)
  181. {
  182.   size_t idx = GraphFindNodeIndexById(pGraph, Id);
  183.   tNode node;
  184.  
  185.   if (idx != (size_t)-1) // node with this Id already exist
  186.     return 0;
  187.  
  188.   node.Id = Id;
  189.   node.Data = Data;
  190.   ArrayInit(&node.LinksTo, sizeof(int));
  191.   ArrayInit(&node.LinksFrom, sizeof(int));
  192.  
  193.   if (!ArrayInsertElement(&pGraph->Nodes, pGraph->Nodes.Count, &node))
  194.     return 0;
  195.  
  196.   qsort(pGraph->Nodes.pElements,
  197.         pGraph->Nodes.Count,
  198.         pGraph->Nodes.ElementSize,
  199.         &NodeIdComparator); // maintain order for binary search
  200.  
  201.   return 1;
  202. }
  203.  
  204. int GraphLinkNodes(tGraph* pGraph, int IdFrom, int IdTo)
  205. {
  206.   size_t idxFrom = GraphFindNodeIndexById(pGraph, IdFrom);
  207.   size_t idxTo = GraphFindNodeIndexById(pGraph, IdTo);
  208.   tNode *pFrom, *pTo;
  209.  
  210.   if (idxFrom == (size_t)-1 || idxTo == (size_t)-1) // one or both nodes don't exist
  211.     return 0;
  212.  
  213.   pFrom = (tNode*)pGraph->Nodes.pElements + idxFrom;
  214.   pTo = (tNode*)pGraph->Nodes.pElements + idxTo;
  215.  
  216.   // link IdFrom -> IdTo
  217.   if (bsearch(&IdTo,
  218.               pFrom->LinksTo.pElements,
  219.               pFrom->LinksTo.Count,
  220.               pFrom->LinksTo.ElementSize,
  221.               &IntComparator) == NULL) // IdFrom doesn't link to IdTo yet
  222.   {
  223.     if (!ArrayInsertElement(&pFrom->LinksTo, pFrom->LinksTo.Count, &IdTo))
  224.       return 0;
  225.  
  226.     qsort(pFrom->LinksTo.pElements,
  227.           pFrom->LinksTo.Count,
  228.           pFrom->LinksTo.ElementSize,
  229.           &IntComparator); // maintain order for binary search
  230.   }
  231.  
  232.   // back link IdFrom <- IdTo
  233.   if (bsearch(&IdFrom,
  234.               pTo->LinksFrom.pElements,
  235.               pTo->LinksFrom.Count,
  236.               pTo->LinksFrom.ElementSize,
  237.               &IntComparator) == NULL) // IdFrom doesn't link to IdTo yet
  238.   {
  239.     if (!ArrayInsertElement(&pTo->LinksFrom, pTo->LinksFrom.Count, &IdFrom))
  240.       return 0;
  241.  
  242.     qsort(pTo->LinksFrom.pElements,
  243.           pTo->LinksFrom.Count,
  244.           pTo->LinksFrom.ElementSize,
  245.           &IntComparator); // maintain order for binary search
  246.   }
  247.  
  248.   return 1;
  249. }
  250.  
  251. int main(void)
  252. {
  253.   tGraph g;
  254.  
  255.   printf("\nCreating empty graph...\n");
  256.   GraphInit(&g);
  257.   GraphPrintNodes(&g);
  258.  
  259.   printf("\nInserting nodes...\n");
  260.   GraphInsertNode(&g, 0, 0);
  261.   GraphInsertNode(&g, 1, 101);
  262.   GraphInsertNode(&g, 2, 202);
  263.   GraphPrintNodes(&g);
  264.  
  265.   printf("\nLinking nodes...\n");
  266.   GraphLinkNodes(&g, 0, 1);
  267.   GraphLinkNodes(&g, 0, 2);
  268.   GraphLinkNodes(&g, 1, 2);
  269.   GraphLinkNodes(&g, 2, 1);
  270.   GraphPrintNodes(&g);
  271.  
  272.   printf("\nDestroying graph...\n");
  273.   GraphDestroy(&g);
  274.   GraphPrintNodes(&g);
  275.  
  276.   // repeat
  277.   printf("\nLet's repeat...\n");
  278.  
  279.   printf("\nCreating empty graph...\n");
  280.   GraphInit(&g);
  281.   GraphPrintNodes(&g);
  282.  
  283.   printf("\nInserting nodes...\n");
  284.   GraphInsertNode(&g, 1, 111);
  285.   GraphInsertNode(&g, 2, 222);
  286.   GraphInsertNode(&g, 3, 333);
  287.   GraphPrintNodes(&g);
  288.  
  289.   printf("\nLinking nodes...\n");
  290.   GraphLinkNodes(&g, 1, 2);
  291.   GraphLinkNodes(&g, 2, 3);
  292.   GraphLinkNodes(&g, 3, 1);
  293.   GraphPrintNodes(&g);
  294.  
  295.   printf("\nDestroying graph...\n");
  296.   GraphDestroy(&g);
  297.   GraphPrintNodes(&g);
  298.  
  299.   return 0;
  300. }
  301.  
Success #stdin #stdout 0s 1968KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Creating empty graph...
Empty graph.

Inserting nodes...
Node 0:
  Data: 0
Node 1:
  Data: 101
Node 2:
  Data: 202

Linking nodes...
Node 0:
  Data: 0
  Links to:
    Node 1
    Node 2
Node 1:
  Data: 101
  Links to:
    Node 2
Node 2:
  Data: 202
  Links to:
    Node 1

Destroying graph...
Empty graph.

Let's repeat...

Creating empty graph...
Empty graph.

Inserting nodes...
Node 1:
  Data: 111
Node 2:
  Data: 222
Node 3:
  Data: 333

Linking nodes...
Node 1:
  Data: 111
  Links to:
    Node 2
Node 2:
  Data: 222
  Links to:
    Node 3
Node 3:
  Data: 333
  Links to:
    Node 1

Destroying graph...
Empty graph.
https://ideone.com/3fD8BC
language:
C99 (gcc 8.3)
created:
12 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!