Drizzled Public API Documentation

discrete_interval.h
00001 /* -*- mode: c++; c-basic-offset: 2; indent-tabs-mode: nil; -*-
00002  *  vim:expandtab:shiftwidth=2:tabstop=2:smarttab:
00003  *
00004  *  Copyright (C) 2008 Sun Microsystems, Inc.
00005  *
00006  *  This program is free software; you can redistribute it and/or modify
00007  *  it under the terms of the GNU General Public License as published by
00008  *  the Free Software Foundation; version 2 of the License.
00009  *
00010  *  This program is distributed in the hope that it will be useful,
00011  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
00012  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00013  *  GNU General Public License for more details.
00014  *
00015  *  You should have received a copy of the GNU General Public License
00016  *  along with this program; if not, write to the Free Software
00017  *  Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
00018  */
00019 
00020 
00021 #pragma once
00022 
00023 #include <cstdlib>
00024 
00025 #include <drizzled/definitions.h>
00026 
00027 namespace drizzled
00028 {
00029 
00030 /*
00031   Such interval is "discrete": it is the set of
00032   { auto_inc_interval_min + k * increment,
00033     0 <= k <= (auto_inc_interval_values-1) }
00034   Where "increment" is maintained separately by the user of this class (and is
00035   currently only session->variables.auto_increment_increment).
00036   It mustn't derive from memory::SqlAlloc, because SET INSERT_ID needs to
00037   allocate memory which must stay allocated for use by the next statement.
00038 */
00039 class Discrete_interval {
00040 private:
00041   uint64_t interval_min;
00042   uint64_t interval_values;
00043   uint64_t  interval_max;    // excluded bound. Redundant.
00044 public:
00045   Discrete_interval *next;    // used when linked into Discrete_intervals_list
00046   void replace(uint64_t start, uint64_t val, uint64_t incr)
00047   {
00048     interval_min=    start;
00049     interval_values= val;
00050     interval_max=    (val == UINT64_MAX) ? val : start + val * incr;
00051   }
00052   Discrete_interval(uint64_t start, uint64_t val, uint64_t incr) :
00053     interval_min(start), interval_values(val),
00054     interval_max((val == UINT64_MAX) ? val : start + val * incr),
00055     next(NULL)
00056   {}
00057   Discrete_interval() :
00058     interval_min(0), interval_values(0),
00059     interval_max(0), next(NULL)
00060   {}
00061   uint64_t minimum() const { return interval_min;    }
00062   uint64_t values()  const { return interval_values; }
00063   uint64_t maximum() const { return interval_max;    }
00064   /*
00065     If appending [3,5] to [1,2], we merge both in [1,5] (they should have the
00066     same increment for that, user of the class has to ensure that). That is
00067     just a space optimization. Returns 0 if merge succeeded.
00068   */
00069   bool merge_if_contiguous(uint64_t start, uint64_t val, uint64_t incr)
00070   {
00071     if (interval_max == start)
00072     {
00073       if (val == UINT64_MAX)
00074       {
00075         interval_values=   interval_max= val;
00076       }
00077       else
00078       {
00079         interval_values+=  val;
00080         interval_max=      start + val * incr;
00081       }
00082       return 0;
00083     }
00084     return 1;
00085   }
00086 };
00087 
00088 
00089 
00090 /* List of Discrete_interval objects */
00091 class Discrete_intervals_list {
00092 private:
00093   Discrete_interval        *head;
00094   Discrete_interval        *tail;
00095   /*
00096     When many intervals are provided at the beginning of the execution of a
00097     statement (in a replication slave or SET INSERT_ID), "current" points to
00098     the interval being consumed by the thread now (so "current" goes from
00099     "head" to "tail" then to NULL).
00100   */
00101   Discrete_interval        *current;
00102   uint32_t                  elements; // number of elements
00103 
00104   /* helper function for copy construct and assignment operator */
00105   void copy_(const Discrete_intervals_list& from)
00106   {
00107     for (Discrete_interval *i= from.head; i; i= i->next)
00108     {
00109       Discrete_interval j= *i;
00110       append(&j);
00111     }
00112   }
00113 public:
00114   Discrete_intervals_list() :
00115     head(NULL), tail(NULL),
00116     current(NULL), elements(0) {}
00117   Discrete_intervals_list(const Discrete_intervals_list& from) :
00118     head(NULL), tail(NULL),
00119     current(NULL), elements(0)
00120   {
00121     copy_(from);
00122   }
00123   Discrete_intervals_list& operator=(const Discrete_intervals_list& from)
00124   {
00125     empty();
00126     copy_(from);
00127     return *this;
00128   }
00129   void empty_no_free()
00130   {
00131     head= current= NULL;
00132     elements= 0;
00133   }
00134   void empty()
00135   {
00136     for (Discrete_interval *i= head; i;)
00137     {
00138       Discrete_interval *next= i->next;
00139       delete i;
00140       i= next;
00141     }
00142     empty_no_free();
00143   }
00144 
00145   const Discrete_interval* get_next()
00146   {
00147     Discrete_interval *tmp= current;
00148     if (current != NULL)
00149       current= current->next;
00150     return tmp;
00151   }
00152   ~Discrete_intervals_list() { empty(); }
00153   uint64_t minimum()     const { return (head ? head->minimum() : 0); }
00154   uint64_t maximum()     const { return (head ? tail->maximum() : 0); }
00155   uint32_t      nb_elements() const { return elements; }
00156 
00157   bool append(uint64_t start, uint64_t val, uint64_t incr)
00158   {
00159     /* first, see if this can be merged with previous */
00160     if ((head == NULL) || tail->merge_if_contiguous(start, val, incr))
00161     {
00162       /* it cannot, so need to add a new interval */
00163       Discrete_interval *new_interval= new Discrete_interval(start, val, incr);
00164       return(append(new_interval));
00165     }
00166     return(0);
00167   }
00168 
00169   bool append(Discrete_interval *new_interval)
00170   {
00171     if (unlikely(new_interval == NULL))
00172       return(1);
00173     if (head == NULL)
00174       head= current= new_interval;
00175     else
00176       tail->next= new_interval;
00177     tail= new_interval;
00178     elements++;
00179     return(0);
00180   }
00181 
00182 };
00183 
00184 } /* namespace drizzled */
00185