heap.h

一个用在mips体系结构中的操作系统

/*
 * 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.h - interface to heap management implementation */
/* We manage a heap of data,key pairs, where the key could be any 
 * simple data type 
 * and the data is any pointer 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
 */

/* $Id: heap.h,v 1.4 1998/02/10 00:36:44 bosch Exp $ */

#ifndef HEAP_H
#define HEAP_H

#ifndef DFK
#include "modularize.h"
#endif
#include "diskevent.h"

typedef TICS HeapKey;	        /* type of the key used in heap */

/* heap data */
typedef struct heapdata {
  REQUESTCODE req_code;
  TICS eventTime;
  int disk;
} heapdata;

typedef heapdata   *HeapData;	        /* type of the data used in heap */
typedef struct heap_struct *Heap;       /* handle on a heap */


/* return TRUE if the two requests in the heap match */
#define Matching_REQUESTS(HeapData1, HeapData2)       \
((HeapData1->disk == HeapData2->disk) &&              \
 (HeapData1->req_code == HeapData2->req_code))


/* set up heap to hold maxsize nodes */
Heap InitHeap(int maxsize);

/* delete a heap data structure */
void FreeHeap(Heap hp);

/* add the element to the heap */
void AddHeap(Heap hp, HeapData data, HeapKey key); 

/* return top of the heap, without removing it from heap (FALSE if empty) */
boolean TopHeap(Heap hp, HeapData *data, HeapKey *key);

/* replace the heap's top item with a new item, and reheap */
void RepHeap(Heap hp, HeapData data, HeapKey key);

/* remove the heap's top item, if any (FALSE if empty heap) */
boolean RemHeap(Heap hp, HeapData *data, HeapKey *key);

/* remove the item that has matching data from the heap, 
   if any (FALSE if empty heap), the data is not returned */
boolean RemHeapItem(Heap hp, HeapData *data, HeapKey *key);

#endif