1b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// Copyright 2014 the V8 project authors. All rights reserved. 2b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// Use of this source code is governed by a BSD-style license that can be 3b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// found in the LICENSE file. 4b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 5b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#ifndef V8_ZONE_CONTAINERS_H_ 6b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#define V8_ZONE_CONTAINERS_H_ 7b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 8b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#include <deque> 9958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier#include <list> 10014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch#include <map> 11b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#include <queue> 12014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch#include <set> 13958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier#include <stack> 14b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#include <vector> 15b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 16b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#include "src/zone-allocator.h" 17b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 18b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochnamespace v8 { 19b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochnamespace internal { 20b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 21b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// A wrapper subclass for std::vector to make it easy to construct one 22b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// that uses a zone allocator. 23b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochtemplate <typename T> 24958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernierclass ZoneVector : public std::vector<T, zone_allocator<T>> { 25b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch public: 26b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Constructs an empty vector. 27b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch explicit ZoneVector(Zone* zone) 28958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier : std::vector<T, zone_allocator<T>>(zone_allocator<T>(zone)) {} 29958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 30958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier // Constructs a new vector and fills it with {size} elements, each 31958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier // constructed via the default constructor. 32014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch ZoneVector(size_t size, Zone* zone) 33958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier : std::vector<T, zone_allocator<T>>(size, T(), zone_allocator<T>(zone)) {} 34b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 35b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Constructs a new vector and fills it with {size} elements, each 36b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // having the value {def}. 37014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch ZoneVector(size_t size, T def, Zone* zone) 38958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier : std::vector<T, zone_allocator<T>>(size, def, zone_allocator<T>(zone)) {} 39b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch}; 40b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 41958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 42b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// A wrapper subclass std::deque to make it easy to construct one 43b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// that uses a zone allocator. 44b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochtemplate <typename T> 45958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernierclass ZoneDeque : public std::deque<T, zone_allocator<T>> { 46b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch public: 47958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier // Constructs an empty deque. 48b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch explicit ZoneDeque(Zone* zone) 49958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier : std::deque<T, zone_allocator<T>>(zone_allocator<T>(zone)) {} 50958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier}; 51958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 52958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 53958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier// A wrapper subclass std::list to make it easy to construct one 54958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier// that uses a zone allocator. 55958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier// TODO(mstarzinger): This should be renamed to ZoneList once we got rid of our 56958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier// own home-grown ZoneList that actually is a ZoneVector. 57958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Berniertemplate <typename T> 58958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernierclass ZoneLinkedList : public std::list<T, zone_allocator<T>> { 59958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier public: 60958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier // Constructs an empty list. 61958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier explicit ZoneLinkedList(Zone* zone) 62958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier : std::list<T, zone_allocator<T>>(zone_allocator<T>(zone)) {} 63b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch}; 64b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 65958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 66014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch// A wrapper subclass std::priority_queue to make it easy to construct one 67014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch// that uses a zone allocator. 68014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochtemplate <typename T, typename Compare = std::less<T>> 69014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochclass ZonePriorityQueue 70014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch : public std::priority_queue<T, ZoneVector<T>, Compare> { 71014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch public: 72014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // Constructs an empty list. 73014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch explicit ZonePriorityQueue(Zone* zone) 74014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch : std::priority_queue<T, ZoneVector<T>, Compare>(Compare(), 75014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch ZoneVector<T>(zone)) {} 76014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch}; 77014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 78014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 79b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// A wrapper subclass for std::queue to make it easy to construct one 80b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// that uses a zone allocator. 81b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochtemplate <typename T> 82958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernierclass ZoneQueue : public std::queue<T, ZoneDeque<T>> { 83b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch public: 84b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Constructs an empty queue. 85b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch explicit ZoneQueue(Zone* zone) 86958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier : std::queue<T, ZoneDeque<T>>(ZoneDeque<T>(zone)) {} 87958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier}; 88958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 89958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 90958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier// A wrapper subclass for std::stack to make it easy to construct one that uses 91958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier// a zone allocator. 92958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Berniertemplate <typename T> 93958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernierclass ZoneStack : public std::stack<T, ZoneDeque<T>> { 94958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier public: 95958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier // Constructs an empty stack. 96958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier explicit ZoneStack(Zone* zone) 97958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier : std::stack<T, ZoneDeque<T>>(ZoneDeque<T>(zone)) {} 98b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch}; 99b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 100958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 101014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch// A wrapper subclass for std::set to make it easy to construct one that uses 102014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch// a zone allocator. 103014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochtemplate <typename K, typename Compare = std::less<K>> 104014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochclass ZoneSet : public std::set<K, Compare, zone_allocator<K>> { 105014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch public: 106014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // Constructs an empty set. 107014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch explicit ZoneSet(Zone* zone) 108014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch : std::set<K, Compare, zone_allocator<K>>(Compare(), 109014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch zone_allocator<K>(zone)) {} 110014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch}; 111014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 112014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 113014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch// A wrapper subclass for std::map to make it easy to construct one that uses 114014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch// a zone allocator. 115014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochtemplate <typename K, typename V, typename Compare = std::less<K>> 116014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochclass ZoneMap 117014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch : public std::map<K, V, Compare, zone_allocator<std::pair<const K, V>>> { 118014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch public: 119014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // Constructs an empty map. 120014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch explicit ZoneMap(Zone* zone) 121014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch : std::map<K, V, Compare, zone_allocator<std::pair<const K, V>>>( 122014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Compare(), zone_allocator<std::pair<const K, V>>(zone)) {} 123014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch}; 124014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 125014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 126b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// Typedefs to shorten commonly used vectors. 127b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochtypedef ZoneVector<bool> BoolVector; 128b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochtypedef ZoneVector<int> IntVector; 129958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 130958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier} // namespace internal 131958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier} // namespace v8 132b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 133b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#endif // V8_ZONE_CONTAINERS_H_ 134