Actual source code: pheap.c
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: 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: 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: 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: }
63: PetscErrorCode PetscHeapCreate(PetscInt maxsize, PetscHeap *heap)
64: {
65: PetscHeap h;
67: *heap = NULL;
68: PetscMalloc1(1, &h);
69: h->end = 1;
70: h->alloc = maxsize + ARITY; /* We waste all but one slot (loc=1) in the first ARITY slots */
71: h->stash = h->alloc;
72: PetscCalloc1(h->alloc, &h->base);
73: h->base[0].id = -1;
74: h->base[0].value = PETSC_MIN_INT;
75: *heap = h;
76: return 0;
77: }
79: PetscErrorCode PetscHeapAdd(PetscHeap h, PetscInt id, PetscInt val)
80: {
81: PetscInt loc, par;
83: if (1 < h->end && h->end < ARITY) h->end = ARITY;
84: loc = h->end++;
86: h->base[loc].id = id;
87: h->base[loc].value = val;
89: /* move up until heap condition is satisfied */
90: while ((void)(par = Parent(loc)), Value(h, par) > val) {
91: Swap(h, loc, par);
92: loc = par;
93: }
94: return 0;
95: }
97: PetscErrorCode PetscHeapPop(PetscHeap h, PetscInt *id, PetscInt *val)
98: {
99: PetscInt loc, chld;
101: if (h->end == 1) {
102: *id = h->base[0].id;
103: *val = h->base[0].value;
104: return 0;
105: }
107: *id = h->base[1].id;
108: *val = h->base[1].value;
110: /* rotate last entry into first position */
111: loc = --h->end;
112: if (h->end == ARITY) h->end = 2; /* Skip over hole */
113: h->base[1].id = Id(h, loc);
114: h->base[1].value = Value(h, loc);
116: /* move down until min heap condition is satisfied */
117: loc = 1;
118: while ((chld = MinChild(h, loc)) && Value(h, loc) > Value(h, chld)) {
119: Swap(h, loc, chld);
120: loc = chld;
121: }
122: return 0;
123: }
125: PetscErrorCode PetscHeapPeek(PetscHeap h, PetscInt *id, PetscInt *val)
126: {
127: if (h->end == 1) {
128: *id = h->base[0].id;
129: *val = h->base[0].value;
130: return 0;
131: }
133: *id = h->base[1].id;
134: *val = h->base[1].value;
135: return 0;
136: }
138: PetscErrorCode PetscHeapStash(PetscHeap h, PetscInt id, PetscInt val)
139: {
140: PetscInt loc;
142: loc = --h->stash;
143: h->base[loc].id = id;
144: h->base[loc].value = val;
145: return 0;
146: }
148: PetscErrorCode PetscHeapUnstash(PetscHeap h)
149: {
150: while (h->stash < h->alloc) {
151: PetscInt id = Id(h, h->stash), value = Value(h, h->stash);
152: h->stash++;
153: PetscHeapAdd(h, id, value);
154: }
155: return 0;
156: }
158: PetscErrorCode PetscHeapDestroy(PetscHeap *heap)
159: {
160: PetscFree((*heap)->base);
161: PetscFree(*heap);
162: return 0;
163: }
165: PetscErrorCode PetscHeapView(PetscHeap h, PetscViewer viewer)
166: {
167: PetscBool iascii;
169: if (!viewer) PetscViewerASCIIGetStdout(PETSC_COMM_SELF, &viewer);
171: PetscObjectTypeCompare((PetscObject)viewer, PETSCVIEWERASCII, &iascii);
172: if (iascii) {
173: PetscViewerASCIIPrintf(viewer, "Heap size %" PetscInt_FMT " with %" PetscInt_FMT " stashed\n", h->end - 1, h->alloc - h->stash);
174: PetscViewerASCIIPrintf(viewer, "Heap in (id,value) pairs\n");
175: PetscIntView(2 * (h->end - 1), (const PetscInt *)(h->base + 1), viewer);
176: PetscViewerASCIIPrintf(viewer, "Stash in (id,value) pairs\n");
177: PetscIntView(2 * (h->alloc - h->stash), (const PetscInt *)(h->base + h->stash), viewer);
178: }
179: return 0;
180: }