queues.cc

/* Copyright (c) 2000, 2025, Oracle and/or its affiliates.

   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License, version 2.0,
   as published by the Free Software Foundation.

   This program is designed to work with certain software (including
   but not limited to OpenSSL) that is licensed under separate terms,
   as designated in a particular file or component or in included license
   documentation.  The authors of MySQL hereby grant you an additional
   permission to link the program and your derivative works with the
   separately licensed software that they have either included with
   the program or referenced in the documentation.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License, version 2.0, for more details.

   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301  USA */

/**
  @file storage/myisam/queues.cc
  Code for handling of priority Queues.
  Implementation of queues from "Algorithms in C" by Robert Sedgewick.
  An optimisation of _downheap suggested in Exercise 7.51 in "Data
  Structures & Algorithms in C++" by Mark Allen Weiss, Second Edition
  was implemented by Mikael Ronstrom 2005. Also the O(N) algorithm
  of queue_fix was implemented.
*/

#include "storage/myisam/queues.h"

#include <sys/types.h>
#include <cstddef>
#include <cstdio>

#include <algorithm>

#include "my_dbug.h"
#include "my_macros.h"
#include "my_sys.h"
#include "my_systime.h"
#include "mysql/service_mysql_alloc.h"
#include "storage/myisam/array.h"
#include "storage/myisam/myisamdef.h"

static int resize_queue(QUEUE *queue, PSI_memory_key key, uint max_elements);

/*
  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

  NOTES
    Will allocate max_element pointers for queue array

  RETURN
    0	ok
    1	Could not allocate memory
*/

extern "C" int init_queue(QUEUE *queue, PSI_memory_key psi_key,
                          uint max_elements, uint offset_to_key,
                          bool max_at_top,
                          int (*compare)(void *, uchar *, uchar *),
                          void *first_cmp_arg) {
  DBUG_TRACE;
  if ((queue->root = (uchar **)my_malloc(
           psi_key, (max_elements + 1) * sizeof(void *), MYF(MY_WME))) ==
      nullptr)
    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_set_max_at_top(queue, max_at_top);
  return 0;
}

/*
  Reinitialize queue for other usage

  SYNOPSIS
    reinit_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

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

  RETURN
    0			ok
    EE_OUTOFMEMORY	Wrong max_elements
*/

extern "C" int reinit_queue(QUEUE *queue, PSI_memory_key psi_key,
                            uint max_elements, uint offset_to_key,
                            bool max_at_top,
                            int (*compare)(void *, uchar *, uchar *),
                            void *first_cmp_arg) {
  DBUG_TRACE;
  queue->elements = 0;
  queue->compare = compare;
  queue->first_cmp_arg = first_cmp_arg;
  queue->offset_to_key = offset_to_key;
  queue_set_max_at_top(queue, max_at_top);
  resize_queue(queue, psi_key, max_elements);
  return 0;
}

/*
  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
*/

static int resize_queue(QUEUE *queue, PSI_memory_key psi_key,
                        uint max_elements) {
  uchar **new_root;
  DBUG_TRACE;
  if (queue->max_elements == max_elements) return 0;
  if ((new_root = (uchar **)my_realloc(psi_key, (void *)queue->root,
                                       (max_elements + 1) * sizeof(void *),
                                       MYF(MY_WME))) == nullptr)
    return 1;
  queue->elements = std::min(queue->elements, max_elements);
  queue->max_elements = max_elements;
  queue->root = new_root;
  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_TRACE;
  my_free(queue->root);
  queue->root = nullptr;
}

/* Code for insert, search and delete of elements */

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

/* Remove item from queue */
/* Returns pointer to removed element */

uchar *queue_remove(QUEUE *queue, uint idx) {
  uchar *element;
  assert(idx < queue->max_elements);
  element = queue->root[++idx]; /* Intern index starts from 1 */
  queue->root[idx] = queue->root[queue->elements--];
  _downheap(queue, idx);
  return element;
}

void _downheap(QUEUE *queue, uint idx) {
  uchar *element;
  uint elements, half_queue, offset_to_key, next_index;
  bool first = true;
  uint const start_idx = idx;

  offset_to_key = queue->offset_to_key;
  element = queue->root[idx];
  half_queue = (elements = queue->elements) >> 1;

  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;
      return;
    }
    queue->root[idx] = queue->root[next_index];
    idx = next_index;
    first = false;
  }

  next_index = idx >> 1;
  while (next_index > start_idx) {
    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];
    idx = next_index;
    next_index = idx >> 1;
  }
  queue->root[idx] = element;
}

/*
  Fix heap when every element was changed.
*/

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