queue.c

PHP v6.0 For Linux 运行环境：Win9X/ WinME/ WinNT/ Win2K/ WinXP

 *
 ** function    : Q_Previous
 *
 ** purpose     : Opposite of Q_Next. Move to next element closer to the
 *                head of the queue.
 *
 ** parameters  : pointer to queue
 *
 ** returns     : pointer to data of new element else NULL if queue IsEmpty
 *
 ** comments    : Makes cursor move towards the head of the queue.
 *
 ***/

void *Q_Previous(queue *q)
{
   if(!q)
      return NULL;
   
   if(q->cursor->prev == NULL)
      return NULL;

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

   return q->cursor->data;
}


void *Q_Iter_Del(queue *q, q_iter iter)
{
   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;
}



/***
 *
 ** function    : Q_DelCur
 *
 ** purpose     : Delete the current queue element as pointed to by
 *                the cursor.
 *
 ** parameters  : queue pointer
 *
 ** returns     : pointer to data element.
 *
 ** comments    : WARNING! It is the responsibility of the caller to
 *                free any memory. Queue cannot distinguish between
 *                pointers to literals and malloced memory.
 *
 ***/

void *Q_DelCur(queue* q) {
   if(q) {
      return Q_Iter_Del(q, (q_iter)q->cursor);
   }
   return 0;
}


/***
 *
 ** function    : Q_Destroy
 *
 ** purpose     : Free all queue resources
 *
 ** parameters  : queue pointer
 *
 ** returns     : null.
 *
 ** comments    : WARNING! It is the responsibility of the caller to
 *                free any memory. Queue cannot distinguish between
 *                pointers to literals and malloced memory.
 *
 ***/

void Q_Destroy(queue *q)
{
   while(!Q_IsEmpty(q)) {
      Q_PopHead(q);
   }
}


/***
 *
 ** function    : Q_Get
 *
 ** purpose     : get the pointer to the data at the cursor location
 *
 ** parameters  : queue pointer
 *
 ** returns     : data element pointer
 *
 ** comments    :
 *
 ***/

void *Q_Get(queue *q)
{
   if(!q)
      return NULL;

   if(q->cursor == NULL)
      return NULL;
   return q->cursor->data;
}



/***
 *
 ** function    : Q_Put
 *
 ** purpose     : replace pointer to data with new pointer to data.
 *
 ** parameters  : queue pointer, data pointer
 *
 ** returns     : boolean- True_ if successful, False_ if cursor at NULL
 *
 ** comments    :
 *
 ***/

int Q_Put(queue *q, void *data)
{
   if(q && data) {
      if(q->cursor == NULL)
         return False_;

      q->cursor->data = data;
      return True_;
   }
   return False_;
}


/***
 *
 ** function    : Q_Find
 *
 ** purpose     : Linear search of queue for match with key in *data
 *
 ** parameters  : queue pointer q, data pointer with data containing key
 *                comparison function here called Comp.
 *
 ** returns     : True_ if found , False_ if not in queue.
 *
 ** comments    : Useful for small queues that are constantly changing
 *                and would otherwise need constant sorting with the
 *                Q_Seek function.
 *                For description of Comp see Q_Sort.
 *                Queue cursor left on position found item else at end.
 *
 ***/

int Q_Find(queue *q, void *data,
           int (*Comp)(const void *, const void *))
{
   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_;
}

/*========  Sorted Queue and Index functions   ========= */


static void QuickSort(void *list[], int low, int high,
                      int (*Comp)(const void *, const void *))
{
   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);
   }
}


/***
 *
 ** function    : Q_Sort
 *
 ** purpose     : sort the queue and allow index style access.
 *
 ** parameters  : queue pointer, comparison function compatible with
 *                with 'qsort'.
 *
 ** returns     : True_ if sort succeeded. False_ if error occurred.
 *
 ** comments    : Comp function supplied by caller must return
 *                  -1 if data1  < data2
 *                   0 if data1 == data2
 *                  +1 if data1  > data2
 *
 *                    for Comp(data1, data2)
 *
 *                If queue is already sorted it frees the memory of the
 *                old index and starts again.
 *
 ***/

int Q_Sort(queue *q, int (*Comp)(const void *, const void *))
{
   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_;
}


/***
 *
 ** function    : Q_BSearch
 *
 ** purpose     : binary search of queue index for node containing key
 *
 ** parameters  : queue pointer 'q', data pointer of key 'key',
 *                  Comp comparison function.
 *
 ** returns     : integer index into array of node pointers,
 *                or -1 if not found.
 *
 ** comments    : see Q_Sort for description of 'Comp' function.
 *
 ***/

static int Q_BSearch( queue *q, void *key,
                      int (*Comp)(const void *, const void*))
{
   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;
}


/***
 *
 ** function    : Q_Seek
 *
 ** purpose     : use index to locate data according to key in 'data'
 *
 ** parameters  : queue pointer 'q', data pointer 'data', Comp comparison
 *                function.
 *
 ** returns     : pointer to data or NULL if could not find it or could
 *                not sort queue.
 *
 ** comments    : see Q_Sort for description of 'Comp' function.
 *
 ***/

void *Q_Seek(queue *q, void *data, int (*Comp)(const void *, const void *))
{
   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];
}



/***
 *
 ** function    : Q_Insert
 *
 ** purpose     : Insert an element into an indexed queue
 *
 ** parameters  : queue pointer 'q', data pointer 'data', Comp comparison
 *                function.
 *
 ** returns     : pointer to data or NULL if could not find it or could
 *                not sort queue.
 *
 ** comments    : see Q_Sort for description of 'Comp' function.
 *                WARNING! This code can be very slow since each new
 *                element means a new Q_Sort.  Should only be used for
 *                the insertion of the odd element ,not the piecemeal
 *                building of an entire queue.
 ***/

int Q_Insert(queue *q, void *data, int (*Comp)(const void *, const void *))
{
   if (q == NULL) {
	return False_;
   }

   Q_PushHead(q, data);

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

   return True_;
}

/* read only funcs for iterating through queue. above funcs modify queue */
q_iter Q_Iter_Head(queue *q) {
   return q ? (q_iter)q->head : NULL;
}

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

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

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

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

int Q_Iter_Put(q_iter qi, void* data) {
   if(qi) {
      ((node*)qi)->data = data;
      return True_;
   }
   return False_;
}