1 // -*- mode: C++ -*-
2 //
3 // Copyright (c) 2007, 2008, 2009, 2010, 2011, 2015 The University of Utah
4 // All rights reserved.
5 //
6 // This file is part of `csmith', a random generator of C programs.
7 //
8 // Redistribution and use in source and binary forms, with or without
9 // modification, are permitted provided that the following conditions are met:
10 //
11 // * Redistributions of source code must retain the above copyright notice,
12 // this list of conditions and the following disclaimer.
13 //
14 // * Redistributions in binary form must reproduce the above copyright
15 // notice, this list of conditions and the following disclaimer in the
16 // documentation and/or other materials provided with the distribution.
17 //
18 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
19 // AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
20 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
21 // ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
22 // LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
23 // CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
24 // SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
25 // INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
26 // CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
27 // ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
28 // POSSIBILITY OF SUCH DAMAGE.
29
30 #ifndef PROBABILITY_TABLE_H
31 #define PROBABILITY_TABLE_H
32
33 #include <vector>
34 #include <algorithm>
35 #include <functional>
36 #include <cassert>
37 #include "Probabilities.h"
38 #include "VectorFilter.h"
39 #include "CGOptions.h"
40 #include "random.h"
41
42 using namespace std;
43
44 template <class Key, class Value>
45 class TableEntry {
46 public:
47 TableEntry(Key k, Value v);
48
get_key()49 Key get_key() { return key_; }
50
get_value()51 Value get_value() { return value_; }
52
53 private:
54 Key key_;
55 Value value_;
56 };
57
58 template <class Key, class Value>
59 class ProbabilityTable {
60 typedef TableEntry<Key, Value> Entry;
61
62 public:
63 ProbabilityTable();
64
65 ~ProbabilityTable();
66
67 void initialize(ProbName pname);
68
69 void add_elem(Key k, Value v);
70
71 void sorted_insert(Entry *t);
72
73 Value get_value(Key k);
74
75 private:
76 Key curr_max_key_;
77 std::vector<Entry *> table_;
78 };
79
80 template <class Key, class Value>
TableEntry(Key k,Value v)81 TableEntry<Key, Value>::TableEntry(Key k, Value v)
82 : key_(k),
83 value_(v)
84 {
85 }
86
87 template <class Key, class Value>
ProbabilityTable()88 ProbabilityTable<Key, Value>::ProbabilityTable()
89 : curr_max_key_(0)
90 {
91 table_.clear();
92 }
93
94 template <class Key, class Value>
~ProbabilityTable()95 ProbabilityTable<Key, Value>::~ProbabilityTable()
96 {
97 typename vector<Entry *>::iterator i;
98 for (i = table_.begin(); i != table_.end(); ++i)
99 delete (*i);
100 table_.clear();
101 }
102
103 template <class Key, class Value>
initialize(ProbName pname)104 void ProbabilityTable<Key, Value>::initialize(ProbName pname)
105 {
106 Probabilities *impl_ = Probabilities::GetInstance();
107 impl_->set_prob_table(this, pname);
108 }
109
110 template <class Key, class Value>
my_less(TableEntry<Key,Value> * t,Key k2)111 bool my_less(TableEntry<Key, Value> *t, Key k2)
112 {
113 Key k1 = t->get_key();
114 return (k1 < k2);
115 }
116
117 template <class Key, class Value>
my_greater(TableEntry<Key,Value> * t,Key k2)118 bool my_greater(TableEntry<Key, Value> *t, Key k2)
119 {
120 Key k1 = t->get_key();
121 return (k1 > k2);
122 }
123
124 template <class Key, class Value>
125 void
sorted_insert(Entry * t)126 ProbabilityTable<Key, Value>::sorted_insert(Entry *t)
127 {
128 assert(t);
129
130 Key k = t->get_key();
131
132 if (table_.empty()) {
133 table_.push_back(t);
134 curr_max_key_ = k;
135 return;
136 }
137
138 typename vector<Entry *>::iterator i;
139 for (i=table_.begin(); i!=table_.end(); i++) {
140 if (my_greater<Key, Value>(*i, k)) {
141 break;
142 }
143 }
144 //i = find_if(table_.begin(), table_.end(), std::bind2nd(std::ptr_fun(my_greater<Key, Value>), k));
145
146 if (i != table_.end()) {
147 table_.insert(i, t);
148 }
149 else {
150 table_.push_back(t);
151 curr_max_key_ = k;
152 }
153 }
154
155 template <class Key, class Value>
156 void
add_elem(Key k,Value v)157 ProbabilityTable<Key, Value>::add_elem(Key k, Value v)
158 {
159 Entry *t = new Entry(k, v);
160 sorted_insert(t);
161 }
162
163 template <class Key, class Value>
164 Value
get_value(Key k)165 ProbabilityTable<Key, Value>::get_value(Key k)
166 {
167 assert(k < curr_max_key_);
168
169 typename vector<Entry *>::iterator i;
170 i = find_if(table_.begin(), table_.end(), std::bind2nd(std::ptr_fun(my_greater<Key, Value>), k));
171
172 assert(i != table_.end());
173 return (*i)->get_value();
174 }
175
176 class DistributionTable {
177 public:
DistributionTable()178 DistributionTable() { max_prob_ = 0;}
~DistributionTable()179 ~DistributionTable() {};
180
181 void add_entry(int key, int prob);
get_max(void)182 int get_max(void) const { return max_prob_;}
183 int key_to_prob(int key) const;
184 int rnd_num_to_key(int rnd) const;
185 private:
186 int max_prob_;
187 vector<int> keys_;
188 vector<int> probs_;
189 };
190
191 #endif
192