priorityq.c File Reference

#include "gluos.h"
#include <assert.h>
#include "memalloc.h"
#include "priorityq-heap.c"
#include "priorityq-sort.h"

Include dependency graph for priorityq.c:

Go to the source code of this file.

Macros
#define	LT(x, y)   (! LEQ(y,x))
#define	GT(x, y)   (! LEQ(x,y))
#define	Swap(a, b)   do{PQkey *tmp = *a; *a = *b; *b = tmp;}while(0)

Functions
PriorityQ *	pqNewPriorityQ (int(*leq)(PQkey key1, PQkey key2))
void	pqDeletePriorityQ (PriorityQ *pq)
int	pqInit (PriorityQ *pq)
PQhandle	pqInsert (PriorityQ *pq, PQkey keyNew)
PQkey	pqExtractMin (PriorityQ *pq)
PQkey	pqMinimum (PriorityQ *pq)
int	pqIsEmpty (PriorityQ *pq)
void	pqDelete (PriorityQ *pq, PQhandle curr)

Macro Definition Documentation

GT

#define GT	(		x,
			y
	)		(! LEQ(x,y))

Definition at line 88 of file priorityq.c.

LT

#define LT	(		x,
			y
	)		(! LEQ(y,x))

Definition at line 87 of file priorityq.c.

Swap

#define Swap	(		a,
			b
	)		do{PQkey *tmp = *a; *a = *b; *b = tmp;}while(0)

Definition at line 89 of file priorityq.c.

Function Documentation

pqDelete()

void pqDelete	(	PriorityQ *	pq,
		PQhandle	curr
	)

Definition at line 248 of file priorityq.c.

{
  if( curr >= 0 ) {
    __gl_pqHeapDelete( pq->heap, curr );
    return;
  }
  curr = -(curr+1);
  assert( curr < pq->max && pq->keys[curr] != NULL );
 
  pq->keys[curr] = NULL;
  while( pq->size > 0 && *(pq->order[pq->size-1]) == NULL ) {
    -- pq->size;
  }
}

pqDeletePriorityQ()

void pqDeletePriorityQ

(

PriorityQ *

pq

)

Definition at line 77 of file priorityq.c.

{
  assert(pq != NULL); 
  if (pq->heap != NULL) __gl_pqHeapDeletePriorityQ( pq->heap );
  if (pq->order != NULL) memFree( pq->order );
  if (pq->keys != NULL) memFree( pq->keys );
  memFree( pq );
}

pqExtractMin()

PQkey pqExtractMin

(

PriorityQ *

pq

)

Definition at line 203 of file priorityq.c.

{
  PQkey sortMin, heapMin;
 
  if( pq->size == 0 ) {
    return __gl_pqHeapExtractMin( pq->heap );
  }
  sortMin = *(pq->order[pq->size-1]);
  if( ! __gl_pqHeapIsEmpty( pq->heap )) {
    heapMin = __gl_pqHeapMinimum( pq->heap );
    if( LEQ( heapMin, sortMin )) {
      return __gl_pqHeapExtractMin( pq->heap );
    }
  }
  do {
    -- pq->size;
  } while( pq->size > 0 && *(pq->order[pq->size-1]) == NULL );
  return sortMin;
}

pqInit()

int pqInit

(

PriorityQ *

pq

)

Definition at line 92 of file priorityq.c.

{
  PQkey **p, **r, **i, **j, *piv;
  struct { PQkey **p, **r; } Stack[50], *top = Stack;
  unsigned long seed = 2016473283;
 
  /* Create an array of indirect pointers to the keys, so that we
   * the handles we have returned are still valid.
   */
/*
  pq->order = (PQHeapKey **)memAlloc( (size_t)
                                  (pq->size * sizeof(pq->order[0])) );
*/
  pq->order = (PQHeapKey **)memAlloc( (size_t)
                                  ((pq->size+1) * sizeof(pq->order[0])) );
/* the previous line is a patch to compensate for the fact that IBM */
/* machines return a null on a malloc of zero bytes (unlike SGI),   */
/* so we have to put in this defense to guard against a memory      */
/* fault four lines down. from fossum@austin.ibm.com.               */
  if (pq->order == NULL) return 0;
 
  p = pq->order;
  r = p + pq->size - 1;
  for( piv = pq->keys, i = p; i <= r; ++piv, ++i ) {
    *i = piv;
  }
 
  /* Sort the indirect pointers in descending order,
   * using randomized Quicksort
   */
  top->p = p; top->r = r; ++top;
  while( --top >= Stack ) {
    p = top->p;
    r = top->r;
    while( r > p + 10 ) {
      seed = seed * 1539415821 + 1;
      i = p + seed % (r - p + 1);
      piv = *i;
      *i = *p;
      *p = piv;
      i = p - 1;
      j = r + 1;
      do {
    do { ++i; } while( GT( **i, *piv ));
    do { --j; } while( LT( **j, *piv ));
    Swap( i, j );
      } while( i < j );
      Swap( i, j ); /* Undo last swap */
      if( i - p < r - j ) {
    top->p = j+1; top->r = r; ++top;
    r = i-1;
      } else {
    top->p = p; top->r = i-1; ++top;
    p = j+1;
      }
    }
    /* Insertion sort small lists */
    for( i = p+1; i <= r; ++i ) {
      piv = *i;
      for( j = i; j > p && LT( **(j-1), *piv ); --j ) {
    *j = *(j-1);
      }
      *j = piv;
    }
  }
  pq->max = pq->size;
  pq->initialized = TRUE;
  __gl_pqHeapInit( pq->heap );  /* always succeeds */
 
#ifndef NDEBUG
  p = pq->order;
  r = p + pq->size - 1;
  for( i = p; i < r; ++i ) {
    assert( LEQ( **(i+1), **i ));
  }
#endif
 
  return 1;
}

pqInsert()

PQhandle pqInsert	(	PriorityQ *	pq,
		PQkey	keyNew
	)

Definition at line 174 of file priorityq.c.

{
  long curr;
 
  if( pq->initialized ) {
    return __gl_pqHeapInsert( pq->heap, keyNew );
  }
  curr = pq->size;
  if( ++ pq->size >= pq->max ) {
    PQkey *saveKey= pq->keys;
 
    /* If the heap overflows, double its size. */
    pq->max <<= 1;
    pq->keys = (PQHeapKey *)memRealloc( pq->keys, 
                                (size_t)
                                     (pq->max * sizeof( pq->keys[0] )));
    if (pq->keys == NULL) { 
       pq->keys = saveKey;  /* restore ptr to free upon return */
       return LONG_MAX;
    }
  }
  assert(curr != LONG_MAX); 
  pq->keys[curr] = keyNew;
 
  /* Negative handles index the sorted array. */
  return -(curr+1);
}

pqIsEmpty()

int pqIsEmpty

(

PriorityQ *

pq

)

Definition at line 242 of file priorityq.c.

{
  return (pq->size == 0) && __gl_pqHeapIsEmpty( pq->heap );
}

pqMinimum()

PQkey pqMinimum

(

PriorityQ *

pq

)

Definition at line 224 of file priorityq.c.

{
  PQkey sortMin, heapMin;
 
  if( pq->size == 0 ) {
    return __gl_pqHeapMinimum( pq->heap );
  }
  sortMin = *(pq->order[pq->size-1]);
  if( ! __gl_pqHeapIsEmpty( pq->heap )) {
    heapMin = __gl_pqHeapMinimum( pq->heap );
    if( LEQ( heapMin, sortMin )) {
      return heapMin;
    }
  }
  return sortMin;
}

pqNewPriorityQ()

PriorityQ * pqNewPriorityQ

(

int(*)(PQkey key1, PQkey key2)

leq

)

Definition at line 50 of file priorityq.c.

{
  PriorityQ *pq = (PriorityQ *)memAlloc( sizeof( PriorityQ ));
  if (pq == NULL) return NULL;
 
  pq->heap = __gl_pqHeapNewPriorityQ( leq );
  if (pq->heap == NULL) {
     memFree(pq);
     return NULL;
  }
 
  pq->keys = (PQHeapKey *)memAlloc( INIT_SIZE * sizeof(pq->keys[0]) );
  if (pq->keys == NULL) {
     __gl_pqHeapDeletePriorityQ(pq->heap);
     memFree(pq);
     return NULL;
  }
 
  pq->order = NULL;
  pq->size = 0;
  pq->max = INIT_SIZE;
  pq->initialized = FALSE;
  pq->leq = leq;
  return pq;
}