GRASS GIS 7 Programmer's Manual  7.9.dev(2021)-e5379bbd7
nodemgmt-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 
24  dglInt32_t nId, void *pvNodeAttr, dglInt32_t nFlags)
25 {
26  DGL_T_NODEITEM_TYPE *pNodeItem;
27  dglInt32_t *pnode;
28 
29  if (pgraph->Flags & DGL_GS_FLAT) {
31  return -pgraph->iErrno;
32  }
33 
34  if ((pNodeItem = DGL_T_NODEITEM_Add(pgraph->pNodeTree, nId)) == NULL) {
36  return -pgraph->iErrno;
37  }
38 
39  if (DGL_T_NODEITEM_NodePTR(pNodeItem) == NULL) {
40  if ((pnode = DGL_NODE_ALLOC(pgraph->NodeAttrSize)) == NULL) {
42  return -pgraph->iErrno;
43  }
44  memset(pnode, 0, DGL_NODE_SIZEOF(pgraph->NodeAttrSize));
45  DGL_NODE_ID(pnode) = nId;
47  DGL_T_NODEITEM_Set_NodePTR(pNodeItem, pnode);
48  pgraph->cNode++;
49  pgraph->cAlone++;
50  }
51  else {
52  /* node already exists */
54  return -pgraph->iErrno;
55  }
56  return 0;
57 }
58 
59 #if !defined(_DGL_V1)
60 /*
61  * Delete the link from the node's out-edgeset
62  */
64  dglInt32_t nEdge)
65 {
66  DGL_T_NODEITEM_TYPE *pNodeItem, findNodeItem;
67  dglInt32_t *pnEdgeset, *pnEdge, *pnNode;
69 
70  findNodeItem.nKey = nNode;
71 
72  if ((pNodeItem = avl_find(pgraph->pNodeTree, &findNodeItem)) != NULL) {
73  pnNode = DGL_T_NODEITEM_NodePTR(pNodeItem);
74  if (DGL_NODE_STATUS(pnNode) == DGL_NS_ALONE) {
75  return 0;
76  }
77  if ((pnEdgeset = DGL_T_NODEITEM_OutEdgesetPTR(pNodeItem)) != NULL) {
78  if (DGL_EDGESET_T_INITIALIZE_FUNC(pgraph, &t, pnEdgeset) >= 0) {
79  for (pnEdge = DGL_EDGESET_T_FIRST_FUNC(&t);
80  pnEdge; pnEdge = DGL_EDGESET_T_NEXT_FUNC(&t)
81  ) {
82  if (DGL_EDGE_ID(pnEdge) == nEdge) {
83  register dglInt32_t *pnSet;
84  register int i1, i2, c;
85 
86  c = pnEdgeset[0];
87 
88  if ((pnSet =
89  malloc(sizeof(dglInt32_t) * (c + 1))) == NULL) {
91  return -pgraph->iErrno;
92  }
93 
94  for (i1 = 0, i2 = 0; i2 < c; i2++) {
95  if (pnEdgeset[1 + i2] != nEdge) {
96  pnSet[1 + i1++] = pnEdgeset[1 + i2];
97  }
98  }
99  pnSet[0] = i1;
100 
101  free(pnEdgeset);
102  DGL_T_NODEITEM_Set_OutEdgesetPTR(pNodeItem, pnSet);
103  break;
104  }
105  }
106  }
107  }
108  { /* check alone status */
109  dglInt32_t *pIn, *pOut, *pNode;
110 
111  pOut = DGL_T_NODEITEM_OutEdgesetPTR(pNodeItem);
112  pIn = DGL_T_NODEITEM_InEdgesetPTR(pNodeItem);
113  pNode = DGL_T_NODEITEM_NodePTR(pNodeItem);
114  if ((pOut == NULL || DGL_EDGESET_EDGECOUNT(pOut) == 0) &&
115  (pIn == NULL || DGL_EDGESET_EDGECOUNT(pIn) == 0)
116  ) {
117  if (DGL_NODE_STATUS(pNode) & DGL_NS_HEAD)
118  pgraph->cHead--;
119  if (DGL_NODE_STATUS(pNode) & DGL_NS_TAIL)
120  pgraph->cTail--;
121  DGL_NODE_STATUS(pNode) = DGL_NS_ALONE;
122  pgraph->cAlone++;
123  }
124  }
125  }
126  return 0;
127 }
128 
130  dglInt32_t nEdge)
131 {
132  DGL_T_NODEITEM_TYPE *pNodeItem, findNodeItem;
133  dglInt32_t *pnEdgeset, *pnEdge, *pnNode;
135 
136  findNodeItem.nKey = nNode;
137 
138  if ((pNodeItem = avl_find(pgraph->pNodeTree, &findNodeItem)) != NULL) {
139  pnNode = DGL_T_NODEITEM_NodePTR(pNodeItem);
140  if (DGL_NODE_STATUS(pnNode) == DGL_NS_ALONE) {
141  return 0;
142  }
143  if ((pnEdgeset = DGL_T_NODEITEM_InEdgesetPTR(pNodeItem)) != NULL) {
144  if (DGL_EDGESET_T_INITIALIZE_FUNC(pgraph, &t, pnEdgeset) >= 0) {
145  for (pnEdge = DGL_EDGESET_T_FIRST_FUNC(&t);
146  pnEdge; pnEdge = DGL_EDGESET_T_NEXT_FUNC(&t)
147  ) {
148  if (DGL_EDGE_ID(pnEdge) == nEdge) {
149  register dglInt32_t *pnSet;
150  register int i1, i2, c;
151 
152  c = pnEdgeset[0];
153 
154  if ((pnSet =
155  malloc(sizeof(dglInt32_t) * (c + 1))) == NULL) {
157  return -pgraph->iErrno;
158  }
159 
160  for (i1 = 0, i2 = 0; i2 < c; i2++) {
161  if (pnEdgeset[1 + i2] != nEdge) {
162  pnSet[1 + i1++] = pnEdgeset[1 + i2];
163  }
164  }
165  pnSet[0] = i1;
166 
167  free(pnEdgeset);
168  DGL_T_NODEITEM_Set_InEdgesetPTR(pNodeItem, pnSet);
169  break;
170  }
171  }
172  }
173  }
174  { /* check alone status */
175  dglInt32_t *pIn, *pOut, *pNode;
176 
177  pOut = DGL_T_NODEITEM_OutEdgesetPTR(pNodeItem);
178  pIn = DGL_T_NODEITEM_InEdgesetPTR(pNodeItem);
179  pNode = DGL_T_NODEITEM_NodePTR(pNodeItem);
180  if ((pOut == NULL || DGL_EDGESET_EDGECOUNT(pOut) == 0) &&
181  (pIn == NULL || DGL_EDGESET_EDGECOUNT(pIn) == 0)
182  ) {
183  if (DGL_NODE_STATUS(pNode) & DGL_NS_HEAD)
184  pgraph->cHead--;
185  if (DGL_NODE_STATUS(pNode) & DGL_NS_TAIL)
186  pgraph->cTail--;
187  DGL_NODE_STATUS(pNode) = DGL_NS_ALONE;
188  pgraph->cAlone++;
189  }
190  }
191  }
192  return 0;
193 }
194 #endif
195 
197 {
198 #if defined(_DGL_V1)
199  pgraph->iErrno = DGL_ERR_NotSupported;
200  return -pgraph->iErrno;
201 #else
202  DGL_T_NODEITEM_TYPE *pNodeItem, findNodeItem;
203  dglInt32_t *pEdgeset;
204  dglInt32_t *pnode;
205  dglInt32_t *pEdge;
207 
208  dglTreeEdge_s *pEdgeItem;
209 
210  if (pgraph->Flags & DGL_GS_FLAT) {
211  pgraph->iErrno = DGL_ERR_BadOnFlatGraph;
212  return -pgraph->iErrno;
213  }
214 
215  if (pgraph->pNodeTree == NULL) {
217  return -pgraph->iErrno;
218  }
219 
220  findNodeItem.nKey = nNodeId;
221  if ((pNodeItem = avl_find(pgraph->pNodeTree, &findNodeItem)) == NULL) {
222  pgraph->iErrno = DGL_ERR_NodeNotFound;
223  return -pgraph->iErrno;
224  }
225 
226  pnode = DGL_T_NODEITEM_NodePTR(pNodeItem);
227 
228  if (DGL_NODE_STATUS(pnode) & DGL_NS_ALONE)
229  goto node_is_alone;
230 
231  pEdgeset = DGL_T_NODEITEM_OutEdgesetPTR(pNodeItem);
232 
233  if (DGL_EDGESET_T_INITIALIZE_FUNC(pgraph, &trav, pEdgeset) < 0)
234  return -pgraph->iErrno;
235  for (pEdge = DGL_EDGESET_T_FIRST_FUNC(&trav);
236  pEdge; pEdge = DGL_EDGESET_T_NEXT_FUNC(&trav)
237  ) {
238  if (DGL_EDGE_TAILNODE_OFFSET(pEdge) != DGL_NODE_ID(pnode)) {
240  (pgraph, DGL_EDGE_TAILNODE_OFFSET(pEdge),
241  DGL_EDGE_ID(pEdge)) < 0) {
242  return -pgraph->iErrno;
243  }
244  }
245  if ((pEdgeItem = trav.pvCurrentItem) != NULL) {
246  /* prioritizer sync
247  */
248  if (pgraph->nOptions & DGL_GO_EdgePrioritize_COST) {
250  (pgraph, DGL_EDGE_ID(pEdge), DGL_EDGE_COST(pEdge)) < 0) {
251  return -pgraph->iErrno;
252  }
253  }
254  /*
255  */
256  pgraph->cEdge--;
257  pgraph->nnCost -= (dglInt64_t) DGL_EDGE_COST(pEdge);
258 
259  avl_delete(pgraph->pEdgeTree, pEdgeItem);
260  dglTreeEdgeCancel(pEdgeItem, NULL);
261  }
262  }
264 
265  pEdgeset = DGL_T_NODEITEM_InEdgesetPTR(pNodeItem);
266 
267  if (DGL_EDGESET_T_INITIALIZE_FUNC(pgraph, &trav, pEdgeset) < 0)
268  return -pgraph->iErrno;
269  for (pEdge = DGL_EDGESET_T_FIRST_FUNC(&trav);
270  pEdge; pEdge = DGL_EDGESET_T_NEXT_FUNC(&trav)
271  ) {
272  if (DGL_EDGE_HEADNODE_OFFSET(pEdge) != DGL_NODE_ID(pnode)) {
274  (pgraph, DGL_EDGE_HEADNODE_OFFSET(pEdge),
275  DGL_EDGE_ID(pEdge)) < 0) {
276  return -pgraph->iErrno;
277  }
278  }
279  if ((pEdgeItem = trav.pvCurrentItem) != NULL) {
280  /* prioritizer sync
281  */
282  if (pgraph->nOptions & DGL_GO_EdgePrioritize_COST) {
284  (pgraph, DGL_EDGE_ID(pEdge), DGL_EDGE_COST(pEdge)) < 0) {
285  return -pgraph->iErrno;
286  }
287  }
288  /*
289  */
290  pgraph->cEdge--;
291  pgraph->nnCost -= (dglInt64_t) DGL_EDGE_COST(pEdge);
292 
293  avl_delete(pgraph->pEdgeTree, pEdgeItem);
294  dglTreeEdgeCancel(pEdgeItem, NULL);
295  }
296  }
298 
299  if (DGL_NODE_STATUS(pnode) & DGL_NS_HEAD)
300  pgraph->cHead--;
301  if (DGL_NODE_STATUS(pnode) & DGL_NS_TAIL)
302  pgraph->cTail--;
303 
304  node_is_alone:
305  if (DGL_NODE_STATUS(pnode) & DGL_NS_ALONE)
306  pgraph->cAlone--;
307  pgraph->cNode--;
308 
309  avl_delete(pgraph->pNodeTree, pNodeItem);
310  DGL_T_NODEITEM_Cancel(pNodeItem, NULL);
311 
312  return 0;
313 #endif
314 }
315 
317 {
318  register dglInt32_t top; /* top of table */
319  register dglInt32_t pos; /* current position to compare */
320  register dglInt32_t bot; /* bottom of table */
321  register dglInt32_t *pref;
322  register int cwords; /* size of a node in words of 32 bit */
323  register dglTreeNode_s *ptreenode;
324  dglTreeNode_s findnode;
325  dglInt32_t id;
326 
327  pgraph->iErrno = 0;
328  if (pgraph->Flags & DGL_GS_FLAT) {
329  cwords = DGL_NODE_WSIZE(pgraph->NodeAttrSize);
330  /*bot = pgraph->iNodeBuffer / DGL_NODE_SIZEOF(pgraph->NodeAttrSize); */
331  bot = pgraph->cNode;
332  top = 0;
333  pos = 0;
334  pref = (dglInt32_t *) pgraph->pNodeBuffer;
335 
336  /* perform a binary search
337  */
338  while (top != bot) {
339  pos = top + (bot - top) / 2;
340  id = DGL_NODE_ID(&pref[pos * cwords]);
341  if (id == nodeid) {
342  break;
343  }
344  else if (nodeid < id) {
345  bot = pos;
346  }
347  else if (nodeid > id) {
348  top = pos + 1;
349  }
350  }
351  if (top == bot) {
352  return NULL;
353  }
354  return &pref[pos * cwords];
355  }
356  else {
357  findnode.nKey = nodeid;
358  ptreenode = avl_find(pgraph->pNodeTree, &findnode);
359  if (ptreenode && ptreenode->pv) {
360  return ptreenode->pv;
361  }
362  return NULL;
363  }
364 }
365 
366 /*
367  * if graph is FLAT retrieve the edge area from the pEdgeBuffer
368  * if graph is TREE retrieve the node from the pNodeTree avl and return pv field
369  */
371  dglInt32_t * pnode)
372 {
373  DGL_T_NODEITEM_TYPE *ptreenode, findnode;
374  dglInt32_t *pEdgeset;
375 
376  pgraph->iErrno = 0;
377 
378  if (pnode == NULL) {
380  return NULL;
381  }
382 
383  if (DGL_NODE_STATUS(pnode) & DGL_NS_ALONE) {
385  return NULL;
386  }
387 
388  if (pgraph->Flags & DGL_GS_FLAT) {
389  pEdgeset =
391  return pEdgeset;
392  }
393  else {
394  findnode.nKey = DGL_NODE_ID(pnode);
395  ptreenode = avl_find(pgraph->pNodeTree, &findnode);
396  if (ptreenode && DGL_T_NODEITEM_OutEdgesetPTR(ptreenode)) {
397  return DGL_T_NODEITEM_OutEdgesetPTR(ptreenode);
398  }
399  return NULL;
400  }
401 }
402 
404  dglInt32_t * pnode)
405 {
406 #if defined(_DGL_V1)
407  pgraph->iErrno = DGL_ERR_NotSupported;
408  return NULL;
409 #endif
410 
411 #if defined(_DGL_V2)
412  DGL_T_NODEITEM_TYPE *ptreenode, findnode;
413  dglInt32_t *pEdgeset;
414 
415  pgraph->iErrno = 0;
416 
417  if (pnode == NULL) {
419  return NULL;
420  }
421 
422  if (DGL_NODE_STATUS(pnode) & DGL_NS_ALONE) {
424  return NULL;
425  }
426 
427  if (pgraph->Flags & DGL_GS_FLAT) {
428  pEdgeset =
430  pEdgeset +=
432  pgraph->EdgeAttrSize);
433  return pEdgeset;
434  }
435  else {
436  findnode.nKey = DGL_NODE_ID(pnode);
437  ptreenode = avl_find(pgraph->pNodeTree, &findnode);
438  if (ptreenode && DGL_T_NODEITEM_InEdgesetPTR(ptreenode)) {
439  return DGL_T_NODEITEM_InEdgesetPTR(ptreenode);
440  }
441  return NULL;
442  }
443 #endif
444 }
dglInt32_t cEdge
Definition: graph.h:166
#define DGL_NS_HEAD
Definition: graph.h:60
dglInt64_t nnCost
Definition: graph.h:167
int DGL_DEL_NODE_FUNC(dglGraph_s *pgraph, dglInt32_t nNodeId)
dglInt32_t Flags
Definition: graph.h:169
int DGL_EDGESET_T_INITIALIZE_FUNC(dglGraph_s *pGraph, dglEdgesetTraverser_s *pT, dglInt32_t *pnEdgeset)
int DGL_DEL_NODE_OUTEDGE_FUNC(dglGraph_s *pgraph, dglInt32_t nNode, dglInt32_t nEdge)
#define DGL_EDGE_COST
Definition: v1-defs.h:136
#define DGL_T_NODEITEM_Add
Definition: v1-defs.h:177
void dglTreeEdgeCancel(void *pvEdge, void *pvParam)
Definition: tree.c:155
#define DGL_T_NODEITEM_NodePTR(p)
Definition: v1-defs.h:169
#define avl_find
Definition: tree.h:38
#define DGL_T_NODEITEM_Set_OutEdgesetPTR(p, ptr)
Definition: v1-defs.h:172
dglInt32_t NodeAttrSize
Definition: graph.h:158
#define DGL_EDGEBUFFER_SHIFT
Definition: v1-defs.h:158
#define DGL_ERR_NodeAlreadyExist
Definition: graph.h:300
void * pNodeTree
Definition: graph.h:173
long nKey
Definition: tree.h:63
#define DGL_NODE_STATUS
Definition: v1-defs.h:125
#define DGL_EDGE_ID
Definition: v1-defs.h:137
#define DGL_T_NODEITEM_InEdgesetPTR(p)
Definition: v1-defs.h:173
#define DGL_T_NODEITEM_TYPE
Definition: v1-defs.h:168
#define avl_delete
Definition: tree.h:37
void free(void *)
#define NULL
Definition: ccmath.h:32
dglInt32_t cNode
Definition: graph.h:162
void * malloc(YYSIZE_T)
int DGL_DEL_NODE_INEDGE_FUNC(dglGraph_s *pgraph, dglInt32_t nNode, dglInt32_t nEdge)
int iErrno
Definition: graph.h:154
double t
Definition: r_raster.c:39
#define DGL_GS_FLAT
Definition: graph.h:36
#define DGL_EDGESET_WSIZE
Definition: v1-defs.h:152
dglInt32_t cTail
Definition: graph.h:164
#define DGL_EDGE_TAILNODE_OFFSET
Definition: v1-defs.h:140
dglInt32_t * DGL_GET_NODE_FUNC(dglGraph_s *pgraph, dglInt32_t nodeid)
#define DGL_ERR_NotSupported
Definition: graph.h:288
#define DGL_NODE_ALLOC
Definition: v1-defs.h:122
#define DGL_NODE_ID
Definition: v1-defs.h:126
#define DGL_ERR_MemoryExhausted
Definition: graph.h:283
#define DGL_T_NODEITEM_OutEdgesetPTR(p)
Definition: v1-defs.h:171
long long dglInt64_t
Definition: type.h:38
#define DGL_ERR_BadOnFlatGraph
Definition: graph.h:293
long dglInt32_t
Definition: type.h:37
void * pEdgeTree
Definition: graph.h:174
void * pvCurrentItem
Definition: graph.h:262
#define DGL_EDGESET_EDGECOUNT
Definition: v1-defs.h:147
dglInt32_t * DGL_GET_NODE_OUTEDGESET_FUNC(dglGraph_s *pgraph, dglInt32_t *pnode)
#define DGL_NODE_WSIZE
Definition: v1-defs.h:124
dglInt32_t cAlone
Definition: graph.h:165
#define DGL_NS_TAIL
Definition: graph.h:61
dglInt32_t * DGL_GET_NODE_INEDGESET_FUNC(dglGraph_s *pgraph, dglInt32_t *pnode)
int dgl_edge_prioritizer_del(dglGraph_s *pG, dglInt32_t nId, dglInt32_t nPriId)
Definition: helpers.c:92
dglInt32_t cHead
Definition: graph.h:163
#define DGL_T_NODEITEM_Cancel
Definition: v1-defs.h:176
#define DGL_T_NODEITEM_Set_NodePTR(p, ptr)
Definition: v1-defs.h:170
dglInt32_t * DGL_EDGESET_T_NEXT_FUNC(dglEdgesetTraverser_s *pT)
#define DGL_NODE_EDGESET_OFFSET
Definition: v1-defs.h:128
dglInt32_t * DGL_EDGESET_T_FIRST_FUNC(dglEdgesetTraverser_s *pT)
#define DGL_ERR_NodeNotFound
Definition: graph.h:295
#define DGL_GO_EdgePrioritize_COST
Definition: graph.h:52
dglInt32_t EdgeAttrSize
Definition: graph.h:159
#define DGL_ERR_UnexpectedNullPointer
Definition: graph.h:297
#define DGL_NS_ALONE
Definition: graph.h:62
#define DGL_ERR_NodeIsAComponent
Definition: graph.h:301
#define DGL_EDGE_HEADNODE_OFFSET
Definition: v1-defs.h:139
void * pv
Definition: tree.h:64
#define DGL_NODE_SIZEOF
Definition: v1-defs.h:123
#define DGL_T_NODEITEM_Set_InEdgesetPTR(p, ptr)
Definition: v1-defs.h:174
dglInt32_t nOptions
Definition: graph.h:171
int DGL_ADD_NODE_FUNC(dglGraph_s *pgraph, dglInt32_t nId, void *pvNodeAttr, dglInt32_t nFlags)
dglByte_t * pNodeBuffer
Definition: graph.h:175
void DGL_EDGESET_T_RELEASE_FUNC(dglEdgesetTraverser_s *pT)