Leptonica  1.82.0
Image processing and image analysis suite
queue.c File Reference
#include <string.h>
#include "allheaders.h"

Go to the source code of this file.

Functions

static l_int32 lqueueExtendArray (L_QUEUE *lq)
 
L_QUEUElqueueCreate (l_int32 nalloc)
 
void lqueueDestroy (L_QUEUE **plq, l_int32 freeflag)
 
l_ok lqueueAdd (L_QUEUE *lq, void *item)
 
void * lqueueRemove (L_QUEUE *lq)
 
l_int32 lqueueGetCount (L_QUEUE *lq)
 
l_ok lqueuePrint (FILE *fp, L_QUEUE *lq)
 

Variables

static const l_int32 MIN_BUFFER_SIZE = 20
 
static const l_int32 INITIAL_BUFFER_ARRAYSIZE = 1024
 

Detailed Description

     Create/Destroy L_Queue
         L_QUEUE        *lqueueCreate()
         void           *lqueueDestroy()
     Operations to add/remove to/from a L_Queue
         l_int32         lqueueAdd()
         static l_int32  lqueueExtendArray()
         void           *lqueueRemove()
     Accessors
         l_int32         lqueueGetCount()
     Debug output
         l_int32         lqueuePrint()
   The lqueue is a fifo that implements a queue of void* pointers.
   It can be used to hold a queue of any type of struct.
   Internally, it maintains two counters:
       nhead:  location of head (in ptrs) from the beginning
               of the buffer
       nelem:  number of ptr elements stored in the queue
   As items are added to the queue, nelem increases.
   As items are removed, nhead increases and nelem decreases.
   Any time the tail reaches the end of the allocated buffer,
     all the pointers are shifted to the left, so that the head
     is at the beginning of the array.
   If the buffer becomes more than 3/4 full, it doubles in size.
   [A circular queue would allow us to skip the shifting and
   to resize only when the buffer is full.  For most applications,
   the extra work we do for a linear queue is not significant.]

Definition in file queue.c.

Function Documentation

◆ lqueueAdd()

l_ok lqueueAdd ( L_QUEUE lq,
void *  item 
)

lqueueAdd()

Parameters
[in]lqlqueue
[in]itemto be added to the tail of the queue
Returns
0 if OK, 1 on error
Notes:
     (1) The algorithm is as follows.  If the queue is populated
         to the end of the allocated array, shift all ptrs toward
         the beginning of the array, so that the head of the queue
         is at the beginning of the array.  Then, if the array is
         more than 0.75 full, realloc with double the array size.
         Finally, add the item to the tail of the queue.

Definition at line 188 of file queue.c.

References L_Queue::array, lqueueExtendArray(), L_Queue::nalloc, L_Queue::nelem, and L_Queue::nhead.

Referenced by seedfillGrayInvLow(), and seedfillGrayLow().

◆ lqueueCreate()

L_QUEUE* lqueueCreate ( l_int32  nalloc)

lqueueCreate()

Parameters
[in]nallocsize of ptr array to be alloc'd; 0 for default
Returns
lqueue, or NULL on error
Notes:
     (1) Allocates a ptr array of given size, and initializes counters.

Definition at line 93 of file queue.c.

References L_Ptraa::nalloc.

Referenced by identifyWatershedBasin(), pixSearchBinaryMaze(), seedfillGrayInvLow(), and seedfillGrayLow().

◆ lqueueDestroy()

void lqueueDestroy ( L_QUEUE **  plq,
l_int32  freeflag 
)

lqueueDestroy()

Parameters
[in,out]plqwill be set to null before returning
[in]freeflagTRUE to free each remaining struct in the array
Returns
void
Notes:
     (1) If freeflag is TRUE, frees each struct in the array.
     (2) If freeflag is FALSE but there are elements on the array,
         gives a warning and destroys the array.  This will
         cause a memory leak of all the items that were on the queue.
         So if the items require their own destroy function, they
         must be destroyed before the queue.  The same applies to the
         auxiliary stack, if it is used.
     (3) To destroy the L_Queue, we destroy the ptr array, then
         the lqueue, and then null the contents of the input ptr.

Definition at line 134 of file queue.c.

References L_Queue::array, lqueueRemove(), lstackDestroy(), L_Queue::nelem, and L_Queue::stack.

Referenced by seedfillGrayInvLow(), and seedfillGrayLow().

◆ lqueueExtendArray()

static l_int32 lqueueExtendArray ( L_QUEUE lq)
static

lqueueExtendArray()

Parameters
[in]lqlqueue
Returns
0 if OK, 1 on error

Definition at line 226 of file queue.c.

References L_Queue::array, L_Queue::nalloc, and reallocNew().

Referenced by lqueueAdd().

◆ lqueueGetCount()

l_int32 lqueueGetCount ( L_QUEUE lq)

lqueueGetCount()

Parameters
[in]lqlqueue
Returns
count, or 0 on error

Definition at line 286 of file queue.c.

References L_Queue::nelem.

Referenced by seedfillGrayInvLow(), and seedfillGrayLow().

◆ lqueuePrint()

l_ok lqueuePrint ( FILE *  fp,
L_QUEUE lq 
)

lqueuePrint()

Parameters
[in]fpfile stream
[in]lqlqueue
Returns
0 if OK; 1 on error

Definition at line 308 of file queue.c.

References L_Queue::array, L_Queue::nalloc, L_Queue::nelem, and L_Queue::nhead.

◆ lqueueRemove()

void* lqueueRemove ( L_QUEUE lq)

lqueueRemove()

Parameters
[in]lqlqueue
Returns
ptr to item popped from the head of the queue, or NULL if the queue is empty or on error
Notes:
     (1) If this is the last item on the queue, so that the queue
         becomes empty, nhead is reset to the beginning of the array.

Definition at line 257 of file queue.c.

References L_Queue::array, L_Queue::nelem, and L_Queue::nhead.

Referenced by lqueueDestroy(), seedfillGrayInvLow(), and seedfillGrayLow().