Cross Reference: /illumos-gate/usr/src/uts/common/os/cyclic.c

Lines Matching refs:heap
150  *  The cyclics are kept sorted by expiration time in the cyc_cpu's heap.  The
151  *  heap is keyed by cyclic expiration time, with parents expiring earlier
156  *  The heap is managed primarily by cyclic_fire().  Upon entry, cyclic_fire()
165  *  (guaranteed to be the earliest in the heap) is then communicated to the
170  *  heap as an array (the cyp_heap member of the cyc_cpu structure), with each
173  *  The heap is laid out in the array according to the following:
175  *   1.  The root of the heap is always in the 0th element of the heap array
180  *  that these constraints correctly lay out a heap (or indeed, any binary
183  *  To see the heap by example, assume our cyclics array has the following
197  *  The heap array could be:
216  *  Note that the heap is laid out by layer:  all nodes at a given depth are
226  *  fewer than sixteen cyclics in the heap, downheaps on UltraSPARC miss at
230  *  heap.  For downheaps proceeding beyond the one-cache-miss depth, every
239  *  depth.  The total number of cache misses for heap management during a
258  *  track the next point-of-insertion into the heap.  In pointer-based heaps,
263  *      heap[number_of_elements]
266  *  heap elements.  Heap insertion, therefore, consists only of filling in
285  *  To insert into this heap, we would just need to fill in the cyclic at
293  *  because the cyclic does not keep a backpointer into the heap.  This makes
294  *  heap manipulation (e.g. downheaps) faster at the expense of removal
448  *  the heap array and the producer/consumer buffers.  Resizing the first two
488  *  all of the old buffers (the heap, the cyclics array and the producer/
522  *    5.  The cyclic is removed from the heap
523  *    6.  If the root of the heap has changed, the backend is reprogrammed.
577  *  bottom of the heap and prevents it from going off until its handler has
587  *    3.  The cyclic is located in the cyclic heap. The search for this is
588  *        done from the bottom of the heap to the top as reprogrammable cyclics
591  *        correct position in the heap (up or down depending on whether the
593  *    5.  If the cyclic move modified the root of the heap, the backend is
737 	cyc_index_t *heap;
744 	heap = cpu->cyp_heap;
749 		current = heap[heap_current];
750 		parent = heap[heap_parent];
760 		 * We need to swap with our parent, and continue up the heap.
762 		heap[heap_parent] = current;
763 		heap[heap_current] = parent;
780 	cyc_index_t *heap = cpu->cyp_heap;
794 		left = heap[heap_left];
795 		me = heap[heap_me];
806 		right = heap[heap_right];
826 			heap[heap_right] = me;
827 			heap[heap_me] = right;
845 		heap[heap_left] = me;
846 		heap[heap_me] = left;
945 	cyc_index_t *heap = cpu->cyp_heap;
963 		cyc_index_t ndx = heap[0];
986 			 * the heap adjustment and reprogramming of the
1354 	 * to CY_HIGH_LEVEL.  This CPU already has a new heap, cyclic array,
1399 	 * We've switched over the heap and the cyclics array.  Now we need
1763 	cyc_index_t *heap, last;
1775 	heap = cpu->cyp_heap;
1821 		if (heap[i] == ndx)
1841 		 * If we just removed the last element of the heap, then
1849 	root = heap[0];
1853 	 * Swap the last element of the heap with the one we want to
1857 	heap[i] = (last = heap[nelems]);
1858 	heap[nelems] = ndx;
1870 			if (heap[i] == last) {
1874 			ASSERT(heap[0] == root);
1883 	cyclic = &cpu->cyp_cyclics[heap[0]];
1961 	cyc_index_t *heap;
1972 	heap = cpu->cyp_heap;
1977 	 * searching from the bottom of the heap to the top instead of the
1981 		if (heap[i] == ndx)
2005 		cyclic = &cpu->cyp_cyclics[heap[0]];