1/* -*- mode: C++; c-basic-offset: 4; indent-tabs-mode: nil -*- */
2// vim: ft=cpp:expandtab:ts=8:sw=4:softtabstop=4:
3#ident "$Id$"
4/*======
5This file is part of PerconaFT.
6
7
8Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved.
9
10 PerconaFT is free software: you can redistribute it and/or modify
11 it under the terms of the GNU General Public License, version 2,
12 as published by the Free Software Foundation.
13
14 PerconaFT is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 GNU General Public License for more details.
18
19 You should have received a copy of the GNU General Public License
20 along with PerconaFT. If not, see <http://www.gnu.org/licenses/>.
21
22----------------------------------------
23
24 PerconaFT is free software: you can redistribute it and/or modify
25 it under the terms of the GNU Affero General Public License, version 3,
26 as published by the Free Software Foundation.
27
28 PerconaFT is distributed in the hope that it will be useful,
29 but WITHOUT ANY WARRANTY; without even the implied warranty of
30 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
31 GNU Affero General Public License for more details.
32
33 You should have received a copy of the GNU Affero General Public License
34 along with PerconaFT. If not, see <http://www.gnu.org/licenses/>.
35======= */
36
37#ident "Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved."
38
39#pragma once
40
41#include <memory.h>
42
43//******************************************************************************
44//
45// Overview: A growable array is a little bit like std::vector except that
46// it doesn't have constructors (hence can be used in static constructs, since
47// the google style guide says no constructors), and it's a little simpler.
48// Operations:
49// init and deinit (we don't have constructors and destructors).
50// fetch_unchecked to get values out.
51// store_unchecked to put values in.
52// push to add an element at the end
53// get_size to find out the size
54// get_memory_size to find out how much memory the data stucture is using.
55//
56//******************************************************************************
57
58namespace toku {
59
60template<typename T> class GrowableArray {
61 public:
62 void init (void)
63 // Effect: Initialize the array to contain no elements.
64 {
65 m_array=NULL;
66 m_size=0;
67 m_size_limit=0;
68 }
69
70 void deinit (void)
71 // Effect: Deinitialize the array (freeing any memory it uses, for example).
72 {
73 toku_free(m_array);
74 m_array =NULL;
75 m_size =0;
76 m_size_limit=0;
77 }
78
79 T fetch_unchecked (size_t i) const
80 // Effect: Fetch the ith element. If i is out of range, the system asserts.
81 {
82 return m_array[i];
83 }
84
85 void store_unchecked (size_t i, T v)
86 // Effect: Store v in the ith element. If i is out of range, the system asserts.
87 {
88 paranoid_invariant(i<m_size);
89 m_array[i]=v;
90 }
91
92 void push (T v)
93 // Effect: Add v to the end of the array (increasing the size). The amortized cost of this operation is constant.
94 // Implementation hint: Double the size of the array when it gets too big so that the amortized cost stays constant.
95 {
96 if (m_size>=m_size_limit) {
97 if (m_array==NULL) {
98 m_size_limit=1;
99 } else {
100 m_size_limit*=2;
101 }
102 XREALLOC_N(m_size_limit, m_array);
103 }
104 m_array[m_size++]=v;
105 }
106
107 size_t get_size (void) const
108 // Effect: Return the number of elements in the array.
109 {
110 return m_size;
111 }
112 size_t memory_size(void) const
113 // Effect: Return the size (in bytes) that the array occupies in memory. This is really only an estimate.
114 {
115 return sizeof(*this)+sizeof(T)*m_size_limit;
116 }
117
118 private:
119 T *m_array;
120 size_t m_size;
121 size_t m_size_limit; // How much space is allocated in array.
122};
123
124}
125