GRASS Programmer's Manual 6.4.1(2011)
|
00001 /* LIBDGL -- a Directed Graph Library implementation 00002 * Copyright (C) 2002 Roberto Micarelli 00003 * 00004 * This program is free software; you can redistribute it and/or modify 00005 * it under the terms of the GNU General Public License as published by 00006 * the Free Software Foundation; either version 2 of the License, or 00007 * (at your option) any later version. 00008 * 00009 * This program is distributed in the hope that it will be useful, 00010 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00011 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00012 * GNU General Public License for more details. 00013 * 00014 * You should have received a copy of the GNU General Public License 00015 * along with this program; if not, write to the Free Software 00016 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. 00017 */ 00018 00019 /* 00020 * best view with tabstop=4 00021 */ 00022 00023 00024 #include <stdlib.h> 00025 #include <string.h> 00026 00027 #include "type.h" 00028 #include "tree.h" 00029 #include "graph.h" 00030 #include "helpers.h" 00031 00032 /* 00033 * helpers for parametric stack 00034 */ 00035 unsigned char *dgl_mempush(unsigned char *pstack, long *istack, long size, 00036 void *pv) 00037 { 00038 if (*istack == 0) 00039 pstack = NULL; 00040 pstack = realloc(pstack, size * (1 + *istack)); 00041 if (pstack == NULL) 00042 return NULL; 00043 memcpy(&pstack[(*istack) * size], pv, size); 00044 (*istack)++; 00045 return pstack; 00046 } 00047 00048 unsigned char *dgl_mempop(unsigned char *pstack, long *istack, long size) 00049 { 00050 if (*istack == 0) 00051 return NULL; 00052 return &pstack[size * (--(*istack))]; 00053 } 00054 00055 void dgl_swapInt32Bytes(dglInt32_t * pn) 00056 { 00057 unsigned char *pb = (unsigned char *)pn; 00058 00059 pb[0] ^= pb[3]; 00060 pb[3] ^= pb[0]; 00061 pb[0] ^= pb[3]; 00062 00063 pb[1] ^= pb[2]; 00064 pb[2] ^= pb[1]; 00065 pb[1] ^= pb[2]; 00066 } 00067 00068 void dgl_swapInt64Bytes(dglInt64_t * pn) 00069 { 00070 unsigned char *pb = (unsigned char *)pn; 00071 00072 pb[0] ^= pb[7]; 00073 pb[7] ^= pb[0]; 00074 pb[0] ^= pb[7]; 00075 00076 pb[1] ^= pb[6]; 00077 pb[6] ^= pb[1]; 00078 pb[1] ^= pb[6]; 00079 00080 pb[2] ^= pb[5]; 00081 pb[5] ^= pb[2]; 00082 pb[2] ^= pb[5]; 00083 00084 pb[3] ^= pb[4]; 00085 pb[4] ^= pb[3]; 00086 pb[3] ^= pb[4]; 00087 } 00088 00089 /* 00090 * Keep the edge cost prioritizer in sync 00091 */ 00092 int dgl_edge_prioritizer_del(dglGraph_s * pG, dglInt32_t nId, 00093 dglInt32_t nPriId) 00094 { 00095 dglTreeEdgePri32_s findPriItem, *pPriItem; 00096 register int iEdge1, iEdge2; 00097 dglInt32_t *pnNew; 00098 00099 if (pG->edgePrioritizer.pvAVL) { 00100 00101 findPriItem.nKey = nPriId; 00102 pPriItem = avl_find(pG->edgePrioritizer.pvAVL, &findPriItem); 00103 00104 if (pPriItem && pPriItem->pnData) { 00105 00106 pnNew = malloc(sizeof(dglInt32_t) * pPriItem->cnData); 00107 00108 if (pnNew == NULL) { 00109 pG->iErrno = DGL_ERR_MemoryExhausted; 00110 return -pG->iErrno; 00111 } 00112 00113 for (iEdge1 = 0, iEdge2 = 0; iEdge2 < pPriItem->cnData; iEdge2++) { 00114 if (pPriItem->pnData[iEdge2] != nId) { 00115 pnNew[iEdge1++] = pPriItem->pnData[iEdge2]; 00116 } 00117 } 00118 00119 free(pPriItem->pnData); 00120 if (iEdge1 == 0) { 00121 free(pnNew); 00122 pPriItem->pnData = NULL; 00123 pPriItem->cnData = 0; 00124 } 00125 else { 00126 pPriItem->pnData = pnNew; 00127 pPriItem->cnData = iEdge1; 00128 } 00129 } 00130 } 00131 return 0; 00132 } 00133 00134 int dgl_edge_prioritizer_add(dglGraph_s * pG, dglInt32_t nId, 00135 dglInt32_t nPriId) 00136 { 00137 dglTreeEdgePri32_s *pPriItem; 00138 00139 if (pG->edgePrioritizer.pvAVL == NULL) { 00140 pG->edgePrioritizer.pvAVL = 00141 avl_create(dglTreeEdgePri32Compare, NULL, dglTreeGetAllocator()); 00142 if (pG->edgePrioritizer.pvAVL == NULL) { 00143 pG->iErrno = DGL_ERR_MemoryExhausted; 00144 return -pG->iErrno; 00145 } 00146 } 00147 pPriItem = dglTreeEdgePri32Add(pG->edgePrioritizer.pvAVL, nPriId); 00148 if (pPriItem == NULL) { 00149 pG->iErrno = DGL_ERR_MemoryExhausted; 00150 return -pG->iErrno; 00151 } 00152 if (pPriItem->cnData == 0) { 00153 pPriItem->pnData = (dglInt32_t *) malloc(sizeof(dglInt32_t)); 00154 } 00155 else { 00156 pPriItem->pnData = 00157 (dglInt32_t *) realloc(pPriItem->pnData, 00158 sizeof(dglInt32_t) * (pPriItem->cnData + 00159 1)); 00160 } 00161 if (pPriItem->pnData == NULL) { 00162 pG->iErrno = DGL_ERR_MemoryExhausted; 00163 return -pG->iErrno; 00164 } 00165 pPriItem->pnData[pPriItem->cnData] = nId; 00166 pPriItem->cnData++; 00167 return 0; 00168 }