Lines Matching refs:heap
22 * get_heap_comp_val - get the LEB properties value for heap comparisons.
39 * move_up_lpt_heap - move a new heap entry up as far as possible.
41 * @heap: LEB category heap
45 * New entries to a heap are added at the bottom and then moved up until the
50 static void move_up_lpt_heap(struct ubifs_info *c, struct ubifs_lpt_heap *heap,
57 return; /* Already top of the heap */
59 /* Compare to parent and, if greater, move up the heap */
63 val2 = get_heap_comp_val(heap->arr[ppos], cat);
67 heap->arr[ppos]->hpos = hpos;
68 heap->arr[hpos] = heap->arr[ppos];
69 heap->arr[ppos] = lprops;
76 * adjust_lpt_heap - move a changed heap entry up or down the heap.
78 * @heap: LEB category heap
80 * @hpos: heap position of @lprops
83 * Changed entries in a heap are moved up or down until the parent's value is
87 static void adjust_lpt_heap(struct ubifs_info *c, struct ubifs_lpt_heap *heap,
93 /* Compare to parent and, if greater than parent, move up the heap */
97 val2 = get_heap_comp_val(heap->arr[ppos], cat);
101 heap->arr[ppos]->hpos = hpos;
102 heap->arr[hpos] = heap->arr[ppos];
103 heap->arr[ppos] = lprops;
109 val2 = get_heap_comp_val(heap->arr[ppos], cat);
121 if (cpos >= heap->cnt)
123 val2 = get_heap_comp_val(heap->arr[cpos], cat);
126 if (cpos + 1 < heap->cnt) {
127 val3 = get_heap_comp_val(heap->arr[cpos + 1],
132 heap->arr[cpos]->hpos = hpos;
133 heap->arr[hpos] = heap->arr[cpos];
134 heap->arr[cpos] = lprops;
141 if (cpos >= heap->cnt)
143 val3 = get_heap_comp_val(heap->arr[cpos], cat);
146 heap->arr[cpos]->hpos = hpos;
147 heap->arr[hpos] = heap->arr[cpos];
148 heap->arr[cpos] = lprops;
158 * add_to_lpt_heap - add LEB properties to a LEB category heap.
163 * This function returns %1 if @lprops is added to the heap for LEB category
164 * @cat, otherwise %0 is returned because the heap is full.
169 struct ubifs_lpt_heap *heap = &c->lpt_heap[cat - 1];
171 if (heap->cnt >= heap->max_cnt) {
175 /* Compare to some other LEB on the bottom of heap */
180 ubifs_assert(c, cpos < heap->cnt);
183 val2 = get_heap_comp_val(heap->arr[cpos], cat);
187 lp = heap->arr[cpos];
192 heap->arr[cpos] = lprops;
193 move_up_lpt_heap(c, heap, lprops, cat);
194 dbg_check_heap(c, heap, cat, lprops->hpos);
195 return 1; /* Added to heap */
197 dbg_check_heap(c, heap, cat, -1);
198 return 0; /* Not added to heap */
200 lprops->hpos = heap->cnt++;
201 heap->arr[lprops->hpos] = lprops;
202 move_up_lpt_heap(c, heap, lprops, cat);
203 dbg_check_heap(c, heap, cat, lprops->hpos);
204 return 1; /* Added to heap */
209 * remove_from_lpt_heap - remove LEB properties from a LEB category heap.
217 struct ubifs_lpt_heap *heap;
220 heap = &c->lpt_heap[cat - 1];
221 ubifs_assert(c, hpos >= 0 && hpos < heap->cnt);
222 ubifs_assert(c, heap->arr[hpos] == lprops);
223 heap->cnt -= 1;
224 if (hpos < heap->cnt) {
225 heap->arr[hpos] = heap->arr[heap->cnt];
226 heap->arr[hpos]->hpos = hpos;
227 adjust_lpt_heap(c, heap, heap->arr[hpos], hpos, cat);
229 dbg_check_heap(c, heap, cat, -1);
233 * lpt_heap_replace - replace lprops in a category heap.
246 struct ubifs_lpt_heap *heap;
249 heap = &c->lpt_heap[cat - 1];
250 heap->arr[hpos] = new_lprops;
254 * ubifs_add_to_cat - add LEB properties to a category list or heap.
270 /* No more room on heap so make it un-categorized */
297 * ubifs_remove_from_cat - remove LEB properties from a category list or heap.
332 * ubifs_replace_cat - replace lprops in a category list or heap.
369 * A LEB may have fallen off of the bottom of a heap, and ended up as
371 * case this function will put the LEB back onto a heap.
393 * that if the LEB category is stored as a heap and the heap is full, the
442 struct ubifs_lpt_heap *heap;
444 /* lprops on a heap now must be moved up or down */
446 return; /* Not on a heap */
447 heap = &c->lpt_heap[new_cat - 1];
448 adjust_lpt_heap(c, heap, lprops, lprops->hpos, new_cat);
757 struct ubifs_lpt_heap *heap;
761 heap = &c->lpt_heap[LPROPS_FREE - 1];
762 if (heap->cnt == 0)
765 lprops = heap->arr[0];
928 struct ubifs_lpt_heap *heap = &c->lpt_heap[cat - 1];
930 for (i = 0; i < heap->cnt; i++) {
931 lprops = heap->arr[i];
933 ubifs_err(c, "null ptr in LPT heap cat %d", cat);
937 ubifs_err(c, "bad ptr in LPT heap cat %d", cat);
941 ubifs_err(c, "taken LEB in LPT heap cat %d", cat);
950 void dbg_check_heap(struct ubifs_info *c, struct ubifs_lpt_heap *heap, int cat,
958 for (i = 0; i < heap->cnt; i++) {
959 struct ubifs_lprops *lprops = heap->arr[i];
984 lp = heap->arr[j];
999 ubifs_dump_heap(c, heap, cat);
1069 /* Check lp is on its category heap (if it has one) */
1071 struct ubifs_lpt_heap *heap = &c->lpt_heap[cat - 1];
1073 if ((lp->hpos != -1 && heap->arr[lp->hpos]->lnum != lnum) ||
1074 lp != heap->arr[lp->hpos]) {
1075 ubifs_err(c, "bad LPT heap (category %d)", cat);