heap.c

来自「一个用在mips体系结构中的操作系统」· C语言 代码 · 共 283 行

/*
 * Copyright (C) 1996-1998 by the Board of Trustees
 *    of Leland Stanford Junior University.
 * 
 * This file is part of the SimOS distribution. 
 * See LICENSE file for terms of the license. 
 *
 */

/* @TITLE "heap.c - heap data structure */
/* We manage a heap of data,key pairs, where the key a simple data type
 * and the data is any singular data type. We allow the caller to add
 * pairs, remote pairs, peek at the top pair, and do delete/add combinations.
 * The latter are efficient because we only reheap once.
 *
 * David Kotz 1990? and 1993
 *
 * Modify the heap to work with events, with the smallest time  on the top.
 * Song Bac Toh, 1994
 */

/* $Id: heap.c,v 1.5 1998/02/10 00:36:43 bosch Exp $ */

#include <stdio.h>
#include "heap.h"


/* the structure representing one entry in the heap */
typedef struct {
    HeapData data;	      /* the arbitrary data */
    HeapKey key;	      /* key for comparison */
}  HeapEntry;

/* the structure that represents a complete heap */
/* typedef struct heap_struct *Heap;   handle on a heap, from heap.h */
struct heap_struct {
    HeapEntry *heap;	      /* the heap in use (an array) */
    int numheap;	      /* number of elements in heap */
};


/* getting around in the heap */
/* we don't use the 0th element of the array */
#define ROOT 1
#define LCHILD(p) (2 * (p))
#define RCHILD(p) (2 * (p) + 1)
#define PARENT(c) ((c) / 2)

/* @SUBTITLE "Debugging macros" */
/* The following are used for debugging our callers 
 * as well as internal stuff 
 */

/* #define CHECK_INVARIANTS */

#ifdef CHECK_INVARIANTS
#define INVARIANT2(x, y) \
  { \
    if (!(x)) { \
       fprintf(stderr, "INVARIANT false: in \"%s\", line %d\n", \
	       __FILE__, __LINE__); \
       fprintf(stderr, (y)); \
       exit(1); \
    } \
  }

/*
#define INVARIANT3(x, y, z) \
  { \
    if (!(x)) { \
       fprintf(stderr, "INVARIANT false: in \"%s\", line %d\n", \
	       __FILE__, __LINE__); \
       fprintf(stderr, (y), (z)); \
       exit(1); \
    } \
  }
  */
#else
/* #define INVARIANT2(x, y) */
/* #define INVARIANT3(x, y, z) already defined in modularize.h */
#endif /* CHECK_INVARIANTS */


/* @SUBTITLE "InitHeap: Allocate a new heap" */
/* might return NULL if no free memory */
Heap			      
InitHeap(int maxsize)
{
    Heap hp;

    hp = (Heap) malloc(sizeof(struct heap_struct));
    if (hp == NULL) {
	fprintf(stderr, "InitHeap: No memory for heap\n");
	return(NULL);
    }

    hp->heap = (HeapEntry *) malloc(sizeof(HeapEntry) * (maxsize+1));
    if (hp->heap == NULL) {
	fprintf(stderr, "InitHeap: No memory for heap of %d elements\n", 
		maxsize);
	free(hp);
	return(NULL);
    }

    hp->numheap = 0;

    return(hp);
}

/* @SUBTITLE "FreeHeap: delete a heap" */
void
FreeHeap(Heap hp)
{
    if (hp != NULL) {
	free(hp->heap);
	free(hp);
    }
}

/* @SUBTITLE "AddHeap: Add an element to the heap" */
void
AddHeap(Heap hp, HeapData data, HeapKey key)
{
    int node;

    INVARIANT2(hp != NULL, "AddHeap: NULL heap\n");
    INVARIANT2((hp->numheap < HEAP_MAX), "AddHeap: Heap overflowed\n");

    /* use new space end of heap */
    node = ++(hp->numheap);

    /* and reheap */
    while (node != ROOT && hp->heap[PARENT(node)].key > key) {
	hp->heap[node] = hp->heap[PARENT(node)];
	node = PARENT(node);
    }

    hp->heap[node].data = data;
    hp->heap[node].key = key;
}

/* @SUBTITLE "TopHeap: Return top element of heap" */
boolean
TopHeap(Heap hp, HeapData *data, HeapKey *key)
{
    INVARIANT2(hp != NULL, "TopHeap: NULL heap\n");

    if (hp->numheap > 0) {
	if (data)
	  *data = hp->heap[ROOT].data;
	if (key)
	  *key = hp->heap[ROOT].key;
	return(TRUE);
    } else 
      return(FALSE);
}

/* @SUBTITLE "RepHeap: Replace top of heap with given element and reheap" */
/* note that hp->numheap does not change, and should already be > 0 */
void
RepHeap(Heap hp, HeapData data, HeapKey key)
{
    int node;		      /* node in heap */
    int lchild, rchild;	      /* left and right children of node */
    boolean left, right;      /* left and right children exist? */
    boolean swapped;	      /* swap was made? */
    HeapEntry *heap;	      /* pointer to the base of this heap array */

    INVARIANT2(hp != NULL, "RepHeap: NULL heap\n");

    /* If heap is empty just add this element */
    /* if used properly this case should never come up */
    if (hp->numheap == 0) {
	AddHeap(hp, data, key);
	return;
    }

    heap = hp->heap;	      /* cache the heap base pointer */

    node = ROOT;
    swapped = FALSE;
    do {
	lchild = LCHILD(node);
	rchild = RCHILD(node);
	left = (lchild <= hp->numheap);
	right = (rchild <= hp->numheap);

	/* Both children exist: which is smaller? */
	if (left && right)
	  if (heap[lchild].key < heap[rchild].key)
	    right = FALSE;
	  else
	    left = FALSE;

	/* Now only one of left and right is true. compare it with us */
	if (left && heap[lchild].key < key) {
	    /* swap with left child */
	    heap[node] = heap[lchild];
	    node = lchild;
	    swapped = TRUE;
	} else if (right && heap[rchild].key < key) {
	    /* swap with right child */
	    heap[node] = heap[rchild];
	    node = rchild;
	    swapped = TRUE;
	} else
	  swapped = FALSE;
    } while (swapped);

    /* final resting place for new element */
    heap[node].key = key;
    heap[node].data = data;
}

/* @SUBTITLE "RemHeap: Remove top element and reheap" */
boolean
RemHeap(Heap hp, HeapData *data, HeapKey *key)
{
    int node;

    /* we don't check hp's validity because TopHeap will do it for us */

    /* get the top element into data and key, if any */
    if (TopHeap(hp, data, key)) {
	/* there was something there, so replace top with last element */
	node = hp->numheap--;
	if (hp->numheap > 0)
	  RepHeap(hp, hp->heap[node].data, hp->heap[node].key);
	return(TRUE);
    } else
      return(FALSE);
}




/* @SUBTITLE "RemItemHeap: Remove the element that has the same data
   as the given HeapData *data, and reheap" 
   Return TRUE if item is found, FALSE if item not found.
   HeapData* and HeapKey* return the item found. */
boolean RemHeapItem(Heap hp, HeapData *data, HeapKey *key)
{
  HeapData inHeap, tempDat;
  int pos = ROOT;		/* starting position in the heap */
  int hole;			/* the position of the removed item */
  int node;

  /* heap is empty */
  if (hp->numheap <= 0)
    return(FALSE);

  inHeap = (hp->heap[ROOT].data);
  tempDat = *data;
  /* search the heap linearly (we don't match the key) */
  while (!Matching_REQUESTS(inHeap, tempDat))
    {
      if (++pos > hp->numheap)
	return(FALSE);		/* couldn't find the event in queue */
      inHeap = hp->heap[pos].data;
    }
  
  /* returned found items */
  *data = inHeap;
  *key = hp->heap[pos].key;
  
  /* We just took out the found item and created a hole.
     Bubble it up to the root.
   */
  hole = pos;
  while(hole != ROOT)
    {
      hp->heap[hole] = hp->heap[PARENT(hole)];
      hole = PARENT(hole);
    }
  
  /* Replace the root with the last item in the heap */
  node = hp->numheap--;
  if (hp->numheap > 0)
      RepHeap(hp, hp->heap[node].data, hp->heap[node].key);

  return(TRUE);
}