Lines Matching refs:heap
33 struct timer **heap; member
57 static void down_heap(struct timer **heap, int pos) in down_heap() argument
59 int sz = GET_HEAP_SIZE(heap), nxt; in down_heap()
60 struct timer *t = heap[pos]; in down_heap()
64 if ( ((nxt+1) <= sz) && (heap[nxt+1]->expires < heap[nxt]->expires) ) in down_heap()
66 if ( heap[nxt]->expires > t->expires ) in down_heap()
68 heap[pos] = heap[nxt]; in down_heap()
69 heap[pos]->heap_offset = pos; in down_heap()
73 heap[pos] = t; in down_heap()
78 static void up_heap(struct timer **heap, int pos) in up_heap() argument
80 struct timer *t = heap[pos]; in up_heap()
82 while ( (pos > 1) && (t->expires < heap[pos>>1]->expires) ) in up_heap()
84 heap[pos] = heap[pos>>1]; in up_heap()
85 heap[pos]->heap_offset = pos; in up_heap()
89 heap[pos] = t; in up_heap()
95 static int remove_from_heap(struct timer **heap, struct timer *t) in remove_from_heap() argument
97 int sz = GET_HEAP_SIZE(heap); in remove_from_heap()
102 SET_HEAP_SIZE(heap, sz-1); in remove_from_heap()
106 heap[pos] = heap[sz]; in remove_from_heap()
107 heap[pos]->heap_offset = pos; in remove_from_heap()
109 SET_HEAP_SIZE(heap, --sz); in remove_from_heap()
111 if ( (pos > 1) && (heap[pos]->expires < heap[pos>>1]->expires) ) in remove_from_heap()
112 up_heap(heap, pos); in remove_from_heap()
114 down_heap(heap, pos); in remove_from_heap()
122 static int add_to_heap(struct timer **heap, struct timer *t) in add_to_heap() argument
124 int sz = GET_HEAP_SIZE(heap); in add_to_heap()
127 if ( unlikely(sz == GET_HEAP_LIMIT(heap)) ) in add_to_heap()
130 SET_HEAP_SIZE(heap, ++sz); in add_to_heap()
131 heap[sz] = t; in add_to_heap()
133 up_heap(heap, sz); in add_to_heap()
181 rc = remove_from_heap(timers->heap, t); in remove_entry()
205 rc = add_to_heap(timers->heap, t); in add_entry()
446 struct timer *t, **heap, *next; in timer_softirq_action() local
451 heap = ts->heap; in timer_softirq_action()
457 int old_limit = GET_HEAP_LIMIT(heap); in timer_softirq_action()
463 memcpy(newheap, heap, (old_limit + 1) * sizeof(*heap)); in timer_softirq_action()
465 ts->heap = newheap; in timer_softirq_action()
468 xfree(heap); in timer_softirq_action()
469 heap = newheap; in timer_softirq_action()
478 while ( (GET_HEAP_SIZE(heap) != 0) && in timer_softirq_action()
479 ((t = heap[1])->expires < now) ) in timer_softirq_action()
481 remove_from_heap(heap, t); in timer_softirq_action()
504 if ( GET_HEAP_SIZE(heap) != 0 ) in timer_softirq_action()
505 deadline = heap[1]->expires; in timer_softirq_action()
548 for ( j = 1; j <= GET_HEAP_SIZE(ts->heap); j++ ) in dump_timerq()
549 dump_timer(ts->heap[j], now); in dump_timerq()
579 while ( (t = GET_HEAP_SIZE(old_ts->heap) in migrate_timers_from_cpu()
580 ? old_ts->heap[1] : old_ts->list) != NULL ) in migrate_timers_from_cpu()
615 ts->heap = &dummy_heap; in cpu_callback()