ch18/bad_table.h103 lines
// reading_table.h: stn::ReadingTable, a hash table with chaining.
#pragma once
#include <cstddef>
#include <cstdint>
#include <stdexcept>
#include <string>
#include <vector>
namespace stn {
struct Reading {
std::uint32_t sensor_id;
std::int64_t time_s;
double value;
std::uint8_t flags;
};
using HashFn = std::uint32_t (*)(std::uint32_t);
inline std::uint32_t mix_hash(std::uint32_t id) {
std::uint32_t h = id * 2654435769u; // spread bits upward
h ^= h >> 16; // fold high bits down
h *= 2654435769u; // and once more
return h ^ (h >> 16);
}
class ReadingTable {
public:
explicit ReadingTable(std::size_t buckets = 8,
HashFn hash = mix_hash);
bool insert_or_assign(const Reading& r); // true if new key
const Reading* find(std::uint32_t id) const; // or nullptr
const Reading& at(std::uint32_t id) const; // or throws
std::size_t size() const { return size_; }
std::size_t bucket_count() const { return buckets_.size(); }
double load_factor() const {
return 1.0 * size_ / buckets_.size();
}
std::size_t bucket_size(std::size_t b) const {
return buckets_[b].size();
}
std::size_t moves() const { return moves_; } // by rehash
private:
std::size_t index_for(std::uint32_t id) const {
return hash_(id) % buckets_.size();
}
void rehash(std::size_t new_count);
static constexpr double MAX_LOAD = 1.0;
std::vector<std::vector<Reading>> buckets_;
HashFn hash_;
std::size_t size_ = 0;
std::size_t moves_ = 0;
};
inline ReadingTable::ReadingTable(std::size_t buckets, HashFn hash)
: buckets_(buckets == 0 ? 1 : buckets), hash_(hash) {}
inline const Reading* ReadingTable::find(std::uint32_t id)
const {
for (const Reading& r : buckets_[index_for(id)]) {
if (r.sensor_id == id) {
return &r;
}
}
return nullptr;
}
inline const Reading& ReadingTable::at(std::uint32_t id) const {
const Reading* r = find(id);
if (r == nullptr) {
throw std::out_of_range("no reading for sensor " +
std::to_string(id));
}
return *r;
}
inline bool ReadingTable::insert_or_assign(const Reading& r) {
std::vector<Reading>& chain =
buckets_[index_for(r.sensor_id)];
for (Reading& old : chain) {
if (old.sensor_id == r.sensor_id) {
old = r; // key exists: overwrite
return false;
}
}
if (1.0 * (size_ + 1) / buckets_.size() > MAX_LOAD) {
rehash(buckets_.size() * 2); // strong guarantee
}
buckets_[index_for(r.sensor_id)].push_back(r);
++size_;
return true;
}
inline void ReadingTable::rehash(std::size_t new_count) {
std::vector<std::vector<Reading>> fresh(new_count);
for (std::size_t i = 0; i < buckets_.size(); ++i) {
fresh[i] = std::move(buckets_[i]); // keep each chain
}
moves_ += size_;
buckets_.swap(fresh);
}
} // namespace stn
ch18/bad_test.cpp16 lines
#include "bad_table.h"
#include <cstdio>
int main(void) {
stn::ReadingTable t;
std::size_t missing = 0;
for (std::uint32_t s = 1; s <= 250; ++s)
for (std::uint32_t k = 1; k <= 4; ++k)
t.insert_or_assign({s * 1000 + k, 60, 20.0, 1});
for (std::uint32_t s = 1; s <= 250; ++s)
for (std::uint32_t k = 1; k <= 4; ++k)
if (t.find(s * 1000 + k) == nullptr) ++missing;
std::printf("size %zu, buckets %zu, keys not found %zu\n", t.size(), t.bucket_count(), missing);
stn::ReadingTable u; for (std::uint32_t id : {1001u,1002u,1003u,1004u,2001u,2002u,2003u,2004u}) u.insert_or_assign({id,0,0,0});
std::size_t m8=0; for (std::uint32_t id : {1001u,1002u,1003u,1004u,2001u,2002u,2003u,2004u}) if(!u.find(id)) ++m8;
std::printf("8 keys, no resize: missing %zu\n", m8);
}
ch18/calibrate.cpp40 lines
// calibrate.cpp: basic and strong exception safety.
#include <cstdio>
#include <stdexcept>
#include <vector>
double calibrated(double celsius, double offset) {
double c = celsius + offset;
if (c < -60.0 || c > 60.0) {
throw std::domain_error("result outside sensor range");
}
return c;
}
// Basic guarantee: after a throw, v is valid, partly changed.
void calibrate_in_place(std::vector<double>& v, double offset) {
for (double& x : v) { x = calibrated(x, offset); }
}
// Strong guarantee: after a throw, v is exactly as it was.
void calibrate_strong(std::vector<double>& v, double offset) {
std::vector<double> work = v; // copy; may throw
for (double& x : work) { x = calibrated(x, offset); }
v.swap(work); // no-throw commit
}
void show(const char* label, const std::vector<double>& v) {
std::printf("%-9s", label);
for (double x : v) { std::printf(" %5.1f", x); }
std::printf("\n");
}
int main(void) {
std::vector<double> a = {20.5, 21.0, 59.5, 22.0};
std::vector<double> b = a;
try { calibrate_in_place(a, 1.0); }
catch (const std::domain_error& e) { std::puts(e.what()); }
try { calibrate_strong(b, 1.0); }
catch (const std::domain_error& e) { std::puts(e.what()); }
show("basic:", a);
show("strong:", b);
return 0;
}
ch18/churn.cpp19 lines
// churn.cpp: heap traffic of 1,000 inserts, with and without resizes.
#include "reading_table.h"
#include <cstdio>
#include <cstdlib>
int main(int argc, char** argv) {
std::size_t start = argc > 1 ? std::strtoul(argv[1], nullptr, 10) : 8;
stn::ReadingTable table(start);
for (std::uint32_t s = 1; s <= 250; ++s) {
for (std::uint32_t k = 1; k <= 4; ++k) {
table.insert_or_assign({s * 1000 + k, 60, 20.0, 1});
}
}
std::printf("start %zu: buckets %zu, entries moved %zu\n", start,
table.bucket_count(), table.moves());
std::printf("sizeof(Reading) %zu, sizeof(chain) %zu\n",
sizeof(stn::Reading), sizeof(std::vector<stn::Reading>));
return 0;
}
ch18/dangle.cpp20 lines
// dangle.cpp: a pointer from find() dies at a later insert.
#include "reading_table.h"
#include <cstdio>
int main(void) {
std::setvbuf(stdout, nullptr, _IONBF, 0); // unbuffered
stn::ReadingTable table; // 8 buckets
table.insert_or_assign({1001, 60, 21.75, 3});
const stn::Reading* p = table.find(1001); // into a chain
std::printf("before: %.2f, buckets %zu\n", p->value,
table.bucket_count());
const std::uint32_t more[] = {1002, 1003, 1004, 2001,
2002, 2003, 2004, 3001};
for (std::uint32_t id : more) { // 9th resizes
table.insert_or_assign({id, 60, 20.0, 1});
}
std::printf("after: buckets %zu\n", table.bucket_count());
std::printf("p->value %.2f\n", p->value); // p is stale
return 0;
}
ch18/hist.cpp33 lines
// hist.cpp: how 1,000 sensor IDs spread over 16 buckets.
#include "reading_table.h"
#include <cstdio>
std::uint32_t weak_hash(std::uint32_t id) { return id % 1000; }
std::uint32_t identity_hash(std::uint32_t id) { return id; }
void histogram(const char* name, stn::HashFn hash) {
const std::size_t BUCKETS = 16;
std::vector<int> count(BUCKETS, 0);
for (std::uint32_t station = 1; station <= 250; ++station) {
for (std::uint32_t k = 1; k <= 4; ++k) {
++count[hash(station * 1000 + k) % BUCKETS];
}
}
int empty = 0, longest = 0;
std::printf("%s\n", name);
for (std::size_t b = 0; b < BUCKETS; ++b) {
std::printf(" %2zu %4d %.*s\n", b, count[b],
count[b] / 10, "#########################");
if (count[b] == 0) { ++empty; }
if (count[b] > longest) { longest = count[b]; }
}
std::printf(" empty buckets %d, longest chain %d\n",
empty, longest);
}
int main(void) {
histogram("weak: id % 1000", weak_hash);
histogram("identity: id", identity_hash);
histogram("mix: stn::mix_hash", stn::mix_hash);
return 0;
}
ch18/lookup.cpp39 lines
// lookup.cpp: exceptions from parsing and lookup.
#include "reading_table.h"
#include <cstdio>
#include <stdexcept>
#include <string>
struct Tracer { // prints when destroyed
const char* name;
~Tracer() { std::printf(" ~Tracer(%s)\n", name); }
};
double latest_value(const stn::ReadingTable& t,
const std::string& text) {
Tracer guard{text.c_str()};
unsigned long id = std::stoul(text); // may throw
if (id > UINT32_MAX) {
throw std::out_of_range("id too large: " + text);
}
return t.at(static_cast<std::uint32_t>(id)).value;
}
int main(void) {
stn::ReadingTable table;
table.insert_or_assign({1001, 60, 21.75, 3});
const char* inputs[] = {"1001", "1002", "x1001", "10O1",
"99999999999"};
for (const char* text : inputs) {
std::printf("lookup \"%s\"\n", text);
try {
double v = latest_value(table, text);
std::printf(" value %.2f\n", v);
} catch (const std::invalid_argument& e) {
std::printf(" not a number (%s)\n", e.what());
} catch (const std::out_of_range& e) {
std::printf(" out of range: %s\n", e.what());
}
}
return 0;
}
ch18/nosink.cpp29 lines
// nosink.cpp: a timing loop whose result is never used.
#include <chrono>
#include <cstdint>
#include <cstdio>
#include <vector>
bool contains(const std::vector<std::uint32_t>& v, std::uint32_t key) {
for (std::uint32_t x : v) { if (x == key) { return true; } }
return false;
}
int main(void) {
std::vector<std::uint32_t> ids;
for (std::uint32_t i = 0; i < 1000000; ++i) { ids.push_back(i); }
auto t0 = std::chrono::steady_clock::now();
for (int q = 0; q < 1000; ++q) {
contains(ids, 999999); // result discarded
}
auto t1 = std::chrono::steady_clock::now();
int found = 0;
for (int q = 0; q < 1000; ++q) {
found += contains(ids, 999999 - q); // result used
}
auto t2 = std::chrono::steady_clock::now();
std::chrono::duration<double, std::micro> a = t1 - t0, b = t2 - t1;
std::printf("unused: %.1f us total\n", a.count());
std::printf("used: %.1f us total (found %d)\n", b.count(), found);
return 0;
}
ch18/reading_table.h105 lines
// reading_table.h: stn::ReadingTable, a hash table with chaining.
#pragma once
#include <cstddef>
#include <cstdint>
#include <stdexcept>
#include <string>
#include <vector>
namespace stn {
struct Reading {
std::uint32_t sensor_id;
std::int64_t time_s;
double value;
std::uint8_t flags;
};
using HashFn = std::uint32_t (*)(std::uint32_t);
inline std::uint32_t mix_hash(std::uint32_t id) {
std::uint32_t h = id * 2654435769u; // spread bits upward
h ^= h >> 16; // fold high bits down
h *= 2654435769u; // and once more
return h ^ (h >> 16);
}
class ReadingTable {
public:
explicit ReadingTable(std::size_t buckets = 8,
HashFn hash = mix_hash);
bool insert_or_assign(const Reading& r); // true if new key
const Reading* find(std::uint32_t id) const; // or nullptr
const Reading& at(std::uint32_t id) const; // or throws
std::size_t size() const { return size_; }
std::size_t bucket_count() const { return buckets_.size(); }
double load_factor() const {
return 1.0 * size_ / buckets_.size();
}
std::size_t bucket_size(std::size_t b) const {
return buckets_[b].size();
}
std::size_t moves() const { return moves_; } // by rehash
private:
std::size_t index_for(std::uint32_t id) const {
return hash_(id) % buckets_.size();
}
void rehash(std::size_t new_count);
static constexpr double MAX_LOAD = 1.0;
std::vector<std::vector<Reading>> buckets_;
HashFn hash_;
std::size_t size_ = 0;
std::size_t moves_ = 0;
};
inline ReadingTable::ReadingTable(std::size_t buckets, HashFn hash)
: buckets_(buckets == 0 ? 1 : buckets), hash_(hash) {}
inline const Reading* ReadingTable::find(std::uint32_t id)
const {
for (const Reading& r : buckets_[index_for(id)]) {
if (r.sensor_id == id) {
return &r;
}
}
return nullptr;
}
inline const Reading& ReadingTable::at(std::uint32_t id) const {
const Reading* r = find(id);
if (r == nullptr) {
throw std::out_of_range("no reading for sensor " +
std::to_string(id));
}
return *r;
}
inline bool ReadingTable::insert_or_assign(const Reading& r) {
std::vector<Reading>& chain =
buckets_[index_for(r.sensor_id)];
for (Reading& old : chain) {
if (old.sensor_id == r.sensor_id) {
old = r; // key exists: overwrite
return false;
}
}
if (1.0 * (size_ + 1) / buckets_.size() > MAX_LOAD) {
rehash(buckets_.size() * 2); // strong guarantee
}
buckets_[index_for(r.sensor_id)].push_back(r);
++size_;
return true;
}
inline void ReadingTable::rehash(std::size_t new_count) {
std::vector<std::vector<Reading>> fresh(new_count);
for (const std::vector<Reading>& chain : buckets_) {
for (const Reading& r : chain) {
fresh[hash_(r.sensor_id) % new_count].push_back(r);
}
}
moves_ += size_;
buckets_.swap(fresh); // noexcept: commit point
} // old buckets freed with fresh
} // namespace stn
ch18/search_study.cpp152 lines
// search_study.cpp: PA6 reference harness (instructor-owned).
// Build for timing: g++ -std=c++20 -O2 -DNDEBUG -o study search_study.cpp
#include "reading_table.h"
#include <algorithm>
#include <chrono>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <memory>
#include <random>
#include <unordered_map>
#include <vector>
static std::uint64_t g_sink = 0; // keeps the optimizer from deleting work
struct Stats { double median, lo, hi; };
template <typename Lookup>
Stats time_lookups(Lookup lookup,
const std::vector<std::uint32_t>& queries) {
const int WARMUP = 1, REPS = 11;
std::vector<double> ns;
for (int rep = 0; rep < WARMUP + REPS; ++rep) {
std::uint64_t sink = 0;
auto start = std::chrono::steady_clock::now();
for (std::uint32_t id : queries) { sink += lookup(id); }
auto stop = std::chrono::steady_clock::now();
g_sink += sink;
if (rep >= WARMUP) { // discard the warm-up run
std::chrono::duration<double, std::nano> d =
stop - start;
ns.push_back(d.count() / queries.size());
}
}
std::sort(ns.begin(), ns.end());
return {ns[REPS / 2], ns.front(), ns.back()};
}
// --- the structures under test -------------------------------------
struct Node {
stn::Reading r;
std::unique_ptr<Node> left, right;
};
class Bst {
public:
void insert(const stn::Reading& r) {
std::unique_ptr<Node>* link = &root_;
while (*link) {
if (r.sensor_id < (*link)->r.sensor_id) link = &(*link)->left;
else if (r.sensor_id > (*link)->r.sensor_id) link = &(*link)->right;
else { (*link)->r = r; return; }
}
*link = std::make_unique<Node>(Node{r, nullptr, nullptr});
}
const stn::Reading* find(std::uint32_t id) const {
const Node* n = root_.get();
while (n && n->r.sensor_id != id) {
n = id < n->r.sensor_id ? n->left.get() : n->right.get();
}
return n ? &n->r : nullptr;
}
~Bst() { destroy(std::move(root_)); }
private:
// iterative teardown so a degenerate tree cannot overflow the stack
static void destroy(std::unique_ptr<Node> n) {
std::vector<std::unique_ptr<Node>> todo;
if (n) todo.push_back(std::move(n));
while (!todo.empty()) {
std::unique_ptr<Node> cur = std::move(todo.back());
todo.pop_back();
if (cur->left) todo.push_back(std::move(cur->left));
if (cur->right) todo.push_back(std::move(cur->right));
}
}
std::unique_ptr<Node> root_;
};
std::uint32_t weak_hash(std::uint32_t id) { return id % 1000; }
static std::int64_t value_of(const stn::Reading* r) { return r ? r->time_s : -1; }
int main(int argc, char** argv) {
const unsigned SEED = 18;
const std::size_t QUERIES = 1000;
std::size_t max_n = argc > 1 ? std::strtoul(argv[1], nullptr, 10) : 1000000;
std::printf("%-8s %-16s %10s %10s %10s\n", "n", "structure", "median_ns", "min_ns",
"max_ns");
for (std::size_t n = 1000; n <= max_n; n *= 10) {
// n distinct sensors: station s has sensors s*1000+1 .. s*1000+4
std::vector<stn::Reading> data;
for (std::size_t i = 0; i < n; ++i) {
std::uint32_t id = static_cast<std::uint32_t>((i / 4 + 1) * 1000 + i % 4 + 1);
data.push_back({id, static_cast<std::int64_t>(i), 20.0, 1});
}
std::mt19937 rng(SEED);
std::shuffle(data.begin(), data.end(), rng); // arrival order
std::vector<std::uint32_t> queries;
std::uniform_int_distribution<std::size_t> pick(0, n - 1);
for (std::size_t q = 0; q < QUERIES; ++q) queries.push_back(data[pick(rng)].sensor_id);
auto report = [&](const char* name, Stats s) {
std::printf("%-8zu %-16s %10.1f %10.1f %10.1f\n", n, name, s.median, s.lo, s.hi);
};
const std::vector<stn::Reading>& unsorted = data;
report("linear scan", time_lookups([&](std::uint32_t id) {
for (const stn::Reading& r : unsorted) if (r.sensor_id == id) return r.time_s;
return std::int64_t{-1};
}, queries));
std::vector<stn::Reading> sorted = data;
std::sort(sorted.begin(), sorted.end(),
[](const stn::Reading& a, const stn::Reading& b) { return a.sensor_id < b.sensor_id; });
report("binary search", time_lookups([&](std::uint32_t id) {
auto it = std::lower_bound(sorted.begin(), sorted.end(), id,
[](const stn::Reading& r, std::uint32_t key) { return r.sensor_id < key; });
return (it != sorted.end() && it->sensor_id == id) ? it->time_s : std::int64_t{-1};
}, queries));
{
Bst bst;
for (const stn::Reading& r : data) bst.insert(r);
report("BST (random)", time_lookups([&](std::uint32_t id) { return value_of(bst.find(id)); }, queries));
}
if (n <= 10000) {
Bst bst;
for (const stn::Reading& r : sorted) bst.insert(r); // sorted arrival
report("BST (sorted)", time_lookups([&](std::uint32_t id) { return value_of(bst.find(id)); }, queries));
}
{
stn::ReadingTable table;
for (const stn::Reading& r : data) table.insert_or_assign(r);
report("hash (mix)", time_lookups([&](std::uint32_t id) { return value_of(table.find(id)); }, queries));
}
if (n <= 100000) {
stn::ReadingTable table(8, weak_hash);
for (const stn::Reading& r : data) table.insert_or_assign(r);
report("hash (id%1000)", time_lookups([&](std::uint32_t id) { return value_of(table.find(id)); }, queries));
}
{
std::unordered_map<std::uint32_t, stn::Reading> map;
for (const stn::Reading& r : data) map[r.sensor_id] = r;
report("unordered_map", time_lookups([&](std::uint32_t id) {
auto it = map.find(id);
return it == map.end() ? std::int64_t{-1} : it->second.time_s;
}, queries));
}
}
std::printf("checksum %llu\n", static_cast<unsigned long long>(g_sink));
return 0;
}
ch18/test_table.cpp24 lines
// test_table.cpp: fixed tests for stn::ReadingTable.
#include "reading_table.h"
#include <cassert>
#include <cstdio>
#include <stdexcept>
int main(void) {
stn::ReadingTable t; // 8 buckets
for (std::uint32_t s = 1; s <= 250; ++s)
for (std::uint32_t k = 1; k <= 4; ++k)
assert(t.insert_or_assign({s * 1000 + k, 60, 20.0, 1}));
assert(t.size() == 1000 && t.bucket_count() == 1024);
for (std::uint32_t s = 1; s <= 250; ++s)
for (std::uint32_t k = 1; k <= 4; ++k)
assert(t.find(s * 1000 + k) != nullptr);
assert(t.find(999) == nullptr);
assert(!t.insert_or_assign({1001, 120, 21.5, 3})); // overwrite
assert(t.at(1001).value == 21.5 && t.size() == 1000);
bool threw = false;
try { t.at(7); } catch (const std::out_of_range&) { threw = true; }
assert(threw);
std::printf("all tests passed: size %zu, buckets %zu, load %.3f\n",
t.size(), t.bucket_count(), t.load_factor());
return 0;
}
ch18/uncaught.cpp5 lines
#include "reading_table.h"
int main(void) {
stn::ReadingTable table;
return static_cast<int>(table.at(1001).value);
}