1/*
2 * Copyright (C) 2017 Apple Inc. All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
6 * are met:
7 * 1. Redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer.
9 * 2. Redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution.
12 *
13 * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
14 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
17 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24 */
25
26#pragma once
27
28#include <wtf/Atomics.h>
29#include <wtf/FastMalloc.h>
30#include <wtf/HashFunctions.h>
31#include <wtf/Lock.h>
32#include <wtf/Noncopyable.h>
33#include <wtf/Vector.h>
34
35namespace WTF {
36
37// ConcurrentBuffer is suitable for when you plan to store immutable data and sometimes append to it.
38// It supports storing data that is not copy-constructable but bit-copyable.
39template<typename T>
40class ConcurrentBuffer {
41 WTF_MAKE_NONCOPYABLE(ConcurrentBuffer);
42 WTF_MAKE_FAST_ALLOCATED;
43public:
44
45 ConcurrentBuffer()
46 {
47 }
48
49 ~ConcurrentBuffer()
50 {
51 if (Array* array = m_array) {
52 for (size_t i = 0; i < array->size; ++i)
53 array->data[i].~T();
54 }
55 for (Array* array : m_allArrays)
56 fastFree(array);
57 }
58
59 // Growing is not concurrent. This assumes you are holding some other lock before you do this.
60 void growExact(size_t newSize)
61 {
62 Array* array = m_array;
63 if (array && newSize <= array->size)
64 return;
65 Array* newArray = createArray(newSize);
66 // This allows us to do ConcurrentBuffer<std::unique_ptr<>>.
67 if (array)
68 memcpy(newArray->data, array->data, sizeof(T) * array->size);
69 for (size_t i = array ? array->size : 0; i < newSize; ++i)
70 new (newArray->data + i) T();
71 WTF::storeStoreFence();
72 m_array = newArray;
73 WTF::storeStoreFence();
74 m_allArrays.append(newArray);
75 }
76
77 void grow(size_t newSize)
78 {
79 size_t size = m_array ? m_array->size : 0;
80 if (newSize <= size)
81 return;
82 growExact(std::max(newSize, size * 2));
83 }
84
85 struct Array {
86 size_t size; // This is an immutable size.
87 T data[1];
88 };
89
90 Array* array() const { return m_array; }
91
92 T& operator[](size_t index) { return m_array->data[index]; }
93 const T& operator[](size_t index) const { return m_array->data[index]; }
94
95private:
96 Array* createArray(size_t size)
97 {
98 Checked<size_t> objectSize = sizeof(T);
99 objectSize *= size;
100 objectSize += static_cast<size_t>(OBJECT_OFFSETOF(Array, data));
101 Array* result = static_cast<Array*>(fastMalloc(objectSize.unsafeGet()));
102 result->size = size;
103 return result;
104 }
105
106 Array* m_array { nullptr };
107 Vector<Array*> m_allArrays;
108};
109
110} // namespace WTF
111
112