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