vector_deque.h

Go to the documentation of this file.

/*
 * Copyright 2012 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.
 */


#ifndef PAGESPEED_KERNEL_BASE_VECTOR_DEQUE_H_
#define PAGESPEED_KERNEL_BASE_VECTOR_DEQUE_H_

#include <cstddef>    
#include <cstring>    

#include "pagespeed/kernel/base/basictypes.h"

namespace net_instaweb {

template<class T> class VectorDeque {
 public:
  VectorDeque()
      : start_position_(0),
        size_minus_1_(static_cast<size_t>(-1)),
        capacity_minus_1_(initial_capacity() - 1),
        data_(new T[initial_capacity()]) {
  }
  ~VectorDeque() {
    delete [] data_;
    data_ = NULL;
  }

  static size_t initial_capacity() { return 4; }

  void push_back(T value) {
    ExpandIfNecessary();
    ++size_minus_1_;
    *PointerAt(size_minus_1_) = value;
  }

# define SPECIAL_CASE_POINTER_AT_0 1

  void push_front(T value) {
    ExpandIfNecessary();
    start_position_ = ModCapacity(start_position_ - 1);
# if SPECIAL_CASE_POINTER_AT_0
    *PointerAt0() = value;
# else
    *PointerAt(0) = value;
# endif
    ++size_minus_1_;
  }

  void pop_back() {
    --size_minus_1_;
  }

  void pop_front() {
    start_position_ = ModCapacity(start_position_ + 1);
    --size_minus_1_;
  }

  T back() const {
    return *PointerAt(size_minus_1_);
  }

  T front() const {
# if SPECIAL_CASE_POINTER_AT_0
    return *PointerAt0();
# else
    return *PointerAt(0);
# endif
  }

  size_t capacity() const { return capacity_minus_1_ + 1; }
  size_t size() const { return size_minus_1_ + 1; }
  bool empty() const { return size_minus_1_ == static_cast<size_t>(-1); }

 private:
  size_t ModCapacity(size_t index) const { return index & capacity_minus_1_; }

  T* PointerAt(size_t position) {
    return data_ + ModCapacity(start_position_ + position);
  }

  const T* PointerAt(size_t position) const {
    return data_ + ModCapacity(start_position_ + position);
  }

# if SPECIAL_CASE_POINTER_AT_0
  T* PointerAt0() {
    return data_ + start_position_;
  }

  const T* PointerAt0() const {
    return data_ + start_position_;
  }
# endif
# undef SPECIAL_CASE_POINTER_AT_0

  void ExpandIfNecessary() {
    if (size_minus_1_ == capacity_minus_1_) {
      capacity_minus_1_ = 2 * capacity() - 1;
      T* old_data = data_;
      data_ = new T[capacity()];
      size_t sz = size();
      if (start_position_ == 0) {
        memcpy(data_, old_data, sz * sizeof(*data_));
      } else {
        memcpy(data_, old_data, start_position_ * sizeof(*data_));
        size_t size_of_right_chunk = sz - start_position_;
        size_t new_start_position = start_position_ + sz;
        memcpy(data_ + new_start_position,
               old_data + start_position_,
               size_of_right_chunk * sizeof(*data_));
        start_position_ = new_start_position;
      }
      delete [] old_data;
    }
  }

  size_t start_position_;
  size_t size_minus_1_;
  size_t capacity_minus_1_; 
  T* data_;

  
};

}  

#endif