Actual source code: pheap.c
petsc-3.6.1 2015-08-06
1: #include <../src/mat/utils/petscheap.h>
2: #include <petsc/private/petscimpl.h>
3: #include <petscviewer.h>
5: typedef struct {
6: PetscInt id;
7: PetscInt value;
8: } HeapNode;
10: struct _PetscHeap {
11: PetscInt end; /* one past the last item */
12: PetscInt alloc; /* length of array */
13: PetscInt stash; /* stash grows down, this points to last item */
14: HeapNode *base;
15: };
17: /*
18: * The arity of the heap can be changed via the parameter B below. Consider the B=2 (arity=4 case below)
19: *
20: * [00 (sentinel); 01 (min node); 10 (unused); 11 (unused); 0100 (first child); 0101; 0110; 0111; ...]
21: *
22: * Slots 10 and 11 are referred to as the "hole" below in the implementation.
23: */
25: #define B 1 /* log2(ARITY) */
26: #define ARITY (1 << B) /* tree branching factor */
27: PETSC_STATIC_INLINE PetscInt Parent(PetscInt loc)
28: {
29: PetscInt p = loc >> B;
30: if (p < ARITY) return (PetscInt)(loc != 1); /* Parent(1) is 0, otherwise fix entries ending up in the hole */
31: return p;
32: }
33: #define Value(h,loc) ((h)->base[loc].value)
34: #define Id(h,loc) ((h)->base[loc].id)
36: PETSC_STATIC_INLINE void Swap(PetscHeap h,PetscInt loc,PetscInt loc2)
37: {
38: PetscInt id,val;
39: id = Id(h,loc);
40: val = Value(h,loc);
41: h->base[loc].id = Id(h,loc2);
42: h->base[loc].value = Value(h,loc2);
43: h->base[loc2].id = id;
44: h->base[loc2].value = val;
45: }
46: PETSC_STATIC_INLINE PetscInt MinChild(PetscHeap h,PetscInt loc)
47: {
48: PetscInt min,chld,left,right;
49: left = loc << B;
50: right = PetscMin(left+ARITY-1,h->end-1);
51: chld = 0;
52: min = PETSC_MAX_INT;
53: for (; left <= right; left++) {
54: PetscInt val = Value(h,left);
55: if (val < min) {
56: min = val;
57: chld = left;
58: }
59: }
60: return chld;
61: }
65: PetscErrorCode PetscHeapCreate(PetscInt maxsize,PetscHeap *heap)
66: {
68: PetscHeap h;
71: *heap = NULL;
72: PetscMalloc1(1,&h);
73: h->end = 1;
74: h->alloc = maxsize+ARITY; /* We waste all but one slot (loc=1) in the first ARITY slots */
75: h->stash = h->alloc;
76: PetscMalloc1(h->alloc,&h->base);
77: PetscMemzero(h->base,h->alloc*sizeof(HeapNode));
78: h->base[0].id = -1;
79: h->base[0].value = PETSC_MIN_INT;
80: *heap = h;
81: return(0);
82: }
86: PetscErrorCode PetscHeapAdd(PetscHeap h,PetscInt id,PetscInt val)
87: {
88: PetscInt loc,par;
91: if (1 < h->end && h->end < ARITY) h->end = ARITY;
92: loc = h->end++;
93: if (h->end > h->stash) SETERRQ2(PETSC_COMM_SELF,PETSC_ERR_ARG_OUTOFRANGE,"Addition would exceed allocation %D (%D stashed)",h->alloc,(h->alloc-h->stash));
94: h->base[loc].id = id;
95: h->base[loc].value = val;
97: /* move up until heap condition is satisfied */
98: while (par = Parent(loc), Value(h,par) > val) {
99: Swap(h,loc,par);
100: loc = par;
101: }
102: return(0);
103: }
107: PetscErrorCode PetscHeapPop(PetscHeap h,PetscInt *id,PetscInt *val)
108: {
109: PetscInt loc,chld;
112: if (h->end == 1) {
113: *id = h->base[0].id;
114: *val = h->base[0].value;
115: return(0);
116: }
118: *id = h->base[1].id;
119: *val = h->base[1].value;
121: /* rotate last entry into first position */
122: loc = --h->end;
123: if (h->end == ARITY) h->end = 2; /* Skip over hole */
124: h->base[1].id = Id(h,loc);
125: h->base[1].value = Value(h,loc);
127: /* move down until min heap condition is satisfied */
128: loc = 1;
129: while ((chld = MinChild(h,loc)) && Value(h,loc) > Value(h,chld)) {
130: Swap(h,loc,chld);
131: loc = chld;
132: }
133: return(0);
134: }
138: PetscErrorCode PetscHeapPeek(PetscHeap h,PetscInt *id,PetscInt *val)
139: {
141: if (h->end == 1) {
142: *id = h->base[0].id;
143: *val = h->base[0].value;
144: return(0);
145: }
147: *id = h->base[1].id;
148: *val = h->base[1].value;
149: return(0);
150: }
154: PetscErrorCode PetscHeapStash(PetscHeap h,PetscInt id,PetscInt val)
155: {
156: PetscInt loc;
159: loc = --h->stash;
160: h->base[loc].id = id;
161: h->base[loc].value = val;
162: return(0);
163: }
167: PetscErrorCode PetscHeapUnstash(PetscHeap h)
168: {
172: while (h->stash < h->alloc) {
173: PetscInt id = Id(h,h->stash),value = Value(h,h->stash);
174: h->stash++;
175: PetscHeapAdd(h,id,value);
176: }
177: return(0);
178: }
182: PetscErrorCode PetscHeapDestroy(PetscHeap *heap)
183: {
187: PetscFree((*heap)->base);
188: PetscFree(*heap);
189: return(0);
190: }
194: PetscErrorCode PetscHeapView(PetscHeap h,PetscViewer viewer)
195: {
197: PetscBool iascii;
200: if (!viewer) {
201: PetscViewerASCIIGetStdout(PETSC_COMM_SELF,&viewer);
202: }
204: PetscObjectTypeCompare((PetscObject)viewer,PETSCVIEWERASCII,&iascii);
205: if (iascii) {
206: PetscViewerASCIIPrintf(viewer,"Heap size %D with %D stashed\n",h->end-1,h->alloc-h->stash);
207: PetscViewerASCIIPrintf(viewer,"Heap in (id,value) pairs\n");
208: PetscIntView(2*(h->end-1),(const PetscInt*)(h->base+1),viewer);
209: PetscViewerASCIIPrintf(viewer,"Stash in (id,value) pairs\n");
210: PetscIntView(2*(h->alloc-h->stash),(const PetscInt*)(h->base+h->stash),viewer);
211: }
212: return(0);
213: }