1/*  *********************************************************************
2    *  Broadcom Common Firmware Environment (CFE)
3    *
4    *  Queue Management routines		File: lib_queue.c
5    *
6    *  Routines to manage doubly-linked queues.
7    *
8    *  Author:  Mitch Lichtenberg
9    *
10    *********************************************************************
11    *
12    *  Copyright 2000,2001,2002,2003
13    *  Broadcom Corporation. All rights reserved.
14    *
15    *  This software is furnished under license and may be used and
16    *  copied only in accordance with the following terms and
17    *  conditions.  Subject to these conditions, you may download,
18    *  copy, install, use, modify and distribute modified or unmodified
19    *  copies of this software in source and/or binary form.  No title
20    *  or ownership is transferred hereby.
21    *
22    *  1) Any source code used, modified or distributed must reproduce
23    *     and retain this copyright notice and list of conditions
24    *     as they appear in the source file.
25    *
26    *  2) No right is granted to use any trade name, trademark, or
27    *     logo of Broadcom Corporation.  The "Broadcom Corporation"
28    *     name may not be used to endorse or promote products derived
29    *     from this software without the prior written permission of
30    *     Broadcom Corporation.
31    *
32    *  3) THIS SOFTWARE IS PROVIDED "AS-IS" AND ANY EXPRESS OR
33    *     IMPLIED WARRANTIES, INCLUDING BUT NOT LIMITED TO, ANY IMPLIED
34    *     WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR
35    *     PURPOSE, OR NON-INFRINGEMENT ARE DISCLAIMED. IN NO EVENT
36    *     SHALL BROADCOM BE LIABLE FOR ANY DAMAGES WHATSOEVER, AND IN
37    *     PARTICULAR, BROADCOM SHALL NOT BE LIABLE FOR DIRECT, INDIRECT,
38    *     INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
39    *     (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
40    *     GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
41    *     BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
42    *     OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR
43    *     TORT (INCLUDING NEGLIGENCE OR OTHERWISE), EVEN IF ADVISED OF
44    *     THE POSSIBILITY OF SUCH DAMAGE.
45    ********************************************************************* */
46
47
48#include "lib_types.h"
49#include "lib_queue.h"
50
51
52/*  *********************************************************************
53    *  Q_ENQUEUE(qb,item)
54    *
55    *  Add item to a queue
56    *
57    *  Input Parameters:
58    *      qb - queue block
59    *      item - item to add
60    *
61    *  Return Value:
62    *      Nothing.
63    ********************************************************************* */
64
65void q_enqueue(queue_t *qb,queue_t *item)
66{
67    qb->q_prev->q_next = item;
68    item->q_next = qb;
69    item->q_prev = qb->q_prev;
70    qb->q_prev = item;
71}
72
73
74/*  *********************************************************************
75    *  Q_DEQUEUE(element)
76    *
77    *  Remove an element from the queue
78    *
79    *  Input Parameters:
80    *      element - element to remove
81    *
82    *  Return Value:
83    *      Nothing.
84    ********************************************************************* */
85
86void q_dequeue(queue_t *item)
87{
88    item->q_prev->q_next = item->q_next;
89    item->q_next->q_prev = item->q_prev;
90}
91
92
93/*  *********************************************************************
94    *  Q_DEQNEXT(qb)
95    *
96    *  Dequeue next element from the specified queue
97    *
98    *  Input Parameters:
99    *      qb - queue block
100    *
101    *  Return Value:
102    *      next element, or NULL
103    ********************************************************************* */
104
105queue_t *q_deqnext(queue_t *qb)
106{
107    if (qb->q_next == qb) {
108	return NULL;
109	}
110
111    qb = qb->q_next;
112
113    qb->q_prev->q_next = qb->q_next;
114    qb->q_next->q_prev = qb->q_prev;
115
116    return qb;
117}
118
119
120/*  *********************************************************************
121    *  Q_MAP(qb)
122    *
123    *  "Map" a queue, calling the specified function for each
124    *  element in the queue
125    *
126    *  If the function returns nonzero, q_map will terminate.
127    *
128    *  Input Parameters:
129    *      qb - queue block
130    *      fn - function pointer
131    *      a,b - parameters for the function
132    *
133    *  Return Value:
134    *      return value from function, or zero if entire queue
135    *      was mapped.
136    ********************************************************************* */
137
138int q_map(queue_t *qb, int (*func)(queue_t *,unsigned int,unsigned int),
139	  unsigned int a,unsigned int b)
140{
141    queue_t *qe;
142    queue_t *nextq;
143    int res;
144
145    qe = qb;
146
147    qe = qb->q_next;
148
149    while (qe != qb) {
150	nextq = qe->q_next;
151	if ((res = (*func)(qe,a,b))) return res;
152	qe = nextq;
153	}
154
155    return 0;
156}
157
158
159
160
161
162/*  *********************************************************************
163    *  Q_COUNT(qb)							*
164    *  									*
165    *  Counts the elements on a queue (not interlocked)			*
166    *  									*
167    *  Input Parameters: 						*
168    *      qb - queue block						*
169    *      								*
170    *  Return Value:							*
171    *      number of elements						*
172    ********************************************************************* */
173int q_count(queue_t *qb)
174{
175    queue_t *qe;
176    int res = 0;
177
178    qe = qb;
179
180    while (qe->q_next != qb) {
181	qe = qe->q_next;
182	res++;
183	}
184
185    return res;
186}
187
188
189
190
191/*  *********************************************************************
192    *  Q_FIND(qb,item)
193    *
194    *  Determines if a particular element is on a queue.
195    *
196    *  Input Parameters:
197    *      qb - queue block
198    *      item - queue element
199    *
200    *  Return Value:
201    *      0 - not on queue
202    *      >0 - position on queue
203    ********************************************************************* */
204int q_find(queue_t *qb,queue_t *item)
205{
206    queue_t *q;
207    int res = 1;
208
209    q = qb->q_next;
210
211    while (q != item) {
212	if (q == qb) return 0;
213	q = q->q_next;
214	res++;
215	}
216
217    return res;
218}
219
220