1 2/******************************************************************************/ 3/* */ 4/* Broadcom BCM4400 Linux Network Driver, Copyright (c) 2002 Broadcom */ 5/* Corporation. */ 6/* All rights reserved. */ 7/* */ 8/* This program is free software; you can redistribute it and/or modify */ 9/* it under the terms of the GNU General Public License as published by */ 10/* the Free Software Foundation, located in the file LICENSE. */ 11/* */ 12/* Queue functions. */ 13/* void QQ_InitQueue(PQQ_CONTAINER pQueue) */ 14/* char QQ_Full(PQQ_CONTAINER pQueue) */ 15/* char QQ_Empty(PQQ_CONTAINER pQueue) */ 16/* unsigned int QQ_GetSize(PQQ_CONTAINER pQueue) */ 17/* unsigned int QQ_GetEntryCnt(PQQ_CONTAINER pQueue) */ 18/* char QQ_PushHead(PQQ_CONTAINER pQueue, PQQ_ENTRY pEntry) */ 19/* char QQ_PushTail(PQQ_CONTAINER pQueue, PQQ_ENTRY pEntry) */ 20/* PQQ_ENTRY QQ_PopHead(PQQ_CONTAINER pQueue) */ 21/* PQQ_ENTRY QQ_PopTail(PQQ_CONTAINER pQueue) */ 22/* PQQ_ENTRY QQ_GetHead(PQQ_CONTAINER pQueue, unsigned int Idx) */ 23/* PQQ_ENTRY QQ_GetTail(PQQ_CONTAINER pQueue, unsigned int Idx) */ 24/* */ 25/* */ 26/* History: */ 27/* 02/25/00 Hav Khauv Initial version. */ 28/******************************************************************************/ 29 30#ifndef BCM_QUEUE_H 31#define BCM_QUEUE_H 32 33 34 35/******************************************************************************/ 36/* Queue definitions. */ 37/******************************************************************************/ 38 39/* Entry for queueing. */ 40typedef void *PQQ_ENTRY; 41 42 43/* Queue header -- base type. */ 44typedef struct { 45 unsigned int Head; 46 unsigned int Tail; 47 unsigned int Size; 48 MM_ATOMIC_T EntryCnt; 49 PQQ_ENTRY Array[1]; 50} QQ_CONTAINER, *PQQ_CONTAINER; 51 52 53/* Declare queue type macro. */ 54#define DECLARE_QUEUE_TYPE(_QUEUE_TYPE, _QUEUE_SIZE) \ 55 \ 56 typedef struct { \ 57 QQ_CONTAINER Container; \ 58 PQQ_ENTRY EntryBuffer[_QUEUE_SIZE]; \ 59 } _QUEUE_TYPE, *P##_QUEUE_TYPE 60 61 62 63/******************************************************************************/ 64/* Compilation switches. */ 65/******************************************************************************/ 66 67#if DBG 68#undef QQ_NO_OVERFLOW_CHECK 69#undef QQ_NO_UNDERFLOW_CHECK 70#endif /* DBG */ 71 72#ifdef QQ_USE_MACROS 73/* notdone */ 74#else 75 76#ifdef QQ_NO_INLINE 77#define __inline 78#endif /* QQ_NO_INLINE */ 79 80 81 82/******************************************************************************/ 83/* Description: */ 84/* */ 85/* Return: */ 86/******************************************************************************/ 87__inline static void 88QQ_InitQueue( 89PQQ_CONTAINER pQueue, 90unsigned int QueueSize) { 91 pQueue->Head = 0; 92 pQueue->Tail = 0; 93 pQueue->Size = QueueSize+1; 94 MM_ATOMIC_SET(&pQueue->EntryCnt, 0); 95} /* QQ_InitQueue */ 96 97 98 99/******************************************************************************/ 100/* Description: */ 101/* */ 102/* Return: */ 103/******************************************************************************/ 104__inline static char 105QQ_Full( 106PQQ_CONTAINER pQueue) { 107 unsigned int NewHead; 108 109 NewHead = (pQueue->Head + 1) % pQueue->Size; 110 111 return(NewHead == pQueue->Tail); 112} /* QQ_Full */ 113 114 115 116/******************************************************************************/ 117/* Description: */ 118/* */ 119/* Return: */ 120/******************************************************************************/ 121__inline static char 122QQ_Empty( 123PQQ_CONTAINER pQueue) { 124 return(pQueue->Head == pQueue->Tail); 125} /* QQ_Empty */ 126 127 128 129/******************************************************************************/ 130/* Description: */ 131/* */ 132/* Return: */ 133/******************************************************************************/ 134__inline static unsigned int 135QQ_GetSize( 136PQQ_CONTAINER pQueue) { 137 return pQueue->Size; 138} /* QQ_GetSize */ 139 140 141 142/******************************************************************************/ 143/* Description: */ 144/* */ 145/* Return: */ 146/******************************************************************************/ 147__inline static unsigned int 148QQ_GetEntryCnt( 149PQQ_CONTAINER pQueue) { 150 return MM_ATOMIC_READ(&pQueue->EntryCnt); 151} /* QQ_GetEntryCnt */ 152 153 154 155/******************************************************************************/ 156/* Description: */ 157/* */ 158/* Return: */ 159/* TRUE entry was added successfully. */ 160/* FALSE queue is full. */ 161/******************************************************************************/ 162__inline static char 163QQ_PushHead( 164PQQ_CONTAINER pQueue, 165PQQ_ENTRY pEntry) { 166 unsigned int Head; 167 168 Head = (pQueue->Head + 1) % pQueue->Size; 169 170#if !defined(QQ_NO_OVERFLOW_CHECK) 171 if(Head == pQueue->Tail) { 172 return 0; 173 } /* if */ 174#endif /* QQ_NO_OVERFLOW_CHECK */ 175 176 pQueue->Array[pQueue->Head] = pEntry; 177 MM_WMB(); 178 pQueue->Head = Head; 179 MM_ATOMIC_INC(&pQueue->EntryCnt); 180 181 return -1; 182} /* QQ_PushHead */ 183 184 185 186/******************************************************************************/ 187/* Description: */ 188/* */ 189/* Return: */ 190/* TRUE entry was added successfully. */ 191/* FALSE queue is full. */ 192/******************************************************************************/ 193__inline static char 194QQ_PushTail( 195PQQ_CONTAINER pQueue, 196PQQ_ENTRY pEntry) { 197 unsigned int Tail; 198 199 Tail = pQueue->Tail; 200 if(Tail == 0) { 201 Tail = pQueue->Size; 202 } /* if */ 203 Tail--; 204 205#if !defined(QQ_NO_OVERFLOW_CHECK) 206 if(Tail == pQueue->Head) { 207 return 0; 208 } /* if */ 209#endif /* QQ_NO_OVERFLOW_CHECK */ 210 211 pQueue->Array[Tail] = pEntry; 212 MM_WMB(); 213 pQueue->Tail = Tail; 214 MM_ATOMIC_INC(&pQueue->EntryCnt); 215 216 return -1; 217} /* QQ_PushTail */ 218 219 220 221/******************************************************************************/ 222/* Description: */ 223/* */ 224/* Return: */ 225/******************************************************************************/ 226__inline static PQQ_ENTRY 227QQ_PopHead( 228PQQ_CONTAINER pQueue) { 229 unsigned int Head; 230 PQQ_ENTRY Entry; 231 232 Head = pQueue->Head; 233 234#if !defined(QQ_NO_UNDERFLOW_CHECK) 235 if(Head == pQueue->Tail) { 236 return (PQQ_ENTRY) 0; 237 } /* if */ 238#endif /* QQ_NO_UNDERFLOW_CHECK */ 239 240 if(Head == 0) { 241 Head = pQueue->Size; 242 } /* if */ 243 Head--; 244 245 Entry = pQueue->Array[Head]; 246 MM_MB(); 247 pQueue->Head = Head; 248 MM_ATOMIC_DEC(&pQueue->EntryCnt); 249 250 return Entry; 251} /* QQ_PopHead */ 252 253 254 255/******************************************************************************/ 256/* Description: */ 257/* */ 258/* Return: */ 259/******************************************************************************/ 260__inline static PQQ_ENTRY 261QQ_PopTail( 262PQQ_CONTAINER pQueue) { 263 unsigned int Tail; 264 PQQ_ENTRY Entry; 265 266 Tail = pQueue->Tail; 267 268#if !defined(QQ_NO_UNDERFLOW_CHECK) 269 if(Tail == pQueue->Head) { 270 return (PQQ_ENTRY) 0; 271 } /* if */ 272#endif /* QQ_NO_UNDERFLOW_CHECK */ 273 274 Entry = pQueue->Array[Tail]; 275 MM_MB(); 276 pQueue->Tail = (Tail + 1) % pQueue->Size; 277 MM_ATOMIC_DEC(&pQueue->EntryCnt); 278 279 return Entry; 280} /* QQ_PopTail */ 281 282 283 284/******************************************************************************/ 285/* Description: */ 286/* */ 287/* Return: */ 288/******************************************************************************/ 289__inline static PQQ_ENTRY 290QQ_GetHead( 291 PQQ_CONTAINER pQueue, 292 unsigned int Idx) 293{ 294 if(Idx >= MM_ATOMIC_READ(&pQueue->EntryCnt)) 295 { 296 return (PQQ_ENTRY) 0; 297 } 298 299 if(pQueue->Head > Idx) 300 { 301 Idx = pQueue->Head - Idx; 302 } 303 else 304 { 305 Idx = pQueue->Size - (Idx - pQueue->Head); 306 } 307 Idx--; 308 309 return pQueue->Array[Idx]; 310} 311 312 313 314/******************************************************************************/ 315/* Description: */ 316/* */ 317/* Return: */ 318/******************************************************************************/ 319__inline static PQQ_ENTRY 320QQ_GetTail( 321 PQQ_CONTAINER pQueue, 322 unsigned int Idx) 323{ 324 if(Idx >= MM_ATOMIC_READ(&pQueue->EntryCnt)) 325 { 326 return (PQQ_ENTRY) 0; 327 } 328 329 Idx += pQueue->Tail; 330 if(Idx >= pQueue->Size) 331 { 332 Idx = Idx - pQueue->Size; 333 } 334 335 return pQueue->Array[Idx]; 336} 337 338#endif /* QQ_USE_MACROS */ 339 340 341 342#endif /* QUEUE_H */ 343