chromium/net/third_party/quiche/src/quiche/common/quiche_intrusive_list.h

// Copyright (c) 2024 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef QUICHE_COMMON_QUICHE_INTRUSIVE_LIST_H_
#define QUICHE_COMMON_QUICHE_INTRUSIVE_LIST_H_

// A QuicheIntrusiveList<> is a doubly-linked list where the link pointers are
// embedded in the elements. They are circularly linked making insertion and
// removal into a known position constant time and branch-free operations.
//
// Usage is similar to an STL list<> where feasible, but there are important
// differences. First and foremost, the elements must derive from the
// QuicheIntrusiveLink<> base class:
//
//   struct Foo : public QuicheIntrusiveLink<Foo> {
//     // ...
//   }
//
//   QuicheIntrusiveList<Foo> l;
//   l.push_back(new Foo);
//   l.push_front(new Foo);
//   l.erase(&l.front());
//   l.erase(&l.back());
//
// Intrusive lists are primarily useful when you would have considered embedding
// link pointers in your class directly for space or performance reasons. An
// QuicheIntrusiveLink<> is the size of 2 pointers, usually 16 bytes on 64-bit
// systems. Intrusive lists do not perform memory allocation (unlike the STL
// list<> class) and thus may use less memory than list<>. In particular, if the
// list elements are pointers to objects, using a list<> would perform an extra
// memory allocation for each list node structure, while an
// QuicheIntrusiveList<> would not.
//
// Note that QuicheIntrusiveLink is exempt from the C++ style guide's
// limitations on multiple inheritance, so it's fine to inherit from both
// QuicheIntrusiveLink and a base class, even if the base class is not a pure
// interface.
//
// Because the list pointers are embedded in the objects stored in an
// QuicheIntrusiveList<>, erasing an item from a list is constant time. Consider
// the following:
//
//   map<string,Foo> foo_map;
//   list<Foo*> foo_list;
//
//   foo_list.push_back(&foo_map["bar"]);
//   foo_list.erase(&foo_map["bar"]); // Compile error!
//
// The problem here is that a Foo* doesn't know where on foo_list it resides,
// so removal requires iteration over the list. Various tricks can be performed
// to overcome this. For example, a foo_list::iterator can be stored inside of
// the Foo object. But at that point you'd be better off using an
// QuicheIntrusiveList<>:
//
//   map<string,Foo> foo_map;
//   QuicheIntrusiveList<Foo> foo_list;
//
//   foo_list.push_back(&foo_map["bar"]);
//   foo_list.erase(&foo_map["bar"]); // Yeah!
//
// Note that QuicheIntrusiveLists come with a few limitations. The primary
// limitation is that the QuicheIntrusiveLink<> base class is not copyable or
// assignable. The result is that STL algorithms which mutate the order of
// iterators, such as reverse() and unique(), will not work by default with
// QuicheIntrusiveLists. In order to allow these algorithms to work you'll need
// to define swap() and/or operator= for your class.
//
// Another limitation is that the QuicheIntrusiveList<> structure itself is not
// copyable or assignable since an item/link combination can only exist on one
// QuicheIntrusiveList<> at a time. This limitation is a result of the link
// pointers for an item being intrusive in the item itself. For example, the
// following will not compile:
//
//   FooList a;
//   FooList b(a); // no copy constructor
//   b = a;        // no assignment operator
//
// The similar STL code does work since the link pointers are external to the
// item:
//
//   list<int*> a;
//   a.push_back(new int);
//   list<int*> b(a);
//   QUICHE_CHECK(a.front() == b.front());
//
// Note that QuicheIntrusiveList::size() runs in O(N) time.

#include <stddef.h>

#include <cstddef>
#include <iterator>

#include "quiche/common/platform/api/quiche_export.h"

namespace quiche {

template <typename T, typename ListID>
class QuicheIntrusiveList;

template <typename T, typename ListID = void>
class QUICHE_EXPORT QuicheIntrusiveLink { … };

template <typename T, typename ListID = void>
class QUICHE_EXPORT QuicheIntrusiveList { … };

}  // namespace quiche

#endif  // QUICHE_COMMON_QUICHE_INTRUSIVE_LIST_H_