1// Copyright (c) 2011 The Chromium Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4//
5// A "smart" pointer type with reference tracking.  Every pointer to a
6// particular object is kept on a circular linked list.  When the last pointer
7// to an object is destroyed or reassigned, the object is deleted.
8//
9// Used properly, this deletes the object when the last reference goes away.
10// There are several caveats:
11// - Like all reference counting schemes, cycles lead to leaks.
12// - Each smart pointer is actually two pointers (8 bytes instead of 4).
13// - Every time a pointer is released, the entire list of pointers to that
14//   object is traversed.  This class is therefore NOT SUITABLE when there
15//   will often be more than two or three pointers to a particular object.
16// - References are only tracked as long as linked_ptr<> objects are copied.
17//   If a linked_ptr<> is converted to a raw pointer and back, BAD THINGS
18//   will happen (double deletion).
19//
20// A good use of this class is storing object references in STL containers.
21// You can safely put linked_ptr<> in a vector<>.
22// Other uses may not be as good.
23//
24// Note: If you use an incomplete type with linked_ptr<>, the class
25// *containing* linked_ptr<> must have a constructor and destructor (even
26// if they do nothing!).
27//
28// Thread Safety:
29//   A linked_ptr is NOT thread safe. Copying a linked_ptr object is
30//   effectively a read-write operation.
31//
32// Alternative: to linked_ptr is shared_ptr, which
33//  - is also two pointers in size (8 bytes for 32 bit addresses)
34//  - is thread safe for copying and deletion
35//  - supports weak_ptrs
36
37#ifndef BASE_MEMORY_LINKED_PTR_H_
38#define BASE_MEMORY_LINKED_PTR_H_
39
40#include "base/logging.h"  // for CHECK macros
41
42// This is used internally by all instances of linked_ptr<>.  It needs to be
43// a non-template class because different types of linked_ptr<> can refer to
44// the same object (linked_ptr<Superclass>(obj) vs linked_ptr<Subclass>(obj)).
45// So, it needs to be possible for different types of linked_ptr to participate
46// in the same circular linked list, so we need a single class type here.
47//
48// DO NOT USE THIS CLASS DIRECTLY YOURSELF.  Use linked_ptr<T>.
49class linked_ptr_internal {
50 public:
51  // Create a new circle that includes only this instance.
52  void join_new() {
53    next_ = this;
54  }
55
56  // Join an existing circle.
57  void join(linked_ptr_internal const* ptr) {
58    next_ = ptr->next_;
59    ptr->next_ = this;
60  }
61
62  // Leave whatever circle we're part of.  Returns true iff we were the
63  // last member of the circle.  Once this is done, you can join() another.
64  bool depart() {
65    if (next_ == this) return true;
66    linked_ptr_internal const* p = next_;
67    while (p->next_ != this) p = p->next_;
68    p->next_ = next_;
69    return false;
70  }
71
72 private:
73  mutable linked_ptr_internal const* next_;
74};
75
76template <typename T>
77class linked_ptr {
78 public:
79  typedef T element_type;
80
81  // Take over ownership of a raw pointer.  This should happen as soon as
82  // possible after the object is created.
83  explicit linked_ptr(T* ptr = NULL) { capture(ptr); }
84  ~linked_ptr() { depart(); }
85
86  // Copy an existing linked_ptr<>, adding ourselves to the list of references.
87  template <typename U> linked_ptr(linked_ptr<U> const& ptr) { copy(&ptr); }
88
89  linked_ptr(linked_ptr const& ptr) {
90    DCHECK_NE(&ptr, this);
91    copy(&ptr);
92  }
93
94  // Assignment releases the old value and acquires the new.
95  template <typename U> linked_ptr& operator=(linked_ptr<U> const& ptr) {
96    depart();
97    copy(&ptr);
98    return *this;
99  }
100
101  linked_ptr& operator=(linked_ptr const& ptr) {
102    if (&ptr != this) {
103      depart();
104      copy(&ptr);
105    }
106    return *this;
107  }
108
109  // Smart pointer members.
110  void reset(T* ptr = NULL) {
111    depart();
112    capture(ptr);
113  }
114  T* get() const { return value_; }
115  T* operator->() const { return value_; }
116  T& operator*() const { return *value_; }
117  // Release ownership of the pointed object and returns it.
118  // Sole ownership by this linked_ptr object is required.
119  T* release() {
120    bool last = link_.depart();
121    CHECK(last);
122    T* v = value_;
123    value_ = NULL;
124    return v;
125  }
126
127  bool operator==(const T* p) const { return value_ == p; }
128  bool operator!=(const T* p) const { return value_ != p; }
129  template <typename U>
130  bool operator==(linked_ptr<U> const& ptr) const {
131    return value_ == ptr.get();
132  }
133  template <typename U>
134  bool operator!=(linked_ptr<U> const& ptr) const {
135    return value_ != ptr.get();
136  }
137
138 private:
139  template <typename U>
140  friend class linked_ptr;
141
142  T* value_;
143  linked_ptr_internal link_;
144
145  void depart() {
146    if (link_.depart()) delete value_;
147  }
148
149  void capture(T* ptr) {
150    value_ = ptr;
151    link_.join_new();
152  }
153
154  template <typename U> void copy(linked_ptr<U> const* ptr) {
155    value_ = ptr->get();
156    if (value_)
157      link_.join(&ptr->link_);
158    else
159      link_.join_new();
160  }
161};
162
163template<typename T> inline
164bool operator==(T* ptr, const linked_ptr<T>& x) {
165  return ptr == x.get();
166}
167
168template<typename T> inline
169bool operator!=(T* ptr, const linked_ptr<T>& x) {
170  return ptr != x.get();
171}
172
173// A function to convert T* into linked_ptr<T>
174// Doing e.g. make_linked_ptr(new FooBarBaz<type>(arg)) is a shorter notation
175// for linked_ptr<FooBarBaz<type> >(new FooBarBaz<type>(arg))
176template <typename T>
177linked_ptr<T> make_linked_ptr(T* ptr) {
178  return linked_ptr<T>(ptr);
179}
180
181#endif  // BASE_MEMORY_LINKED_PTR_H_
182