32 #define Value(h, loc) ((h)->base[loc].value)  argument
33 #define Id(h, loc)    ((h)->base[loc].id)  argument
35 static inline void Swap(PetscHeap h, PetscInt loc, PetscInt loc2)  in Swap()  argument
38   id                  = Id(h, loc);  in Swap()
39   val                 = Value(h, loc);  in Swap()
40   h->base[loc].id     = Id(h, loc2);  in Swap()
41   h->base[loc].value  = Value(h, loc2);  in Swap()
42   h->base[loc2].id    = id;  in Swap()
43   h->base[loc2].value = val;  in Swap()
45 static inline PetscInt MinChild(PetscHeap h, PetscInt loc)  in MinChild()  argument
49   right = PetscMin(left + ARITY - 1, h->end - 1);  in MinChild()
53     PetscInt val = Value(h, left);  in MinChild()
64   PetscHeap h;  in PetscHeapCreate()  local
68   PetscCall(PetscMalloc1(1, &h));  in PetscHeapCreate()
69   h->end   = 1;  in PetscHeapCreate()
70   h->alloc = maxsize + ARITY; /* We waste all but one slot (loc=1) in the first ARITY slots */  in PetscHeapCreate()
71   h->stash = h->alloc;  in PetscHeapCreate()
72   PetscCall(PetscCalloc1(h->alloc, &h->base));  in PetscHeapCreate()
73   h->base[0].id    = -1;  in PetscHeapCreate()
74   h->base[0].value = PETSC_INT_MIN;  in PetscHeapCreate()
75   *heap            = h;  in PetscHeapCreate()
79 PetscErrorCode PetscHeapAdd(PetscHeap h, PetscInt id, PetscInt val)  in PetscHeapAdd()  argument
84   if (1 < h->end && h->end < ARITY) h->end = ARITY;  in PetscHeapAdd()
85   loc = h->end++;  in PetscHeapAdd()
86 …h->end <= h->stash, PETSC_COMM_SELF, PETSC_ERR_ARG_OUTOFRANGE, "Addition would exceed allocation %…  in PetscHeapAdd()
87   h->base[loc].id    = id;  in PetscHeapAdd()
88   h->base[loc].value = val;  in PetscHeapAdd()
91   while ((void)(par = Parent(loc)), Value(h, par) > val) {  in PetscHeapAdd()
92     Swap(h, loc, par);  in PetscHeapAdd()
98 PetscErrorCode PetscHeapPop(PetscHeap h, PetscInt *id, PetscInt *val)  in PetscHeapPop()  argument
103   if (h->end == 1) {  in PetscHeapPop()
104     *id  = h->base[0].id;  in PetscHeapPop()
105     *val = h->base[0].value;  in PetscHeapPop()
109   *id  = h->base[1].id;  in PetscHeapPop()
110   *val = h->base[1].value;  in PetscHeapPop()
113   loc = --h->end;  in PetscHeapPop()
114   if (h->end == ARITY) h->end = 2; /* Skip over hole */  in PetscHeapPop()
115   h->base[1].id    = Id(h, loc);  in PetscHeapPop()
116   h->base[1].value = Value(h, loc);  in PetscHeapPop()
120   while ((chld = MinChild(h, loc)) && Value(h, loc) > Value(h, chld)) {  in PetscHeapPop()
121     Swap(h, loc, chld);  in PetscHeapPop()
127 PetscErrorCode PetscHeapPeek(PetscHeap h, PetscInt *id, PetscInt *val)  in PetscHeapPeek()  argument
130   if (h->end == 1) {  in PetscHeapPeek()
131     *id  = h->base[0].id;  in PetscHeapPeek()
132     *val = h->base[0].value;  in PetscHeapPeek()
136   *id  = h->base[1].id;  in PetscHeapPeek()
137   *val = h->base[1].value;  in PetscHeapPeek()
141 PetscErrorCode PetscHeapStash(PetscHeap h, PetscInt id, PetscInt val)  in PetscHeapStash()  argument
146   loc                = --h->stash;  in PetscHeapStash()
147   h->base[loc].id    = id;  in PetscHeapStash()
148   h->base[loc].value = val;  in PetscHeapStash()
152 PetscErrorCode PetscHeapUnstash(PetscHeap h)  in PetscHeapUnstash()  argument
155   while (h->stash < h->alloc) {  in PetscHeapUnstash()
156     PetscInt id = Id(h, h->stash), value = Value(h, h->stash);  in PetscHeapUnstash()
157     h->stash++;  in PetscHeapUnstash()
158     PetscCall(PetscHeapAdd(h, id, value));  in PetscHeapUnstash()
171 PetscErrorCode PetscHeapView(PetscHeap h, PetscViewer viewer)  in PetscHeapView()  argument
180 … "Heap size %" PetscInt_FMT " with %" PetscInt_FMT " stashed\n", h->end - 1, h->alloc - h->stash));  in PetscHeapView()
182     PetscCall(PetscIntView(2 * (h->end - 1), (const PetscInt *)(h->base + 1), viewer));  in PetscHeapView()
184 …PetscCall(PetscIntView(2 * (h->alloc - h->stash), (const PetscInt *)(h->base + h->stash), viewer));  in PetscHeapView()