Lines Matching refs:heap
46 static int callout_chunk; /* callout heap chunk size */
142 * the heap. However, we do not want to look at 1-nanosecond
228 * Macro to swap two heap items.
511 * Initialize a callout table's heap, if necessary. Preallocate some free
529 * Reallocate the heap. Return 0 if the heap is still full at the end of it.
530 * Return 1 otherwise. Note that the heap only expands, it never contracts.
536 callout_heap_t *heap;
547 heap = kmem_alloc(size, KM_NOSLEEP);
550 if (heap == NULL) {
558 * If we still have no space in the heap, inform the
570 kmem_free(heap, size);
574 bcopy(ct->ct_heap, heap, osize);
576 ct->ct_heap = heap;
584 * Move an expiration from the bottom of the heap to its correct place
585 * in the heap. If we reached the root doing this, return 1. Else,
592 callout_heap_t *heap, *hcurrent, *hparent;
601 heap = ct->ct_heap;
606 hparent = &heap[parent];
607 hcurrent = &heap[current];
617 * We need to swap with our parent, and continue up the heap.
634 * Insert a new heap item into a callout table's heap.
645 * of the heap.
659 * in the heap.
666 * Move an expiration from the top of the heap to its correct place
667 * in the heap.
673 callout_heap_t *heap, *hleft, *hright, *hcurrent;
678 heap = ct->ct_heap;
690 hleft = &heap[left];
691 hcurrent = &heap[current];
702 hright = &heap[right];
746 * Delete and handle all past expirations in a callout table's heap.
753 callout_heap_t *heap;
760 * There are too many heap elements pointing to empty callout
767 heap = ct->ct_heap;
770 expiration = heap->ch_expiration;
772 cl = heap->ch_list;
785 * If the root of the heap expires in the future,
803 * the last item in the heap and downheaping the item.
807 heap[0] = heap[ct->ct_heap_num];
828 if ((heap[1].ch_expiration < next) ||
829 (heap[2].ch_expiration < next))
839 * There are some situations when the entire heap is walked and processed.
842 * 1. When the reap count reaches its threshold, the heap has to be cleared
845 * 2. When the system enters and exits KMDB/OBP, all entries in the heap
848 * 3. When system time is changed, the heap has to be scanned for
849 * absolute hrestime timers. These need to be removed from the heap
853 * scanning the heap anyway.
861 callout_heap_t *heap;
875 heap = ct->ct_heap;
878 * We walk the heap from the top to the bottom. If we encounter
879 * a heap item that points to an empty callout list, we clean
884 * During the walk, we also compact the heap from the bottom and
885 * reconstruct the heap using upheap operations. This is very
887 * or equal to half the heap. This is the common case.
898 cl = heap[i].ch_list;
900 * If the callout list is empty, delete the heap element and
911 * Delete the heap element and expire the callout list, if
937 heap[i].ch_expiration = expiration;
947 heap[ct->ct_heap_num] = heap[i];
957 * immediately. If the heap has become empty, then we return infinity.
958 * Else, return the expiration of the earliest callout in the heap.
966 return (heap->ch_expiration);
1027 * There are too many heap elements pointing to empty callout
1030 * of the heap gets cleaned out.
1120 * Plus, the heap could have become full. So, the best
1131 * Check if we have enough space in the heap to insert one
1132 * expiration. If not, expand the heap.
1137 * Could not expand the heap. Just queue it.
1161 * This is a new expiration. So, insert it into the heap.
1163 * propagated to the root of the heap.
1312 * corresponds to the top of the the callout heap, we
1327 * - in the heap, it needs to be cleaned along
1328 * with its heap entry. Increment a reap count.
1688 * the heap by delta. Also, if the caller indicates
1769 * Walk the heap and process all the absolute hrestime entries.
1903 * could potentially expand the cyclic heap. We don't want to be
2004 * We use the heap pointer to check if stuff has been