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