summaryrefslogtreecommitdiffstats
path: root/mysys/queues.c
blob: 0a1149bf9fc64b6c27930dc1fb957dceaf21905a (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
/* Copyright (C) 2010 Monty Program Ab
   All Rights reserved

   Redistribution and use in source and binary forms, with or without
   modification, are permitted provided that the following conditions are met:
    * Redistributions of source code must retain the above copyright
      notice, this list of conditions and the following disclaimer.
    * Redistributions in binary form must reproduce the following disclaimer
      in the documentation and/or other materials provided with the
      distribution.

  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
  <COPYRIGHT HOLDER> BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
  USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
  ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
  OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  SUCH DAMAGE.
*/

/*
  This code originates from the Unireg project.

  Code for generell handling of priority Queues.
  Implementation of queues from "Algorithms in C" by Robert Sedgewick.

  The queue can optionally store the position in queue in the element
  that is in the queue. This allows one to remove any element from the queue
  in O(1) time.

  Optimisation of _downheap() and queue_fix() is inspired by code done
  by Mikael Ronström, based on an optimisation of _downheap from
  Exercise 7.51 in "Data Structures & Algorithms in C++" by Mark Allen
  Weiss, Second Edition.
*/

#include "mysys_priv.h"
#include "mysys_err.h"
#include <queues.h>


/*
  Init queue

  SYNOPSIS
    init_queue()
    queue		Queue to initialise
    max_elements	Max elements that will be put in queue
    offset_to_key	Offset to key in element stored in queue
			Used when sending pointers to compare function
    max_at_top		Set to 1 if you want biggest element on top.
    compare		Compare function for elements, takes 3 arguments.
    first_cmp_arg	First argument to compare function
    offset_to_queue_pos If <> 0, then offset+1 in element to store position
                        in queue (for fast delete of element in queue)
    auto_extent         When the queue is full and there is insert operation
                        extend the queue.

  NOTES
    Will allocate max_element pointers for queue array

  RETURN
    0	ok
    1	Could not allocate memory
*/

int init_queue(QUEUE *queue, uint max_elements, uint offset_to_key,
	       my_bool max_at_top, int (*compare) (void *, uchar *, uchar *),
	       void *first_cmp_arg, uint offset_to_queue_pos,
               uint auto_extent)
{
  DBUG_ENTER("init_queue");
  if ((queue->root= (uchar **) my_malloc(key_memory_QUEUE,
                                         (max_elements + 1) * sizeof(void*),
					 MYF(MY_WME))) == 0)
    DBUG_RETURN(1);
  queue->elements=      	0;
  queue->compare=       	compare;
  queue->first_cmp_arg= 	first_cmp_arg;
  queue->max_elements=  	max_elements;
  queue->offset_to_key= 	offset_to_key;
  queue->offset_to_queue_pos=   offset_to_queue_pos;
  queue->auto_extent=   	auto_extent;
  queue_set_max_at_top(queue, max_at_top);
  DBUG_RETURN(0);
}


/*
  Reinitialize queue for other usage

  SYNOPSIS
    reinit_queue()
    queue		Queue to initialise
    For rest of arguments, see init_queue() above

  NOTES
    This will delete all elements from the queue.  If you don't want this,
    use resize_queue() instead.

  RETURN
    0			ok
    1			Wrong max_elements; Queue has old size
*/

int reinit_queue(QUEUE *queue, uint max_elements, uint offset_to_key,
		 my_bool max_at_top, int (*compare) (void *, uchar *, uchar *),
		 void *first_cmp_arg, uint offset_to_queue_pos,
                 uint auto_extent)
{
  DBUG_ENTER("reinit_queue");
  queue->elements=		0;
  queue->compare=		compare;
  queue->first_cmp_arg=		first_cmp_arg;
  queue->offset_to_key=		offset_to_key;
  queue->offset_to_queue_pos=   offset_to_queue_pos;
  queue->auto_extent= 		auto_extent;
  queue_set_max_at_top(queue, max_at_top);
  DBUG_RETURN(resize_queue(queue, max_elements));
}


/*
  Resize queue

  SYNOPSIS
    resize_queue()
    queue			Queue
    max_elements		New max size for queue

  NOTES
    If you resize queue to be less than the elements you have in it,
    the extra elements will be deleted

  RETURN
    0	ok
    1	Error.  In this case the queue is unchanged
*/

int resize_queue(QUEUE *queue, uint max_elements)
{
  uchar **new_root;
  DBUG_ENTER("resize_queue");
  if (queue->max_elements == max_elements)
    DBUG_RETURN(0);
  if ((new_root= (uchar **) my_realloc(key_memory_QUEUE, (void *)queue->root,
                                       (max_elements + 1)* sizeof(void*),
                                       MYF(MY_WME))) == 0)
    DBUG_RETURN(1);
  set_if_smaller(queue->elements, max_elements);
  queue->max_elements= max_elements;
  queue->root= new_root;
  DBUG_RETURN(0);
}


/*
  Delete queue

  SYNOPSIS
   delete_queue()
   queue		Queue to delete

  IMPLEMENTATION
    Just free allocated memory.

  NOTES
    Can be called safely multiple times
*/

void delete_queue(QUEUE *queue)
{
  DBUG_ENTER("delete_queue");
  my_free(queue->root);
  queue->root=0;                              /* Allow multiple calls */
  DBUG_VOID_RETURN;
}


static void insert_at(QUEUE *queue, uchar *element, uint idx)
{
  uint next_index, offset_to_key= queue->offset_to_key;
  uint offset_to_queue_pos= queue->offset_to_queue_pos;
  /* max_at_top swaps the comparison if we want to order by desc */
  while ((next_index= idx >> 1) > 0 &&
          queue->compare(queue->first_cmp_arg,
                         element + offset_to_key,
                         queue->root[next_index] + offset_to_key) *
          queue->max_at_top < 0)
  {
    queue->root[idx]= queue->root[next_index];
    if (offset_to_queue_pos)
      (*(uint*) (queue->root[idx] + offset_to_queue_pos-1))= idx;
    idx= next_index;
  }
  queue->root[idx]= element;
  if (offset_to_queue_pos)
    (*(uint*) (element + offset_to_queue_pos-1))= idx;
}


/*
  Insert element in queue

  SYNOPSIS
    queue_insert()
    queue		Queue to use
    element		Element to insert
*/

void queue_insert(QUEUE *queue, uchar *element)
{
  DBUG_ASSERT(queue->elements < queue->max_elements);
  insert_at(queue, element, ++queue->elements);
}


/*
  Like queue_insert, but resize queue if queue is full

  SYNOPSIS
    queue_insert_safe()
    queue		Queue to use
    element		Element to insert

  RETURN
    0	OK
    1	Cannot allocate more memory
    2   auto_extend is 0; No insertion done
*/

int queue_insert_safe(QUEUE *queue, uchar *element)
{

  if (queue->elements == queue->max_elements)
  {
    if (!queue->auto_extent)
      return 2;
    if (resize_queue(queue, queue->max_elements + queue->auto_extent))
      return 1;
  }

  queue_insert(queue, element);
  return 0;
}


/*
  Remove item from queue

  SYNOPSIS
    queue_remove()
    queue		Queue to use
    element		Index of element to remove.
			First element in queue is 'queue_first_element(queue)'

  RETURN
   pointer to removed element
*/

uchar *queue_remove(QUEUE *queue, uint idx)
{
  uchar *element;
  DBUG_ASSERT(idx >= 1);
  DBUG_ASSERT(idx <= queue->elements);
  element= queue->root[idx];
  queue->root[idx]= queue->root[queue->elements--];
  queue_replace(queue, idx);
  return element;
}


/*
  Restores the heap property from idx down the heap

  SYNOPSIS
    _downheap()
    queue	Queue to use
    idx         Index of element to change
*/

void _downheap(QUEUE *queue, uint idx)
{
  uchar *element= queue->root[idx];
  uint   next_index,
         elements= queue->elements,
         half_queue= elements >> 1,
         offset_to_key= queue->offset_to_key,
         offset_to_queue_pos= queue->offset_to_queue_pos;

  while (idx <= half_queue)
  {
    next_index= idx+idx;
    if (next_index < elements &&
        (queue->compare(queue->first_cmp_arg,
                        queue->root[next_index]+offset_to_key,
                        queue->root[next_index+1]+offset_to_key) *
         queue->max_at_top) > 0)
      next_index++;
    if ((queue->compare(queue->first_cmp_arg,
                        queue->root[next_index]+offset_to_key,
                        element+offset_to_key) * queue->max_at_top) >= 0)
      break;
    queue->root[idx]= queue->root[next_index];
    if (offset_to_queue_pos)
      (*(uint*) (queue->root[idx] + offset_to_queue_pos-1))= idx;
    idx= next_index;
  }
  queue->root[idx]=element;
  if (offset_to_queue_pos)
    (*(uint*) (element + offset_to_queue_pos-1))= idx;
}


/*
  Fix heap when every element was changed.

  SYNOPSIS
    queue_fix()
    queue	Queue to use
*/

void queue_fix(QUEUE *queue)
{
  uint i;
  for (i= queue->elements >> 1; i > 0; i--)
    _downheap(queue, i);
}


/*
  Change element at fixed position

  SYNOPSIS
    queue_replace()
    queue	Queue to use
    idx         Index of element to change

  NOTE
    optimized for the case when the new position is close to the end of the
    heap (typical for queue_remove() replacements).
*/

void queue_replace(QUEUE *queue, uint idx)
{
  uchar *element= queue->root[idx];
  uint next_index,
       elements= queue->elements,
       half_queue= elements>>1,
       offset_to_key= queue->offset_to_key,
       offset_to_queue_pos= queue->offset_to_queue_pos;
  my_bool first= TRUE;

  while (idx <= half_queue)
  {
    next_index= idx + idx;
    if (next_index < elements &&
	queue->compare(queue->first_cmp_arg,
			queue->root[next_index]+offset_to_key,
			queue->root[next_index+1]+offset_to_key) *
	 queue->max_at_top > 0)
      next_index++;
    if (first &&
        queue->compare(queue->first_cmp_arg,
                        queue->root[next_index]+offset_to_key,
                        element+offset_to_key) * queue->max_at_top >= 0)
    {
      queue->root[idx]= element;
      if (offset_to_queue_pos)
        (*(uint*) (element + offset_to_queue_pos-1))= idx;
      break;
    }
    first= FALSE;
    queue->root[idx]= queue->root[next_index];
    if (offset_to_queue_pos)
      (*(uint*) (queue->root[idx] + offset_to_queue_pos-1))= idx;
    idx=next_index;
  }

  insert_at(queue, element, idx);
}