GRASS GIS 8 Programmer's Manual  8.2.2dev(2023)-3d2c704037
helpers.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 
24 #include <stdlib.h>
25 #include <string.h>
26 
27 #include "type.h"
28 #include "tree.h"
29 #include "graph.h"
30 #include "helpers.h"
31 
32 /*
33  * helpers for parametric stack
34  */
35 unsigned char *dgl_mempush(unsigned char *pstack, long *istack, long size,
36  void *pv)
37 {
38  if (*istack == 0)
39  pstack = NULL;
40  pstack = realloc(pstack, size * (1 + *istack));
41  if (pstack == NULL)
42  return NULL;
43  memcpy(&pstack[(*istack) * size], pv, size);
44  (*istack)++;
45  return pstack;
46 }
47 
48 unsigned char *dgl_mempop(unsigned char *pstack, long *istack, long size)
49 {
50  if (*istack == 0)
51  return NULL;
52  return &pstack[size * (--(*istack))];
53 }
54 
56 {
57  unsigned char *pb = (unsigned char *)pn;
58 
59  pb[0] ^= pb[3];
60  pb[3] ^= pb[0];
61  pb[0] ^= pb[3];
62 
63  pb[1] ^= pb[2];
64  pb[2] ^= pb[1];
65  pb[1] ^= pb[2];
66 }
67 
69 {
70  unsigned char *pb = (unsigned char *)pn;
71 
72  pb[0] ^= pb[7];
73  pb[7] ^= pb[0];
74  pb[0] ^= pb[7];
75 
76  pb[1] ^= pb[6];
77  pb[6] ^= pb[1];
78  pb[1] ^= pb[6];
79 
80  pb[2] ^= pb[5];
81  pb[5] ^= pb[2];
82  pb[2] ^= pb[5];
83 
84  pb[3] ^= pb[4];
85  pb[4] ^= pb[3];
86  pb[3] ^= pb[4];
87 }
88 
89 /*
90  * Keep the edge cost prioritizer in sync
91  */
93  dglInt32_t nPriId)
94 {
95  dglTreeEdgePri32_s findPriItem, *pPriItem;
96  register int iEdge1, iEdge2;
97  dglInt32_t *pnNew;
98 
99  if (pG->edgePrioritizer.pvAVL) {
100 
101  findPriItem.nKey = nPriId;
102  pPriItem = avl_find(pG->edgePrioritizer.pvAVL, &findPriItem);
103 
104  if (pPriItem && pPriItem->pnData) {
105 
106  pnNew = malloc(sizeof(dglInt32_t) * pPriItem->cnData);
107 
108  if (pnNew == NULL) {
110  return -pG->iErrno;
111  }
112 
113  for (iEdge1 = 0, iEdge2 = 0; iEdge2 < pPriItem->cnData; iEdge2++) {
114  if (pPriItem->pnData[iEdge2] != nId) {
115  pnNew[iEdge1++] = pPriItem->pnData[iEdge2];
116  }
117  }
118 
119  free(pPriItem->pnData);
120  if (iEdge1 == 0) {
121  free(pnNew);
122  pPriItem->pnData = NULL;
123  pPriItem->cnData = 0;
124  }
125  else {
126  pPriItem->pnData = pnNew;
127  pPriItem->cnData = iEdge1;
128  }
129  }
130  }
131  return 0;
132 }
133 
135  dglInt32_t nPriId)
136 {
137  dglTreeEdgePri32_s *pPriItem;
138 
139  if (pG->edgePrioritizer.pvAVL == NULL) {
140  pG->edgePrioritizer.pvAVL =
142  if (pG->edgePrioritizer.pvAVL == NULL) {
144  return -pG->iErrno;
145  }
146  }
147  pPriItem = dglTreeEdgePri32Add(pG->edgePrioritizer.pvAVL, nPriId);
148  if (pPriItem == NULL) {
150  return -pG->iErrno;
151  }
152  if (pPriItem->cnData == 0) {
153  pPriItem->pnData = (dglInt32_t *) malloc(sizeof(dglInt32_t));
154  }
155  else {
156  pPriItem->pnData =
157  (dglInt32_t *) realloc(pPriItem->pnData,
158  sizeof(dglInt32_t) * (pPriItem->cnData +
159  1));
160  }
161  if (pPriItem->pnData == NULL) {
163  return -pG->iErrno;
164  }
165  pPriItem->pnData[pPriItem->cnData] = nId;
166  pPriItem->cnData++;
167  return 0;
168 }
dglEdgePrioritizer_s edgePrioritizer
Definition: graph.h:181
dglInt32_t * pnData
Definition: tree.h:163
#define avl_find
Definition: tree.h:38
void dgl_swapInt64Bytes(dglInt64_t *pn)
Definition: helpers.c:68
void free(void *)
#define NULL
Definition: ccmath.h:32
int dgl_edge_prioritizer_add(dglGraph_s *pG, dglInt32_t nId, dglInt32_t nPriId)
Definition: helpers.c:134
void * malloc(YYSIZE_T)
int iErrno
Definition: graph.h:154
#define avl_create
Definition: tree.h:31
void dgl_swapInt32Bytes(dglInt32_t *pn)
Definition: helpers.c:55
#define DGL_ERR_MemoryExhausted
Definition: graph.h:283
long long dglInt64_t
Definition: type.h:38
long dglInt32_t
Definition: type.h:37
void * dglTreeGetAllocator()
Definition: tree.c:422
dglInt32_t cnData
Definition: tree.h:162
unsigned char * dgl_mempop(unsigned char *pstack, long *istack, long size)
Definition: helpers.c:48
dglTreeEdgePri32_s * dglTreeEdgePri32Add(void *pavl, dglInt32_t nKey)
Definition: tree.c:385
unsigned char * dgl_mempush(unsigned char *pstack, long *istack, long size, void *pv)
Definition: helpers.c:35
int dgl_edge_prioritizer_del(dglGraph_s *pG, dglInt32_t nId, dglInt32_t nPriId)
Definition: helpers.c:92
int dglTreeEdgePri32Compare(const void *pvEdgePri32A, const void *pvEdgePri32B, void *pvParam)
Definition: tree.c:372
dglInt32_t nKey
Definition: tree.h:161