sandbox/linux/bpf_dsl/cons.h

   1 // Copyright 2014 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 #ifndef SANDBOX_LINUX_BPF_DSL_CONS_H_
   6 #define SANDBOX_LINUX_BPF_DSL_CONS_H_
   7
   8 #include "base/memory/ref_counted.h"
   9 #include "sandbox/sandbox_export.h"
  10
  11 namespace sandbox {
  12 namespace cons {
  13
  14 // Namespace cons provides an abstraction for immutable "cons list"
  15 // data structures as commonly provided in functional programming
  16 // languages like Lisp or Haskell.
  17 //
  18 // A cons list is a linked list consisting of "cells", each of which
  19 // have a "head" and a "tail" element. A cell's head element contains
  20 // a user specified value, while the tail element contains a (possibly
  21 // null) pointer to another cell.
  22 //
  23 // An empty list (idiomatically referred to as "nil") can be
  24 // constructed as "cons::List<Foo>()" or simply as "nullptr" if Foo
  25 // can be inferred from context (e.g., calling a function that has a
  26 // "cons::List<Foo>" parameter).
  27 //
  28 // Existing lists (including empty lists) can be extended by
  29 // prepending new values to the front using the "Cons(head, tail)"
  30 // function, which will allocate a new cons cell. Notably, cons lists
  31 // support creating multiple lists that share a common tail sequence.
  32 //
  33 // Lastly, lists support iteration via C++11's range-based for loop
  34 // construct.
  35 //
  36 // Examples:
  37 //
  38 //   // basic construction
  39 //   const cons::List<char> kNil = nullptr;
  40 //   cons::List<char> ba = Cons('b', Cons('a', kNil));
  41 //
  42 //   // common tail sequence
  43 //   cons::List<char> cba = Cons('c', ba);
  44 //   cons::List<char> dba = Cons('d', ba);
  45 //
  46 //   // iteration
  47 //   for (const char& ch : cba) {
  48 //     // iterates 'c', 'b', 'a'
  49 //   }
  50 //   for (const char& ch : dba) {
  51 //     // iterates 'd', 'b', 'a'
  52 //   }
  53
  54 // Forward declarations.
  55 template <typename T>
  56 class Cell;
  57 template <typename T>
  58 class ListIterator;
  59
  60 // List represents a (possibly null) pointer to a cons cell.
  61 template <typename T>
  62 using List = scoped_refptr<const Cell<T>>;
  63
  64 // Cons extends a cons list by prepending a new value to the front.
  65 template <typename T>
  66 List<T> Cons(const T& head, const List<T>& tail) {
  67   return List<T>(new const Cell<T>(head, tail));
  68 }
  69
  70 // Cell represents an individual "cons cell" within a cons list.
  71 template <typename T>
  72 class Cell : public base::RefCounted<Cell<T>> {
  73  public:
  74   Cell(const T& head, const List<T>& tail) : head_(head), tail_(tail) {}
  75
  76   // Head returns this cell's head element.
  77   const T& head() const { return head_; }
  78
  79   // Tail returns this cell's tail element.
  80   const List<T>& tail() const { return tail_; }
  81
  82  private:
  83   virtual ~Cell() {}
  84
  85   T head_;
  86   List<T> tail_;
  87
  88   friend class base::RefCounted<Cell<T>>;
  89   DISALLOW_COPY_AND_ASSIGN(Cell);
  90 };
  91
  92 // Begin returns a list iterator pointing to the first element of the
  93 // cons list. It's provided to support range-based for loops.
  94 template <typename T>
  95 ListIterator<T> begin(const List<T>& list) {
  96   return ListIterator<T>(list);
  97 }
  98
  99 // End returns a list iterator pointing to the "past-the-end" element
 100 // of the cons list (i.e., nil). It's provided to support range-based
 101 // for loops.
 102 template <typename T>
 103 ListIterator<T> end(const List<T>& list) {
 104   return ListIterator<T>();
 105 }
 106
 107 // ListIterator provides C++ forward iterator semantics for traversing
 108 // a cons list.
 109 template <typename T>
 110 class ListIterator {
 111  public:
 112   ListIterator() : list_() {}
 113   explicit ListIterator(const List<T>& list) : list_(list) {}
 114
 115   const T& operator*() const { return list_->head(); }
 116
 117   ListIterator& operator++() {
 118     list_ = list_->tail();
 119     return *this;
 120   }
 121
 122   friend bool operator==(const ListIterator& lhs, const ListIterator& rhs) {
 123     return lhs.list_ == rhs.list_;
 124   }
 125
 126  private:
 127   List<T> list_;
 128 };
 129
 130 template <typename T>
 131 bool operator!=(const ListIterator<T>& lhs, const ListIterator<T>& rhs) {
 132   return !(lhs == rhs);
 133 }
 134
 135 }  // namespace cons
 136 }  // namespace sandbox
 137
 138 #endif  // SANDBOX_LINUX_BPF_DSL_CONS_H_