cons.h revision 59c5f4b0fb104e8e4806e4934a3d5d112ad695ab 
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
11namespace sandbox {
12namespace 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.
55template <typename T>
56class Cell;
57template <typename T>
58class ListIterator;
59
60// List represents a (possibly null) pointer to a cons cell.
61template <typename T>
62using List = scoped_refptr<const Cell<T>>;
63
64// Cons extends a cons list by prepending a new value to the front.
65template <typename T>
66List<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.
71template <typename T>
72class 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.
94template <typename T>
95ListIterator<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.
102template <typename T>
103ListIterator<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.
109template <typename T>
110class 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
130template <typename T>
131bool 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_
139