File: mheap.c

package info (click to toggle)
glam2 1064-9
  • links: PTS, VCS
  • area: main
  • in suites: bookworm, bullseye, sid
  • size: 956 kB
  • sloc: ansic: 6,925; xml: 757; asm: 74; makefile: 54; sh: 11
file content (77 lines) | stat: -rw-r--r-- 1,345 bytes parent folder | download | duplicates (4)
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
72
73
74
75
76
77
#include "mheap.h"

mh_type	Mheap(long hpsz, long d)
{
	mh_type H;
	long	i;

	NEW(H,1,mheap_type); 
	NEW(H->avail,hpsz+1,long);
	H->heap=dheap(hpsz,d);
	H->maxheap=dheap(hpsz,d);
	H->hpsz = hpsz;
	H->nfree = hpsz;
	for(i=1; i<=hpsz; i++) H->avail[i] = i;
	return H;
}

mh_type	NilMheap(mh_type H)
{
	if(H==NULL) return (mh_type) NULL;
	Nildheap(H->heap);
	Nildheap(H->maxheap);
	free(H->avail);
	free(H); 
	return (mh_type) NULL;
}

long	DelMinMheap(mh_type H)
{
	long i;
	
	if((i=delminHeap(H->heap))!=(long)NULL){
		rmHeap(i,H->maxheap); 
		H->nfree++;
		H->avail[H->nfree] = i;
		return i;
	} else return (long)NULL;
}

long	DelMaxMheap(mh_type H)
{
	long i;
	
	if((i=delminHeap(H->maxheap))!=(long)NULL){
		rmHeap(i,H->heap); 
		H->nfree++;
		H->avail[H->nfree] = i;
		return i;
	} else return (long)NULL;
}

long	RmMheap(long i, mh_type H)
{
	if(rmHeap(i,H->heap) == (long)NULL) return (long)NULL; 
	rmHeap(i,H->maxheap); 
	H->nfree++;
	H->avail[H->nfree] = i;
	return i;
}

long	InsertMheap(keytyp key, mh_type H)
/* NULL == not inserted; -1 == inserted but none deleted  */
{	
	long i;

	if(H->nfree > 0){
		i = H->avail[H->nfree];
		H->nfree--;
	} else if(minkeyHeap(H->maxheap) < -key) {
		i=delminHeap(H->maxheap);
		rmHeap(i,H->heap);
	} else return (long)NULL;
	insrtHeap(i,key,H->heap);
	insrtHeap(i,-key,H->maxheap);
	return i;
}