1 #include <../src/mat/utils/petscheap.h> 2 3 typedef struct { 4 PetscInt id; 5 PetscInt value; 6 } HeapNode; 7 8 struct _PetscHeap { 9 PetscInt end; /* one past the last item */ 10 PetscInt alloc; /* length of array */ 11 PetscInt stash; /* stash grows down, this points to last item */ 12 HeapNode *base; 13 }; 14 15 #define Parent(loc) ((loc) >> 1) 16 #define Left(loc) ((loc) << 1) 17 #define Right(loc) (Left((loc))+1) 18 #define Value(h,loc) ((h)->base[loc].value) 19 #define Id(h,loc) ((h)->base[loc].id) 20 21 PETSC_STATIC_INLINE void Swap(PetscHeap h,PetscInt loc,PetscInt loc2) { 22 PetscInt id,val; 23 id = Id(h,loc); 24 val = Value(h,loc); 25 h->base[loc].id = Id(h,loc2); 26 h->base[loc].value = Value(h,loc2); 27 h->base[loc2].id = id; 28 h->base[loc2].value = val; 29 } 30 PETSC_STATIC_INLINE PetscInt MinChild(PetscHeap h,PetscInt loc) { 31 if (Left(loc) >= h->end) return 0; 32 if (Right(loc) >= h->end) return Left(loc); 33 return Value(h,Left(loc)) <= Value(h,Right(loc)) ? Left(loc) : Right(loc); 34 } 35 36 #undef __FUNCT__ 37 #define __FUNCT__ "PetscHeapCreate" 38 PetscErrorCode PetscHeapCreate(PetscInt maxsize,PetscHeap *heap) 39 { 40 PetscErrorCode ierr; 41 PetscHeap h; 42 43 PetscFunctionBegin; 44 *heap = PETSC_NULL; 45 ierr = PetscMalloc(sizeof *h,&h);CHKERRQ(ierr); 46 h->end = 1; 47 h->alloc = maxsize+1; 48 h->stash = h->alloc; 49 ierr = PetscMalloc((maxsize+1)*sizeof(HeapNode),&h->base);CHKERRQ(ierr); 50 h->base[0].id = -1; 51 h->base[0].value = PETSC_MIN_INT; 52 *heap = h; 53 PetscFunctionReturn(0); 54 } 55 56 #undef __FUNCT__ 57 #define __FUNCT__ "PetscHeapAdd" 58 PetscErrorCode PetscHeapAdd(PetscHeap h,PetscInt id,PetscInt val) 59 { 60 PetscInt loc; 61 62 PetscFunctionBegin; 63 loc = h->end++; 64 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)); 65 h->base[loc].id = id; 66 h->base[loc].value = val; 67 68 /* move up until heap condition is satisfied */ 69 while (Value(h,Parent(loc)) > val) { 70 Swap(h,loc,Parent(loc)); 71 loc = Parent(loc); 72 } 73 PetscFunctionReturn(0); 74 } 75 76 #undef __FUNCT__ 77 #define __FUNCT__ "PetscHeapPop" 78 PetscErrorCode PetscHeapPop(PetscHeap h,PetscInt *id,PetscInt *val) 79 { 80 PetscInt loc,chld; 81 82 PetscFunctionBegin; 83 if (h->end == 1) { 84 *id = h->base[0].id; 85 *val = h->base[0].value; 86 PetscFunctionReturn(0); 87 } 88 89 *id = h->base[1].id; 90 *val = h->base[1].value; 91 92 /* rotate last entry into first position */ 93 loc = --h->end; 94 h->base[1].id = Id(h,loc); 95 h->base[1].value = Value(h,loc); 96 97 /* move down until min heap condition is satisfied */ 98 loc = 1; 99 while ((chld = MinChild(h,loc)) && Value(h,loc) > Value(h,chld)) { 100 Swap(h,loc,chld); 101 loc = chld; 102 } 103 PetscFunctionReturn(0); 104 } 105 106 #undef __FUNCT__ 107 #define __FUNCT__ "PetscHeapPeek" 108 PetscErrorCode PetscHeapPeek(PetscHeap h,PetscInt *id,PetscInt *val) 109 { 110 PetscFunctionBegin; 111 if (h->end == 1) { 112 *id = h->base[0].id; 113 *val = h->base[0].value; 114 PetscFunctionReturn(0); 115 } 116 117 *id = h->base[1].id; 118 *val = h->base[1].value; 119 PetscFunctionReturn(0); 120 } 121 122 #undef __FUNCT__ 123 #define __FUNCT__ "PetscHeapStash" 124 PetscErrorCode PetscHeapStash(PetscHeap h,PetscInt id,PetscInt val) 125 { 126 PetscInt loc; 127 128 PetscFunctionBegin; 129 loc = --h->stash; 130 h->base[loc].id = id; 131 h->base[loc].value = val; 132 PetscFunctionReturn(0); 133 } 134 135 #undef __FUNCT__ 136 #define __FUNCT__ "PetscHeapUnstash" 137 PetscErrorCode PetscHeapUnstash(PetscHeap h) 138 { 139 PetscErrorCode ierr; 140 141 PetscFunctionBegin; 142 while (h->stash < h->alloc) { 143 PetscInt id = Id(h,h->stash),value = Value(h,h->stash); 144 h->stash++; 145 ierr = PetscHeapAdd(h,id,value);CHKERRQ(ierr); 146 } 147 PetscFunctionReturn(0); 148 } 149 150 #undef __FUNCT__ 151 #define __FUNCT__ "PetscHeapDestroy" 152 PetscErrorCode PetscHeapDestroy(PetscHeap *heap) 153 { 154 PetscErrorCode ierr; 155 156 PetscFunctionBegin; 157 ierr = PetscFree((*heap)->base);CHKERRQ(ierr); 158 ierr = PetscFree(*heap);CHKERRQ(ierr); 159 PetscFunctionReturn(0); 160 } 161 162 #undef __FUNCT__ 163 #define __FUNCT__ "PetscHeapView" 164 PetscErrorCode PetscHeapView(PetscHeap h,PetscViewer viewer) 165 { 166 PetscErrorCode ierr; 167 PetscBool iascii; 168 169 PetscFunctionBegin; 170 if (!viewer) { 171 ierr = PetscViewerASCIIGetStdout(PETSC_COMM_SELF,&viewer);CHKERRQ(ierr); 172 } 173 PetscValidHeaderSpecific(viewer,PETSC_VIEWER_CLASSID,2); 174 ierr = PetscObjectTypeCompare((PetscObject)viewer,PETSCVIEWERASCII,&iascii);CHKERRQ(ierr); 175 if (iascii) { 176 ierr = PetscViewerASCIIPrintf(viewer,"Heap size %D with %D stashed\n",h->end-1,h->alloc-h->stash);CHKERRQ(ierr); 177 ierr = PetscViewerASCIIPrintf(viewer,"Heap in (id,value) pairs\n");CHKERRQ(ierr); 178 ierr = PetscIntView(2*(h->end-1),(const PetscInt*)(h->base+1),viewer);CHKERRQ(ierr); 179 ierr = PetscViewerASCIIPrintf(viewer,"Stash in (id,value) pairs\n");CHKERRQ(ierr); 180 ierr = PetscIntView(2*(h->alloc-h->stash),(const PetscInt*)(h->base+h->stash),viewer);CHKERRQ(ierr); 181 } 182 PetscFunctionReturn(0); 183 } 184