initial.commit | 3f4a732 | 2008-07-27 06:49:38 +0900 | [diff] [blame] | 1 | // Copyright 2008, Google Inc. |
| 2 | // 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 are |
| 6 | // met: |
| 7 | // |
| 8 | // * Redistributions of source code must retain the above copyright |
| 9 | // notice, this list of conditions and the following disclaimer. |
| 10 | // * Redistributions in binary form must reproduce the above |
| 11 | // copyright notice, this list of conditions and the following disclaimer |
| 12 | // in the documentation and/or other materials provided with the |
| 13 | // distribution. |
| 14 | // * Neither the name of Google Inc. nor the names of its |
| 15 | // contributors may be used to endorse or promote products derived from |
| 16 | // this software without specific prior written permission. |
| 17 | // |
| 18 | // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS |
| 19 | // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT |
| 20 | // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR |
| 21 | // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT |
| 22 | // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |
| 23 | // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT |
| 24 | // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
| 25 | // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
| 26 | // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
| 27 | // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE |
| 28 | // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| 29 | // |
| 30 | // A "smart" pointer type with reference tracking. Every pointer to a |
| 31 | // particular object is kept on a circular linked list. When the last pointer |
| 32 | // to an object is destroyed or reassigned, the object is deleted. |
| 33 | // |
| 34 | // Used properly, this deletes the object when the last reference goes away. |
| 35 | // There are several caveats: |
| 36 | // - Like all reference counting schemes, cycles lead to leaks. |
| 37 | // - Each smart pointer is actually two pointers (8 bytes instead of 4). |
| 38 | // - Every time a pointer is released, the entire list of pointers to that |
| 39 | // object is traversed. This class is therefore NOT SUITABLE when there |
| 40 | // will often be more than two or three pointers to a particular object. |
| 41 | // - References are only tracked as long as linked_ptr<> objects are copied. |
| 42 | // If a linked_ptr<> is converted to a raw pointer and back, BAD THINGS |
| 43 | // will happen (double deletion). |
| 44 | // |
| 45 | // A good use of this class is storing object references in STL containers. |
| 46 | // You can safely put linked_ptr<> in a vector<>. |
| 47 | // Other uses may not be as good. |
| 48 | // |
| 49 | // Note: If you use an incomplete type with linked_ptr<>, the class |
| 50 | // *containing* linked_ptr<> must have a constructor and destructor (even |
| 51 | // if they do nothing!). |
| 52 | // |
| 53 | // Thread Safety: |
| 54 | // A linked_ptr is NOT thread safe. Copying a linked_ptr object is |
| 55 | // effectively a read-write operation. |
| 56 | // |
| 57 | // Alternative: to linked_ptr is shared_ptr, which |
| 58 | // - is also two pointers in size (8 bytes for 32 bit addresses) |
| 59 | // - is thread safe for copying and deletion |
| 60 | // - supports weak_ptrs |
| 61 | |
| 62 | #ifndef BASE_LINKED_PTR_H_ |
| 63 | #define BASE_LINKED_PTR_H_ |
| 64 | |
| 65 | #include "base/logging.h" // for CHECK macros |
| 66 | |
| 67 | // This is used internally by all instances of linked_ptr<>. It needs to be |
| 68 | // a non-template class because different types of linked_ptr<> can refer to |
| 69 | // the same object (linked_ptr<Superclass>(obj) vs linked_ptr<Subclass>(obj)). |
| 70 | // So, it needs to be possible for different types of linked_ptr to participate |
| 71 | // in the same circular linked list, so we need a single class type here. |
| 72 | // |
| 73 | // DO NOT USE THIS CLASS DIRECTLY YOURSELF. Use linked_ptr<T>. |
| 74 | class linked_ptr_internal { |
| 75 | public: |
| 76 | // Create a new circle that includes only this instance. |
| 77 | void join_new() { |
| 78 | next_ = this; |
| 79 | } |
| 80 | |
| 81 | // Join an existing circle. |
| 82 | void join(linked_ptr_internal const* ptr) { |
| 83 | next_ = ptr->next_; |
| 84 | ptr->next_ = this; |
| 85 | } |
| 86 | |
| 87 | // Leave whatever circle we're part of. Returns true iff we were the |
| 88 | // last member of the circle. Once this is done, you can join() another. |
| 89 | bool depart() { |
| 90 | if (next_ == this) return true; |
| 91 | linked_ptr_internal const* p = next_; |
| 92 | while (p->next_ != this) p = p->next_; |
| 93 | p->next_ = next_; |
| 94 | return false; |
| 95 | } |
| 96 | |
| 97 | private: |
| 98 | mutable linked_ptr_internal const* next_; |
| 99 | }; |
| 100 | |
| 101 | template <typename T> |
| 102 | class linked_ptr { |
| 103 | public: |
| 104 | typedef T element_type; |
| 105 | |
| 106 | // Take over ownership of a raw pointer. This should happen as soon as |
| 107 | // possible after the object is created. |
| 108 | explicit linked_ptr(T* ptr = NULL) { capture(ptr); } |
| 109 | ~linked_ptr() { depart(); } |
| 110 | |
| 111 | // Copy an existing linked_ptr<>, adding ourselves to the list of references. |
| 112 | template <typename U> linked_ptr(linked_ptr<U> const& ptr) { copy(&ptr); } |
| 113 | linked_ptr(linked_ptr const& ptr) { DCHECK_NE(&ptr, this); copy(&ptr); } |
| 114 | |
| 115 | // Assignment releases the old value and acquires the new. |
| 116 | template <typename U> linked_ptr& operator=(linked_ptr<U> const& ptr) { |
| 117 | depart(); |
| 118 | copy(&ptr); |
| 119 | return *this; |
| 120 | } |
| 121 | |
| 122 | linked_ptr& operator=(linked_ptr const& ptr) { |
| 123 | if (&ptr != this) { |
| 124 | depart(); |
| 125 | copy(&ptr); |
| 126 | } |
| 127 | return *this; |
| 128 | } |
| 129 | |
| 130 | // Smart pointer members. |
| 131 | void reset(T* ptr = NULL) { depart(); capture(ptr); } |
| 132 | T* get() const { return value_; } |
| 133 | T* operator->() const { return value_; } |
| 134 | T& operator*() const { return *value_; } |
| 135 | // Release ownership of the pointed object and returns it. |
| 136 | // Sole ownership by this linked_ptr object is required. |
| 137 | T* release() { |
| 138 | bool last = link_.depart(); |
| 139 | CHECK(last); |
| 140 | T* v = value_; |
| 141 | value_ = NULL; |
| 142 | return v; |
| 143 | } |
| 144 | |
| 145 | bool operator==(T* p) const { return value_ == p; } |
| 146 | bool operator!=(T* p) const { return value_ != p; } |
| 147 | template <typename U> |
| 148 | bool operator==(linked_ptr<U> const& ptr) const { |
| 149 | return value_ == ptr.get(); |
| 150 | } |
| 151 | template <typename U> |
| 152 | bool operator!=(linked_ptr<U> const& ptr) const { |
| 153 | return value_ != ptr.get(); |
| 154 | } |
| 155 | |
| 156 | private: |
| 157 | template <typename U> |
| 158 | friend class linked_ptr; |
| 159 | |
| 160 | T* value_; |
| 161 | linked_ptr_internal link_; |
| 162 | |
| 163 | void depart() { |
| 164 | if (link_.depart()) delete value_; |
| 165 | } |
| 166 | |
| 167 | void capture(T* ptr) { |
| 168 | value_ = ptr; |
| 169 | link_.join_new(); |
| 170 | } |
| 171 | |
| 172 | template <typename U> void copy(linked_ptr<U> const* ptr) { |
| 173 | value_ = ptr->get(); |
| 174 | if (value_) |
| 175 | link_.join(&ptr->link_); |
| 176 | else |
| 177 | link_.join_new(); |
| 178 | } |
| 179 | }; |
| 180 | |
| 181 | template<typename T> inline |
| 182 | bool operator==(T* ptr, const linked_ptr<T>& x) { |
| 183 | return ptr == x.get(); |
| 184 | } |
| 185 | |
| 186 | template<typename T> inline |
| 187 | bool operator!=(T* ptr, const linked_ptr<T>& x) { |
| 188 | return ptr != x.get(); |
| 189 | } |
| 190 | |
| 191 | // A function to convert T* into linked_ptr<T> |
| 192 | // Doing e.g. make_linked_ptr(new FooBarBaz<type>(arg)) is a shorter notation |
| 193 | // for linked_ptr<FooBarBaz<type> >(new FooBarBaz<type>(arg)) |
| 194 | template <typename T> |
| 195 | linked_ptr<T> make_linked_ptr(T* ptr) { |
| 196 | return linked_ptr<T>(ptr); |
| 197 | } |
| 198 | |
| 199 | #endif // BASE_LINKED_PTR_H_ |