Lines Matching refs:topo
116 static void addEdge (pANTLR3_TOPO topo, ANTLR3_UINT32 edge, ANTLR3_UINT32 dependency);
117 static pANTLR3_UINT32 sortToArray (pANTLR3_TOPO topo);
118 static void sortVector (pANTLR3_TOPO topo, pANTLR3_VECTOR v);
119 static void freeTopo (pANTLR3_TOPO topo);
2272 pANTLR3_TOPO topo;
2273 topo = antlr3NewTopo();
2275 if (topo == NULL) { out of memory }
2277 topo->addEdge(topo, 3, 0); // Node 3 depends on node 0
2278 topo->addEdge(topo, 0, 1); // Node - depends on node 1
2279 topo->sortVector(topo, myVector); // Sort the vector in place (node numbers are the vector entry numbers)
2286 pANTLR3_TOPO topo = (pANTLR3_TOPO)ANTLR3_MALLOC(sizeof(ANTLR3_TOPO));
2288 if (topo == NULL)
2296 topo->visited = NULL; // Don't know how big it is yet
2297 topo->limit = 1; // No edges added yet
2298 topo->edges = NULL; // No edges added yet
2299 topo->sorted = NULL; // Nothing sorted at the start
2300 topo->cycle = NULL; // No cycles at the start
2301 topo->cycleMark = 0; // No cycles at the start
2302 topo->hasCycle = ANTLR3_FALSE; // No cycle at the start
2306 topo->addEdge = addEdge;
2307 topo->sortToArray = sortToArray;
2308 topo->sortVector = sortVector;
2309 topo->free = freeTopo;
2311 return topo;
2316 addEdge (pANTLR3_TOPO topo, ANTLR3_UINT32 edge, ANTLR3_UINT32 dependency)
2336 if (topo->edges == NULL)
2340 topo->edges = ANTLR3_CALLOC(sizeof(pANTLR3_BITSET) * (maxEdge + 1), 1);
2341 if (topo->edges == NULL)
2348 topo->limit = maxEdge + 1;
2350 else if (topo->limit <= maxEdge)
2354 topo->edges = ANTLR3_REALLOC(topo->edges, sizeof(pANTLR3_BITSET) * (maxEdge + 1));
2355 if (topo->edges == NULL)
2362 for (i = topo->limit; i <= maxEdge; i++)
2364 *((topo->edges) + i) = NULL;
2369 topo->limit = maxEdge + 1;
2383 edgeDeps = *((topo->edges) + edge);
2390 *((topo->edges) + edge) = edgeDeps;
2415 DFS(pANTLR3_TOPO topo, ANTLR3_UINT32 node)
2421 if (topo->hasCycle == ANTLR3_TRUE)
2426 if (topo->visited->isMember(topo->visited, node))
2433 for (i=0; i<topo->cycleMark; i++)
2435 if (topo->cycle[i] == node)
2443 for (l = i; l < topo->cycleMark; l++)
2445 topo->cycle[l - i] = topo->cycle[l]; // Move to zero base in the cycle list
2450 topo->cycleMark -= i;
2454 topo->hasCycle = ANTLR3_TRUE;
2465 topo->cycle[topo->cycleMark++] = node;
2469 topo->visited->add(topo->visited, node);
2475 edges = *((topo->edges) + node);
2500 DFS(topo, i);
2510 topo->sorted[topo->limit++] = node;
2514 if (topo->hasCycle == ANTLR3_FALSE)
2516 topo->cycleMark--;
2523 sortToArray (pANTLR3_TOPO topo)
2530 if (topo->edges == NULL)
2538 topo->sorted = ANTLR3_MALLOC(topo->limit * sizeof(ANTLR3_UINT32));
2539 topo->cycle = ANTLR3_MALLOC(topo->limit * sizeof(ANTLR3_UINT32));
2547 topo->visited = antlr3BitsetNew(0);
2552 oldLimit = topo->limit; // Number of nodes to traverse linearly
2553 topo->limit = 0; // Next entry in the sorted table
2560 if (topo->visited->isMember(topo->visited, v) == ANTLR3_FALSE)
2564 DFS(topo, v);
2570 if (topo->hasCycle == ANTLR3_TRUE)
2581 topo->limit = oldLimit;
2587 return topo->sorted;
2591 sortVector (pANTLR3_TOPO topo, pANTLR3_VECTOR v)
2611 // stored in the topo
2613 if (topo->sortToArray(topo) == 0)
2618 if (topo->hasCycle == ANTLR3_TRUE)
2628 if (topo->limit > v->count)
2634 topo->limit = v->count;
2642 vIndex = ANTLR3_MALLOC(topo->limit * sizeof(ANTLR3_UINT32));
2646 for (i = 0; i < topo->limit; i++)
2656 for (i=0; i < topo->limit; i++)
2663 if (vIndex[topo->sorted[i]] == i)
2669 // vector entry indicated by topo->sorted[i]. The vector entry
2670 // at topo->sorted[i] may have already been swapped out though, so we
2673 ind = vIndex[topo->sorted[i]];
2681 vIndex[topo->sorted[i]] = i;
2692 freeTopo (pANTLR3_TOPO topo)
2698 if (topo->sorted != NULL)
2700 ANTLR3_FREE(topo->sorted);
2701 topo->sorted = NULL;
2706 if (topo->visited != NULL)
2709 topo->visited->free(topo->visited);
2710 topo->visited = NULL;
2715 if (topo->edges != NULL)
2720 for (i=0; i<topo
2722 edgeList = *((topo->edges) + i);
2729 ANTLR3_FREE(topo->edges);
2731 topo->edges = NULL;
2735 if (topo->cycle != NULL)
2737 ANTLR3_FREE(topo->cycle);
2740 ANTLR3_FREE(topo);
