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,  in move_up_lpt_heap()  argument
57 		return; /* Already top of the heap */  in move_up_lpt_heap()
59 	/* Compare to parent and, if greater, move up the heap */  in move_up_lpt_heap()
63 		val2 = get_heap_comp_val(heap->arr[ppos], cat);  in move_up_lpt_heap()
67 		heap->arr[ppos]->hpos = hpos;  in move_up_lpt_heap()
68 		heap->arr[hpos] = heap->arr[ppos];  in move_up_lpt_heap()
69 		heap->arr[ppos] = lprops;  in move_up_lpt_heap()
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,  in adjust_lpt_heap()  argument
93 	/* Compare to parent and, if greater than parent, move up the heap */  in adjust_lpt_heap()
97 		val2 = get_heap_comp_val(heap->arr[ppos], cat);  in adjust_lpt_heap()
101 				heap->arr[ppos]->hpos = hpos;  in adjust_lpt_heap()
102 				heap->arr[hpos] = heap->arr[ppos];  in adjust_lpt_heap()
103 				heap->arr[ppos] = lprops;  in adjust_lpt_heap()
109 				val2 = get_heap_comp_val(heap->arr[ppos], cat);  in adjust_lpt_heap()
121 		if (cpos >= heap->cnt)  in adjust_lpt_heap()
123 		val2 = get_heap_comp_val(heap->arr[cpos], cat);  in adjust_lpt_heap()
126 			if (cpos + 1 < heap->cnt) {  in adjust_lpt_heap()
127 				val3 = get_heap_comp_val(heap->arr[cpos + 1],  in adjust_lpt_heap()
132 			heap->arr[cpos]->hpos = hpos;  in adjust_lpt_heap()
133 			heap->arr[hpos] = heap->arr[cpos];  in adjust_lpt_heap()
134 			heap->arr[cpos] = lprops;  in adjust_lpt_heap()
141 		if (cpos >= heap->cnt)  in adjust_lpt_heap()
143 		val3 = get_heap_comp_val(heap->arr[cpos], cat);  in adjust_lpt_heap()
146 			heap->arr[cpos]->hpos = hpos;  in adjust_lpt_heap()
147 			heap->arr[hpos] = heap->arr[cpos];  in adjust_lpt_heap()
148 			heap->arr[cpos] = lprops;  in adjust_lpt_heap()
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];  in add_to_lpt_heap()  local
171 	if (heap->cnt >= heap->max_cnt) {  in add_to_lpt_heap()
175 		/* Compare to some other LEB on the bottom of heap */  in add_to_lpt_heap()
180 		ubifs_assert(c, cpos < heap->cnt);  in add_to_lpt_heap()
183 		val2 = get_heap_comp_val(heap->arr[cpos], cat);  in add_to_lpt_heap()
187 			lp = heap->arr[cpos];  in add_to_lpt_heap()
192 			heap->arr[cpos] = lprops;  in add_to_lpt_heap()
193 			move_up_lpt_heap(c, heap, lprops, cat);  in add_to_lpt_heap()
194 			dbg_check_heap(c, heap, cat, lprops->hpos);  in add_to_lpt_heap()
195 			return 1; /* Added to heap */  in add_to_lpt_heap()
197 		dbg_check_heap(c, heap, cat, -1);  in add_to_lpt_heap()
198 		return 0; /* Not added to heap */  in add_to_lpt_heap()
200 		lprops->hpos = heap->cnt++;  in add_to_lpt_heap()
201 		heap->arr[lprops->hpos] = lprops;  in add_to_lpt_heap()
202 		move_up_lpt_heap(c, heap, lprops, cat);  in add_to_lpt_heap()
203 		dbg_check_heap(c, heap, cat, lprops->hpos);  in add_to_lpt_heap()
204 		return 1; /* Added to heap */  in add_to_lpt_heap()
209  * remove_from_lpt_heap - remove LEB properties from a LEB category heap.
217 	struct ubifs_lpt_heap *heap;  in remove_from_lpt_heap()  local
220 	heap = &c->lpt_heap[cat - 1];  in remove_from_lpt_heap()
221 	ubifs_assert(c, hpos >= 0 && hpos < heap->cnt);  in remove_from_lpt_heap()
222 	ubifs_assert(c, heap->arr[hpos] == lprops);  in remove_from_lpt_heap()
223 	heap->cnt -= 1;  in remove_from_lpt_heap()
224 	if (hpos < heap->cnt) {  in remove_from_lpt_heap()
225 		heap->arr[hpos] = heap->arr[heap->cnt];  in remove_from_lpt_heap()
226 		heap->arr[hpos]->hpos = hpos;  in remove_from_lpt_heap()
227 		adjust_lpt_heap(c, heap, heap->arr[hpos], hpos, cat);  in remove_from_lpt_heap()
229 	dbg_check_heap(c, heap, cat, -1);  in remove_from_lpt_heap()
233  * lpt_heap_replace - replace lprops in a category heap.
246 	struct ubifs_lpt_heap *heap;  in lpt_heap_replace()  local
249 	heap = &c->lpt_heap[cat - 1];  in lpt_heap_replace()
250 	heap->arr[hpos] = new_lprops;  in lpt_heap_replace()
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 */  in ubifs_add_to_cat()
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;  in change_category()  local
444 		/* lprops on a heap now must be moved up or down */  in change_category()
446 			return; /* Not on a heap */  in change_category()
447 		heap = &c->lpt_heap[new_cat - 1];  in change_category()
448 		adjust_lpt_heap(c, heap, lprops, lprops->hpos, new_cat);  in change_category()
757 	struct ubifs_lpt_heap *heap;  in ubifs_fast_find_free()  local
761 	heap = &c->lpt_heap[LPROPS_FREE - 1];  in ubifs_fast_find_free()
762 	if (heap->cnt == 0)  in ubifs_fast_find_free()
765 	lprops = heap->arr[0];  in ubifs_fast_find_free()
928 		struct ubifs_lpt_heap *heap = &c->lpt_heap[cat - 1];  in dbg_check_cats()  local
930 		for (i = 0; i < heap->cnt; i++) {  in dbg_check_cats()
931 			lprops = heap->arr[i];  in dbg_check_cats()
933 				ubifs_err(c, "null ptr in LPT heap cat %d", cat);  in dbg_check_cats()
937 				ubifs_err(c, "bad ptr in LPT heap cat %d", cat);  in dbg_check_cats()
941 				ubifs_err(c, "taken LEB in LPT heap cat %d", cat);  in dbg_check_cats()
950 void dbg_check_heap(struct ubifs_info *c, struct ubifs_lpt_heap *heap, int cat,  in dbg_check_heap()  argument
958 	for (i = 0; i < heap->cnt; i++) {  in dbg_check_heap()
959 		struct ubifs_lprops *lprops = heap->arr[i];  in dbg_check_heap()
984 			lp = heap->arr[j];  in dbg_check_heap()
999 		ubifs_dump_heap(c, heap, cat);  in dbg_check_heap()
1069 	/* Check lp is on its category heap (if it has one) */  in scan_check_cb()
1071 		struct ubifs_lpt_heap *heap = &c->lpt_heap[cat - 1];  in scan_check_cb()  local
1073 		if ((lp->hpos != -1 && heap->arr[lp->hpos]->lnum != lnum) ||  in scan_check_cb()
1074 		    lp != heap->arr[lp->hpos]) {  in scan_check_cb()
1075 			ubifs_err(c, "bad LPT heap (category %d)", cat);  in scan_check_cb()