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