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