src/leveldb/util/arena.cc

   1 // Copyright (c) 2011 The LevelDB Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file. See the AUTHORS file for names of contributors.
   4
   5 #include "util/arena.h"
   6 #include <assert.h>
   7
   8 namespace leveldb {
   9
  10 static const int kBlockSize = 4096;
  11
  12 Arena::Arena() {
  13   blocks_memory_ = 0;
  14   alloc_ptr_ = NULL;  // First allocation will allocate a block
  15   alloc_bytes_remaining_ = 0;
  16 }
  17
  18 Arena::~Arena() {
  19   for (size_t i = 0; i < blocks_.size(); i++) {
  20     delete[] blocks_[i];
  21   }
  22 }
  23
  24 char* Arena::AllocateFallback(size_t bytes) {
  25   if (bytes > kBlockSize / 4) {
  26     // Object is more than a quarter of our block size.  Allocate it separately
  27     // to avoid wasting too much space in leftover bytes.
  28     char* result = AllocateNewBlock(bytes);
  29     return result;
  30   }
  31
  32   // We waste the remaining space in the current block.
  33   alloc_ptr_ = AllocateNewBlock(kBlockSize);
  34   alloc_bytes_remaining_ = kBlockSize;
  35
  36   char* result = alloc_ptr_;
  37   alloc_ptr_ += bytes;
  38   alloc_bytes_remaining_ -= bytes;
  39   return result;
  40 }
  41
  42 char* Arena::AllocateAligned(size_t bytes) {
  43   const int align = sizeof(void*);    // We'll align to pointer size
  44   assert((align & (align-1)) == 0);   // Pointer size should be a power of 2
  45   size_t current_mod = reinterpret_cast<uintptr_t>(alloc_ptr_) & (align-1);
  46   size_t slop = (current_mod == 0 ? 0 : align - current_mod);
  47   size_t needed = bytes + slop;
  48   char* result;
  49   if (needed <= alloc_bytes_remaining_) {
  50     result = alloc_ptr_ + slop;
  51     alloc_ptr_ += needed;
  52     alloc_bytes_remaining_ -= needed;
  53   } else {
  54     // AllocateFallback always returned aligned memory
  55     result = AllocateFallback(bytes);
  56   }
  57   assert((reinterpret_cast<uintptr_t>(result) & (align-1)) == 0);
  58   return result;
  59 }
  60
  61 char* Arena::AllocateNewBlock(size_t block_bytes) {
  62   char* result = new char[block_bytes];
  63   blocks_memory_ += block_bytes;
  64   blocks_.push_back(result);
  65   return result;
  66 }
  67
  68 }  // namespace leveldb