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