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