heap.h
2.02 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
/*
* 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.1.1.1 2002/05/29 01:09:11 blythe 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