Back to index

php5  5.3.10
Classes | Defines | Typedefs | Functions
queue.h File Reference
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes

struct  nodeptr
struct  queue
struct  index_elt

Defines

#define False_   0
#define True_   1
#define Q_Iter_Head_F(q)   (q ? (q_iter)((queue*)q)->head : NULL)
#define Q_Iter_Tail_F(q)   (q ? (q_iter)((queue*)q)->tail : NULL)
#define Q_Iter_Next_F(qi)   (qi ? (q_iter)((node*)qi)->next : NULL)
#define Q_Iter_Prev_F(qi)   (qi ? (q_iter)((node*)qi)->prev : NULL)
#define Q_Iter_Get_F(qi)   (qi ? ((node*)qi)->data : NULL)

Typedefs

typedef struct nodeptr
typedef struct nodeptr node
typedef struct nodeptrq_iter

Functions

int Q_Init (queue *q)
void Q_Destroy (queue *q)
int Q_IsEmpty (queue *q)
int Q_Size (queue *q)
int Q_AtHead (queue *q)
int Q_AtTail (queue *q)
int Q_PushHead (queue *q, void *d)
int Q_PushTail (queue *q, void *d)
void * Q_Head (queue *q)
void * Q_Tail (queue *q)
void * Q_PopHead (queue *q)
void * Q_PopTail (queue *q)
void * Q_Next (queue *q)
void * Q_Previous (queue *q)
void * Q_DelCur (queue *q)
void * Q_Get (queue *q)
int Q_Put (queue *q, void *data)
int Q_Sort (queue *q, int(*Comp)(const void *, const void *))
int Q_Find (queue *q, void *data, int(*Comp)(const void *, const void *))
void * Q_Seek (queue *q, void *data, int(*Comp)(const void *, const void *))
int Q_Insert (queue *q, void *data, int(*Comp)(const void *, const void *))
q_iter Q_Iter_Head (queue *q)
q_iter Q_Iter_Tail (queue *q)
q_iter Q_Iter_Next (q_iter qi)
q_iter Q_Iter_Prev (q_iter qi)
void * Q_Iter_Get (q_iter qi)
int Q_Iter_Put (q_iter qi, void *data)
void * Q_Iter_Del (queue *q, q_iter iter)

Class Documentation

struct nodeptr

Definition at line 29 of file queue.h.

Class Members
void * data
datanode * next
datanode * prev
struct queue

Definition at line 37 of file queue.h.

Collaboration diagram for queue:
Class Members
node * cursor
node * head
int item_deleted
int size
int sorted
node * tail
struct index_elt

Definition at line 42 of file queue.h.

Collaboration diagram for index_elt:
Class Members
void * dataptr
node * loc

Define Documentation

#define False_   0

Definition at line 20 of file queue.h.

#define Q_Iter_Get_F (   qi)    (qi ? ((node*)qi)->data : NULL)

Definition at line 87 of file queue.h.

#define Q_Iter_Head_F (   q)    (q ? (q_iter)((queue*)q)->head : NULL)

Definition at line 83 of file queue.h.

#define Q_Iter_Next_F (   qi)    (qi ? (q_iter)((node*)qi)->next : NULL)

Definition at line 85 of file queue.h.

#define Q_Iter_Prev_F (   qi)    (qi ? (q_iter)((node*)qi)->prev : NULL)

Definition at line 86 of file queue.h.

#define Q_Iter_Tail_F (   q)    (q ? (q_iter)((queue*)q)->tail : NULL)

Definition at line 84 of file queue.h.

#define True_   1

Definition at line 24 of file queue.h.


Typedef Documentation

typedef struct nodeptr node
typedef struct nodeptr

Definition at line 27 of file queue.h.

typedef struct nodeptr* q_iter

Definition at line 35 of file queue.h.


Function Documentation

int Q_AtHead ( queue q)

Definition at line 157 of file queue.c.

{
   return(q && q->cursor == q->head);
}
int Q_AtTail ( queue q)

Definition at line 177 of file queue.c.

{
   return(q && q->cursor == q->tail);
}

Here is the caller graph for this function:

void* Q_DelCur ( queue q)

Definition at line 586 of file queue.c.

                         {
   if(q) {
      return Q_Iter_Del(q, (q_iter)q->cursor);
   }
   return 0;
}

Here is the call graph for this function:

void Q_Destroy ( queue q)

Definition at line 610 of file queue.c.

{
   while(!Q_IsEmpty(q)) {
      Q_PopHead(q);
   }
}

Here is the call graph for this function:

Here is the caller graph for this function:

int Q_Find ( queue q,
void *  data,
int(*)(const void *, const void *)  Comp 
)

Definition at line 690 of file queue.c.

{
   void *d;

   if (q == NULL) {
       return False_;
   }

   d = Q_Head(q);
   do {
      if(Comp(d, data) == 0)
         return True_;
      d = Q_Next(q);
   } while(!Q_AtTail(q));

   if(Comp(d, data) == 0)
      return True_;

   return False_;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void* Q_Get ( queue q)

Definition at line 632 of file queue.c.

{
   if(!q)
      return NULL;

   if(q->cursor == NULL)
      return NULL;
   return q->cursor->data;
}
void* Q_Head ( queue q)

Definition at line 236 of file queue.c.

{
   if(Q_IsEmpty(q))
      return NULL;

   q->cursor = q->head;

   return  q->cursor->data;
}

Here is the call graph for this function:

Here is the caller graph for this function:

int Q_Init ( queue q)

Definition at line 131 of file queue.c.

{
   if(q) {
      q->head = q->tail = NULL;
      q->cursor = q->head;
      q->size = 0;
      q->sorted = False_;
   }

   return True_;
}

Here is the caller graph for this function:

int Q_Insert ( queue q,
void *  data,
int(*)(const void *, const void *)  Comp 
)

Definition at line 941 of file queue.c.

{
   if (q == NULL) {
       return False_;
   }

   Q_PushHead(q, data);

   if(!Q_Sort(q, Comp))
      return False_;

   return True_;
}

Here is the call graph for this function:

int Q_IsEmpty ( queue q) [inline]

Definition at line 197 of file queue.c.

{
   return(!q || q->size == 0);
}

Here is the caller graph for this function:

void* Q_Iter_Del ( queue q,
q_iter  iter 
)

Definition at line 521 of file queue.c.

{
   void        *d;
   datanode    *n, *p;

   if(!q)
      return NULL;

   if(iter == NULL)
      return NULL;

   if(iter == (q_iter)q->head)
      return Q_PopHead(q);

   if(iter == (q_iter)q->tail)
      return Q_PopTail(q);

   n = ((node*)iter)->next;
   p = ((node*)iter)->prev;
   d = ((node*)iter)->data;

   free(iter);

   if(p) {
      p->next = n;
   }
   if (q->cursor == (node*)iter) {
      if (p) {
         q->cursor = p;
      } else {
         q->cursor = n;
      }
   }


   if (n != NULL) {
       n->prev = p;
   }

   q->size--;

   q->sorted = False_;

   return d;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void* Q_Iter_Get ( q_iter  qi)

Definition at line 972 of file queue.c.

                             {
   return qi ? ((node*)qi)->data : NULL;
}

Definition at line 956 of file queue.c.

                             {
   return q ? (q_iter)q->head : NULL;
}

Definition at line 964 of file queue.c.

                              {
   return qi ? (q_iter)((node*)qi)->next : NULL;
}

Definition at line 968 of file queue.c.

                              {
   return qi ? (q_iter)((node*)qi)->prev : NULL;
}
int Q_Iter_Put ( q_iter  qi,
void *  data 
)

Definition at line 976 of file queue.c.

                                      {
   if(qi) {
      ((node*)qi)->data = data;
      return True_;
   }
   return False_;
}

Definition at line 960 of file queue.c.

                             {
   return q ? (q_iter)q->tail : NULL;
}
void* Q_Next ( queue q)

Definition at line 477 of file queue.c.

{
   if(!q)
      return NULL;

   if(!q->cursor || q->cursor->next == NULL)
      return NULL;

   q->cursor = (node *)q->cursor->next;

   return  q->cursor->data ;
}

Here is the caller graph for this function:

void* Q_PopHead ( queue q)

Definition at line 390 of file queue.c.

{
   datanode    *n;
   void        *d;

   if(Q_IsEmpty(q))
      return NULL;

   d = q->head->data;
   n = q->head->next;
   free(q->head);

   q->size--;

   if(q->size == 0)
      q->head = q->tail = q->cursor = NULL;
   else {
      q->head = (node *)n;
      q->head->prev = NULL;
      q->cursor = q->head;
   }

   q->sorted = False_;

   return d;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void* Q_PopTail ( queue q)

Definition at line 433 of file queue.c.

{
   datanode    *p;
   void        *d;

   if(Q_IsEmpty(q))
      return NULL;

   d = q->tail->data;
   p = q->tail->prev;
   free(q->tail);
   q->size--;

   if(q->size == 0)
      q->head = q->tail = q->cursor = NULL;
   else {
      q->tail = (node *)p;
      q->tail->next = NULL;
      q->cursor = q->tail;
   }

   q->sorted = False_;

   return d;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void* Q_Previous ( queue q)

Definition at line 507 of file queue.c.

{
   if(!q)
      return NULL;
   
   if(q->cursor->prev == NULL)
      return NULL;

   q->cursor = (node *)q->cursor->prev;

   return q->cursor->data;
}
int Q_PushHead ( queue q,
void *  d 
)

Definition at line 286 of file queue.c.

{
   if(q && d) {
      node    *n;
      datanode *p;

      p = malloc(sizeof(datanode));
      if(p == NULL)
         return False_;

      n = q->head;

      q->head = (node*)p;
      q->head->prev = NULL;

      if(q->size == 0) {
         q->head->next = NULL;
         q->tail = q->head;
      }
      else {
         q->head->next = (datanode*)n;
         n->prev = q->head;
      }

      q->head->data = d;
      q->size++;

      q->cursor = q->head;

      q->sorted = False_;

      return True_;
   }
   return False_;
}

Here is the caller graph for this function:

int Q_PushTail ( queue q,
void *  d 
)

Definition at line 338 of file queue.c.

{
   if(q && d) {
      node        *p;
      datanode    *n;

      n = malloc(sizeof(datanode));
      if(n == NULL)
         return False_;

      p = q->tail;
      q->tail = (node *)n;

      if(q->size == 0) {
         q->tail->prev = NULL;
         q->head = q->tail;
      }
      else {
         q->tail->prev = (datanode *)p;
         p->next = q->tail;
      }

      q->tail->next = NULL;

      q->tail->data =  d;
      q->cursor = q->tail;
      q->size++;

      q->sorted = False_;

      return True_;
   }
   return False_;
}

Here is the caller graph for this function:

int Q_Put ( queue q,
void *  data 
)

Definition at line 658 of file queue.c.

{
   if(q && data) {
      if(q->cursor == NULL)
         return False_;

      q->cursor->data = data;
      return True_;
   }
   return False_;
}
void* Q_Seek ( queue q,
void *  data,
int(*)(const void *, const void *)  Comp 
)

Definition at line 897 of file queue.c.

{
   int idx;

   if (q == NULL) {
       return NULL;
   }

   if(!q->sorted) {
      if(!Q_Sort(q, Comp))
         return NULL;
   }

   idx = Q_BSearch(q, data, Comp);

   if(idx < 0)
      return NULL;

   q->cursor = posn_index[idx];

   return index[idx];
}

Here is the call graph for this function:

int Q_Size ( queue q)

Definition at line 216 of file queue.c.

{
   return q ? q->size : 0;
}

Here is the caller graph for this function:

int Q_Sort ( queue q,
int(*)(const void *, const void *)  Comp 
)

Definition at line 777 of file queue.c.

{
   int         i;
   void        *d;
   datanode    *dn;

   /* if already sorted free memory for tag array */

   if(q->sorted) {
      free(index);
      free(posn_index);
      q->sorted = False_;
   }

   /* Now allocate memory of array, array of pointers */

   index = malloc(q->size * sizeof(q->cursor->data));
   if(index == NULL)
      return False_;

   posn_index = malloc(q->size * sizeof(q->cursor));
   if(posn_index == NULL) {
      free(index);
      return False_;
   }

   /* Walk queue putting pointers into array */

   d = Q_Head(q);
   for(i=0; i < q->size; i++) {
      index[i] = d;
      posn_index[i] = q->cursor;
      d = Q_Next(q);
   }

   /* Now sort the index */

   QuickSort(index, 0, q->size - 1, Comp);

   /* Rearrange the actual queue into correct order */

   dn = q->head;
   i = 0;
   while(dn != NULL) {
      dn->data = index[i++];
      dn = dn->next;
   }

   /* Re-position to original element */

   if(d != NULL)
      Q_Find(q, d, Comp);
   else  Q_Head(q);

   q->sorted = True_;

   return True_;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void* Q_Tail ( queue q)

Definition at line 261 of file queue.c.

{
   if(Q_IsEmpty(q))
      return NULL;

   q->cursor = q->tail;

   return  q->cursor->data;
}

Here is the call graph for this function: