tomwalters@406: // Copyright (c) 2003 Google Inc. tomwalters@406: // tomwalters@406: // Permission is hereby granted, free of charge, to any person or organization tomwalters@406: // obtaining a copy of the software and accompanying documentation covered by tomwalters@406: // this license (the "Software") to use, reproduce, display, distribute, tomwalters@406: // execute, and transmit the Software, and to prepare derivative works of the tomwalters@406: // Software, and to permit third-parties to whom the Software is furnished to tomwalters@406: // do so, all subject to the following: tomwalters@406: // tomwalters@406: // The copyright notices in the Software and this entire statement, including tomwalters@406: // the above license grant, this restriction and the following disclaimer, tomwalters@406: // must be included in all copies of the Software, in whole or in part, and tomwalters@406: // all derivative works of the Software, unless such copies or derivative tomwalters@406: // works are solely in the form of machine-executable object code generated by tomwalters@406: // a source language processor. tomwalters@406: // tomwalters@406: // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR tomwalters@406: // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, tomwalters@406: // FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT tomwalters@406: // SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE tomwalters@406: // FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE, tomwalters@406: // ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER tomwalters@406: // DEALINGS IN THE SOFTWARE. tomwalters@406: // tomwalters@406: // linked_ptr.h tomwalters@406: // Author: Dan Egnor tomwalters@406: // tomwalters@406: // A "smart" pointer type with reference tracking. Every pointer to a tomwalters@406: // particular object is kept on a circular linked list. When the last pointer tomwalters@406: // to an object is destroyed or reassigned, the object is deleted. tomwalters@406: // tomwalters@406: // Used properly, this deletes the object when the last reference goes away. tomwalters@406: // There are several caveats: tomwalters@406: // - Like all reference counting schemes, cycles lead to leaks. tomwalters@406: // - Each smart pointer is actually two pointers (8 bytes instead of 4). tomwalters@406: // - Every time a pointer is assigned, the entire list of pointers to that tomwalters@406: // object is traversed. This class is therefore NOT SUITABLE when there tomwalters@406: // will often be more than two or three pointers to a particular object. tomwalters@406: // - References are only tracked as long as linked_ptr<> objects are copied. tomwalters@406: // If a linked_ptr<> is converted to a raw pointer and back, BAD THINGS tomwalters@406: // will happen (double deletion). tomwalters@406: // tomwalters@406: // A good use of this class is storing object references in STL containers. tomwalters@406: // You can safely put linked_ptr<> in a vector<>. tomwalters@406: // Other uses may not be as good. tomwalters@406: // tomwalters@406: // Note: If you use an incomplete type with linked_ptr<>, the class tomwalters@406: // *containing* linked_ptr<> must have a constructor and destructor (even tomwalters@406: // if they do nothing!). tomwalters@406: // tomwalters@406: // Bill Gibbons suggested we use something like this. Yonat Sharon has tomwalters@406: // a different (less useful IMHO) implementation at ootips.org. tomwalters@406: // tomwalters@406: // Thread Safety: tomwalters@406: // A linked_ptr is NOT thread safe. Copying a linked_ptr object is tomwalters@406: // effectively a read-write operation. tomwalters@406: tomwalters@406: #ifndef UTIL_GTL_LINKED_PTR_H__ tomwalters@406: #define UTIL_GTL_LINKED_PTR_H__ tomwalters@406: tomwalters@406: #include tomwalters@406: tomwalters@406: // This is used internally by all instances of linked_ptr<>. It needs to be tomwalters@406: // a non-template class because different types of linked_ptr<> can refer to tomwalters@406: // the same object (linked_ptr(obj) vs linked_ptr(obj)). tomwalters@406: // So, it needs to be possible for different types of linked_ptr to participate tomwalters@406: // in the same circular linked list, so we need a single class type here. tomwalters@406: // tomwalters@406: // DO NOT USE THIS CLASS DIRECTLY YOURSELF. Use linked_ptr. tomwalters@406: class linked_ptr_internal { tomwalters@406: public: tomwalters@406: // Create a new circle that includes only this instance. tomwalters@406: void join_new() { tomwalters@406: next_ = this; tomwalters@406: } tomwalters@406: tomwalters@406: // Join an existing circle. tomwalters@406: void join(linked_ptr_internal const* ptr) { tomwalters@406: linked_ptr_internal const* p = ptr; tomwalters@406: while (p->next_ != ptr) p = p->next_; tomwalters@406: p->next_ = this; tomwalters@406: next_ = ptr; tomwalters@406: } tomwalters@406: tomwalters@406: // Leave whatever circle we're part of. Returns true iff we were the tomwalters@406: // last member of the circle. Once this is done, you can join() another. tomwalters@406: bool depart() { tomwalters@406: if (next_ == this) return true; tomwalters@406: linked_ptr_internal const* p = next_; tomwalters@406: while (p->next_ != this) p = p->next_; tomwalters@406: p->next_ = next_; tomwalters@406: return false; tomwalters@406: } tomwalters@406: tomwalters@406: private: tomwalters@406: mutable linked_ptr_internal const* next_; tomwalters@406: }; tomwalters@406: tomwalters@406: template tomwalters@406: class linked_ptr { tomwalters@406: public: tomwalters@406: typedef T element_type; tomwalters@406: tomwalters@406: // Take over ownership of a raw pointer. This should happen as soon as tomwalters@406: // possible after the object is created. tomwalters@406: explicit linked_ptr(T* ptr = NULL) { capture(ptr); } tomwalters@406: ~linked_ptr() { depart(); } tomwalters@406: tomwalters@406: // Copy an existing linked_ptr<>, adding ourselves to the list of references. tomwalters@406: template linked_ptr(linked_ptr const& ptr) { copy(&ptr); } tomwalters@406: linked_ptr(linked_ptr const& ptr) { assert(&ptr != this); copy(&ptr); } tomwalters@406: tomwalters@406: // Assignment releases the old value and acquires the new. tomwalters@406: template linked_ptr& operator=(linked_ptr const& ptr) { tomwalters@406: depart(); tomwalters@406: copy(&ptr); tomwalters@406: return *this; tomwalters@406: } tomwalters@406: tomwalters@406: linked_ptr& operator=(linked_ptr const& ptr) { tomwalters@406: if (&ptr != this) { tomwalters@406: depart(); tomwalters@406: copy(&ptr); tomwalters@406: } tomwalters@406: return *this; tomwalters@406: } tomwalters@406: tomwalters@406: // Smart pointer members. tomwalters@406: void reset(T* ptr = NULL) { depart(); capture(ptr); } tomwalters@406: T* get() const { return value_; } tomwalters@406: T* operator->() const { return value_; } tomwalters@406: T& operator*() const { return *value_; } tomwalters@406: // Release ownership of the pointed object and returns it. tomwalters@406: // Sole ownership by this linked_ptr object is required. tomwalters@406: T* release() { tomwalters@406: // !! GOOGLE Gears specific modification !! tomwalters@406: // GCC emits a warning for not using last in a opt build. tomwalters@406: // Warnings are treated as errors. tomwalters@406: #ifdef DEBUG tomwalters@406: bool last = link_.depart(); tomwalters@406: assert(last); tomwalters@406: #else tomwalters@406: link_.depart(); tomwalters@406: #endif tomwalters@406: T* v = value_; tomwalters@406: value_ = NULL; tomwalters@406: return v; tomwalters@406: } tomwalters@406: tomwalters@406: bool operator==(T* p) const { return value_ == p; } tomwalters@406: bool operator!=(T* p) const { return value_ != p; } tomwalters@406: template tomwalters@406: bool operator==(linked_ptr const& ptr) const { tomwalters@406: return value_ == ptr.get(); tomwalters@406: } tomwalters@406: template tomwalters@406: bool operator!=(linked_ptr const& ptr) const { tomwalters@406: return value_ != ptr.get(); tomwalters@406: } tomwalters@406: tomwalters@406: private: tomwalters@406: template tomwalters@406: friend class linked_ptr; tomwalters@406: tomwalters@406: T* value_; tomwalters@406: linked_ptr_internal link_; tomwalters@406: tomwalters@406: void depart() { tomwalters@406: if (link_.depart()) delete value_; tomwalters@406: } tomwalters@406: tomwalters@406: void capture(T* ptr) { tomwalters@406: value_ = ptr; tomwalters@406: link_.join_new(); tomwalters@406: } tomwalters@406: tomwalters@406: template void copy(linked_ptr const* ptr) { tomwalters@406: value_ = ptr->get(); tomwalters@406: if (value_) tomwalters@406: link_.join(&ptr->link_); tomwalters@406: else tomwalters@406: link_.join_new(); tomwalters@406: } tomwalters@406: }; tomwalters@406: tomwalters@406: template inline tomwalters@406: bool operator==(T* ptr, const linked_ptr& x) { tomwalters@406: return ptr == x.get(); tomwalters@406: } tomwalters@406: tomwalters@406: template inline tomwalters@406: bool operator!=(T* ptr, const linked_ptr& x) { tomwalters@406: return ptr != x.get(); tomwalters@406: } tomwalters@406: tomwalters@406: // A function to convert T* into linked_ptr tomwalters@406: // Doing e.g. make_linked_ptr(new FooBarBaz(arg)) is a shorter notation tomwalters@406: // for linked_ptr >(new FooBarBaz(arg)) tomwalters@406: template tomwalters@406: linked_ptr make_linked_ptr(T* ptr) { tomwalters@406: return linked_ptr(ptr); tomwalters@406: } tomwalters@406: tomwalters@406: #endif // UTIL_GTL_LINKED_PTR_H__