Lines Matching defs: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);
2271 pANTLR3_TOPO topo;
2272 topo = antlr3NewTopo();
2274 if (topo == NULL) { out of memory }
2276 topo->addEdge(topo, 3, 0); // Node 3 depends on node 0
2277 topo->addEdge(topo, 0, 1); // Node - depends on node 1
2278 topo->sortVector(topo, myVector); // Sort the vector in place (node numbers are the vector entry numbers)
2285 pANTLR3_TOPO topo = (pANTLR3_TOPO)ANTLR3_MALLOC(sizeof(ANTLR3_TOPO));
2287 if (topo == NULL)
2295 topo->visited = NULL; // Don't know how big it is yet
2296 topo->limit = 1; // No edges added yet
2297 topo->edges = NULL; // No edges added yet
2298 topo->sorted = NULL; // Nothing sorted at the start
2299 topo->cycle = NULL; // No cycles at the start
2300 topo->cycleMark = 0; // No cycles at the start
2301 topo->hasCycle = ANTLR3_FALSE; // No cycle at the start
2305 topo->addEdge = addEdge;
2306 topo->sortToArray = sortToArray;
2307 topo->sortVector = sortVector;
2308 topo->free = freeTopo;
2310 return topo;
2315 addEdge (pANTLR3_TOPO topo, ANTLR3_UINT32 edge, ANTLR3_UINT32 dependency)
2335 if (topo->edges == NULL)
2339 topo->edges = ANTLR3_CALLOC(sizeof(pANTLR3_BITSET) * (maxEdge + 1), 1);
2340 if (topo->edges == NULL)
2347 topo->limit = maxEdge + 1;
2349 else if (topo->limit <= maxEdge)
2353 topo->edges = ANTLR3_REALLOC(topo->edges, sizeof(pANTLR3_BITSET) * (maxEdge + 1));
2354 if (topo->edges == NULL)
2361 for (i = topo->limit; i <= maxEdge; i++)
2363 *((topo->edges) + i) = NULL;
2368 topo->limit = maxEdge + 1;
2382 edgeDeps = *((topo->edges) + edge);
2389 *((topo->edges) + edge) = edgeDeps;
2414 DFS(pANTLR3_TOPO topo, ANTLR3_UINT32 node)
2420 if (topo->hasCycle == ANTLR3_TRUE)
2425 if (topo->visited->isMember(topo->visited, node))
2432 for (i=0; i<topo->cycleMark; i++)
2434 if (topo->cycle[i] == node)
2442 for (l = i; l < topo->cycleMark; l++)
2444 topo->cycle[l - i] = topo->cycle[l]; // Move to zero base in the cycle list
2449 topo->cycleMark -= i;
2453 topo->hasCycle = ANTLR3_TRUE;
2464 topo->cycle[topo->cycleMark++] = node;
2468 topo->visited->add(topo->visited, node);
2474 edges = *((topo->edges) + node);
2499 DFS(topo, i);
2509 topo->sorted[topo->limit++] = node;
2513 if (topo->hasCycle == ANTLR3_FALSE)
2515 topo->cycleMark--;
2522 sortToArray (pANTLR3_TOPO topo)
2529 if (topo->edges == NULL)
2537 topo->sorted = ANTLR3_MALLOC(topo->limit * sizeof(ANTLR3_UINT32));
2538 topo->cycle = ANTLR3_MALLOC(topo->limit * sizeof(ANTLR3_UINT32));
2546 topo->visited = antlr3BitsetNew(0);
2551 oldLimit = topo->limit; // Number of nodes to traverse linearly
2552 topo->limit = 0; // Next entry in the sorted table
2559 if (topo->visited->isMember(topo->visited, v) == ANTLR3_FALSE)
2563 DFS(topo, v);
2569 if (topo->hasCycle == ANTLR3_TRUE)
2580 topo->limit = oldLimit;
2586 return topo->sorted;
2590 sortVector (pANTLR3_TOPO topo, pANTLR3_VECTOR v)
2610 // stored in the topo
2612 if (topo->sortToArray(topo) == 0)
2617 if (topo->hasCycle == ANTLR3_TRUE)
2627 if (topo->limit > v->count)
2633 topo->limit = v->count;
2641 vIndex = ANTLR3_MALLOC(topo->limit * sizeof(ANTLR3_UINT32));
2645 for (i = 0; i < topo->limit; i++)
2655 for (i=0; i < topo->limit; i++)
2662 if (vIndex[topo->sorted[i]] == i)
2668 // vector entry indicated by topo->sorted[i]. The vector entry
2669 // at topo->sorted[i] may have already been swapped out though, so we
2672 ind = vIndex[topo->sorted[i]];
2680 vIndex[topo->sorted[i]] = i;
2691 freeTopo (pANTLR3_TOPO topo)
2697 if (topo->sorted != NULL)
2699 ANTLR3_FREE(topo->sorted);
2700 topo->sorted = NULL;
2705 if (topo->visited != NULL)
2708 topo->visited->free(topo->visited);
2709 topo->visited = NULL;
2714 if (topo->edges != NULL)
2719 for (i=0; i<topo->limit; i++)
2721 edgeList = *((topo->edges) + i);
2728 ANTLR3_FREE(topo->edges);
2730 topo->edges = NULL;
2734 if (topo->cycle != NULL)
2736 ANTLR3_FREE(topo->cycle);
2739 ANTLR3_FREE(topo);