You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@impala.apache.org by he...@apache.org on 2017/03/29 02:53:47 UTC
[06/14] incubator-impala git commit: IMPALA-4758: (1/2) Update gutil/
from Kudu@a1bfd7b
http://git-wip-us.apache.org/repos/asf/incubator-impala/blob/02f3e3fc/be/src/gutil/sparsetable.h
----------------------------------------------------------------------
diff --git a/be/src/gutil/sparsetable.h b/be/src/gutil/sparsetable.h
deleted file mode 100644
index 007f76b..0000000
--- a/be/src/gutil/sparsetable.h
+++ /dev/null
@@ -1,1838 +0,0 @@
-// Copyright (c) 2005, Google Inc.
-// 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 above
-// copyright notice, this list of conditions and the following disclaimer
-// in the documentation and/or other materials provided with the
-// distribution.
-// * Neither the name of Google Inc. nor the names of its
-// contributors may be used to endorse or promote products derived from
-// this software without specific prior written permission.
-//
-// 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 THE COPYRIGHT
-// OWNER OR CONTRIBUTORS 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.
-
-// ---
-//
-//
-// A sparsetable is a random container that implements a sparse array,
-// that is, an array that uses very little memory to store unassigned
-// indices (in this case, between 1-2 bits per unassigned index). For
-// instance, if you allocate an array of size 5 and assign a[2] = <big
-// struct>, then a[2] will take up a lot of memory but a[0], a[1],
-// a[3], and a[4] will not. Array elements that have a value are
-// called "assigned". Array elements that have no value yet, or have
-// had their value cleared using erase() or clear(), are called
-// "unassigned".
-//
-// Unassigned values seem to have the default value of T (see below).
-// Nevertheless, there is a difference between an unassigned index and
-// one explicitly assigned the value of T(). The latter is considered
-// assigned.
-//
-// Access to an array element is constant time, as is insertion and
-// deletion. Insertion and deletion may be fairly slow, however:
-// because of this container's memory economy, each insert and delete
-// causes a memory reallocation.
-//
-// NOTE: You should not test(), get(), or set() any index that is
-// greater than sparsetable.size(). If you need to do that, call
-// resize() first.
-//
-// --- Template parameters
-// PARAMETER DESCRIPTION DEFAULT
-// T The value of the array: the type of --
-// object that is stored in the array.
-//
-// GROUP_SIZE How large each "group" in the table 48
-// is (see below). Larger values use
-// a little less memory but cause most
-// operations to be a little slower
-//
-// Alloc: Allocator to use to allocate memory. libc_allocator_with_realloc
-//
-// --- Model of
-// Random Access Container
-//
-// --- Type requirements
-// T must be Copy Constructible. It need not be Assignable.
-//
-// --- Public base classes
-// None.
-//
-// --- Members
-// Type members
-//
-// MEMBER WHERE DEFINED DESCRIPTION
-// value_type container The type of object, T, stored in the array
-// allocator_type container Allocator to use
-// pointer container Pointer to p
-// const_pointer container Const pointer to p
-// reference container Reference to t
-// const_reference container Const reference to t
-// size_type container An unsigned integral type
-// difference_type container A signed integral type
-// iterator [*] container Iterator used to iterate over a sparsetable
-// const_iterator container Const iterator used to iterate over a table
-// reverse_iterator reversible Iterator used to iterate backwards over
-// container a sparsetable
-// const_reverse_iterator reversible container Guess
-// nonempty_iterator [+] sparsetable Iterates over assigned
-// array elements only
-// const_nonempty_iterator sparsetable Iterates over assigned
-// array elements only
-// reverse_nonempty_iterator sparsetable Iterates backwards over
-// assigned array elements only
-// const_reverse_nonempty_iterator sparsetable Iterates backwards over
-// assigned array elements only
-//
-// [*] All iterators are const in a sparsetable (though nonempty_iterators
-// may not be). Use get() and set() to assign values, not iterators.
-//
-// [+] iterators are random-access iterators. nonempty_iterators are
-// bidirectional iterators.
-
-// Iterator members
-// MEMBER WHERE DEFINED DESCRIPTION
-//
-// iterator begin() container An iterator to the beginning of the table
-// iterator end() container An iterator to the end of the table
-// const_iterator container A const_iterator pointing to the
-// begin() const beginning of a sparsetable
-// const_iterator container A const_iterator pointing to the
-// end() const end of a sparsetable
-//
-// reverse_iterator reversable Points to beginning of a reversed
-// rbegin() container sparsetable
-// reverse_iterator reversable Points to end of a reversed table
-// rend() container
-// const_reverse_iterator reversable Points to beginning of a
-// rbegin() const container reversed sparsetable
-// const_reverse_iterator reversable Points to end of a reversed table
-// rend() const container
-//
-// nonempty_iterator sparsetable Points to first assigned element
-// begin() of a sparsetable
-// nonempty_iterator sparsetable Points past last assigned element
-// end() of a sparsetable
-// const_nonempty_iterator sparsetable Points to first assigned element
-// begin() const of a sparsetable
-// const_nonempty_iterator sparsetable Points past last assigned element
-// end() const of a sparsetable
-//
-// reverse_nonempty_iterator sparsetable Points to first assigned element
-// begin() of a reversed sparsetable
-// reverse_nonempty_iterator sparsetable Points past last assigned element
-// end() of a reversed sparsetable
-// const_reverse_nonempty_iterator sparsetable Points to first assigned
-// begin() const elt of a reversed sparsetable
-// const_reverse_nonempty_iterator sparsetable Points past last assigned
-// end() const elt of a reversed sparsetable
-//
-//
-// Other members
-// MEMBER WHERE DEFINED DESCRIPTION
-// sparsetable() sparsetable A table of size 0; must resize()
-// before using.
-// sparsetable(size_type size) sparsetable A table of size size. All
-// indices are unassigned.
-// sparsetable(
-// const sparsetable &tbl) sparsetable Copy constructor
-// ~sparsetable() sparsetable The destructor
-// sparsetable &operator=( sparsetable The assignment operator
-// const sparsetable &tbl)
-//
-// void resize(size_type size) sparsetable Grow or shrink a table to
-// have size indices [*]
-//
-// void swap(sparsetable &x) sparsetable Swap two sparsetables
-// void swap(sparsetable &x, sparsetable Swap two sparsetables
-// sparsetable &y) (global, not member, function)
-//
-// size_type size() const sparsetable Number of "buckets" in the table
-// size_type max_size() const sparsetable Max allowed size of a sparsetable
-// bool empty() const sparsetable true if size() == 0
-// size_type num_nonempty() const sparsetable Number of assigned "buckets"
-//
-// const_reference get( sparsetable Value at index i, or default
-// size_type i) const value if i is unassigned
-// const_reference operator[]( sparsetable Identical to get(i) [+]
-// difference_type i) const
-// reference set(size_type i, sparsetable Set element at index i to
-// const_reference val) be a copy of val
-// bool test(size_type i) sparsetable True if element at index i
-// const has been assigned to
-// bool test(iterator pos) sparsetable True if element pointed to
-// const by pos has been assigned to
-// void erase(iterator pos) sparsetable Set element pointed to by
-// pos to be unassigned [!]
-// void erase(size_type i) sparsetable Set element i to be unassigned
-// void erase(iterator start, sparsetable Erases all elements between
-// iterator end) start and end
-// void clear() sparsetable Erases all elements in the table
-//
-// I/O versions exist for both FILE* and for File* (Google2-style files):
-// bool write_metadata(FILE *fp) sparsetable Writes a sparsetable to the
-// bool write_metadata(File *fp) given file. true if write
-// completes successfully
-// bool read_metadata(FILE *fp) sparsetable Replaces sparsetable with
-// bool read_metadata(File *fp) version read from fp. true
-// if read completes sucessfully
-// bool write_nopointer_data(FILE *fp) Read/write the data stored in
-// bool read_nopointer_data(FILE*fp) the table, if it's simple
-//
-// bool operator==( forward Tests two tables for equality.
-// const sparsetable &t1, container This is a global function,
-// const sparsetable &t2) not a member function.
-// bool operator<( forward Lexicographical comparison.
-// const sparsetable &t1, container This is a global function,
-// const sparsetable &t2) not a member function.
-//
-// [*] If you shrink a sparsetable using resize(), assigned elements
-// past the end of the table are removed using erase(). If you grow
-// a sparsetable, new unassigned indices are created.
-//
-// [+] Note that operator[] returns a const reference. You must use
-// set() to change the value of a table element.
-//
-// [!] Unassignment also calls the destructor.
-//
-// Iterators are invalidated whenever an item is inserted or
-// deleted (ie set() or erase() is used) or when the size of
-// the table changes (ie resize() or clear() is used).
-//
-// See doc/sparsetable.html for more information about how to use this class.
-
-// Note: this uses STL style for naming, rather than Google naming.
-// That's because this is an STL-y container
-
-#ifndef UTIL_GTL_SPARSETABLE_H_
-#define UTIL_GTL_SPARSETABLE_H_
-
-#include <assert.h> // for bounds checking
-#include <stdio.h> // to read/write tables
-#include <stdlib.h> // for malloc/free
-#include <string.h> // for memcpy
-#include <sys/types.h> // to get u_int16_t (ISO naming madness)
-#include <algorithm>
-using std::copy;
-using std::max;
-using std::min;
-using std::reverse;
-using std::sort;
-using std::swap; // equal, lexicographical_compare, swap,...
-#include <iterator>
-using std::back_insert_iterator;
-using std::iterator_traits; // to define reverse_iterator for me
-#include <memory> // uninitialized_copy, uninitialized_fill
-#include <vector>
-using std::vector; // a sparsetable is a vector of groups
-
-#include "gutil/type_traits.h"
-#include "gutil/libc_allocator_with_realloc.h"
-
-// A lot of work to get a type that's guaranteed to be 16 bits...
-#ifndef HAVE_U_INT16_T
-# if defined HAVE_UINT16_T
- typedef uint16_t u_int16_t; // true on solaris, possibly other C99 libc's
-# elif defined HAVE___UINT16
- typedef __int16 int16_t; // true on vc++7
- typedef unsigned __int16 u_int16_t;
-# else
- // Cannot find a 16-bit integer type. Hoping for the best with "short"...
- typedef short int int16_t;
- typedef unsigned short int u_int16_t;
-# endif
-#endif
-
-namespace base {
-
-namespace base { // just to make google->opensource transition easier
-using base::true_type;
-using base::false_type;
-using base::integral_constant;
-using base::has_trivial_copy;
-using base::has_trivial_destructor;
-using base::is_same;
-}
-
-
-// The smaller this is, the faster lookup is (because the group bitmap is
-// smaller) and the faster insert is, because there's less to move.
-// On the other hand, there are more groups. Since group::size_type is
-// a short, this number should be of the form 32*x + 16 to avoid waste.
-static const u_int16_t DEFAULT_SPARSEGROUP_SIZE = 48; // fits in 1.5 words
-
-
-// Our iterator as simple as iterators can be: basically it's just
-// the index into our table. Dereference, the only complicated
-// thing, we punt to the table class. This just goes to show how
-// much machinery STL requires to do even the most trivial tasks.
-//
-// A NOTE ON ASSIGNING:
-// A sparse table does not actually allocate memory for entries
-// that are not filled. Because of this, it becomes complicated
-// to have a non-const iterator: we don't know, if the iterator points
-// to a not-filled bucket, whether you plan to fill it with something
-// or whether you plan to read its value (in which case you'll get
-// the default bucket value). Therefore, while we can define const
-// operations in a pretty 'normal' way, for non-const operations, we
-// define something that returns a helper object with operator= and
-// operator& that allocate a bucket lazily. We use this for table[]
-// and also for regular table iterators.
-
-template <class tabletype>
-class table_element_adaptor {
- public:
- typedef typename tabletype::value_type value_type;
- typedef typename tabletype::size_type size_type;
- typedef typename tabletype::reference reference;
- typedef typename tabletype::pointer pointer;
-
- table_element_adaptor(tabletype *tbl, size_type p)
- : table(tbl), pos(p) { }
- table_element_adaptor& operator= (const value_type &val) {
- table->set(pos, val);
- return *this;
- }
- operator value_type() { return table->get(pos); } // we look like a value
- pointer operator& () { return &table->mutating_get(pos); }
-
- private:
- tabletype* table;
- size_type pos;
-};
-
-// Our iterator as simple as iterators can be: basically it's just
-// the index into our table. Dereference, the only complicated
-// thing, we punt to the table class. This just goes to show how
-// much machinery STL requires to do even the most trivial tasks.
-//
-// By templatizing over tabletype, we have one iterator type which
-// we can use for both sparsetables and sparsebins. In fact it
-// works on any class that allows size() and operator[] (eg vector),
-// as long as it does the standard STL typedefs too (eg value_type).
-
-template <class tabletype>
-class table_iterator {
- public:
- typedef table_iterator iterator;
-
- typedef std::random_access_iterator_tag iterator_category;
- typedef typename tabletype::value_type value_type;
- typedef typename tabletype::difference_type difference_type;
- typedef typename tabletype::size_type size_type;
- typedef table_element_adaptor<tabletype> reference;
- typedef table_element_adaptor<tabletype>* pointer;
-
- // The "real" constructor
- table_iterator(tabletype *tbl, size_type p)
- : table(tbl), pos(p) { }
- // The default constructor, used when I define vars of type table::iterator
- table_iterator() : table(NULL), pos(0) { }
- // The copy constructor, for when I say table::iterator foo = tbl.begin()
- // The default destructor is fine; we don't define one
- // The default operator= is fine; we don't define one
-
- // The main thing our iterator does is dereference. If the table entry
- // we point to is empty, we return the default value type.
- // This is the big different function from the const iterator.
- reference operator*() {
- return table_element_adaptor<tabletype>(table, pos);
- }
- pointer operator->() { return &(operator*()); }
-
- // Helper function to assert things are ok; eg pos is still in range
- void check() const {
- assert(table);
- assert(pos <= table->size());
- }
-
- // Arithmetic: we just do arithmetic on pos. We don't even need to
- // do bounds checking, since STL doesn't consider that its job. :-)
- iterator& operator+=(size_type t) { pos += t; check(); return *this; }
- iterator& operator-=(size_type t) { pos -= t; check(); return *this; }
- iterator& operator++() { ++pos; check(); return *this; }
- iterator& operator--() { --pos; check(); return *this; }
- iterator operator++(int) { iterator tmp(*this); // for x++
- ++pos; check(); return tmp; }
- iterator operator--(int) { iterator tmp(*this); // for x--
- --pos; check(); return tmp; }
- iterator operator+(difference_type i) const { iterator tmp(*this);
- tmp += i; return tmp; }
- iterator operator-(difference_type i) const { iterator tmp(*this);
- tmp -= i; return tmp; }
- difference_type operator-(iterator it) const { // for "x = it2 - it"
- assert(table == it.table);
- return pos - it.pos;
- }
- reference operator[](difference_type n) const {
- return *(*this + n); // simple though not totally efficient
- }
-
- // Comparisons.
- bool operator==(const iterator& it) const {
- return table == it.table && pos == it.pos;
- }
- bool operator<(const iterator& it) const {
- assert(table == it.table); // life is bad bad bad otherwise
- return pos < it.pos;
- }
- bool operator!=(const iterator& it) const { return !(*this == it); }
- bool operator<=(const iterator& it) const { return !(it < *this); }
- bool operator>(const iterator& it) const { return it < *this; }
- bool operator>=(const iterator& it) const { return !(*this < it); }
-
- // Here's the info we actually need to be an iterator
- tabletype *table; // so we can dereference and bounds-check
- size_type pos; // index into the table
-};
-
-// support for "3 + iterator" has to be defined outside the class, alas
-template<class T>
-table_iterator<T> operator+(typename table_iterator<T>::difference_type i,
- table_iterator<T> it) {
- return it + i; // so people can say it2 = 3 + it
-}
-
-template <class tabletype>
-class const_table_iterator {
- public:
- typedef table_iterator<tabletype> iterator;
- typedef const_table_iterator const_iterator;
-
- typedef std::random_access_iterator_tag iterator_category;
- typedef typename tabletype::value_type value_type;
- typedef typename tabletype::difference_type difference_type;
- typedef typename tabletype::size_type size_type;
- typedef typename tabletype::const_reference reference; // we're const-only
- typedef typename tabletype::const_pointer pointer;
-
- // The "real" constructor
- const_table_iterator(const tabletype *tbl, size_type p)
- : table(tbl), pos(p) { }
- // The default constructor, used when I define vars of type table::iterator
- const_table_iterator() : table(NULL), pos(0) { }
- // The copy constructor, for when I say table::iterator foo = tbl.begin()
- // Also converts normal iterators to const iterators
- const_table_iterator(const iterator &from)
- : table(from.table), pos(from.pos) { }
- // The default destructor is fine; we don't define one
- // The default operator= is fine; we don't define one
-
- // The main thing our iterator does is dereference. If the table entry
- // we point to is empty, we return the default value type.
- reference operator*() const { return (*table)[pos]; }
- pointer operator->() const { return &(operator*()); }
-
- // Helper function to assert things are ok; eg pos is still in range
- void check() const {
- assert(table);
- assert(pos <= table->size());
- }
-
- // Arithmetic: we just do arithmetic on pos. We don't even need to
- // do bounds checking, since STL doesn't consider that its job. :-)
- const_iterator& operator+=(size_type t) { pos += t; check(); return *this; }
- const_iterator& operator-=(size_type t) { pos -= t; check(); return *this; }
- const_iterator& operator++() { ++pos; check(); return *this; }
- const_iterator& operator--() { --pos; check(); return *this; }
- const_iterator operator++(int) { const_iterator tmp(*this); // for x++
- ++pos; check(); return tmp; }
- const_iterator operator--(int) { const_iterator tmp(*this); // for x--
- --pos; check(); return tmp; }
- const_iterator operator+(difference_type i) const { const_iterator tmp(*this);
- tmp += i; return tmp; }
- const_iterator operator-(difference_type i) const { const_iterator tmp(*this);
- tmp -= i; return tmp; }
- difference_type operator-(const_iterator it) const { // for "x = it2 - it"
- assert(table == it.table);
- return pos - it.pos;
- }
- reference operator[](difference_type n) const {
- return *(*this + n); // simple though not totally efficient
- }
-
- // Comparisons.
- bool operator==(const const_iterator& it) const {
- return table == it.table && pos == it.pos;
- }
- bool operator<(const const_iterator& it) const {
- assert(table == it.table); // life is bad bad bad otherwise
- return pos < it.pos;
- }
- bool operator!=(const const_iterator& it) const { return !(*this == it); }
- bool operator<=(const const_iterator& it) const { return !(it < *this); }
- bool operator>(const const_iterator& it) const { return it < *this; }
- bool operator>=(const const_iterator& it) const { return !(*this < it); }
-
- // Here's the info we actually need to be an iterator
- const tabletype *table; // so we can dereference and bounds-check
- size_type pos; // index into the table
-};
-
-// support for "3 + iterator" has to be defined outside the class, alas
-template<class T>
-const_table_iterator<T> operator+(typename
- const_table_iterator<T>::difference_type i,
- const_table_iterator<T> it) {
- return it + i; // so people can say it2 = 3 + it
-}
-
-
-// ---------------------------------------------------------------------------
-
-
-/*
-// This is a 2-D iterator. You specify a begin and end over a list
-// of *containers*. We iterate over each container by iterating over
-// it. It's actually simple:
-// VECTOR.begin() VECTOR[0].begin() --------> VECTOR[0].end() ---,
-// | ________________________________________________/
-// | \_> VECTOR[1].begin() --------> VECTOR[1].end() -,
-// | ___________________________________________________/
-// v \_> ......
-// VECTOR.end()
-//
-// It's impossible to do random access on one of these things in constant
-// time, so it's just a bidirectional iterator.
-//
-// Unfortunately, because we need to use this for a non-empty iterator,
-// we use nonempty_begin() and nonempty_end() instead of begin() and end()
-// (though only going across, not down).
-*/
-
-#define TWOD_BEGIN_ nonempty_begin
-#define TWOD_END_ nonempty_end
-#define TWOD_ITER_ nonempty_iterator
-#define TWOD_CONST_ITER_ const_nonempty_iterator
-
-template <class containertype>
-class two_d_iterator {
- public:
- typedef two_d_iterator iterator;
-
- typedef std::bidirectional_iterator_tag iterator_category;
- // apparently some versions of VC++ have trouble with two ::'s in a typename
- typedef typename containertype::value_type _tmp_vt;
- typedef typename _tmp_vt::value_type value_type;
- typedef typename _tmp_vt::difference_type difference_type;
- typedef typename _tmp_vt::reference reference;
- typedef typename _tmp_vt::pointer pointer;
-
- // The "real" constructor. begin and end specify how many rows we have
- // (in the diagram above); we always iterate over each row completely.
- two_d_iterator(typename containertype::iterator begin,
- typename containertype::iterator end,
- typename containertype::iterator curr)
- : row_begin(begin), row_end(end), row_current(curr), col_current() {
- if ( row_current != row_end ) {
- col_current = row_current->TWOD_BEGIN_();
- advance_past_end(); // in case cur->begin() == cur->end()
- }
- }
- // If you want to start at an arbitrary place, you can, I guess
- two_d_iterator(typename containertype::iterator begin,
- typename containertype::iterator end,
- typename containertype::iterator curr,
- typename containertype::value_type::TWOD_ITER_ col)
- : row_begin(begin), row_end(end), row_current(curr), col_current(col) {
- advance_past_end(); // in case cur->begin() == cur->end()
- }
- // The default constructor, used when I define vars of type table::iterator
- two_d_iterator() : row_begin(), row_end(), row_current(), col_current() { }
- // The default destructor is fine; we don't define one
- // The default operator= is fine; we don't define one
-
- // Happy dereferencer
- reference operator*() const { return *col_current; }
- pointer operator->() const { return &(operator*()); }
-
- // Arithmetic: we just do arithmetic on pos. We don't even need to
- // do bounds checking, since STL doesn't consider that its job. :-)
- // NOTE: this is not amortized constant time! What do we do about it?
- void advance_past_end() { // used when col_current points to end()
- while ( col_current == row_current->TWOD_END_() ) { // end of current row
- ++row_current; // go to beginning of next
- if ( row_current != row_end ) // col is irrelevant at end
- col_current = row_current->TWOD_BEGIN_();
- else
- break; // don't go past row_end
- }
- }
-
- iterator& operator++() {
- assert(row_current != row_end); // how to ++ from there?
- ++col_current;
- advance_past_end(); // in case col_current is at end()
- return *this;
- }
- iterator& operator--() {
- while ( row_current == row_end ||
- col_current == row_current->TWOD_BEGIN_() ) {
- assert(row_current != row_begin);
- --row_current;
- col_current = row_current->TWOD_END_(); // this is 1 too far
- }
- --col_current;
- return *this;
- }
- iterator operator++(int) { iterator tmp(*this); ++*this; return tmp; }
- iterator operator--(int) { iterator tmp(*this); --*this; return tmp; }
-
-
- // Comparisons.
- bool operator==(const iterator& it) const {
- return ( row_begin == it.row_begin &&
- row_end == it.row_end &&
- row_current == it.row_current &&
- (row_current == row_end || col_current == it.col_current) );
- }
- bool operator!=(const iterator& it) const { return !(*this == it); }
-
-
- // Here's the info we actually need to be an iterator
- // These need to be public so we convert from iterator to const_iterator
- typename containertype::iterator row_begin, row_end, row_current;
- typename containertype::value_type::TWOD_ITER_ col_current;
-};
-
-// The same thing again, but this time const. :-(
-template <class containertype>
-class const_two_d_iterator {
- public:
- typedef const_two_d_iterator iterator;
-
- typedef std::bidirectional_iterator_tag iterator_category;
- // apparently some versions of VC++ have trouble with two ::'s in a typename
- typedef typename containertype::value_type _tmp_vt;
- typedef typename _tmp_vt::value_type value_type;
- typedef typename _tmp_vt::difference_type difference_type;
- typedef typename _tmp_vt::const_reference reference;
- typedef typename _tmp_vt::const_pointer pointer;
-
- const_two_d_iterator(typename containertype::const_iterator begin,
- typename containertype::const_iterator end,
- typename containertype::const_iterator curr)
- : row_begin(begin), row_end(end), row_current(curr), col_current() {
- if ( curr != end ) {
- col_current = curr->TWOD_BEGIN_();
- advance_past_end(); // in case cur->begin() == cur->end()
- }
- }
- const_two_d_iterator(typename containertype::const_iterator begin,
- typename containertype::const_iterator end,
- typename containertype::const_iterator curr,
- typename containertype::value_type::TWOD_CONST_ITER_ col)
- : row_begin(begin), row_end(end), row_current(curr), col_current(col) {
- advance_past_end(); // in case cur->begin() == cur->end()
- }
- const_two_d_iterator()
- : row_begin(), row_end(), row_current(), col_current() {
- }
- // Need this explicitly so we can convert normal iterators to const iterators
- // TODO(user): explicit?
- const_two_d_iterator(const two_d_iterator<containertype>& it) :
- row_begin(it.row_begin), row_end(it.row_end), row_current(it.row_current),
- col_current(it.col_current) { }
-
- typename containertype::const_iterator row_begin, row_end, row_current;
- typename containertype::value_type::TWOD_CONST_ITER_ col_current;
-
-
- // EVERYTHING FROM HERE DOWN IS THE SAME AS THE NON-CONST ITERATOR
- reference operator*() const { return *col_current; }
- pointer operator->() const { return &(operator*()); }
-
- void advance_past_end() { // used when col_current points to end()
- while ( col_current == row_current->TWOD_END_() ) { // end of current row
- ++row_current; // go to beginning of next
- if ( row_current != row_end ) // col is irrelevant at end
- col_current = row_current->TWOD_BEGIN_();
- else
- break; // don't go past row_end
- }
- }
- iterator& operator++() {
- assert(row_current != row_end); // how to ++ from there?
- ++col_current;
- advance_past_end(); // in case col_current is at end()
- return *this;
- }
- iterator& operator--() {
- while ( row_current == row_end ||
- col_current == row_current->TWOD_BEGIN_() ) {
- assert(row_current != row_begin);
- --row_current;
- col_current = row_current->TWOD_END_(); // this is 1 too far
- }
- --col_current;
- return *this;
- }
- iterator operator++(int) { iterator tmp(*this); ++*this; return tmp; }
- iterator operator--(int) { iterator tmp(*this); --*this; return tmp; }
-
- bool operator==(const iterator& it) const {
- return ( row_begin == it.row_begin &&
- row_end == it.row_end &&
- row_current == it.row_current &&
- (row_current == row_end || col_current == it.col_current) );
- }
- bool operator!=(const iterator& it) const { return !(*this == it); }
-};
-
-// We provide yet another version, to be as frugal with memory as
-// possible. This one frees each block of memory as it finishes
-// iterating over it. By the end, the entire table is freed.
-// For understandable reasons, you can only iterate over it once,
-// which is why it's an input iterator
-template <class containertype>
-class destructive_two_d_iterator {
- public:
- typedef destructive_two_d_iterator iterator;
-
- typedef std::input_iterator_tag iterator_category;
- // apparently some versions of VC++ have trouble with two ::'s in a typename
- typedef typename containertype::value_type _tmp_vt;
- typedef typename _tmp_vt::value_type value_type;
- typedef typename _tmp_vt::difference_type difference_type;
- typedef typename _tmp_vt::reference reference;
- typedef typename _tmp_vt::pointer pointer;
-
- destructive_two_d_iterator(typename containertype::iterator begin,
- typename containertype::iterator end,
- typename containertype::iterator curr)
- : row_begin(begin), row_end(end), row_current(curr), col_current() {
- if ( curr != end ) {
- col_current = curr->TWOD_BEGIN_();
- advance_past_end(); // in case cur->begin() == cur->end()
- }
- }
- destructive_two_d_iterator(typename containertype::iterator begin,
- typename containertype::iterator end,
- typename containertype::iterator curr,
- typename containertype::value_type::TWOD_ITER_ col)
- : row_begin(begin), row_end(end), row_current(curr), col_current(col) {
- advance_past_end(); // in case cur->begin() == cur->end()
- }
- destructive_two_d_iterator()
- : row_begin(), row_end(), row_current(), col_current() {
- }
-
- typename containertype::iterator row_begin, row_end, row_current;
- typename containertype::value_type::TWOD_ITER_ col_current;
-
- // This is the part that destroys
- void advance_past_end() { // used when col_current points to end()
- while ( col_current == row_current->TWOD_END_() ) { // end of current row
- row_current->clear(); // the destructive part
- // It would be nice if we could decrement sparsetable->num_buckets here
- ++row_current; // go to beginning of next
- if ( row_current != row_end ) // col is irrelevant at end
- col_current = row_current->TWOD_BEGIN_();
- else
- break; // don't go past row_end
- }
- }
-
- // EVERYTHING FROM HERE DOWN IS THE SAME AS THE REGULAR ITERATOR
- reference operator*() const { return *col_current; }
- pointer operator->() const { return &(operator*()); }
-
- iterator& operator++() {
- assert(row_current != row_end); // how to ++ from there?
- ++col_current;
- advance_past_end(); // in case col_current is at end()
- return *this;
- }
- iterator operator++(int) { iterator tmp(*this); ++*this; return tmp; }
-
- bool operator==(const iterator& it) const {
- return ( row_begin == it.row_begin &&
- row_end == it.row_end &&
- row_current == it.row_current &&
- (row_current == row_end || col_current == it.col_current) );
- }
- bool operator!=(const iterator& it) const { return !(*this == it); }
-};
-
-#undef TWOD_BEGIN_
-#undef TWOD_END_
-#undef TWOD_ITER_
-#undef TWOD_CONST_ITER_
-
-
-
-
-// SPARSE-TABLE
-// ------------
-// The idea is that a table with (logically) t buckets is divided
-// into t/M *groups* of M buckets each. (M is a constant set in
-// GROUP_SIZE for efficiency.) Each group is stored sparsely.
-// Thus, inserting into the table causes some array to grow, which is
-// slow but still constant time. Lookup involves doing a
-// logical-position-to-sparse-position lookup, which is also slow but
-// constant time. The larger M is, the slower these operations are
-// but the less overhead (slightly).
-//
-// To store the sparse array, we store a bitmap B, where B[i] = 1 iff
-// bucket i is non-empty. Then to look up bucket i we really look up
-// array[# of 1s before i in B]. This is constant time for fixed M.
-//
-// Terminology: the position of an item in the overall table (from
-// 1 .. t) is called its "location." The logical position in a group
-// (from 1 .. M ) is called its "position." The actual location in
-// the array (from 1 .. # of non-empty buckets in the group) is
-// called its "offset."
-
-// The weird mod in the offset is entirely to quiet compiler warnings
-// as is the cast to int after doing the "x mod 256"
-#define PUT_(take_from, offset) do { \
- if (putc(static_cast<int>(((take_from) >> ((offset) % (sizeof(take_from)*8)))\
- % 256), fp) \
- == EOF) \
- return false; \
-} while (0)
-
-#define GET_(add_to, offset) do { \
- if ((x=getc(fp)) == EOF) \
- return false; \
- else \
- add_to |= (static_cast<size_type>(x) << ((offset) % (sizeof(add_to)*8))); \
-} while (0)
-
-template <class T, u_int16_t GROUP_SIZE, class Alloc>
-class sparsegroup {
- private:
- typedef typename Alloc::template rebind<T>::other value_alloc_type;
-
- public:
- // Basic types
- typedef T value_type;
- typedef Alloc allocator_type;
- typedef typename value_alloc_type::reference reference;
- typedef typename value_alloc_type::const_reference const_reference;
- typedef typename value_alloc_type::pointer pointer;
- typedef typename value_alloc_type::const_pointer const_pointer;
-
- typedef table_iterator<sparsegroup<T, GROUP_SIZE, Alloc> > iterator;
- typedef const_table_iterator<sparsegroup<T, GROUP_SIZE, Alloc> >
- const_iterator;
- typedef table_element_adaptor<sparsegroup<T, GROUP_SIZE, Alloc> >
- element_adaptor;
- typedef u_int16_t size_type; // max # of buckets
- typedef int16_t difference_type;
- typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
- typedef std::reverse_iterator<iterator> reverse_iterator; // from iterator.h
-
- // These are our special iterators, that go over non-empty buckets in a
- // group. These aren't const-only because you can change non-empty bcks.
- typedef pointer nonempty_iterator;
- typedef const_pointer const_nonempty_iterator;
- typedef std::reverse_iterator<nonempty_iterator> reverse_nonempty_iterator;
- typedef std::reverse_iterator<const_nonempty_iterator>
- const_reverse_nonempty_iterator;
-
- // Iterator functions
- iterator begin() { return iterator(this, 0); }
- const_iterator begin() const { return const_iterator(this, 0); }
- iterator end() { return iterator(this, size()); }
- const_iterator end() const { return const_iterator(this, size()); }
- reverse_iterator rbegin() { return reverse_iterator(end()); }
- const_reverse_iterator rbegin() const {
- return const_reverse_iterator(end());
- }
- reverse_iterator rend() { return reverse_iterator(begin()); }
- const_reverse_iterator rend() const {
- return const_reverse_iterator(begin());
- }
-
- // We'll have versions for our special non-empty iterator too
- nonempty_iterator nonempty_begin() { return group; }
- const_nonempty_iterator nonempty_begin() const { return group; }
- nonempty_iterator nonempty_end() {
- return group + settings.num_buckets;
- }
- const_nonempty_iterator nonempty_end() const {
- return group + settings.num_buckets;
- }
- reverse_nonempty_iterator nonempty_rbegin() {
- return reverse_nonempty_iterator(nonempty_end());
- }
- const_reverse_nonempty_iterator nonempty_rbegin() const {
- return const_reverse_nonempty_iterator(nonempty_end());
- }
- reverse_nonempty_iterator nonempty_rend() {
- return reverse_nonempty_iterator(nonempty_begin());
- }
- const_reverse_nonempty_iterator nonempty_rend() const {
- return const_reverse_nonempty_iterator(nonempty_begin());
- }
-
-
- // This gives us the "default" value to return for an empty bucket.
- // We just use the default constructor on T, the template type
- const_reference default_value() const {
- static value_type defaultval = value_type();
- return defaultval;
- }
-
-
- private:
- // We need to do all this bit manipulation, of course. ick
- static size_type charbit(size_type i) { return i >> 3; }
- static size_type modbit(size_type i) { return 1 << (i&7); }
- int bmtest(size_type i) const { return bitmap[charbit(i)] & modbit(i); }
- void bmset(size_type i) { bitmap[charbit(i)] |= modbit(i); }
- void bmclear(size_type i) { bitmap[charbit(i)] &= ~modbit(i); }
-
- pointer allocate_group(size_type n) {
- pointer retval = settings.allocate(n);
- if (retval == NULL) {
- // We really should use PRIuS here, but I don't want to have to add
- // a whole new configure option, with concomitant macro namespace
- // pollution, just to print this (unlikely) error message. So I cast.
- fprintf(stderr, "sparsehash FATAL ERROR: failed to allocate %lu groups\n",
- static_cast<unsigned long>(n));
- exit(1);
- }
- return retval;
- }
-
- void free_group() {
- if (!group) return;
- pointer end_it = group + settings.num_buckets;
- for (pointer p = group; p != end_it; ++p)
- p->~value_type();
- settings.deallocate(group, settings.num_buckets);
- group = NULL;
- }
-
- static size_type bits_in_char(unsigned char c) {
- // We could make these ints. The tradeoff is size (eg does it overwhelm
- // the cache?) vs efficiency in referencing sub-word-sized array elements.
- static const char bits_in[256] = {
- 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
- 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
- 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
- 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
- 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
- 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
- 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
- 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
- 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
- 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
- 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
- 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
- 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
- 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
- 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
- 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,
- };
- return bits_in[c];
- }
-
- public: // get_iter() in sparsetable needs it
- // We need a small function that tells us how many set bits there are
- // in positions 0..i-1 of the bitmap. It uses a big table.
- // We make it static so templates don't allocate lots of these tables.
- // There are lots of ways to do this calculation (called 'popcount').
- // The 8-bit table lookup is one of the fastest, though this
- // implementation suffers from not doing any loop unrolling. See, eg,
- // http://www.dalkescientific.com/writings/diary/archive/2008/07/03/hakmem_and_other_popcounts.html
- // http://gurmeetsingh.wordpress.com/2008/08/05/fast-bit-counting-routines/
- static size_type pos_to_offset(const unsigned char *bm, size_type pos) {
- size_type retval = 0;
-
- // [Note: condition pos > 8 is an optimization; convince yourself we
- // give exactly the same result as if we had pos >= 8 here instead.]
- for ( ; pos > 8; pos -= 8 ) // bm[0..pos/8-1]
- retval += bits_in_char(*bm++); // chars we want *all* bits in
- return retval + bits_in_char(*bm & ((1 << pos)-1)); // char including pos
- }
-
- size_type pos_to_offset(size_type pos) const { // not static but still const
- return pos_to_offset(bitmap, pos);
- }
-
- // Returns the (logical) position in the bm[] array, i, such that
- // bm[i] is the offset-th set bit in the array. It is the inverse
- // of pos_to_offset. get_pos() uses this function to find the index
- // of an nonempty_iterator in the table. Bit-twiddling from
- // http://hackersdelight.org/basics.pdf
- static size_type offset_to_pos(const unsigned char *bm, size_type offset) {
- size_type retval = 0;
- // This is sizeof(this->bitmap).
- const size_type group_size = (GROUP_SIZE-1) / 8 + 1;
- for (size_type i = 0; i < group_size; i++) { // forward scan
- unsigned char pop_count = bits_in_char(*bm);
- if (pop_count > offset) {
- unsigned char last_bm = *bm;
- for (; offset > 0; offset--) {
- last_bm &= (last_bm-1); // remove right-most set bit
- }
- // Clear all bits to the left of the rightmost bit (the &),
- // and then clear the rightmost bit but set all bits to the
- // right of it (the -1).
- last_bm = (last_bm & -last_bm) - 1;
- retval += bits_in_char(last_bm);
- return retval;
- }
- offset -= pop_count;
- retval += 8;
- bm++;
- }
- return retval;
- }
-
- size_type offset_to_pos(size_type offset) const {
- return offset_to_pos(bitmap, offset);
- }
-
-
- public:
- // Constructors -- default and copy -- and destructor
- explicit sparsegroup(allocator_type& a) :
- group(0), settings(alloc_impl<value_alloc_type>(a)) {
- memset(bitmap, 0, sizeof(bitmap));
- }
- sparsegroup(const sparsegroup& x) : group(0), settings(x.settings) {
- if ( settings.num_buckets ) {
- group = allocate_group(x.settings.num_buckets);
- std::uninitialized_copy(x.group, x.group + x.settings.num_buckets, group);
- }
- memcpy(bitmap, x.bitmap, sizeof(bitmap));
- }
- ~sparsegroup() { free_group(); }
-
- // Operator= is just like the copy constructor, I guess
- // TODO(user): Make this exception safe. Handle exceptions in value_type's
- // copy constructor.
- sparsegroup &operator=(const sparsegroup& x) {
- if ( &x == this ) return *this; // x = x
- if ( x.settings.num_buckets == 0 ) {
- free_group();
- } else {
- pointer p = allocate_group(x.settings.num_buckets);
- std::uninitialized_copy(x.group, x.group + x.settings.num_buckets, p);
- free_group();
- group = p;
- }
- memcpy(bitmap, x.bitmap, sizeof(bitmap));
- settings.num_buckets = x.settings.num_buckets;
- return *this;
- }
-
- // Many STL algorithms use swap instead of copy constructors
- void swap(sparsegroup& x) {
- std::swap(group, x.group); // defined in <algorithm>
- for ( int i = 0; i < sizeof(bitmap) / sizeof(*bitmap); ++i )
- std::swap(bitmap[i], x.bitmap[i]); // swap not defined on arrays
- std::swap(settings.num_buckets, x.settings.num_buckets);
- // we purposefully don't swap the allocator, which may not be swap-able
- }
-
- // It's always nice to be able to clear a table without deallocating it
- void clear() {
- free_group();
- memset(bitmap, 0, sizeof(bitmap));
- settings.num_buckets = 0;
- }
-
- // Functions that tell you about size. Alas, these aren't so useful
- // because our table is always fixed size.
- size_type size() const { return GROUP_SIZE; }
- size_type max_size() const { return GROUP_SIZE; }
- bool empty() const { return false; }
- // We also may want to know how many *used* buckets there are
- size_type num_nonempty() const { return settings.num_buckets; }
-
-
- // get()/set() are explicitly const/non-const. You can use [] if
- // you want something that can be either (potentially more expensive).
- const_reference get(size_type i) const {
- if ( bmtest(i) ) // bucket i is occupied
- return group[pos_to_offset(bitmap, i)];
- else
- return default_value(); // return the default reference
- }
-
- // TODO(user): make protected + friend
- // This is used by sparse_hashtable to get an element from the table
- // when we know it exists.
- const_reference unsafe_get(size_type i) const {
- assert(bmtest(i));
- return group[pos_to_offset(bitmap, i)];
- }
-
- // TODO(user): make protected + friend
- reference mutating_get(size_type i) { // fills bucket i before getting
- if ( !bmtest(i) )
- set(i, default_value());
- return group[pos_to_offset(bitmap, i)];
- }
-
- // Syntactic sugar. It's easy to return a const reference. To
- // return a non-const reference, we need to use the assigner adaptor.
- const_reference operator[](size_type i) const {
- return get(i);
- }
-
- element_adaptor operator[](size_type i) {
- return element_adaptor(this, i);
- }
-
- private:
- // Create space at group[offset], assuming value_type has trivial
- // copy constructor and destructor, and the allocator_type is
- // the default libc_allocator_with_alloc. (Really, we want it to have
- // "trivial move", because that's what realloc and memmove both do.
- // But there's no way to capture that using type_traits, so we
- // pretend that move(x, y) is equivalent to "x.~T(); new(x) T(y);"
- // which is pretty much correct, if a bit conservative.)
- void set_aux(size_type offset, base::true_type) {
- group = settings.realloc_or_die(group, settings.num_buckets+1);
- // This is equivalent to memmove(), but faster on my Intel P4,
- // at least with gcc4.1 -O2 / glibc 2.3.6.
- for (size_type i = settings.num_buckets; i > offset; --i)
- memcpy(group + i, group + i-1, sizeof(*group));
- }
-
- // Create space at group[offset], without special assumptions about value_type
- // and allocator_type.
- void set_aux(size_type offset, base::false_type) {
- // This is valid because 0 <= offset <= num_buckets
- pointer p = allocate_group(settings.num_buckets + 1);
- std::uninitialized_copy(group, group + offset, p);
- std::uninitialized_copy(group + offset, group + settings.num_buckets,
- p + offset + 1);
- free_group();
- group = p;
- }
-
- public:
- // This returns a reference to the inserted item (which is a copy of val).
- // TODO(user): Make this exception safe: handle exceptions from
- // value_type's copy constructor.
- reference set(size_type i, const_reference val) {
- size_type offset =
- pos_to_offset(bitmap, i); // where we'll find (or insert)
- if ( bmtest(i) ) {
- // Delete the old value, which we're replacing with the new one
- group[offset].~value_type();
- } else {
- typedef base::integral_constant<bool,
- (base::has_trivial_copy<value_type>::value &&
- base::has_trivial_destructor<value_type>::value &&
- base::is_same<
- allocator_type,
- libc_allocator_with_realloc<value_type> >::value)>
- realloc_and_memmove_ok; // we pretend mv(x,y) == "x.~T(); new(x) T(y)"
- set_aux(offset, realloc_and_memmove_ok());
- ++settings.num_buckets;
- bmset(i);
- }
- // This does the actual inserting. Since we made the array using
- // malloc, we use "placement new" to just call the constructor.
- new(&group[offset]) value_type(val);
- return group[offset];
- }
-
- // We let you see if a bucket is non-empty without retrieving it
- bool test(size_type i) const {
- return bmtest(i) != 0;
- }
- bool test(iterator pos) const {
- return bmtest(pos.pos) != 0;
- }
-
- private:
- // Shrink the array, assuming value_type has trivial copy
- // constructor and destructor, and the allocator_type is the default
- // libc_allocator_with_alloc. (Really, we want it to have "trivial
- // move", because that's what realloc and memmove both do. But
- // there's no way to capture that using type_traits, so we pretend
- // that move(x, y) is equivalent to ""x.~T(); new(x) T(y);"
- // which is pretty much correct, if a bit conservative.)
- void erase_aux(size_type offset, base::true_type) {
- // This isn't technically necessary, since we know we have a
- // trivial destructor, but is a cheap way to get a bit more safety.
- group[offset].~value_type();
- // This is equivalent to memmove(), but faster on my Intel P4,
- // at lesat with gcc4.1 -O2 / glibc 2.3.6.
- assert(settings.num_buckets > 0);
- for (size_type i = offset; i < settings.num_buckets-1; ++i)
- memcpy(group + i, group + i+1, sizeof(*group)); // hopefully inlined!
- group = settings.realloc_or_die(group, settings.num_buckets-1);
- }
-
- // Shrink the array, without any special assumptions about value_type and
- // allocator_type.
- void erase_aux(size_type offset, base::false_type) {
- // This is valid because 0 <= offset < num_buckets. Note the inequality.
- pointer p = allocate_group(settings.num_buckets - 1);
- std::uninitialized_copy(group, group + offset, p);
- std::uninitialized_copy(group + offset + 1, group + settings.num_buckets,
- p + offset);
- free_group();
- group = p;
- }
-
- public:
- // This takes the specified elements out of the group. This is
- // "undefining", rather than "clearing".
- // TODO(user): Make this exception safe: handle exceptions from
- // value_type's copy constructor.
- void erase(size_type i) {
- if ( bmtest(i) ) { // trivial to erase empty bucket
- size_type offset =
- pos_to_offset(bitmap, i); // where we'll find (or insert)
- if ( settings.num_buckets == 1 ) {
- free_group();
- group = NULL;
- } else {
- typedef base::integral_constant<bool,
- (base::has_trivial_copy<value_type>::value &&
- base::has_trivial_destructor<value_type>::value &&
- base::is_same<
- allocator_type,
- libc_allocator_with_realloc<value_type> >::value)>
- realloc_and_memmove_ok; // pretend mv(x,y) == "x.~T(); new(x) T(y)"
- erase_aux(offset, realloc_and_memmove_ok());
- }
- --settings.num_buckets;
- bmclear(i);
- }
- }
-
- void erase(iterator pos) {
- erase(pos.pos);
- }
-
- void erase(iterator start_it, iterator end_it) {
- // This could be more efficient, but to do so we'd need to make
- // bmclear() clear a range of indices. Doesn't seem worth it.
- for ( ; start_it != end_it; ++start_it )
- erase(start_it);
- }
-
-
- // I/O
- // We support reading and writing groups to disk. We don't store
- // the actual array contents (which we don't know how to store),
- // just the bitmap and size. Meant to be used with table I/O.
-
- // Returns true if all was ok.
- bool write_metadata(FILE *fp) const {
- // we explicitly set to u_int16_t
- assert(sizeof(settings.num_buckets) == 2);
- PUT_(settings.num_buckets, 8);
- PUT_(settings.num_buckets, 0);
- if ( !fwrite(bitmap, sizeof(bitmap), 1, fp) )
- return false;
- return true;
- }
-
- // Reading destroys the old group contents! Returns true if all was ok.
- bool read_metadata(FILE *fp) {
- clear();
-
- int x; // the GET_ macro requires an 'int x' to be defined
- GET_(settings.num_buckets, 8);
- GET_(settings.num_buckets, 0);
-
- if ( !fread(bitmap, sizeof(bitmap), 1, fp) ) return false;
-
- // We'll allocate the space, but we won't fill it: it will be
- // left as uninitialized raw memory.
- group = allocate_group(settings.num_buckets);
- return true;
- }
-
- // If your keys and values are simple enough, we can write them
- // to disk for you. "simple enough" means POD and no pointers.
- // However, we don't try to normalize endianness.
- bool write_nopointer_data(FILE *fp) const {
- for ( const_nonempty_iterator it = nonempty_begin();
- it != nonempty_end(); ++it ) {
- if ( !fwrite(&*it, sizeof(*it), 1, fp) ) return false;
- }
- return true;
- }
-
- // When reading, we have to override the potential const-ness of *it.
- // Again, only meaningful if value_type is a POD.
- bool read_nopointer_data(FILE *fp) {
- for ( nonempty_iterator it = nonempty_begin();
- it != nonempty_end(); ++it ) {
- if ( !fread(reinterpret_cast<void*>(&(*it)), sizeof(*it), 1, fp) )
- return false;
- }
- return true;
- }
-
-
- // Comparisons. We only need to define == and < -- we get
- // != > <= >= via relops.h (which we happily included above).
- // Note the comparisons are pretty arbitrary: we compare
- // values of the first index that isn't equal (using default
- // value for empty buckets).
- bool operator==(const sparsegroup& x) const {
- return ( settings.num_buckets == x.settings.num_buckets &&
- memcmp(bitmap, x.bitmap, sizeof(bitmap)) == 0 &&
- std::equal(begin(), end(), x.begin()) ); // from <algorithm>
- }
-
- bool operator<(const sparsegroup& x) const { // also from <algorithm>
- return std::lexicographical_compare(begin(), end(), x.begin(), x.end());
- }
- bool operator!=(const sparsegroup& x) const { return !(*this == x); }
- bool operator<=(const sparsegroup& x) const { return !(x < *this); }
- bool operator>(const sparsegroup& x) const { return x < *this; }
- bool operator>=(const sparsegroup& x) const { return !(*this < x); }
-
- private:
- template <class A>
- class alloc_impl : public A {
- public:
- typedef typename A::pointer pointer;
- typedef typename A::size_type size_type;
-
- // Convert a normal allocator to one that has realloc_or_die()
- alloc_impl(const A& a) : A(a) {} // TODO(user): explicit?
-
- // realloc_or_die should only be used when using the default
- // allocator (libc_allocator_with_realloc).
- pointer realloc_or_die(pointer /*ptr*/, size_type /*n*/) {
- fprintf(stderr, "realloc_or_die is only supported for "
- "libc_allocator_with_realloc\n");
- exit(1);
- return NULL;
- }
- };
-
- // A template specialization of alloc_impl for
- // libc_allocator_with_realloc that can handle realloc_or_die.
- template <class A>
- class alloc_impl<libc_allocator_with_realloc<A> >
- : public libc_allocator_with_realloc<A> {
- public:
- typedef typename libc_allocator_with_realloc<A>::pointer pointer;
- typedef typename libc_allocator_with_realloc<A>::size_type size_type;
-
- alloc_impl(const libc_allocator_with_realloc<A>& a)
- : libc_allocator_with_realloc<A>(a) { }
-
- pointer realloc_or_die(pointer ptr, size_type n) {
- pointer retval = this->reallocate(ptr, n);
- if (retval == NULL) {
- fprintf(stderr, "sparsehash: FATAL ERROR: failed to reallocate "
- "%lu elements for ptr %p", static_cast<unsigned long>(n), ptr);
- exit(1);
- }
- return retval;
- }
- };
-
- // Package allocator with num_buckets to eliminate memory needed for the
- // zero-size allocator.
- // If new fields are added to this class, we should add them to
- // operator= and swap.
- class Settings : public alloc_impl<value_alloc_type> {
- public:
- Settings(const alloc_impl<value_alloc_type>& a, u_int16_t n = 0)
- : alloc_impl<value_alloc_type>(a), num_buckets(n) { }
- Settings(const Settings& s)
- : alloc_impl<value_alloc_type>(s), num_buckets(s.num_buckets) { }
-
- u_int16_t num_buckets; // limits GROUP_SIZE to 64K
- };
-
- // The actual data
- pointer group; // (small) array of T's
- Settings settings; // allocator and num_buckets
- unsigned char bitmap[(GROUP_SIZE-1)/8 + 1]; // fancy math is so we round up
-};
-
-// We need a global swap as well
-template <class T, u_int16_t GROUP_SIZE, class Alloc>
-inline void swap(sparsegroup<T, GROUP_SIZE, Alloc> &x,
- sparsegroup<T, GROUP_SIZE, Alloc> &y) {
- x.swap(y);
-}
-
-// ---------------------------------------------------------------------------
-
-
-template <class T, u_int16_t GROUP_SIZE = DEFAULT_SPARSEGROUP_SIZE,
- class Alloc = libc_allocator_with_realloc<T> >
-class sparsetable {
- private:
- typedef typename Alloc::template rebind<T>::other value_alloc_type;
- typedef typename Alloc::template rebind<
- sparsegroup<T, GROUP_SIZE, value_alloc_type> >::other vector_alloc;
-
- public:
- // Basic types
- typedef T value_type; // stolen from stl_vector.h
- typedef Alloc allocator_type;
- typedef typename value_alloc_type::size_type size_type;
- typedef typename value_alloc_type::difference_type difference_type;
- typedef typename value_alloc_type::reference reference;
- typedef typename value_alloc_type::const_reference const_reference;
- typedef typename value_alloc_type::pointer pointer;
- typedef typename value_alloc_type::const_pointer const_pointer;
- typedef table_iterator<sparsetable<T, GROUP_SIZE, Alloc> > iterator;
- typedef const_table_iterator<sparsetable<T, GROUP_SIZE, Alloc> >
- const_iterator;
- typedef table_element_adaptor<sparsetable<T, GROUP_SIZE, Alloc> >
- element_adaptor;
- typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
- typedef std::reverse_iterator<iterator> reverse_iterator; // from iterator.h
-
- // These are our special iterators, that go over non-empty buckets in a
- // table. These aren't const only because you can change non-empty bcks.
- typedef two_d_iterator<
- std::vector< sparsegroup<value_type, GROUP_SIZE, value_alloc_type>,
- vector_alloc> >
- nonempty_iterator;
- typedef const_two_d_iterator<
- std::vector< sparsegroup<value_type, GROUP_SIZE, value_alloc_type>,
- vector_alloc> >
- const_nonempty_iterator;
- typedef std::reverse_iterator<nonempty_iterator> reverse_nonempty_iterator;
- typedef std::reverse_iterator<const_nonempty_iterator>
- const_reverse_nonempty_iterator;
- // Another special iterator: it frees memory as it iterates (used to resize)
- typedef destructive_two_d_iterator<
- std::vector< sparsegroup<value_type, GROUP_SIZE, value_alloc_type >,
- vector_alloc> >
- destructive_iterator;
-
- // Iterator functions
- iterator begin() { return iterator(this, 0); }
- const_iterator begin() const { return const_iterator(this, 0); }
- iterator end() { return iterator(this, size()); }
- const_iterator end() const { return const_iterator(this, size()); }
- reverse_iterator rbegin() { return reverse_iterator(end()); }
- const_reverse_iterator rbegin() const {
- return const_reverse_iterator(end());
- }
- reverse_iterator rend() { return reverse_iterator(begin()); }
- const_reverse_iterator rend() const {
- return const_reverse_iterator(begin());
- }
-
- // Versions for our special non-empty iterator
- nonempty_iterator nonempty_begin() {
- return nonempty_iterator(groups.begin(), groups.end(), groups.begin());
- }
- const_nonempty_iterator nonempty_begin() const {
- return
- const_nonempty_iterator(groups.begin(), groups.end(), groups.begin());
- }
- nonempty_iterator nonempty_end() {
- return nonempty_iterator(groups.begin(), groups.end(), groups.end());
- }
- const_nonempty_iterator nonempty_end() const {
- return const_nonempty_iterator(groups.begin(), groups.end(), groups.end());
- }
- reverse_nonempty_iterator nonempty_rbegin() {
- return reverse_nonempty_iterator(nonempty_end());
- }
- const_reverse_nonempty_iterator nonempty_rbegin() const {
- return const_reverse_nonempty_iterator(nonempty_end());
- }
- reverse_nonempty_iterator nonempty_rend() {
- return reverse_nonempty_iterator(nonempty_begin());
- }
- const_reverse_nonempty_iterator nonempty_rend() const {
- return const_reverse_nonempty_iterator(nonempty_begin());
- }
- destructive_iterator destructive_begin() {
- return destructive_iterator(groups.begin(), groups.end(), groups.begin());
- }
- destructive_iterator destructive_end() {
- return destructive_iterator(groups.begin(), groups.end(), groups.end());
- }
-
- typedef sparsegroup<value_type, GROUP_SIZE, allocator_type> group_type;
- typedef std::vector<group_type, vector_alloc > group_vector_type;
-
- typedef typename group_vector_type::reference GroupsReference;
- typedef typename group_vector_type::const_reference GroupsConstReference;
- typedef typename group_vector_type::iterator GroupsIterator;
- typedef typename group_vector_type::const_iterator GroupsConstIterator;
-
- // How to deal with the proper group
- static size_type num_groups(size_type num) { // how many to hold num buckets
- return num == 0 ? 0 : ((num-1) / GROUP_SIZE) + 1;
- }
-
- u_int16_t pos_in_group(size_type i) const {
- return static_cast<u_int16_t>(i % GROUP_SIZE);
- }
- size_type group_num(size_type i) const {
- return i / GROUP_SIZE;
- }
- GroupsReference which_group(size_type i) {
- return groups[group_num(i)];
- }
- GroupsConstReference which_group(size_type i) const {
- return groups[group_num(i)];
- }
-
- public:
- // Constructors -- default, normal (when you specify size), and copy
- explicit sparsetable(size_type sz = 0, Alloc alloc = Alloc())
- : groups(vector_alloc(alloc)), settings(alloc, sz) {
- groups.resize(num_groups(sz), group_type(settings));
- }
- // We can get away with using the default copy constructor,
- // and default destructor, and hence the default operator=. Huzzah!
-
- // Many STL algorithms use swap instead of copy constructors
- void swap(sparsetable& x) {
- std::swap(groups, x.groups); // defined in stl_algobase.h
- std::swap(settings.table_size, x.settings.table_size);
- std::swap(settings.num_buckets, x.settings.num_buckets);
- }
-
- // It's always nice to be able to clear a table without deallocating it
- void clear() {
- GroupsIterator group;
- for ( group = groups.begin(); group != groups.end(); ++group ) {
- group->clear();
- }
- settings.num_buckets = 0;
- }
-
- // ACCESSOR FUNCTIONS for the things we templatize on, basically
- allocator_type get_allocator() const {
- return allocator_type(settings);
- }
-
-
- // Functions that tell you about size.
- // NOTE: empty() is non-intuitive! It does not tell you the number
- // of not-empty buckets (use num_nonempty() for that). Instead
- // it says whether you've allocated any buckets or not.
- size_type size() const { return settings.table_size; }
- size_type max_size() const { return settings.max_size(); }
- bool empty() const { return settings.table_size == 0; }
- // We also may want to know how many *used* buckets there are
- size_type num_nonempty() const { return settings.num_buckets; }
-
- // OK, we'll let you resize one of these puppies
- void resize(size_type new_size) {
- groups.resize(num_groups(new_size), group_type(settings));
- if ( new_size < settings.table_size ) {
- // lower num_buckets, clear last group
- if ( pos_in_group(new_size) > 0 ) // need to clear inside last group
- groups.back().erase(groups.back().begin() + pos_in_group(new_size),
- groups.back().end());
- settings.num_buckets = 0; // refigure # of used buckets
- GroupsConstIterator group;
- for ( group = groups.begin(); group != groups.end(); ++group )
- settings.num_buckets += group->num_nonempty();
- }
- settings.table_size = new_size;
- }
-
-
- // We let you see if a bucket is non-empty without retrieving it
- bool test(size_type i) const {
- assert(i < settings.table_size);
- return which_group(i).test(pos_in_group(i));
- }
- bool test(iterator pos) const {
- return which_group(pos.pos).test(pos_in_group(pos.pos));
- }
- bool test(const_iterator pos) const {
- return which_group(pos.pos).test(pos_in_group(pos.pos));
- }
-
- // We only return const_references because it's really hard to
- // return something settable for empty buckets. Use set() instead.
- const_reference get(size_type i) const {
- assert(i < settings.table_size);
- return which_group(i).get(pos_in_group(i));
- }
-
- // TODO(user): make protected + friend
- // This is used by sparse_hashtable to get an element from the table
- // when we know it exists (because the caller has called test(i)).
- const_reference unsafe_get(size_type i) const {
- assert(i < settings.table_size);
- assert(test(i));
- return which_group(i).unsafe_get(pos_in_group(i));
- }
-
- // TODO(user): make protected + friend element_adaptor
- reference mutating_get(size_type i) { // fills bucket i before getting
- assert(i < settings.table_size);
- size_type old_numbuckets = which_group(i).num_nonempty();
- reference retval = which_group(i).mutating_get(pos_in_group(i));
- settings.num_buckets += which_group(i).num_nonempty() - old_numbuckets;
- return retval;
- }
-
- // Syntactic sugar. As in sparsegroup, the non-const version is harder
- const_reference operator[](size_type i) const {
- return get(i);
- }
-
- element_adaptor operator[](size_type i) {
- return element_adaptor(this, i);
- }
-
- // Needed for hashtables, gets as a nonempty_iterator. Crashes for empty bcks
- const_nonempty_iterator get_iter(size_type i) const {
- assert(test(i)); // how can a nonempty_iterator point to an empty bucket?
- return const_nonempty_iterator(
- groups.begin(), groups.end(),
- groups.begin() + group_num(i),
- (groups[group_num(i)].nonempty_begin() +
- groups[group_num(i)].pos_to_offset(pos_in_group(i))));
- }
- // For nonempty we can return a non-const version
- nonempty_iterator get_iter(size_type i) {
- assert(test(i)); // how can a nonempty_iterator point to an empty bucket?
- return nonempty_iterator(
- groups.begin(), groups.end(),
- groups.begin() + group_num(i),
- (groups[group_num(i)].nonempty_begin() +
- groups[group_num(i)].pos_to_offset(pos_in_group(i))));
- }
-
- // And the reverse transformation.
- size_type get_pos(const const_nonempty_iterator it) const {
- difference_type current_row = it.row_current - it.row_begin;
- difference_type current_col = (it.col_current -
- groups[current_row].nonempty_begin());
- return ((current_row * GROUP_SIZE) +
- groups[current_row].offset_to_pos(current_col));
- }
-
-
- // This returns a reference to the inserted item (which is a copy of val)
- // The trick is to figure out whether we're replacing or inserting anew
- reference set(size_type i, const_reference val) {
- assert(i < settings.table_size);
- size_type old_numbuckets = which_group(i).num_nonempty();
- reference retval = which_group(i).set(pos_in_group(i), val);
- settings.num_buckets += which_group(i).num_nonempty() - old_numbuckets;
- return retval;
- }
-
- // This takes the specified elements out of the table. This is
- // "undefining", rather than "clearing".
- void erase(size_type i) {
- assert(i < settings.table_size);
- size_type old_numbuckets = which_group(i).num_nonempty();
- which_group(i).erase(pos_in_group(i));
- settings.num_buckets += which_group(i).num_nonempty() - old_numbuckets;
- }
-
- void erase(iterator pos) {
- erase(pos.pos);
- }
-
- void erase(iterator start_it, iterator end_it) {
- // This could be more efficient, but then we'd need to figure
- // out if we spanned groups or not. Doesn't seem worth it.
- for ( ; start_it != end_it; ++start_it )
- erase(start_it);
- }
-
-
- // We support reading and writing tables to disk. We don't store
- // the actual array contents (which we don't know how to store),
- // just the groups and sizes. Returns true if all went ok.
-
- private:
- // Every time the disk format changes, this should probably change too
- typedef unsigned long MagicNumberType;
- static const MagicNumberType MAGIC_NUMBER = 0x24687531;
-
- // Old versions of this code write all data in 32 bits. We need to
- // support these files as well as having support for 64-bit systems.
- // So we use the following encoding scheme: for values < 2^32-1, we
- // store in 4 bytes in big-endian order. For values > 2^32, we
- // store 0xFFFFFFF followed by 8 bytes in big-endian order. This
- // causes us to mis-read old-version code that stores exactly
- // 0xFFFFFFF, but I don't think that is likely to have happened for
- // these particular values.
- template <typename IntType>
- static bool write_32_or_64(FILE* fp, IntType value) {
- if ( value < 0xFFFFFFFFULL ) { // fits in 4 bytes
- PUT_(value, 24);
- PUT_(value, 16);
- PUT_(value, 8);
- PUT_(value, 0);
- } else if ( value == 0xFFFFFFFFUL ) { // special case in 32bit systems
- PUT_(0xFF, 0); PUT_(0xFF, 0); PUT_(0xFF, 0); PUT_(0xFF, 0); // marker
- PUT_(0, 0); PUT_(0, 0); PUT_(0, 0); PUT_(0, 0);
- PUT_(0xFF, 0); PUT_(0xFF, 0); PUT_(0xFF, 0); PUT_(0xFF, 0);
- } else {
- PUT_(0xFF, 0); PUT_(0xFF, 0); PUT_(0xFF, 0); PUT_(0xFF, 0); // marker
- PUT_(value, 56);
- PUT_(value, 48);
- PUT_(value, 40);
- PUT_(value, 32);
- PUT_(value, 24);
- PUT_(value, 16);
- PUT_(value, 8);
- PUT_(value, 0);
- }
- return true;
- }
-
- template <typename IntType>
- static bool read_32_or_64(FILE* fp, IntType *value) { // reads into value
- size_type first4 = 0;
- int x;
- GET_(first4, 24);
- GET_(first4, 16);
- GET_(first4, 8);
- GET_(first4, 0);
- if ( first4 < 0xFFFFFFFFULL ) {
- *value = first4;
- } else {
- GET_(*value, 56);
- GET_(*value, 48);
- GET_(*value, 40);
- GET_(*value, 32);
- GET_(*value, 24);
- GET_(*value, 16);
- GET_(*value, 8);
- GET_(*value, 0);
- }
- return true;
- }
-
- public:
- bool write_metadata(FILE *fp) const {
- if ( !write_32_or_64(fp, MAGIC_NUMBER) ) return false;
- if ( !write_32_or_64(fp, settings.table_size) ) return false;
- if ( !write_32_or_64(fp, settings.num_buckets) ) return false;
-
- GroupsConstIterator group;
- for ( group = groups.begin(); group != groups.end(); ++group )
- if ( group->write_metadata(fp) == false ) return false;
- return true;
- }
-
- // Reading destroys the old table contents! Returns true if read ok.
- bool read_metadata(FILE *fp) {
- size_type magic_read = 0;
- if ( !read_32_or_64(fp, &magic_read) ) return false;
- if ( magic_read != MAGIC_NUMBER ) {
- clear(); // just to be consistent
- return false;
- }
-
- if ( !read_32_or_64(fp, &settings.table_size) ) return false;
- if ( !read_32_or_64(fp, &settings.num_buckets) ) return false;
-
- resize(settings.table_size); // so the vector's sized ok
- GroupsIterator group;
- for ( group = groups.begin(); group != groups.end(); ++group )
- if ( group->read_metadata(fp) == false ) return false;
- return true;
- }
-
- // This code is identical to that for SparseGroup
- // If your keys and values are simple enough, we can write them
- // to disk for you. "simple enough" means no pointers.
- // However, we don't try to normalize endianness
- bool write_nopointer_data(FILE *fp) const {
- for ( const_nonempty_iterator it = nonempty_begin();
- it != nonempty_end(); ++it ) {
- if ( !fwrite(&*it, sizeof(*it), 1, fp) ) return false;
- }
- return true;
- }
-
- // When reading, we have to override the potential const-ness of *it
- bool read_nopointer_data(FILE *fp) {
- for ( nonempty_iterator it = nonempty_begin();
- it != nonempty_end(); ++it ) {
- if ( !fread(reinterpret_cast<void*>(&(*it)), sizeof(*it), 1, fp) )
- return false;
- }
- return true;
- }
-
-
- // Comparisons. Note the comparisons are pretty arbitrary: we
- // compare values of the first index that isn't equal (using default
- // value for empty buckets).
- bool operator==(const sparsetable& x) const {
- return settings.table_size == x.settings.table_size &&
- settings.num_buckets == x.settings.num_buckets &&
- groups == x.groups;
- }
-
- bool operator<(const sparsetable& x) const {
- return std::lexicographical_compare(begin(), end(), x.begin(), x.end());
- }
- bool operator!=(const sparsetable& x) const { return !(*this == x); }
- bool operator<=(const sparsetable& x) const { return !(x < *this); }
- bool operator>(const sparsetable& x) const { return x < *this; }
- bool operator>=(const sparsetable& x) const { return !(*this < x); }
-
-
- private:
- // Package allocator with table_size and num_buckets to eliminate memory
- // needed for the zero-size allocator.
- // If new fields are added to this class, we should add them to
- // operator= and swap.
- class Settings : public allocator_type {
- public:
- typedef typename allocator_type::size_type size_type;
-
- Settings(const allocator_type& a, size_type sz = 0, size_type n = 0)
- : allocator_type(a), table_size(sz), num_buckets(n) { }
-
- Settings(const Settings& s)
- : allocator_type(s),
- table_size(s.table_size), num_buckets(s.num_buckets) { }
-
- size_type table_size; // how many buckets they want
- size_type num_buckets; // number of non-empty buckets
- };
-
- // The actual data
- group_vector_type groups; // our list of groups
- Settings settings; // allocator, table size, buckets
-};
-
-// We need a global swap as well
-template <class T, u_int16_t GROUP_SIZE, class Alloc>
-inline void swap(sparsetable<T, GROUP_SIZE, Alloc> &x,
- sparsetable<T, GROUP_SIZE, Alloc> &y) {
- x.swap(y);
-}
-
-#undef GET_
-#undef PUT_
-
-}
-
-#endif // UTIL_GTL_SPARSETABLE_H_
http://git-wip-us.apache.org/repos/asf/incubator-impala/blob/02f3e3fc/be/src/gutil/spinlock.cc
----------------------------------------------------------------------
diff --git a/be/src/gutil/spinlock.cc b/be/src/gutil/spinlock.cc
index a5ca7c6..8a02c95 100644
--- a/be/src/gutil/spinlock.cc
+++ b/be/src/gutil/spinlock.cc
@@ -32,11 +32,11 @@
* Author: Sanjay Ghemawat
*/
-#include "gutil/spinlock.h"
-#include "gutil/synchronization_profiling.h"
-#include "gutil/spinlock_internal.h"
-#include "gutil/walltime.h"
-#include "gutil/sysinfo.h" /* for NumCPUs() */
+#include "kudu/gutil/spinlock.h"
+#include "kudu/gutil/synchronization_profiling.h"
+#include "kudu/gutil/spinlock_internal.h"
+#include "kudu/gutil/walltime.h"
+#include "kudu/gutil/sysinfo.h" /* for NumCPUs() */
namespace base {
http://git-wip-us.apache.org/repos/asf/incubator-impala/blob/02f3e3fc/be/src/gutil/spinlock.h
----------------------------------------------------------------------
diff --git a/be/src/gutil/spinlock.h b/be/src/gutil/spinlock.h
index 3cf7d3e..fcd6287 100644
--- a/be/src/gutil/spinlock.h
+++ b/be/src/gutil/spinlock.h
@@ -39,10 +39,10 @@
#ifndef BASE_SPINLOCK_H_
#define BASE_SPINLOCK_H_
-#include "gutil/atomicops.h"
-#include "gutil/basictypes.h"
-#include "gutil/dynamic_annotations.h"
-#include "gutil/thread_annotations.h"
+#include "kudu/gutil/atomicops.h"
+#include "kudu/gutil/basictypes.h"
+#include "kudu/gutil/dynamic_annotations.h"
+#include "kudu/gutil/thread_annotations.h"
// This isn't originally in the base:: namespace in tcmalloc,
// but tcmalloc inadvertently exports these symbols. So, if we
http://git-wip-us.apache.org/repos/asf/incubator-impala/blob/02f3e3fc/be/src/gutil/spinlock_internal.cc
----------------------------------------------------------------------
diff --git a/be/src/gutil/spinlock_internal.cc b/be/src/gutil/spinlock_internal.cc
index 0850cf1..151b0dd 100644
--- a/be/src/gutil/spinlock_internal.cc
+++ b/be/src/gutil/spinlock_internal.cc
@@ -41,17 +41,17 @@
// In all cases, it must return in bounded time even if SpinlockWake() is not
// called.
-#include "gutil/spinlock_internal.h"
+#include "kudu/gutil/spinlock_internal.h"
// forward declaration for use by spinlock_*-inl.h
namespace base { namespace internal { static int SuggestedDelayNS(int loop); }}
#if defined(_WIN32)
-#include "gutil/spinlock_win32-inl.h"
+#include "kudu/gutil/spinlock_win32-inl.h"
#elif defined(__linux__)
-#include "gutil/spinlock_linux-inl.h"
+#include "kudu/gutil/spinlock_linux-inl.h"
#else
-#include "gutil/spinlock_posix-inl.h"
+#include "kudu/gutil/spinlock_posix-inl.h"
#endif
namespace base {
http://git-wip-us.apache.org/repos/asf/incubator-impala/blob/02f3e3fc/be/src/gutil/spinlock_internal.h
----------------------------------------------------------------------
diff --git a/be/src/gutil/spinlock_internal.h b/be/src/gutil/spinlock_internal.h
index a7f5150..c235893 100644
--- a/be/src/gutil/spinlock_internal.h
+++ b/be/src/gutil/spinlock_internal.h
@@ -36,8 +36,8 @@
#ifndef BASE_SPINLOCK_INTERNAL_H_
#define BASE_SPINLOCK_INTERNAL_H_
-#include "gutil/basictypes.h"
-#include "gutil/atomicops.h"
+#include "kudu/gutil/basictypes.h"
+#include "kudu/gutil/atomicops.h"
namespace base {
namespace internal {
http://git-wip-us.apache.org/repos/asf/incubator-impala/blob/02f3e3fc/be/src/gutil/spinlock_linux-inl.h
----------------------------------------------------------------------
diff --git a/be/src/gutil/spinlock_linux-inl.h b/be/src/gutil/spinlock_linux-inl.h
index c9838e4..41ef03a 100644
--- a/be/src/gutil/spinlock_linux-inl.h
+++ b/be/src/gutil/spinlock_linux-inl.h
@@ -36,7 +36,7 @@
#include <sched.h>
#include <time.h>
#include <limits.h>
-#include "gutil/linux_syscall_support.h"
+#include "kudu/gutil/linux_syscall_support.h"
#define FUTEX_WAIT 0
#define FUTEX_WAKE 1
http://git-wip-us.apache.org/repos/asf/incubator-impala/blob/02f3e3fc/be/src/gutil/spinlock_win32-inl.h
----------------------------------------------------------------------
diff --git a/be/src/gutil/spinlock_win32-inl.h b/be/src/gutil/spinlock_win32-inl.h
index ed636b4..956b965 100644
--- a/be/src/gutil/spinlock_win32-inl.h
+++ b/be/src/gutil/spinlock_win32-inl.h
@@ -1,37 +1,54 @@
-// Copyright 2009 Google, Inc.
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-// http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-//
-// All rights reserved.
+// -*- Mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*-
+/* Copyright (c) 2009, Google Inc.
+ * 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 above
+ * copyright notice, this list of conditions and the following disclaimer
+ * in the documentation and/or other materials provided with the
+ * distribution.
+ * * Neither the name of Google Inc. nor the names of its
+ * contributors may be used to endorse or promote products derived from
+ * this software without specific prior written permission.
+ *
+ * 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 THE COPYRIGHT
+ * OWNER OR CONTRIBUTORS 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 file is a Win32-specific part of spinlock_internal.cc
+ */
-// This file is a Win32-specific part of spinlock_wait.cc
#include <windows.h>
namespace base {
-namespace subtle {
+namespace internal {
void SpinLockDelay(volatile Atomic32 *w, int32 value, int loop) {
if (loop == 0) {
} else if (loop == 1) {
Sleep(0);
} else {
- Sleep(base::subtle::SuggestedDelayNS(loop) / 1000000);
+ Sleep(base::internal::SuggestedDelayNS(loop) / 1000000);
}
}
void SpinLockWake(volatile Atomic32 *w, bool all) {
}
-} // namespace subtle
+} // namespace internal
} // namespace base