[Commits] Rev 3429: MDEV-415: added missing files. in file:///home/igor/maria/maria-10.0-mdev415/

Igor Babaev igor at askmonty.org
Sat Sep 1 10:50:50 EEST 2012


At file:///home/igor/maria/maria-10.0-mdev415/

------------------------------------------------------------
revno: 3429
revision-id: igor at askmonty.org-20120901075049-j5vt56rd249k3gnw
parent: igor at askmonty.org-20120831235152-qnaf5ybb09p25xds
committer: Igor Babaev <igor at askmonty.org>
branch nick: maria-10.0-mdev415
timestamp: Sat 2012-09-01 00:50:49 -0700
message:
  MDEV-415: added missing files.
-------------- next part --------------
=== added file 'sql/bounded_queue.h'
--- a/sql/bounded_queue.h	1970-01-01 00:00:00 +0000
+++ b/sql/bounded_queue.h	2012-09-01 07:50:49 +0000
@@ -0,0 +1,195 @@
+/* Copyright (c) 2010, Oracle and/or its affiliates. All rights reserved. 
+
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; version 2 of the License.
+
+   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 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., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
+
+#ifndef BOUNDED_QUEUE_INCLUDED
+#define BOUNDED_QUEUE_INCLUDED
+
+#include <string.h>
+#include "my_global.h"
+#include "my_base.h"
+#include "my_sys.h"
+#include "queues.h"
+
+class Sort_param;
+
+/**
+  A priority queue with a fixed, limited size.
+
+  This is a wrapper on top of QUEUE and the queue_xxx() functions.
+  It keeps the top-N elements which are inserted.
+
+  Elements of type Element_type are pushed into the queue.
+  For each element, we call a user-supplied keymaker_function,
+  to generate a key of type Key_type for the element.
+  Instances of Key_type are compared with the user-supplied compare_function.
+
+  The underlying QUEUE implementation needs one extra element for replacing
+  the lowest/highest element when pushing into a full queue.
+ */
+template<typename Element_type, typename Key_type>
+class Bounded_queue
+{
+public:
+  Bounded_queue()
+  {
+    memset(&m_queue, 0, sizeof(m_queue));
+  }
+
+  ~Bounded_queue()
+  {
+    delete_queue(&m_queue);
+  }
+
+  /**
+     Function for making sort-key from input data.
+     @param param Sort parameters.
+     @param to    Where to put the key.
+     @param from  The input data.
+  */
+  typedef void (*keymaker_function)(Sort_param *param,
+                                    Key_type *to,
+                                    Element_type *from);
+
+  /**
+     Function for comparing two keys.
+     @param  n Pointer to number of bytes to compare.
+     @param  a First key.
+     @param  b Second key.
+     @retval -1, 0, or 1 depending on whether the left argument is 
+             less than, equal to, or greater than the right argument.
+   */
+  typedef int (*compare_function)(size_t *n, Key_type **a, Key_type **b);
+
+  /**
+    Initialize the queue.
+
+    @param max_elements   The size of the queue.
+    @param max_at_top     Set to true if you want biggest element on top.
+           false: We keep the n largest elements.
+                  pop() will return the smallest key in the result set.
+           true:  We keep the n smallest elements.
+                  pop() will return the largest key in the result set.
+    @param compare        Compare function for elements, takes 3 arguments.
+                          If NULL, we use get_ptr_compare(compare_length).
+    @param compare_length Length of the data (i.e. the keys) used for sorting.
+    @param keymaker       Function which generates keys for elements.
+    @param sort_param     Sort parameters.
+    @param sort_keys      Array of pointers to keys to sort.
+
+    @retval 0 OK, 1 Could not allocate memory.
+
+    We do *not* take ownership of any of the input pointer arguments.
+   */
+  int init(ha_rows max_elements, bool max_at_top,
+           compare_function compare, size_t compare_length,
+           keymaker_function keymaker, Sort_param *sort_param,
+           Key_type **sort_keys);
+
+  /**
+    Pushes an element on the queue.
+    If the queue is already full, we discard one element.
+    Calls keymaker_function to generate a key for the element.
+
+    @param element        The element to be pushed.
+   */
+  void push(Element_type *element);
+
+  /**
+    Removes the top element from the queue.
+
+    @retval Pointer to the (key of the) removed element.
+
+    @note This function is for unit testing, where we push elements into to the
+          queue, and test that the appropriate keys are retained.
+          Interleaving of push() and pop() operations has not been tested.
+   */
+  Key_type **pop()
+  {
+    // Don't return the extra element to the client code.
+    if (queue_is_full((&m_queue)))
+      queue_remove(&m_queue, 0);
+    DBUG_ASSERT(m_queue.elements > 0);
+    if (m_queue.elements == 0)
+      return NULL;
+    return reinterpret_cast<Key_type**>(queue_remove(&m_queue, 0));
+  }
+
+  /**
+    The number of elements in the queue.
+   */
+  uint num_elements() const { return m_queue.elements; }
+
+  /**
+    Is the queue initialized?
+   */
+  bool is_initialized() const { return m_queue.max_elements > 0; }
+
+private:
+  Key_type         **m_sort_keys;
+  size_t             m_compare_length;
+  keymaker_function  m_keymaker;
+  Sort_param        *m_sort_param;
+  st_queue           m_queue;
+};
+
+
+template<typename Element_type, typename Key_type>
+int Bounded_queue<Element_type, Key_type>::init(ha_rows max_elements,
+                                                bool max_at_top,
+                                                compare_function compare,
+                                                size_t compare_length,
+                                                keymaker_function keymaker,
+                                                Sort_param *sort_param,
+                                                Key_type **sort_keys)
+{
+  DBUG_ASSERT(sort_keys != NULL);
+
+  m_sort_keys=      sort_keys;
+  m_compare_length= compare_length;
+  m_keymaker=       keymaker;
+  m_sort_param=     sort_param;
+  // init_queue() takes an uint, and also does (max_elements + 1)
+  if (max_elements >= (UINT_MAX - 1))
+    return 1;
+  if (compare == NULL)
+    compare=
+      reinterpret_cast<compare_function>(get_ptr_compare(compare_length));
+  // We allocate space for one extra element, for replace when queue is full.
+  return init_queue(&m_queue, (uint) max_elements + 1,
+                    0, max_at_top,
+                    reinterpret_cast<queue_compare>(compare),
+                    &m_compare_length, 0, 0);
+}
+
+
+template<typename Element_type, typename Key_type>
+void Bounded_queue<Element_type, Key_type>::push(Element_type *element)
+{
+  DBUG_ASSERT(is_initialized());
+  if (queue_is_full((&m_queue)))
+  {
+    // Replace top element with new key, and re-order the queue.
+    Key_type **pq_top= reinterpret_cast<Key_type **>(queue_top(&m_queue));
+    (*m_keymaker)(m_sort_param, *pq_top, element);
+    queue_replace_top(&m_queue);
+  } else {
+    // Insert new key into the queue.
+    (*m_keymaker)(m_sort_param, m_sort_keys[m_queue.elements], element);
+    queue_insert(&m_queue,
+                 reinterpret_cast<uchar*>(&m_sort_keys[m_queue.elements]));
+  }
+}
+
+#endif  // BOUNDED_QUEUE_INCLUDED

=== added file 'sql/filesort_utils.cc'
--- a/sql/filesort_utils.cc	1970-01-01 00:00:00 +0000
+++ b/sql/filesort_utils.cc	2012-09-01 07:50:49 +0000
@@ -0,0 +1,140 @@
+/* Copyright (c) 2010, Oracle and/or its affiliates. All rights reserved. 
+
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; version 2 of the License.
+
+   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 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., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
+
+#include "filesort_utils.h"
+#include "sql_const.h"
+#include "sql_sort.h"
+#include "table.h"
+#include "my_sys.h"
+
+
+namespace {
+/**
+  A local helper function. See comments for get_merge_buffers_cost().
+ */
+double get_merge_cost(ha_rows num_elements, ha_rows num_buffers, uint elem_size)
+{
+  return 
+    2.0 * ((double) num_elements * elem_size) / IO_SIZE
+    + (double) num_elements * log((double) num_buffers) /
+      (TIME_FOR_COMPARE_ROWID * M_LN2);
+}
+}
+
+/**
+  This is a simplified, and faster version of @see get_merge_many_buffs_cost().
+  We calculate the cost of merging buffers, by simulating the actions
+  of @see merge_many_buff. For explanations of formulas below,
+  see comments for get_merge_buffers_cost().
+  TODO: Use this function for Unique::get_use_cost().
+*/
+double get_merge_many_buffs_cost_fast(ha_rows num_rows,
+                                      ha_rows num_keys_per_buffer,
+                                      uint    elem_size)
+{
+  ha_rows num_buffers= num_rows / num_keys_per_buffer;
+  ha_rows last_n_elems= num_rows % num_keys_per_buffer;
+  double total_cost;
+
+  // Calculate CPU cost of sorting buffers.
+  total_cost=
+    ( num_buffers * num_keys_per_buffer * log(1.0 + num_keys_per_buffer) +
+      last_n_elems * log(1.0 + last_n_elems) )
+    / TIME_FOR_COMPARE_ROWID;
+  
+  // Simulate behavior of merge_many_buff().
+  while (num_buffers >= MERGEBUFF2)
+  {
+    // Calculate # of calls to merge_buffers().
+    const ha_rows loop_limit= num_buffers - MERGEBUFF*3/2;
+    const ha_rows num_merge_calls= 1 + loop_limit/MERGEBUFF;
+    const ha_rows num_remaining_buffs=
+      num_buffers - num_merge_calls * MERGEBUFF;
+
+    // Cost of merge sort 'num_merge_calls'.
+    total_cost+=
+      num_merge_calls *
+      get_merge_cost(num_keys_per_buffer * MERGEBUFF, MERGEBUFF, elem_size);
+
+    // # of records in remaining buffers.
+    last_n_elems+= num_remaining_buffs * num_keys_per_buffer;
+
+    // Cost of merge sort of remaining buffers.
+    total_cost+=
+      get_merge_cost(last_n_elems, 1 + num_remaining_buffs, elem_size);
+
+    num_buffers= num_merge_calls;
+    num_keys_per_buffer*= MERGEBUFF;
+  }
+
+  // Simulate final merge_buff call.
+  last_n_elems+= num_keys_per_buffer * num_buffers;
+  total_cost+= get_merge_cost(last_n_elems, 1 + num_buffers, elem_size);
+  return total_cost;
+}
+
+uchar **Filesort_buffer::alloc_sort_buffer(uint num_records, uint record_length)
+{
+  DBUG_ENTER("alloc_sort_buffer");
+
+  DBUG_EXECUTE_IF("alloc_sort_buffer_fail",
+                  DBUG_SET("+d,simulate_out_of_memory"););
+
+  if (m_idx_array.is_null())
+  {
+    uchar **sort_keys=
+      (uchar**) my_malloc(num_records * (record_length + sizeof(uchar*)),
+                          MYF(0));
+    m_idx_array= Idx_array(sort_keys, num_records);
+    m_record_length= record_length;
+    uchar **start_of_data= m_idx_array.array() + m_idx_array.size();
+    m_start_of_data= reinterpret_cast<uchar*>(start_of_data);
+  }
+  else
+  {
+    DBUG_ASSERT(num_records == m_idx_array.size());
+    DBUG_ASSERT(record_length == m_record_length);
+  }
+  DBUG_RETURN(m_idx_array.array());
+}
+
+
+void Filesort_buffer::free_sort_buffer()
+{
+  my_free(m_idx_array.array());
+  m_idx_array= Idx_array();
+  m_record_length= 0;
+  m_start_of_data= NULL;
+}
+
+
+void Filesort_buffer::sort_buffer(const Sort_param *param, uint count)
+{
+  if (count <= 1)
+    return;
+  uchar **keys= get_sort_keys();
+  uchar **buffer= NULL;
+  if (radixsort_is_appliccable(count, param->sort_length) &&
+      (buffer= (uchar**) my_malloc(count*sizeof(char*), MYF(0))))
+  {
+    radixsort_for_str_ptr(keys, count, param->sort_length, buffer);
+    my_free(buffer);
+    return;
+  }
+  
+  size_t size= param->sort_length;
+  my_qsort2(keys, count, sizeof(uchar*), get_ptr_compare(size), &size);
+}
+

=== added file 'sql/filesort_utils.h'
--- a/sql/filesort_utils.h	1970-01-01 00:00:00 +0000
+++ b/sql/filesort_utils.h	2012-09-01 07:50:49 +0000
@@ -0,0 +1,129 @@
+/* Copyright (c) 2010, 2012 Oracle and/or its affiliates. All rights reserved.
+
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; version 2 of the License.
+
+   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 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 */
+
+#ifndef FILESORT_UTILS_INCLUDED
+#define FILESORT_UTILS_INCLUDED
+
+#include "my_global.h"
+#include "my_base.h"
+#include "sql_array.h"
+
+class Sort_param;
+/*
+  Calculate cost of merge sort
+
+    @param num_rows            Total number of rows.
+    @param num_keys_per_buffer Number of keys per buffer.
+    @param elem_size           Size of each element.
+
+    Calculates cost of merge sort by simulating call to merge_many_buff().
+
+  @retval
+    Computed cost of merge sort in disk seeks.
+
+  @note
+    Declared here in order to be able to unit test it,
+    since library dependencies have not been sorted out yet.
+
+    See also comments get_merge_many_buffs_cost().
+*/
+
+double get_merge_many_buffs_cost_fast(ha_rows num_rows,
+                                      ha_rows num_keys_per_buffer,
+                                      uint    elem_size);
+
+
+/**
+  A wrapper class around the buffer used by filesort().
+  The buffer is a contiguous chunk of memory,
+  where the first part is <num_records> pointers to the actual data.
+
+  We wrap the buffer in order to be able to do lazy initialization of the
+  pointers: the buffer is often much larger than what we actually need.
+
+  The buffer must be kept available for multiple executions of the
+  same sort operation, so we have explicit allocate and free functions,
+  rather than doing alloc/free in CTOR/DTOR.
+*/
+class Filesort_buffer
+{
+public:
+  Filesort_buffer() :
+    m_idx_array(), m_record_length(0), m_start_of_data(NULL)
+  {}
+
+  /** Sort me... */
+  void sort_buffer(const Sort_param *param, uint count);
+
+  /// Initializes a record pointer.
+  uchar *get_record_buffer(uint idx)
+  {
+    m_idx_array[idx]= m_start_of_data + (idx * m_record_length);
+    return m_idx_array[idx];
+  }
+
+  /// Initializes all the record pointers.
+  void init_record_pointers()
+  {
+    for (uint ix= 0; ix < m_idx_array.size(); ++ix)
+      (void) get_record_buffer(ix);
+  }
+
+  /// Returns total size: pointer array + record buffers.
+  size_t sort_buffer_size() const
+  {
+    return m_idx_array.size() * (m_record_length + sizeof(uchar*));
+  }
+
+  /// Allocates the buffer, but does *not* initialize pointers.
+  uchar **alloc_sort_buffer(uint num_records, uint record_length);
+
+
+  /// Check  <num_records, record_length> for the buffer
+  bool check_sort_buffer_properties(uint num_records,  uint record_length)
+  {
+    return (static_cast<uint>(m_idx_array.size()) == num_records &&
+            m_record_length == m_record_length);
+  }
+
+  /// Frees the buffer.
+  void free_sort_buffer();
+
+  /// Getter, for calling routines which still use the uchar** interface.
+  uchar **get_sort_keys() { return m_idx_array.array(); }
+
+  /**
+    We need an assignment operator, see filesort().
+    This happens to have the same semantics as the one that would be
+    generated by the compiler. We still implement it here, to show shallow
+    assignment explicitly: we have two objects sharing the same array.
+  */
+  Filesort_buffer &operator=(const Filesort_buffer &rhs)
+  {
+    m_idx_array= rhs.m_idx_array;
+    m_record_length= rhs.m_record_length;
+    m_start_of_data= rhs.m_start_of_data;
+    return *this;
+  }
+
+private:
+  typedef Bounds_checked_array<uchar*> Idx_array;
+
+  Idx_array  m_idx_array;
+  uint       m_record_length;
+  uchar     *m_start_of_data;
+};
+
+#endif  // FILESORT_UTILS_INCLUDED



More information about the commits mailing list