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 }