Back to index

php5  5.3.10
Functions | Variables
queue.c File Reference
#include <stdlib.h>
#include "queue.h"

Go to the source code of this file.

Functions

static void QuickSort (void *list[], int low, int high, int(*Comp)(const void *, const void *))
static int Q_BSearch (queue *q, void *key, int(*Comp)(const void *, const void *))
int Q_Init (queue *q)
int Q_AtHead (queue *q)
int Q_AtTail (queue *q)
int Q_IsEmpty (queue *q)
int Q_Size (queue *q)
void * Q_Head (queue *q)
void * Q_Tail (queue *q)
int Q_PushHead (queue *q, void *d)
int Q_PushTail (queue *q, void *d)
void * Q_PopHead (queue *q)
void * Q_PopTail (queue *q)
void * Q_Next (queue *q)
void * Q_Previous (queue *q)
void * Q_Iter_Del (queue *q, q_iter iter)
void * Q_DelCur (queue *q)
void Q_Destroy (queue *q)
void * Q_Get (queue *q)
int Q_Put (queue *q, void *data)
int Q_Find (queue *q, void *data, int(*Comp)(const void *, const void *))
int Q_Sort (queue *q, 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)

Variables

static const char rcsid [] = "#(@) $Id: queue.c 87765 2002-07-05 04:43:55Z danda $"
static void ** index
static datanode ** posn_index

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:

static int Q_BSearch ( queue q,
void *  key,
int(*)(const void *, const void *)  Comp 
) [static]

Definition at line 853 of file queue.c.

{
   int low, mid, hi, val;

   low = 0;
   hi = q->size - 1;

   while(low <= hi) {
      mid = (low + hi) / 2;
      val = Comp(key, index[ mid ]);

      if(val < 0)
         hi = mid - 1;

      else if(val > 0)
         low = mid + 1;

      else /* Success */
         return mid;
   }

   /* Not Found */

   return -1;
}

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:

static void QuickSort ( void *  list[],
int  low,
int  high,
int(*)(const void *, const void *)  Comp 
) [static]

Definition at line 715 of file queue.c.

{
   int     flag = 1, i, j;
   void    *key, *temp;

   if(low < high) {
      i = low;
      j = high + 1;

      key = list[ low ];

      while(flag) {
         i++;
         while(Comp(list[i], key) < 0)
            i++;

         j--;
         while(Comp(list[j], key) > 0)
            j--;

         if(i < j) {
            temp = list[i];
            list[i] = list[j];
            list[j] = temp;
         }
         else  flag = 0;
      }

      temp = list[low];
      list[low] = list[j];
      list[j] = temp;

      QuickSort(list, low, j-1, Comp);
      QuickSort(list, j+1, high, Comp);
   }
}

Here is the caller graph for this function:


Variable Documentation

void** index [static]

Definition at line 114 of file queue.c.

datanode** posn_index [static]

Definition at line 115 of file queue.c.

const char rcsid[] = "#(@) $Id: queue.c 87765 2002-07-05 04:43:55Z danda $" [static]

Definition at line 1 of file queue.c.