Move //courgette/third_party to subfolder.

courgette/third_party/paged_array.h

-// Copyright (c) 2010 The Chromium Authors. All rights reserved.
-// Use of this source code is governed by a BSD-style license that can be
-// found in the LICENSE file.
-
-// PagedArray implements an array stored using many fixed-size pages.
-//
-// PagedArray is a work-around to allow large arrays to be allocated when there
-// is too much address space fragmentation for allocating the large arrays as
-// contigous arrays.
-
-#ifndef COURGETTE_BSDIFF_PAGED_ARRAY_H_
-#define COURGETTE_BSDIFF_PAGED_ARRAY_H_
-
-#include <stddef.h>
-
-#include "base/macros.h"
-#include "base/process/memory.h"
-
-namespace courgette {
-
-// PagedArray implements an array stored using many fixed-size pages.
-template<typename T>
-class PagedArray {
-  enum {
-    // Page size in elements.  Page size of 2^18 * sizeof(T) is 1MB for T = int.
-    kLogPageSize = 18,
-    kPageSize = 1 << kLogPageSize
-  };
-
- public:
-  PagedArray() : pages_(NULL), page_count_(0) {}
-
-  ~PagedArray() { clear(); }
-
-  T& operator[](size_t i) {
-    size_t page = i >> kLogPageSize;
-    size_t offset = i & (kPageSize - 1);
-    // It is tempting to add a DCHECK(page < page_count_), but that makes
-    // bsdiff_create run 2x slower (even when compiled optimized.)
-    return pages_[page][offset];
-  }
-
-  // Allocates storage for |size| elements. Returns true on success and false if
-  // allocation fails.
-  bool Allocate(size_t size) {
-    clear();
-    size_t pages_needed = (size + kPageSize - 1) >> kLogPageSize;
-    if (!base::UncheckedMalloc(sizeof(T*) * pages_needed,
-                               reinterpret_cast<void**>(&pages_))) {
-      return false;
-    }
-
-    for (page_count_ = 0; page_count_ < pages_needed; ++page_count_) {
-      T* block = nullptr;
-      if (!base::UncheckedMalloc(sizeof(T) * kPageSize,
-                                 reinterpret_cast<void**>(&block))) {
-        clear();
-        return false;
-      }
-      pages_[page_count_] = block;
-    }
-    return true;
-  }
-
-  // Releases all storage.  May be called more than once.
-  void clear() {
-    if (pages_ != NULL) {
-      while (page_count_ != 0) {
-        --page_count_;
-        free(pages_[page_count_]);
-      }
-      free(pages_);
-      pages_ = NULL;
-    }
-  }
-
- private:
-  T** pages_;
-  size_t page_count_;
-
-  DISALLOW_COPY_AND_ASSIGN(PagedArray);
-};
-}  // namespace
-#endif  // COURGETTE_BSDIFF_PAGED_ARRAY_H_