File indexing completed on 2024-04-28 07:32:05
0001 /* 0002 ** Author: Eric Veach, July 1994. 0003 ** 0004 */ 0005 0006 #include <limits.h> 0007 #include <stddef.h> 0008 #include <assert.h> 0009 #include "priorityq-heap.h" 0010 #include "memalloc.h" 0011 0012 #define INIT_SIZE 32 0013 0014 #ifndef TRUE 0015 #define TRUE 1 0016 #endif 0017 #ifndef FALSE 0018 #define FALSE 0 0019 #endif 0020 0021 #ifdef FOR_TRITE_TEST_PROGRAM 0022 #define LEQ(x, y) (*pq->leq)(x, y) 0023 #else 0024 /* Violates modularity, but a little faster */ 0025 #include "geom.h" 0026 #define LEQ(x, y) VertLeq((GLUvertex *)x, (GLUvertex *)y) 0027 #endif 0028 0029 /* really __gl_pqHeapNewPriorityQ */ 0030 PriorityQ *pqNewPriorityQ(int (*leq)(PQkey key1, PQkey key2)) 0031 { 0032 PriorityQ *pq = (PriorityQ *)memAlloc(sizeof(PriorityQ)); 0033 if (pq == NULL) 0034 return NULL; 0035 0036 pq->size = 0; 0037 pq->max = INIT_SIZE; 0038 pq->nodes = (PQnode *)memAlloc((INIT_SIZE + 1) * sizeof(pq->nodes[0])); 0039 if (pq->nodes == NULL) 0040 { 0041 memFree(pq); 0042 return NULL; 0043 } 0044 0045 pq->handles = (PQhandleElem *)memAlloc((INIT_SIZE + 1) * sizeof(pq->handles[0])); 0046 if (pq->handles == NULL) 0047 { 0048 memFree(pq->nodes); 0049 memFree(pq); 0050 return NULL; 0051 } 0052 0053 pq->initialized = FALSE; 0054 pq->freeList = 0; 0055 pq->leq = leq; 0056 0057 pq->nodes[1].handle = 1; /* so that Minimum() returns NULL */ 0058 pq->handles[1].key = NULL; 0059 return pq; 0060 } 0061 0062 /* really __gl_pqHeapDeletePriorityQ */ 0063 void pqDeletePriorityQ(PriorityQ *pq) 0064 { 0065 memFree(pq->handles); 0066 memFree(pq->nodes); 0067 memFree(pq); 0068 } 0069 0070 static void FloatDown(PriorityQ *pq, long curr) 0071 { 0072 PQnode *n = pq->nodes; 0073 PQhandleElem *h = pq->handles; 0074 PQhandle hCurr, hChild; 0075 long child; 0076 0077 hCurr = n[curr].handle; 0078 for (;;) 0079 { 0080 child = curr << 1; 0081 if (child < pq->size && LEQ(h[n[child + 1].handle].key, h[n[child].handle].key)) 0082 { 0083 ++child; 0084 } 0085 0086 assert(child <= pq->max); 0087 0088 hChild = n[child].handle; 0089 if (child > pq->size || LEQ(h[hCurr].key, h[hChild].key)) 0090 { 0091 n[curr].handle = hCurr; 0092 h[hCurr].node = curr; 0093 break; 0094 } 0095 n[curr].handle = hChild; 0096 h[hChild].node = curr; 0097 curr = child; 0098 } 0099 } 0100 0101 static void FloatUp(PriorityQ *pq, long curr) 0102 { 0103 PQnode *n = pq->nodes; 0104 PQhandleElem *h = pq->handles; 0105 PQhandle hCurr, hParent; 0106 long parent; 0107 0108 hCurr = n[curr].handle; 0109 for (;;) 0110 { 0111 parent = curr >> 1; 0112 hParent = n[parent].handle; 0113 if (parent == 0 || LEQ(h[hParent].key, h[hCurr].key)) 0114 { 0115 n[curr].handle = hCurr; 0116 h[hCurr].node = curr; 0117 break; 0118 } 0119 n[curr].handle = hParent; 0120 h[hParent].node = curr; 0121 curr = parent; 0122 } 0123 } 0124 0125 /* really __gl_pqHeapInit */ 0126 void pqInit(PriorityQ *pq) 0127 { 0128 long i; 0129 0130 /* This method of building a heap is O(n), rather than O(n lg n). */ 0131 0132 for (i = pq->size; i >= 1; --i) 0133 { 0134 FloatDown(pq, i); 0135 } 0136 pq->initialized = TRUE; 0137 } 0138 0139 /* really __gl_pqHeapInsert */ 0140 /* returns LONG_MAX iff out of memory */ 0141 PQhandle pqInsert(PriorityQ *pq, PQkey keyNew) 0142 { 0143 long curr; 0144 PQhandle free_handle; 0145 0146 curr = ++pq->size; 0147 if ((curr * 2) > pq->max) 0148 { 0149 PQnode *saveNodes = pq->nodes; 0150 PQhandleElem *saveHandles = pq->handles; 0151 0152 /* If the heap overflows, double its size. */ 0153 pq->max <<= 1; 0154 pq->nodes = (PQnode *)memRealloc(pq->nodes, (size_t)((pq->max + 1) * sizeof(pq->nodes[0]))); 0155 if (pq->nodes == NULL) 0156 { 0157 pq->nodes = saveNodes; /* restore ptr to free upon return */ 0158 return LONG_MAX; 0159 } 0160 pq->handles = (PQhandleElem *)memRealloc(pq->handles, (size_t)((pq->max + 1) * sizeof(pq->handles[0]))); 0161 if (pq->handles == NULL) 0162 { 0163 pq->handles = saveHandles; /* restore ptr to free upon return */ 0164 return LONG_MAX; 0165 } 0166 } 0167 0168 if (pq->freeList == 0) 0169 { 0170 free_handle = curr; 0171 } 0172 else 0173 { 0174 free_handle = pq->freeList; 0175 pq->freeList = pq->handles[free_handle].node; 0176 } 0177 0178 pq->nodes[curr].handle = free_handle; 0179 pq->handles[free_handle].node = curr; 0180 pq->handles[free_handle].key = keyNew; 0181 0182 if (pq->initialized) 0183 { 0184 FloatUp(pq, curr); 0185 } 0186 assert(free_handle != LONG_MAX); 0187 return free_handle; 0188 } 0189 0190 /* really __gl_pqHeapExtractMin */ 0191 PQkey pqExtractMin(PriorityQ *pq) 0192 { 0193 PQnode *n = pq->nodes; 0194 PQhandleElem *h = pq->handles; 0195 PQhandle hMin = n[1].handle; 0196 PQkey min = h[hMin].key; 0197 0198 if (pq->size > 0) 0199 { 0200 n[1].handle = n[pq->size].handle; 0201 h[n[1].handle].node = 1; 0202 0203 h[hMin].key = NULL; 0204 h[hMin].node = pq->freeList; 0205 pq->freeList = hMin; 0206 0207 if (--pq->size > 0) 0208 { 0209 FloatDown(pq, 1); 0210 } 0211 } 0212 return min; 0213 } 0214 0215 /* really __gl_pqHeapDelete */ 0216 void pqDelete(PriorityQ *pq, PQhandle hCurr) 0217 { 0218 PQnode *n = pq->nodes; 0219 PQhandleElem *h = pq->handles; 0220 long curr; 0221 0222 assert(hCurr >= 1 && hCurr <= pq->max && h[hCurr].key != NULL); 0223 0224 curr = h[hCurr].node; 0225 n[curr].handle = n[pq->size].handle; 0226 h[n[curr].handle].node = curr; 0227 0228 if (curr <= --pq->size) 0229 { 0230 if (curr <= 1 || LEQ(h[n[curr >> 1].handle].key, h[n[curr].handle].key)) 0231 { 0232 FloatDown(pq, curr); 0233 } 0234 else 0235 { 0236 FloatUp(pq, curr); 0237 } 0238 } 0239 h[hCurr].key = NULL; 0240 h[hCurr].node = pq->freeList; 0241 pq->freeList = hCurr; 0242 }