1 /*====================================================================* 2 - Copyright (C) 2001 Leptonica. All rights reserved. 3 - This software is distributed in the hope that it will be 4 - useful, but with NO WARRANTY OF ANY KIND. 5 - No author or distributor accepts responsibility to anyone for the 6 - consequences of using this software, or for whether it serves any 7 - particular purpose or works at all, unless he or she says so in 8 - writing. Everyone is granted permission to copy, modify and 9 - redistribute this source code, for commercial or non-commercial 10 - purposes, with the following restrictions: (1) the origin of this 11 - source code must not be misrepresented; (2) modified versions must 12 - be plainly marked as such; and (3) this notice may not be removed 13 - or altered from any source or modified source distribution. 14 *====================================================================*/ 15 16 #ifndef LEPTONICA_QUEUE_H 17 #define LEPTONICA_QUEUE_H 18 19 /* 20 * queue.h 21 * 22 * Expandable pointer queue for arbitrary void* data. 23 * 24 * The L_Queue is a fifo that implements a queue of void* pointers. 25 * It can be used to hold a queue of any type of struct. 26 * 27 * Internally, it maintains two counters: 28 * nhead: location of head (in ptrs) from the beginning 29 * of the array. 30 * nelem: number of ptr elements stored in the queue. 31 * 32 * The element at the head of the queue, which is the next to 33 * be removed, is array[nhead]. The location at the tail of the 34 * queue to which the next element will be added is 35 * array[nhead + nelem]. 36 * 37 * As items are added to the queue, nelem increases. 38 * As items are removed, nhead increases and nelem decreases. 39 * Any time the tail reaches the end of the allocated array, 40 * all the pointers are shifted to the left, so that the head 41 * is at the beginning of the array. 42 * If the array becomes more than 3/4 full, it doubles in size. 43 * 44 * The auxiliary stack can be used in a wrapper for re-using 45 * items popped from the queue. It is not made by default. 46 * 47 * For further implementation details, see queue.c. 48 */ 49 50 struct L_Queue 51 { 52 l_int32 nalloc; /* size of allocated ptr array */ 53 l_int32 nhead; /* location of head (in ptrs) from the */ 54 /* beginning of the array */ 55 l_int32 nelem; /* number of elements stored in the queue */ 56 void **array; /* ptr array */ 57 struct L_Stack *stack; /* auxiliary stack */ 58 59 }; 60 typedef struct L_Queue L_QUEUE; 61 62 63 #endif /* LEPTONICA_QUEUE_H */ 64