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
|
// Copyright 2014 The Chromium Authors. All rights reserved.
// 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 "base/macros.h"
#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)) {}
// 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_;
DISALLOW_COPY_AND_ASSIGN(Cell);
};
// 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_
|
