home *** CD-ROM | disk | FTP | other *** search
/ Chip 2001 January / Chip_2001-01_cd1.bin / tema / mysql / mysql-3.23.28g-win-source.exe / mysys / queues.c < prev    next >
C/C++ Source or Header  |  2000-09-14  |  4KB  |  169 lines
  1. /* Copyright (C) 2000 MySQL AB & MySQL Finland AB & TCX DataKonsult AB
  2.    
  3.    This library is free software; you can redistribute it and/or
  4.    modify it under the terms of the GNU Library General Public
  5.    License as published by the Free Software Foundation; either
  6.    version 2 of the License, or (at your option) any later version.
  7.    
  8.    This library is distributed in the hope that it will be useful,
  9.    but WITHOUT ANY WARRANTY; without even the implied warranty of
  10.    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  11.    Library General Public License for more details.
  12.    
  13.    You should have received a copy of the GNU Library General Public
  14.    License along with this library; if not, write to the Free
  15.    Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  16.    MA 02111-1307, USA */
  17.  
  18. /*
  19.   Code for generell handling of priority Queues.
  20.   Implemention of queues from "Algoritms in C" by Robert Sedgewick.
  21. */
  22.  
  23. #include "mysys_priv.h"
  24. #include "mysys_err.h"
  25. #include <queues.h>
  26.  
  27.  
  28. /* Init queue */
  29.  
  30. int init_queue(QUEUE *queue, uint max_elements, uint offset_to_key,
  31.            pbool max_at_top, int (*compare) (void *, byte *, byte *),
  32.            void *first_cmp_arg)
  33. {
  34.   DBUG_ENTER("init_queue");
  35.   if ((queue->root= (byte **) my_malloc((max_elements+1)*sizeof(void*),
  36.                      MYF(MY_WME))) == 0)
  37.     DBUG_RETURN(1);
  38.   queue->elements=0;
  39.   queue->compare=compare;
  40.   queue->first_cmp_arg=first_cmp_arg;
  41.   queue->max_elements=max_elements;
  42.   queue->offset_to_key=offset_to_key;
  43.   queue->max_at_top= max_at_top ? (-1 ^ 1) : 0;
  44.   DBUG_RETURN(0);
  45. }
  46.  
  47. /*
  48.   Reinitialize queue for new usage;  Note that you can't currently resize
  49.   the number of elements!  If you need this, fix it :)
  50. */
  51.  
  52.  
  53. int reinit_queue(QUEUE *queue, uint max_elements, uint offset_to_key,
  54.                pbool max_at_top, int (*compare) (void *, byte *, byte *),
  55.                void *first_cmp_arg)
  56. {
  57.   DBUG_ENTER("reinit_queue");
  58.   if (queue->max_elements < max_elements)
  59.     /* It's real easy to do realloc here, just don't want to bother */
  60.     DBUG_RETURN(my_errno=EE_OUTOFMEMORY);
  61.  
  62.   queue->elements=0;
  63.   queue->compare=compare;
  64.   queue->first_cmp_arg=first_cmp_arg;
  65.   queue->offset_to_key=offset_to_key;
  66.   queue->max_at_top= max_at_top ? (-1 ^ 1) : 0;
  67.   DBUG_RETURN(0);
  68. }
  69.  
  70. void delete_queue(QUEUE *queue)
  71. {
  72.   DBUG_ENTER("delete_queue");
  73.   if (queue->root)
  74.   {
  75.     my_free((gptr) queue->root,MYF(0));
  76.     queue->root=0;
  77.   }
  78.   DBUG_VOID_RETURN;
  79. }
  80.  
  81.  
  82.     /* Code for insert, search and delete of elements */
  83.  
  84. void queue_insert(register QUEUE *queue, byte *element)
  85. {
  86.   reg2 uint idx,next;
  87.   int cmp;
  88.  
  89. #ifndef DBUG_OFF
  90.   if (queue->elements < queue->max_elements)
  91. #endif
  92.   {
  93.     queue->root[0]=element;
  94.     idx= ++queue->elements;
  95.  
  96.     /* max_at_top swaps the comparison if we want to order by desc */
  97.     while ((cmp=queue->compare(queue->first_cmp_arg,
  98.                    element+queue->offset_to_key,
  99.                    queue->root[(next=idx >> 1)] +
  100.                    queue->offset_to_key)) &&
  101.        (cmp ^ queue->max_at_top) < 0)
  102.     {
  103.       queue->root[idx]=queue->root[next];
  104.       idx=next;
  105.     }
  106.     queue->root[idx]=element;
  107.   }
  108. }
  109.  
  110.     /* Remove item from queue */
  111.     /* Returns pointer to removed element */
  112.  
  113. byte *queue_remove(register QUEUE *queue, uint idx)
  114. {
  115. #ifndef DBUG_OFF
  116.   if (idx >= queue->max_elements)
  117.     return 0;
  118. #endif
  119.   {
  120.     byte *element=queue->root[++idx];        /* Intern index starts from 1 */
  121.     queue->root[idx]=queue->root[queue->elements--];
  122.     _downheap(queue,idx);
  123.     return element;
  124.   }
  125. }
  126.  
  127.  
  128.     /* Fix when element on top has been replaced */
  129.  
  130. #ifndef queue_replaced
  131. void queue_replaced(queue)
  132. QUEUE *queue;
  133. {
  134.   _downheap(queue,1);
  135. }
  136. #endif
  137.  
  138.     /* Fix heap when index have changed */
  139.  
  140. void _downheap(register QUEUE *queue, uint idx)
  141. {
  142.   byte *element;
  143.   uint elements,half_queue,next_index,offset_to_key;
  144.   int cmp;
  145.  
  146.   offset_to_key=queue->offset_to_key;
  147.   element=queue->root[idx];
  148.   half_queue=(elements=queue->elements) >> 1;
  149.  
  150.   while (idx <= half_queue)
  151.   {
  152.     next_index=idx+idx;
  153.     if (next_index < elements &&
  154.     (queue->compare(queue->first_cmp_arg,
  155.             queue->root[next_index]+offset_to_key,
  156.             queue->root[next_index+1]+offset_to_key) ^
  157.      queue->max_at_top) > 0)
  158.       next_index++;
  159.     if ((cmp=queue->compare(queue->first_cmp_arg,
  160.                 queue->root[next_index]+offset_to_key,
  161.                 element+offset_to_key)) == 0 ||
  162.     (cmp ^ queue->max_at_top) > 0)
  163.       break;
  164.     queue->root[idx]=queue->root[next_index];
  165.     idx=next_index;
  166.   }
  167.   queue->root[idx]=element;
  168. }
  169.