3  * Copyright (c) 1995 Carnegie-Mellon University.
23  *  Pittsburgh PA 15213-3890
31  * rf_fifo.c --  prioritized fifo queue code.
59 	RF_FifoHeader_t *q;  in rf_FifoCreate()  local
61 	q = RF_MallocAndAdd(sizeof(*q), clList);  in rf_FifoCreate()
62 	q->hq_count = q->lq_count = 0;  in rf_FifoCreate()
63 	return ((void *) q);  in rf_FifoCreate()
69 	RF_FifoHeader_t *q = (RF_FifoHeader_t *) q_in;  in rf_FifoEnqueue()  local
73 	elem->next = NULL;  in rf_FifoEnqueue()
75 		if (!q->hq_tail) {  in rf_FifoEnqueue()
76 			RF_ASSERT(q->hq_count == 0 && q->hq_head == NULL);  in rf_FifoEnqueue()
77 			q->hq_head = q->hq_tail = elem;  in rf_FifoEnqueue()
79 			RF_ASSERT(q->hq_count != 0 && q->hq_head != NULL);  in rf_FifoEnqueue()
80 			q->hq_tail->next = elem;  in rf_FifoEnqueue()
81 			q->hq_tail = elem;  in rf_FifoEnqueue()
83 		q->hq_count++;  in rf_FifoEnqueue()
85 		RF_ASSERT(elem->next == NULL);  in rf_FifoEnqueue()
89 			       elem->raidPtr->raidid);  in rf_FifoEnqueue()
92 		if (!q->lq_tail) {  in rf_FifoEnqueue()
93 			RF_ASSERT(q->lq_count == 0 && q->lq_head == NULL);  in rf_FifoEnqueue()
94 			q->lq_head = q->lq_tail = elem;  in rf_FifoEnqueue()
96 			RF_ASSERT(q->lq_count != 0 && q->lq_head != NULL);  in rf_FifoEnqueue()
97 			q->lq_tail->next = elem;  in rf_FifoEnqueue()
98 			q->lq_tail = elem;  in rf_FifoEnqueue()
100 		q->lq_count++;  in rf_FifoEnqueue()
102 	if ((q->hq_count + q->lq_count) != elem->queue->queueLength) {  in rf_FifoEnqueue()
104 		    q->hq_count, q->lq_count, (int) elem->queue->queueLength);  in rf_FifoEnqueue()
106 		    (int) elem->queue->numOutstanding,  in rf_FifoEnqueue()
107 		    (int) elem->queue->maxOutstanding,  in rf_FifoEnqueue()
108 		    (int) elem->queue->col);  in rf_FifoEnqueue()
110 	RF_ASSERT((q->hq_count + q->lq_count) == elem->queue->queueLength);  in rf_FifoEnqueue()
116 	RF_FifoHeader_t *q = (RF_FifoHeader_t *) q_in;  in rf_FifoDequeue()  local
119 	RF_ASSERT(q);  in rf_FifoDequeue()
120 	if (q->hq_head) {  in rf_FifoDequeue()
121 		RF_ASSERT(q->hq_count != 0 && q->hq_tail != NULL);  in rf_FifoDequeue()
122 		nd = q->hq_head;  in rf_FifoDequeue()
123 		q->hq_head = q->hq_head->next;  in rf_FifoDequeue()
124 		if (!q->hq_head)  in rf_FifoDequeue()
125 			q->hq_tail = NULL;  in rf_FifoDequeue()
126 		nd->next = NULL;  in rf_FifoDequeue()
127 		q->hq_count--;  in rf_FifoDequeue()
129 		if (q->lq_head) {  in rf_FifoDequeue()
130 			RF_ASSERT(q->lq_count != 0 && q->lq_tail != NULL);  in rf_FifoDequeue()
131 			nd = q->lq_head;  in rf_FifoDequeue()
132 			q->lq_head = q->lq_head->next;  in rf_FifoDequeue()
133 			if (!q->lq_head)  in rf_FifoDequeue()
134 				q->lq_tail = NULL;  in rf_FifoDequeue()
135 			nd->next = NULL;  in rf_FifoDequeue()
136 			q->lq_count--;  in rf_FifoDequeue()
140 				       nd->raidPtr->raidid, (long) nd);  in rf_FifoDequeue()
144 			RF_ASSERT(q->hq_count == 0 && q->lq_count == 0 && q->hq_tail == NULL && q->lq_tail == NULL);  in rf_FifoDequeue()
161 	RF_FifoHeader_t *q = (RF_FifoHeader_t *) q_in;  in rf_FifoPromote()  local
162 	RF_DiskQueueData_t *lp = q->lq_head, *pt = NULL;	/* lp = lo-pri queue  in rf_FifoPromote()
168 		/* search for the indicated parity stripe in the low-pri queue */  in rf_FifoPromote()
169 		if (lp->parityStripeID == parityStripeID && lp->which_ru == which_ru) {  in rf_FifoPromote()
173 				pt->next = lp->next;	/* delete an entry other  in rf_FifoPromote()
176 				q->lq_head = lp->next;	/* delete the head entry */  in rf_FifoPromote()
178 			if (!q->lq_head)  in rf_FifoPromote()
179 				q->lq_tail = NULL;	/* we deleted the only  in rf_FifoPromote()
182 				if (lp == q->lq_tail)  in rf_FifoPromote()
183 					q->lq_tail = pt;	/* we deleted the tail  in rf_FifoPromote()
186 			lp->next = NULL;  in rf_FifoPromote()
187 			q->lq_count--;  in rf_FifoPromote()
189 			if (q->hq_tail) {  in rf_FifoPromote()
190 				q->hq_tail->next = lp;  in rf_FifoPromote()
191 				q->hq_tail = lp;  in rf_FifoPromote()
193 			 /* append to hi-priority queue */  in rf_FifoPromote()
195 				q->hq_head = q->hq_tail = lp;  in rf_FifoPromote()
197 			q->hq_count++;  in rf_FifoPromote()
199 			/* UpdateShortestSeekFinishTimeForced(lp->requestPtr,  in rf_FifoPromote()
200 			 * lp->diskState); *//* deal with this later, if ever */  in rf_FifoPromote()
202 			lp = (pt) ? pt->next : q->lq_head;	/* reset low-pri pointer  in rf_FifoPromote()
208 			lp = lp->next;  in rf_FifoPromote()
213 	 * the low-pri queue */  in rf_FifoPromote()