File indexing completed on 2024-03-24 15:17:33
0001 /* 0002 ** Author: Eric Veach, July 1994. 0003 ** 0004 */ 0005 0006 #include "gluos.h" 0007 #include <stddef.h> 0008 #include <assert.h> 0009 #include <limits.h> /* LONG_MAX */ 0010 #include "memalloc.h" 0011 0012 /* Include all the code for the regular heap-based queue here. */ 0013 0014 #include "priorityq-heap.c" 0015 0016 /* Now redefine all the function names to map to their "Sort" versions. */ 0017 0018 #include "priorityq-sort.h" 0019 0020 /* really __gl_pqSortNewPriorityQ */ 0021 PriorityQ *pqNewPriorityQ(int (*leq)(PQkey key1, PQkey key2)) 0022 { 0023 PriorityQ *pq = (PriorityQ *)memAlloc(sizeof(PriorityQ)); 0024 if (pq == NULL) 0025 return NULL; 0026 0027 pq->heap = __gl_pqHeapNewPriorityQ(leq); 0028 if (pq->heap == NULL) 0029 { 0030 memFree(pq); 0031 return NULL; 0032 } 0033 0034 pq->keys = (PQHeapKey *)memAlloc(INIT_SIZE * sizeof(pq->keys[0])); 0035 if (pq->keys == NULL) 0036 { 0037 __gl_pqHeapDeletePriorityQ(pq->heap); 0038 memFree(pq); 0039 return NULL; 0040 } 0041 0042 pq->size = 0; 0043 pq->max = INIT_SIZE; 0044 pq->initialized = FALSE; 0045 pq->leq = leq; 0046 return pq; 0047 } 0048 0049 /* really __gl_pqSortDeletePriorityQ */ 0050 void pqDeletePriorityQ(PriorityQ *pq) 0051 { 0052 assert(pq != NULL); 0053 if (pq->heap != NULL) 0054 __gl_pqHeapDeletePriorityQ(pq->heap); 0055 if (pq->order != NULL) 0056 memFree(pq->order); 0057 if (pq->keys != NULL) 0058 memFree(pq->keys); 0059 memFree(pq); 0060 } 0061 0062 #define LT(x, y) (!LEQ(y, x)) 0063 #define GT(x, y) (!LEQ(x, y)) 0064 #define Swap(a, b) \ 0065 do \ 0066 { \ 0067 PQkey *tmp = *a; \ 0068 *a = *b; \ 0069 *b = tmp; \ 0070 } while (0) 0071 0072 /* really __gl_pqSortInit */ 0073 int pqInit(PriorityQ *pq) 0074 { 0075 PQkey **p, **r, **i, **j, *piv; 0076 struct 0077 { 0078 PQkey **p, **r; 0079 } Stack[50], *top = Stack; 0080 unsigned long seed = 2016473283; 0081 0082 /* Create an array of indirect pointers to the keys, so that we 0083 * the handles we have returned are still valid. 0084 */ 0085 /* 0086 pq->order = (PQHeapKey **)memAlloc( (size_t) 0087 (pq->size * sizeof(pq->order[0])) ); 0088 */ 0089 pq->order = (PQHeapKey **)memAlloc((size_t)((pq->size + 1) * sizeof(pq->order[0]))); 0090 /* the previous line is a patch to compensate for the fact that IBM */ 0091 /* machines return a null on a malloc of zero bytes (unlike SGI), */ 0092 /* so we have to put in this defense to guard against a memory */ 0093 /* fault four lines down. from fossum@austin.ibm.com. */ 0094 if (pq->order == NULL) 0095 return 0; 0096 0097 p = pq->order; 0098 r = p + pq->size - 1; 0099 for (piv = pq->keys, i = p; i <= r; ++piv, ++i) 0100 { 0101 *i = piv; 0102 } 0103 0104 /* Sort the indirect pointers in descending order, 0105 * using randomized Quicksort 0106 */ 0107 top->p = p; 0108 top->r = r; 0109 ++top; 0110 while (--top >= Stack) 0111 { 0112 p = top->p; 0113 r = top->r; 0114 while (r > p + 10) 0115 { 0116 seed = seed * 1539415821 + 1; 0117 i = p + seed % (r - p + 1); 0118 piv = *i; 0119 *i = *p; 0120 *p = piv; 0121 i = p - 1; 0122 j = r + 1; 0123 do 0124 { 0125 do 0126 { 0127 ++i; 0128 } while (GT(**i, *piv)); 0129 do 0130 { 0131 --j; 0132 } while (LT(**j, *piv)); 0133 Swap(i, j); 0134 } while (i < j); 0135 Swap(i, j); /* Undo last swap */ 0136 if (i - p < r - j) 0137 { 0138 top->p = j + 1; 0139 top->r = r; 0140 ++top; 0141 r = i - 1; 0142 } 0143 else 0144 { 0145 top->p = p; 0146 top->r = i - 1; 0147 ++top; 0148 p = j + 1; 0149 } 0150 } 0151 /* Insertion sort small lists */ 0152 for (i = p + 1; i <= r; ++i) 0153 { 0154 piv = *i; 0155 for (j = i; j > p && LT(**(j - 1), *piv); --j) 0156 { 0157 *j = *(j - 1); 0158 } 0159 *j = piv; 0160 } 0161 } 0162 pq->max = pq->size; 0163 pq->initialized = TRUE; 0164 __gl_pqHeapInit(pq->heap); /* always succeeds */ 0165 0166 #ifndef NDEBUG 0167 p = pq->order; 0168 r = p + pq->size - 1; 0169 for (i = p; i < r; ++i) 0170 { 0171 assert(LEQ(**(i + 1), **i)); 0172 } 0173 #endif 0174 0175 return 1; 0176 } 0177 0178 /* really __gl_pqSortInsert */ 0179 /* returns LONG_MAX iff out of memory */ 0180 PQhandle pqInsert(PriorityQ *pq, PQkey keyNew) 0181 { 0182 long curr; 0183 0184 if (pq->initialized) 0185 { 0186 return __gl_pqHeapInsert(pq->heap, keyNew); 0187 } 0188 curr = pq->size; 0189 if (++pq->size >= pq->max) 0190 { 0191 PQkey *saveKey = pq->keys; 0192 0193 /* If the heap overflows, double its size. */ 0194 pq->max <<= 1; 0195 pq->keys = (PQHeapKey *)memRealloc(pq->keys, (size_t)(pq->max * sizeof(pq->keys[0]))); 0196 if (pq->keys == NULL) 0197 { 0198 pq->keys = saveKey; /* restore ptr to free upon return */ 0199 return LONG_MAX; 0200 } 0201 } 0202 assert(curr != LONG_MAX); 0203 pq->keys[curr] = keyNew; 0204 0205 /* Negative handles index the sorted array. */ 0206 return -(curr + 1); 0207 } 0208 0209 /* really __gl_pqSortExtractMin */ 0210 PQkey pqExtractMin(PriorityQ *pq) 0211 { 0212 PQkey sortMin, heapMin; 0213 0214 if (pq->size == 0) 0215 { 0216 return __gl_pqHeapExtractMin(pq->heap); 0217 } 0218 sortMin = *(pq->order[pq->size - 1]); 0219 if (!__gl_pqHeapIsEmpty(pq->heap)) 0220 { 0221 heapMin = __gl_pqHeapMinimum(pq->heap); 0222 if (LEQ(heapMin, sortMin)) 0223 { 0224 return __gl_pqHeapExtractMin(pq->heap); 0225 } 0226 } 0227 do 0228 { 0229 --pq->size; 0230 } while (pq->size > 0 && *(pq->order[pq->size - 1]) == NULL); 0231 return sortMin; 0232 } 0233 0234 /* really __gl_pqSortMinimum */ 0235 PQkey pqMinimum(PriorityQ *pq) 0236 { 0237 PQkey sortMin, heapMin; 0238 0239 if (pq->size == 0) 0240 { 0241 return __gl_pqHeapMinimum(pq->heap); 0242 } 0243 sortMin = *(pq->order[pq->size - 1]); 0244 if (!__gl_pqHeapIsEmpty(pq->heap)) 0245 { 0246 heapMin = __gl_pqHeapMinimum(pq->heap); 0247 if (LEQ(heapMin, sortMin)) 0248 { 0249 return heapMin; 0250 } 0251 } 0252 return sortMin; 0253 } 0254 0255 /* really __gl_pqSortIsEmpty */ 0256 int pqIsEmpty(PriorityQ *pq) 0257 { 0258 return (pq->size == 0) && __gl_pqHeapIsEmpty(pq->heap); 0259 } 0260 0261 /* really __gl_pqSortDelete */ 0262 void pqDelete(PriorityQ *pq, PQhandle curr) 0263 { 0264 if (curr >= 0) 0265 { 0266 __gl_pqHeapDelete(pq->heap, curr); 0267 return; 0268 } 0269 curr = -(curr + 1); 0270 assert(curr < pq->max && pq->keys[curr] != NULL); 0271 0272 pq->keys[curr] = NULL; 0273 while (pq->size > 0 && *(pq->order[pq->size - 1]) == NULL) 0274 { 0275 --pq->size; 0276 } 0277 }