GRASS GIS 8 Programmer's Manual  8.4.0dev(2024)-535c39c9fc
misc-template.c
Go to the documentation of this file.
1 /* LIBDGL -- a Directed Graph Library implementation
2  * Copyright (C) 2002 Roberto Micarelli
3  *
4  * This program is free software; you can redistribute it and/or modify
5  * it under the terms of the GNU General Public License as published by
6  * the Free Software Foundation; either version 2 of the License, or
7  * (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software
16  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
17  */
18 
19 /*
20  * best view with tabstop=4
21  */
22 
23 #include <grass/gis.h>
24 
25 /*
26  * Edge Traversing
27  */
31 {
32 #if defined(_DGL_V1)
33  pGraph->iErrno = DGL_ERR_NotSupported;
34  return -pGraph->iErrno;
35 #else
36  if (pGraph->Flags & DGL_GS_FLAT) {
37  if (pEP && pEP->pvAVL) {
38  if ((pT->pvAVLT = malloc(sizeof(struct avl_traverser))) == NULL) {
40  return -pGraph->iErrno;
41  }
42  avl_t_init(pT->pvAVLT, pEP->pvAVL);
43  pT->pnEdge = NULL;
44  pT->pEdgePrioritizer = pEP;
45  }
46  else {
47  pT->pvAVLT = NULL;
48  pT->pnEdge = NULL;
49  pT->pEdgePrioritizer = NULL;
50  }
51  }
52  else {
53  if ((pT->pvAVLT = malloc(sizeof(struct avl_traverser))) == NULL) {
55  return -pGraph->iErrno;
56  }
57  if (pEP && pEP->pvAVL) {
58  avl_t_init(pT->pvAVLT, pEP->pvAVL);
59  pT->pnEdge = NULL;
60  pT->pEdgePrioritizer = pEP;
61  }
62  else {
63  avl_t_init(pT->pvAVLT, pGraph->pEdgeTree);
64  pT->pnEdge = NULL;
65  pT->pEdgePrioritizer = NULL;
66  }
67  }
68  pT->pGraph = pGraph;
69  return 0;
70 #endif
71 }
72 
74 {
75 #if defined(_DGL_V1)
77 #else
78  if (pT->pvAVLT)
79  free(pT->pvAVLT);
80  pT->pvAVLT = NULL;
81  pT->pnEdge = NULL;
82  pT->pEdgePrioritizer = NULL;
83 #endif
84 }
85 
87 {
88 #if defined(_DGL_V1)
90  return NULL;
91 #else
92  dglGraph_s *pG = pT->pGraph;
93 
94  pT->pnEdge = NULL;
95  if (pT->pvAVLT && pT->pEdgePrioritizer) {
97  dglTreeEdgePri32_s *pItem;
98 
99  pItem = avl_t_first(pT->pvAVLT, pPri->pvAVL);
100  if (pItem) {
101  /*
102  printf("edge_t_first: cEdge=%ld\n", pItem->cnData);
103  */
104  pPri->cEdge = pItem->cnData;
105  pPri->iEdge = 0;
106  if (pPri->iEdge < pPri->cEdge) {
107  pT->pnEdge = DGL_GET_EDGE_FUNC(pG, pItem->pnData[pPri->iEdge]);
108  pPri->iEdge++;
109  }
110  }
111  pPri->pEdgePri32Item = pItem;
112  }
113  else if (pT->pvAVLT) {
114  dglTreeEdge_s *pEdgeItem;
115 
116  if ((pEdgeItem = avl_t_first(pT->pvAVLT, pG->pEdgeTree)) == NULL) {
117  pT->pnEdge = NULL;
118  }
119  else {
120  pT->pnEdge = pEdgeItem->pv;
121  }
122  }
123  else {
124  if (pG->cEdge > 0)
125  pT->pnEdge = (dglInt32_t *)pG->pEdgeBuffer;
126  else
127  pT->pnEdge = NULL;
128  }
129  return pT->pnEdge;
130 #endif
131 }
132 
134 {
135 #if defined(_DGL_V1)
137  return NULL;
138 #else
139  dglGraph_s *pG = pT->pGraph;
140 
141  pT->pnEdge = NULL;
142 
143  if (pT->pvAVLT && pT->pEdgePrioritizer) {
145  dglTreeEdgePri32_s *pItem = pPri->pEdgePri32Item;
146 
147  if (pItem && pPri->iEdge < pPri->cEdge) {
148  pT->pnEdge = DGL_GET_EDGE_FUNC(pG, pItem->pnData[pPri->iEdge]);
149  pPri->iEdge++;
150  }
151  else {
152  if ((pItem = avl_t_next(pT->pvAVLT)) != NULL) {
153  pPri->cEdge = pItem->cnData;
154  pPri->iEdge = 0;
155  if (pPri->iEdge < pPri->cEdge) {
156  pT->pnEdge =
157  DGL_GET_EDGE_FUNC(pG, pItem->pnData[pPri->iEdge]);
158  pPri->iEdge++;
159  }
160  }
161  pPri->pEdgePri32Item = pItem;
162  }
163  }
164  else if (pT->pvAVLT) {
165  dglTreeEdge_s *pItem;
166 
167  if ((pItem = avl_t_next(pT->pvAVLT)) != NULL) {
168  pT->pnEdge = pItem->pv;
169  }
170  }
171  else {
172  pT->pnEdge += DGL_NODE_WSIZE(pG->EdgeAttrSize);
173  if (pT->pnEdge >= (dglInt32_t *)(pG->pEdgeBuffer + pG->iEdgeBuffer)) {
174  pT->pnEdge = NULL;
175  }
176  }
177  return pT->pnEdge;
178 #endif
179 }
180 
181 /*
182  * Node Traversing
183  */
185 {
186  if (pGraph->Flags & DGL_GS_FLAT) {
187  pT->pnNode = NULL;
188  pT->pvAVLT = NULL;
189  }
190  else {
191  if ((pT->pvAVLT = malloc(sizeof(struct avl_traverser))) == NULL) {
193  return -pGraph->iErrno;
194  }
195  avl_t_init(pT->pvAVLT, pGraph->pNodeTree);
196  pT->pnNode = NULL;
197  }
198  pT->pGraph = pGraph;
199  return 0;
200 }
201 
203 {
204  if (pT->pvAVLT)
205  free(pT->pvAVLT);
206  pT->pvAVLT = NULL;
207  pT->pnNode = NULL;
208 }
209 
211 {
212  DGL_T_NODEITEM_TYPE *pNodeItem;
213 
214  if (pT->pvAVLT) {
215  if ((pNodeItem = avl_t_first(pT->pvAVLT, pT->pGraph->pNodeTree)) ==
216  NULL)
217  pT->pnNode = NULL;
218  else
219  pT->pnNode = DGL_T_NODEITEM_NodePTR(pNodeItem);
220  }
221  else {
222  if (pT->pGraph->cNode > 0)
223  pT->pnNode = (dglInt32_t *)pT->pGraph->pNodeBuffer;
224  else
225  pT->pnNode = NULL;
226  }
227  return pT->pnNode;
228 }
229 
231 {
232  DGL_T_NODEITEM_TYPE *pNodeItem;
233 
234  if (pT->pvAVLT) {
235  if ((pNodeItem = avl_t_next(pT->pvAVLT)) == NULL)
236  pT->pnNode = NULL;
237  else
238  pT->pnNode = DGL_T_NODEITEM_NodePTR(pNodeItem);
239  }
240  else {
242  if (pT->pnNode >=
244  pT->pnNode = NULL;
245  }
246  return pT->pnNode;
247 }
248 
250 {
251  DGL_T_NODEITEM_TYPE *pNodeItem, findItem;
252 
253  if (pT->pvAVLT) {
254  findItem.nKey = nNodeId;
255  if ((pNodeItem = avl_t_find(pT->pvAVLT, pT->pGraph->pNodeTree,
256  &findItem)) == NULL)
257  pT->pnNode = NULL;
258  else
259  pT->pnNode = DGL_T_NODEITEM_NodePTR(pNodeItem);
260  }
261  else {
262  pT->pnNode = DGL_GET_NODE_FUNC(pT->pGraph, nNodeId);
263  }
264  return pT->pnNode;
265 }
266 
267 /*
268  * Edgeset Traversing
269  */
271  dglInt32_t *pnEdgeset)
272 {
273  pT->pGraph = pGraph;
274  pT->pnEdgeset = pnEdgeset;
275  pT->cEdge = (pnEdgeset) ? *pnEdgeset : 0;
276  pT->iEdge = 0;
277  return 0;
278 }
279 
281 {
282 }
283 
285 {
286 #if defined(_DGL_V2)
287  dglInt32_t *pnOffset;
288  dglTreeEdge_s *pEdgeItem, EdgeItem;
289 #endif
290 
291  if (pT->cEdge == 0)
292  return NULL;
293  pT->iEdge = 1;
294 #if defined(_DGL_V1)
295  return pT->pnEdgeset + 1;
296 #endif
297 #if defined(_DGL_V2)
298  pnOffset = pT->pnEdgeset + 1;
299  if (pT->pGraph->Flags & DGL_GS_FLAT) {
300  pT->pvCurrentItem = NULL;
301  return DGL_EDGEBUFFER_SHIFT(pT->pGraph, *pnOffset);
302  }
303  else {
304  EdgeItem.nKey = *pnOffset;
305  if ((pEdgeItem = avl_find(pT->pGraph->pEdgeTree, &EdgeItem)) != NULL) {
306  pT->pvCurrentItem = pEdgeItem;
307  return pEdgeItem->pv;
308  }
309  }
310 #endif
311  return NULL;
312 }
313 
315 {
316 #if defined(_DGL_V2)
317  dglInt32_t *pnOffset;
318  dglTreeEdge_s *pEdgeItem, EdgeItem;
319 #endif
320 
321  if (pT->cEdge > 0 && pT->iEdge < pT->cEdge) {
322 #if defined(_DGL_V1)
323  return DGL_EDGESET_EDGE_PTR(pT->pnEdgeset, pT->iEdge++,
324  pT->pGraph->EdgeAttrSize);
325 #endif
326 #if defined(_DGL_V2)
327  pnOffset = pT->pnEdgeset + 1 + pT->iEdge++;
328  if (pT->pGraph->Flags & DGL_GS_FLAT) {
329  return DGL_EDGEBUFFER_SHIFT(pT->pGraph, *pnOffset);
330  }
331  else {
332  EdgeItem.nKey = *pnOffset;
333  if ((pEdgeItem = avl_find(pT->pGraph->pEdgeTree, &EdgeItem)) !=
334  NULL) {
335  pT->pvCurrentItem = pEdgeItem;
336  return pEdgeItem->pv;
337  }
338  }
339 #endif
340  }
341  return NULL;
342 }
343 
344 /*
345  * Flatten the graph
346  */
348 {
349  register DGL_T_NODEITEM_TYPE *ptreenode;
350 
351 #if defined(_DGL_V2)
352  register dglTreeEdge_s *ptreeEdge;
353  int i;
354 #endif
355  register dglInt32_t *pEdge;
356  register dglInt32_t *pnode;
357  register dglInt32_t *pnodescan;
358  dglInt32_t *pOutEdgeset;
359 #if !defined(_DGL_V1)
360  dglInt32_t *pInEdgeset;
361 #endif
362  int cOutEdgeset;
363  int cInEdgeset;
364 
365  struct avl_traverser avlTraverser;
366 
367  if (pgraph->Flags & DGL_GS_FLAT) {
368  pgraph->iErrno = DGL_ERR_BadOnFlatGraph;
369  return -pgraph->iErrno;
370  }
371 
372  pgraph->pNodeBuffer = NULL; /* should be already */
373  pgraph->iNodeBuffer = 0;
374  pgraph->pEdgeBuffer = NULL;
375  pgraph->iEdgeBuffer = 0;
376 
377 #if defined(_DGL_V2)
378  /*
379  printf("flatten: traversing edges\n");
380  */
381  avl_t_init(&avlTraverser, pgraph->pEdgeTree);
382 
383  for (ptreeEdge = avl_t_first(&avlTraverser, pgraph->pEdgeTree); ptreeEdge;
384  ptreeEdge = avl_t_next(&avlTraverser)) {
385  pEdge = ptreeEdge->pv;
386 
387  /*
388  printf( "flatten: add edge %ld to edge buffer\n", DGL_EDGE_ID(pEdge)
389  );
390  */
391 
392  pgraph->pEdgeBuffer = realloc(
393  pgraph->pEdgeBuffer,
394  pgraph->iEdgeBuffer + DGL_EDGE_SIZEOF(pgraph->EdgeAttrSize));
395 
396  if (pgraph->pEdgeBuffer == NULL) {
398  return -pgraph->iErrno;
399  }
400 
401  memcpy(pgraph->pEdgeBuffer + pgraph->iEdgeBuffer, pEdge,
402  DGL_EDGE_SIZEOF(pgraph->EdgeAttrSize));
403 
404  pgraph->iEdgeBuffer += DGL_EDGE_SIZEOF(pgraph->EdgeAttrSize);
405  }
406 #endif
407 
408  /*
409  printf("flatten: traversing nodes\n");
410  */
411  avl_t_init(&avlTraverser, pgraph->pNodeTree);
412 
413  for (ptreenode = avl_t_first(&avlTraverser, pgraph->pNodeTree); ptreenode;
414  ptreenode = avl_t_next(&avlTraverser)) {
415  pnode = DGL_T_NODEITEM_NodePTR(ptreenode);
416  pOutEdgeset = DGL_T_NODEITEM_OutEdgesetPTR(ptreenode);
417 #if !defined(_DGL_V1)
418  pInEdgeset = DGL_T_NODEITEM_InEdgesetPTR(ptreenode);
419 #endif
420 
421  if (!(DGL_NODE_STATUS(pnode) & DGL_NS_ALONE)) {
422  cOutEdgeset =
423  (pOutEdgeset)
425  pgraph->EdgeAttrSize)
426  : sizeof(dglInt32_t);
427 
428 #if !defined(_DGL_V1)
429  cInEdgeset =
430  (pInEdgeset)
432  pgraph->EdgeAttrSize)
433  : sizeof(dglInt32_t);
434 #else
435  cInEdgeset = 0;
436 #endif
437 
438  pgraph->pEdgeBuffer =
439  realloc(pgraph->pEdgeBuffer,
440  pgraph->iEdgeBuffer + cOutEdgeset + cInEdgeset);
441 
442  if (pgraph->pEdgeBuffer == NULL) {
444  return -pgraph->iErrno;
445  }
446 
447  {
448  dglInt32_t nDummy = 0;
449 
450  memcpy(pgraph->pEdgeBuffer + pgraph->iEdgeBuffer,
451  (pOutEdgeset) ? pOutEdgeset : &nDummy, cOutEdgeset);
452 #if !defined(_DGL_V1)
453  memcpy(pgraph->pEdgeBuffer + pgraph->iEdgeBuffer + cOutEdgeset,
454  (pInEdgeset) ? pInEdgeset : &nDummy, cInEdgeset);
455 #endif
456  }
457 
458  DGL_NODE_EDGESET_OFFSET(pnode) = pgraph->iEdgeBuffer;
459 
460  pgraph->iEdgeBuffer += cOutEdgeset + cInEdgeset;
461  }
462 
463  pgraph->pNodeBuffer = realloc(
464  pgraph->pNodeBuffer,
465  pgraph->iNodeBuffer + DGL_NODE_SIZEOF(pgraph->NodeAttrSize));
466 
467  if (pgraph->pNodeBuffer == NULL) {
469  return -pgraph->iErrno;
470  }
471 
472  memcpy(pgraph->pNodeBuffer + pgraph->iNodeBuffer, pnode,
473  DGL_NODE_SIZEOF(pgraph->NodeAttrSize));
474  pgraph->iNodeBuffer += DGL_NODE_SIZEOF(pgraph->NodeAttrSize);
475  }
476 
477 #if defined(_DGL_V2)
478  if (pgraph->pEdgeTree) {
480  pgraph->pEdgeTree = NULL;
481  }
482 #endif
483 
484  if (pgraph->pNodeTree) {
486  pgraph->pNodeTree = NULL;
487  }
488 
489  pgraph->Flags |= DGL_GS_FLAT; /* flattened */
490 
491  /*
492  * convert node-id to node-offset
493  */
494  DGL_FOREACH_NODE (pgraph, pnodescan) {
495  if (!(DGL_NODE_STATUS(pnodescan) & DGL_NS_ALONE)) {
496  pOutEdgeset = DGL_EDGEBUFFER_SHIFT(
497  pgraph, DGL_NODE_EDGESET_OFFSET(pnodescan));
498 
499 #if defined(_DGL_V2)
500  for (i = 0; i < pOutEdgeset[0]; i++) {
501  /*
502  printf("flatten: node %ld: scan out edge %ld/%ld - %ld\n",
503  DGL_NODE_ID(pnodescan), i+1, pOutEdgeset[0],
504  pOutEdgeset[i+1]);
505  */
506  pEdge = DGL_GET_EDGE_FUNC(pgraph, pOutEdgeset[i + 1]);
507  if (pEdge == NULL) {
509  return -pgraph->iErrno;
510  }
511  /*
512  printf(" retrieved id %ld\n", DGL_EDGE_ID(pEdge) );
513  */
514  pOutEdgeset[i + 1] = DGL_EDGEBUFFER_OFFSET(pgraph, pEdge);
515  }
516 
517  pInEdgeset = pOutEdgeset + pOutEdgeset[0] + 1;
518 
519  for (i = 0; i < pInEdgeset[0]; i++) {
520  /*
521  printf("flatten: node %ld: scan in edge %ld/%ld - %ld\n",
522  DGL_NODE_ID(pnodescan), i+1, pInEdgeset[0], pInEdgeset[i+1]);
523  */
524  pEdge = DGL_GET_EDGE_FUNC(pgraph, pInEdgeset[i + 1]);
525  if (pEdge == NULL) {
527  return -pgraph->iErrno;
528  }
529  /*
530  printf(" retrieved id %ld\n", DGL_EDGE_ID(pEdge) );
531  */
532  pInEdgeset[i + 1] = DGL_EDGEBUFFER_OFFSET(pgraph, pEdge);
533  }
534 #endif
535 
536 #if defined(_DGL_V2)
537  {
538  int iEdge;
539 
540  DGL_FOREACH_EDGE (pgraph, pOutEdgeset, pEdge, iEdge)
541 #else
542  DGL_FOREACH_EDGE (pgraph, pOutEdgeset, pEdge)
543 #endif
544  {
545  if ((pnode = DGL_GET_NODE_FUNC(
546  pgraph, DGL_EDGE_HEADNODE_OFFSET(pEdge))) ==
547  NULL) {
549  return -pgraph->iErrno;
550  }
551  DGL_EDGE_HEADNODE_OFFSET(pEdge) =
552  DGL_NODEBUFFER_OFFSET(pgraph, pnode);
553 
554  if ((pnode = DGL_GET_NODE_FUNC(
555  pgraph, DGL_EDGE_TAILNODE_OFFSET(pEdge))) ==
556  NULL) {
558  return -pgraph->iErrno;
559  }
560  DGL_EDGE_TAILNODE_OFFSET(pEdge) =
561  DGL_NODEBUFFER_OFFSET(pgraph, pnode);
562  }
563 #if defined(_DGL_V2)
564  }
565 #endif
566  }
567  }
568 
569  return 0;
570 }
571 
573 {
574  register dglInt32_t *pHead;
575  register dglInt32_t *pTail;
576  register dglInt32_t *pEdge;
577  register dglInt32_t *pEdgeset;
578  int nret;
579 
580  if (!(pgraph->Flags & DGL_GS_FLAT)) {
581  pgraph->iErrno = DGL_ERR_BadOnTreeGraph;
582  return -pgraph->iErrno;
583  }
584 
585  /*
586  * unflag it now to avoid DGL_ADD_EDGE_FUNC() failure
587  */
588  pgraph->Flags &= ~DGL_GS_FLAT;
589  pgraph->cNode = 0;
590  pgraph->cEdge = 0;
591  pgraph->cHead = 0;
592  pgraph->cTail = 0;
593  pgraph->cAlone = 0;
594  pgraph->nnCost = (dglInt64_t)0;
595 
596  if (pgraph->pNodeTree == NULL)
597  pgraph->pNodeTree =
599  if (pgraph->pNodeTree == NULL) {
601  return -pgraph->iErrno;
602  }
603 #if defined(_DGL_V1)
604  pgraph->pEdgeTree = NULL;
605 #else
606  if (pgraph->pEdgeTree == NULL)
607  pgraph->pEdgeTree =
609  if (pgraph->pEdgeTree == NULL) {
611  return -pgraph->iErrno;
612  }
613 #endif
614 
615  DGL_FOREACH_NODE (pgraph, pHead) {
616  if (DGL_NODE_STATUS(pHead) & DGL_NS_HEAD) {
617  pEdgeset =
619 
620 #if defined(_DGL_V2)
621  {
622  int iEdge;
623 
624  DGL_FOREACH_EDGE (pgraph, pEdgeset, pEdge, iEdge)
625 #else
626  DGL_FOREACH_EDGE (pgraph, pEdgeset, pEdge)
627 #endif
628  {
629  pTail = DGL_NODEBUFFER_SHIFT(
630  pgraph, DGL_EDGE_TAILNODE_OFFSET(pEdge));
631 
632  nret = DGL_ADD_EDGE_FUNC(
633  pgraph, DGL_NODE_ID(pHead), DGL_NODE_ID(pTail),
634  DGL_EDGE_COST(pEdge), DGL_EDGE_ID(pEdge),
635  DGL_NODE_ATTR_PTR(pHead), DGL_NODE_ATTR_PTR(pTail),
636  DGL_EDGE_ATTR_PTR(pEdge), 0);
637 
638  if (nret < 0) {
639  goto error;
640  }
641  }
642 #if defined(_DGL_V2)
643  }
644 #endif
645  }
646  else if (DGL_NODE_STATUS(pHead) & DGL_NS_ALONE) {
647  nret = DGL_ADD_NODE_FUNC(pgraph, DGL_NODE_ID(pHead),
648  DGL_NODE_ATTR_PTR(pHead), 0);
649  if (nret < 0) {
650  goto error;
651  }
652  }
653  }
654 
655  /* move away flat-state data
656  */
657  if (pgraph->pNodeBuffer)
658  free(pgraph->pNodeBuffer);
659  if (pgraph->pEdgeBuffer)
660  free(pgraph->pEdgeBuffer);
661  pgraph->pNodeBuffer = NULL;
662  pgraph->pEdgeBuffer = NULL;
663  return 0;
664 
665 error:
666  if (pgraph->pNodeTree)
668  if (pgraph->pEdgeTree)
670  pgraph->pNodeTree = NULL;
671  pgraph->pEdgeTree = NULL;
672  pgraph->Flags |= DGL_GS_FLAT;
673  return nret;
674 }
#define NULL
Definition: ccmath.h:32
int DGL_ADD_EDGE_FUNC(dglGraph_s *pgraph, dglInt32_t nHead, dglInt32_t nTail, dglInt32_t nCost, dglInt32_t nEdge, void *pvHeadAttr, void *pvTailAttr, void *pvEdgeAttr, dglInt32_t nFlags)
dglInt32_t * DGL_GET_EDGE_FUNC(dglGraph_s *pgraph, dglInt32_t nEdge UNUSED)
#define UNUSED
A macro for an attribute, if attached to a variable, indicating that the variable is not used.
Definition: gis.h:47
#define DGL_ERR_BadOnTreeGraph
Definition: graph.h:265
#define DGL_NS_ALONE
Definition: graph.h:61
#define DGL_ERR_MemoryExhausted
Definition: graph.h:254
#define DGL_ERR_BadOnFlatGraph
Definition: graph.h:264
#define DGL_NS_HEAD
Definition: graph.h:59
#define DGL_ERR_NotSupported
Definition: graph.h:259
#define DGL_GS_FLAT
Definition: graph.h:36
#define DGL_ERR_HeadNodeNotFound
Definition: graph.h:261
#define DGL_ERR_UnexpectedNullPointer
Definition: graph.h:268
#define DGL_ERR_TailNodeNotFound
Definition: graph.h:262
void DGL_EDGESET_T_RELEASE_FUNC(dglEdgesetTraverser_s *pT UNUSED)
dglInt32_t * DGL_EDGE_T_FIRST_FUNC(dglEdgeTraverser_s *pT)
Definition: misc-template.c:86
void DGL_EDGE_T_RELEASE_FUNC(dglEdgeTraverser_s *pT)
Definition: misc-template.c:73
dglInt32_t * DGL_EDGESET_T_FIRST_FUNC(dglEdgesetTraverser_s *pT)
int DGL_EDGESET_T_INITIALIZE_FUNC(dglGraph_s *pGraph, dglEdgesetTraverser_s *pT, dglInt32_t *pnEdgeset)
int DGL_FLATTEN_FUNC(dglGraph_s *pgraph)
dglInt32_t * DGL_EDGESET_T_NEXT_FUNC(dglEdgesetTraverser_s *pT)
int DGL_UNFLATTEN_FUNC(dglGraph_s *pgraph)
int DGL_EDGE_T_INITIALIZE_FUNC(dglGraph_s *pGraph, dglEdgeTraverser_s *pT UNUSED, dglEdgePrioritizer_s *pEP UNUSED)
Definition: misc-template.c:28
dglInt32_t * DGL_NODE_T_NEXT_FUNC(dglNodeTraverser_s *pT)
dglInt32_t * DGL_EDGE_T_NEXT_FUNC(dglEdgeTraverser_s *pT)
dglInt32_t * DGL_NODE_T_FIND_FUNC(dglNodeTraverser_s *pT, dglInt32_t nNodeId)
void DGL_NODE_T_RELEASE_FUNC(dglNodeTraverser_s *pT)
int DGL_NODE_T_INITIALIZE_FUNC(dglGraph_s *pGraph, dglNodeTraverser_s *pT)
dglInt32_t * DGL_NODE_T_FIRST_FUNC(dglNodeTraverser_s *pT)
int DGL_ADD_NODE_FUNC(dglGraph_s *pgraph, dglInt32_t nId, void *pvNodeAttr UNUSED, dglInt32_t nFlags UNUSED)
dglInt32_t * DGL_GET_NODE_FUNC(dglGraph_s *pgraph, dglInt32_t nodeid)
void * malloc(YYSIZE_T)
void free(void *)
dglByte_t * pEdgeBuffer
Definition: graph.h:161
dglInt32_t NodeAttrSize
Definition: graph.h:142
dglInt32_t cTail
Definition: graph.h:148
dglInt32_t cEdge
Definition: graph.h:150
dglInt32_t EdgeAttrSize
Definition: graph.h:143
dglInt32_t cAlone
Definition: graph.h:149
dglByte_t * pNodeBuffer
Definition: graph.h:159
dglInt32_t iEdgeBuffer
Definition: graph.h:162
dglInt32_t iNodeBuffer
Definition: graph.h:160
dglInt32_t cHead
Definition: graph.h:147
int iErrno
Definition: graph.h:138
dglInt32_t cNode
Definition: graph.h:146
void * pNodeTree
Definition: graph.h:157
void * pEdgeTree
Definition: graph.h:158
dglInt32_t Flags
Definition: graph.h:153
dglInt64_t nnCost
Definition: graph.h:151
dglInt32_t * pnData
Definition: tree.h:150
dglInt32_t cnData
Definition: tree.h:149
dglInt32_t nKey
Definition: tree.h:90
void * pv
Definition: tree.h:91
dglTreeEdgePri32_s * pEdgePri32Item
Definition: graph.h:130
dglInt32_t * pnEdge
Definition: graph.h:245
dglGraph_s * pGraph
Definition: graph.h:243
void * pvAVLT
Definition: graph.h:244
dglEdgePrioritizer_s * pEdgePrioritizer
Definition: graph.h:246
dglInt32_t * pnEdgeset
Definition: graph.h:234
void * pvCurrentItem
Definition: graph.h:235
dglGraph_s * pGraph
Definition: graph.h:233
dglInt32_t * pnNode
Definition: graph.h:226
void * pvAVLT
Definition: graph.h:225
dglGraph_s * pGraph
Definition: graph.h:224
int dglTreeEdgeCompare(const void *pvEdgeA, const void *pvEdgeB, void *pvParam UNUSED)
Definition: tree.c:159
void dglTreeNodeCancel(void *pvNode, void *pvParam UNUSED)
Definition: tree.c:45
void * dglTreeGetAllocator(void)
Definition: tree.c:406
void dglTreeEdgeCancel(void *pvEdge, void *pvParam UNUSED)
Definition: tree.c:152
#define avl_find
Definition: tree.h:38
#define avl_create
Definition: tree.h:31
#define avl_t_next
Definition: tree.h:47
#define avl_t_find
Definition: tree.h:44
#define avl_t_first
Definition: tree.h:42
#define avl_destroy
Definition: tree.h:33
#define avl_t_init
Definition: tree.h:41
long long dglInt64_t
Definition: type.h:37
long dglInt32_t
Definition: type.h:36
#define DGL_EDGESET_EDGE_PTR
Definition: v1-defs.h:149
#define DGL_T_NODEITEM_InEdgesetPTR(p)
Definition: v1-defs.h:173
#define DGL_NODEBUFFER_OFFSET
Definition: v1-defs.h:158
#define DGL_T_NODEITEM_TYPE
Definition: v1-defs.h:168
#define DGL_NODE_STATUS
Definition: v1-defs.h:126
#define DGL_EDGE_SIZEOF
Definition: v1-defs.h:134
#define DGL_NODE_ID
Definition: v1-defs.h:127
#define DGL_NODE_EDGESET_OFFSET
Definition: v1-defs.h:129
#define DGL_T_NODEITEM_OutEdgesetPTR(p)
Definition: v1-defs.h:171
#define DGL_T_NODEITEM_Compare
Definition: v1-defs.h:175
#define DGL_EDGE_TAILNODE_OFFSET
Definition: v1-defs.h:141
#define DGL_EDGEBUFFER_SHIFT
Definition: v1-defs.h:159
#define DGL_NODE_WSIZE
Definition: v1-defs.h:125
#define DGL_EDGESET_EDGECOUNT
Definition: v1-defs.h:148
#define DGL_EDGE_ATTR_PTR
Definition: v1-defs.h:139
#define DGL_EDGEBUFFER_OFFSET
Definition: v1-defs.h:160
#define DGL_NODE_SIZEOF
Definition: v1-defs.h:124
#define DGL_EDGESET_SIZEOF
Definition: v1-defs.h:152
#define DGL_T_NODEITEM_NodePTR(p)
Definition: v1-defs.h:169
#define DGL_NODE_ATTR_PTR
Definition: v1-defs.h:128
#define DGL_EDGE_ID
Definition: v1-defs.h:138
#define DGL_EDGE_HEADNODE_OFFSET
Definition: v1-defs.h:140
#define DGL_FOREACH_EDGE
Definition: v1-defs.h:163
#define DGL_FOREACH_NODE
Definition: v1-defs.h:162
#define DGL_EDGE_COST
Definition: v1-defs.h:137
#define DGL_NODEBUFFER_SHIFT
Definition: v1-defs.h:157