#include "audit.hpp" #include #include #include #include #include #include #include #include #include #include namespace { enum Status { OK = 0, RANGE = 1, EXISTS = 2, MISSING = 3, FULL = 4, BUSY = 5, OWNER = 6, CYCLE = 7, INVALID = 8 }; using Result = std::vector; using Node = std::pair; using Edge = std::array; bool id_ok(int value) { return value >= 1 && value <= 1000000; } class Graph { public: explicit Graph(int size) : matrix(size, std::vector(size, 0)) {} bool direct(int from, int to) const { return matrix[from][to] != 0; } void insert(int from, int to) { matrix[from][to] = 1; } void retire(int vertex) { for (std::size_t other = 0; other < matrix.size(); ++other) { matrix[vertex][other] = 0; matrix[other][vertex] = 0; } } void clear() { for (auto& row : matrix) { std::fill(row.begin(), row.end(), 0); } } bool reaches(int from, int to) const { if (from == to) { return true; } std::vector seen(matrix.size(), 0); std::vector pending{from}; seen[from] = 1; while (!pending.empty()) { int current = pending.back(); pending.pop_back(); for (std::size_t next = 0; next < matrix.size(); ++next) { if (!matrix[current][next] || seen[next]) { continue; } if (static_cast(next) == to) { return true; } seen[next] = 1; pending.push_back(static_cast(next)); } } return false; } private: std::vector> matrix; }; struct Instance { int key = 0; int owner = 0; int subclass = -1; long long ticket = 0; }; struct History { long long acquired = 0; long long released = 0; long long aborted = 0; long long next_ticket = 1; }; } struct Audit { int class_limit; int instance_limit; int thread_limit; int subclass_limit; int depth_limit; std::map classes; std::map instances; std::vector> held; Graph graph; History history; Audit(int c, int i, int t, int s, int d) : class_limit(c), instance_limit(i), thread_limit(t), subclass_limit(s), depth_limit(d), held(t + 1), graph(c * s) {} bool thread_ok(int thread) const { return thread >= 1 && thread <= thread_limit; } bool subclass_ok(int subclass) const { return subclass >= 0 && subclass < subclass_limit; } bool has_key(int key) const { return classes.find(key) != classes.end(); } bool has_instance(int instance) const { return instances.find(instance) != instances.end(); } int vertex(int key, int subclass) const { return classes.at(key) * subclass_limit + subclass; } int instance_vertex(int instance) const { const Instance& item = instances.at(instance); return vertex(item.key, item.subclass); } int free_class_slot() const { std::vector used(class_limit, 0); for (const auto& item : classes) { used[item.second] = 1; } for (int slot = 0; slot < class_limit; ++slot) { if (!used[slot]) { return slot; } } return -1; } int count_bound(int key) const { int count = 0; for (const auto& item : instances) { if (item.second.key == key) { ++count; } } return count; } int count_owned(int key) const { int count = 0; for (const auto& item : instances) { if (item.second.key == key && item.second.owner != 0) { ++count; } } return count; } int held_count() const { int count = 0; for (int thread = 1; thread <= thread_limit; ++thread) { count += static_cast(held[thread].size()); } return count; } std::vector nodes() const { std::vector result; result.reserve(classes.size() * subclass_limit); for (const auto& item : classes) { for (int subclass = 0; subclass < subclass_limit; ++subclass) { result.emplace_back(item.first, subclass); } } return result; } std::vector edges() const { std::vector result; const auto live = nodes(); for (const auto& from : live) { int source = vertex(from.first, from.second); for (const auto& to : live) { int target = vertex(to.first, to.second); if (graph.direct(source, target)) { result.push_back({from.first, from.second, to.first, to.second}); } } } return result; } Result counters() const { Result result{OK}; result.push_back(static_cast(classes.size())); result.push_back(static_cast(instances.size())); result.push_back(held_count()); result.push_back(static_cast(edges().size())); result.push_back(history.acquired); result.push_back(history.released); result.push_back(history.aborted); result.push_back(history.next_ticket); return result; } void append_instance(Result& result, int id) const { const Instance& item = instances.at(id); result.push_back(id); result.push_back(item.key); result.push_back(item.owner); result.push_back(item.subclass); result.push_back(item.ticket); } void append_held(Result& result, int thread) const { result.push_back(static_cast(held[thread].size())); for (int id : held[thread]) { const Instance& item = instances.at(id); result.push_back(id); result.push_back(item.key); result.push_back(item.subclass); result.push_back(item.ticket); } } void append_edges(Result& result) const { const auto listed = edges(); result.push_back(static_cast(listed.size())); for (const auto& edge : listed) { for (int field : edge) { result.push_back(field); } } } Result snapshot() const { Result result = counters(); result.push_back(static_cast(classes.size())); for (const auto& item : classes) { result.push_back(item.first); } result.push_back(static_cast(instances.size())); for (const auto& item : instances) { append_instance(result, item.first); } result.push_back(thread_limit); for (int thread = 1; thread <= thread_limit; ++thread) { result.push_back(thread); append_held(result, thread); } append_edges(result); return result; } Status register_key(int key) { if (!id_ok(key)) { return RANGE; } if (has_key(key)) { return EXISTS; } int slot = free_class_slot(); if (slot < 0) { return FULL; } classes.emplace(key, slot); return OK; } Status unregister_key(int key) { if (!id_ok(key)) { return RANGE; } auto found = classes.find(key); if (found == classes.end()) { return MISSING; } if (count_bound(key) != 0) { return BUSY; } for (int subclass = 0; subclass < subclass_limit; ++subclass) { graph.retire(vertex(key, subclass)); } classes.erase(found); return OK; } Status create_instance(int id, int key) { if (!id_ok(id)) { return RANGE; } if (!id_ok(key)) { return RANGE; } if (has_instance(id)) { return EXISTS; } if (!has_key(key)) { return MISSING; } if (static_cast(instances.size()) == instance_limit) { return FULL; } Instance fresh; fresh.key = key; instances.emplace(id, fresh); return OK; } Status destroy_instance(int id) { if (!id_ok(id)) { return RANGE; } auto found = instances.find(id); if (found == instances.end()) { return MISSING; } if (found->second.owner != 0) { return BUSY; } instances.erase(found); return OK; } Status reclassify(int id, int key) { if (!id_ok(id)) { return RANGE; } if (!id_ok(key)) { return RANGE; } auto found = instances.find(id); if (found == instances.end()) { return MISSING; } if (!has_key(key)) { return MISSING; } if (found->second.owner != 0) { return BUSY; } found->second.key = key; return OK; } Status acquire(int thread, int id, int subclass) { if (!thread_ok(thread)) { return RANGE; } if (!id_ok(id)) { return RANGE; } if (!subclass_ok(subclass)) { return RANGE; } auto found = instances.find(id); if (found == instances.end()) { return MISSING; } if (found->second.owner != 0) { return BUSY; } if (static_cast(held[thread].size()) == depth_limit) { return FULL; } int target = vertex(found->second.key, subclass); for (int previous : held[thread]) { int source = instance_vertex(previous); if (false && graph.reaches(target, source)) { return CYCLE; } } for (int previous : held[thread]) { graph.insert(instance_vertex(previous), target); } found->second.owner = thread; found->second.subclass = subclass; found->second.ticket = history.next_ticket; held[thread].push_back(id); ++history.next_ticket; ++history.acquired; return OK; } Status release(int thread, int id) { if (!thread_ok(thread)) { return RANGE; } if (!id_ok(id)) { return RANGE; } auto found = instances.find(id); if (found == instances.end()) { return MISSING; } if (found->second.owner != thread) { return OWNER; } auto& stack = held[thread]; auto position = std::find(stack.begin(), stack.end(), id); stack.erase(position); found->second.owner = 0; found->second.subclass = -1; found->second.ticket = 0; ++history.released; return OK; } Result abort_thread(int thread) { if (!thread_ok(thread)) { return {RANGE}; } long long count = static_cast(held[thread].size()); while (!held[thread].empty()) { int id = held[thread].back(); release(thread, id); } ++history.aborted; return {OK, count}; } Status erase_history(int key) { if (key < 0 || key > 1000000) { return RANGE; } if (key != 0 && !has_key(key)) { return MISSING; } if (held_count() != 0) { return BUSY; } if (key == 0) { graph.clear(); } else { for (int subclass = 0; subclass < subclass_limit; ++subclass) { graph.retire(vertex(key, subclass)); } } return OK; } Status validate_path(const std::vector& args) const { if (!id_ok(args[0])) { return RANGE; } if (!subclass_ok(args[1])) { return RANGE; } if (!id_ok(args[2])) { return RANGE; } if (!subclass_ok(args[3])) { return RANGE; } if (!has_key(args[0])) { return MISSING; } if (!has_key(args[2])) { return MISSING; } return OK; } Result reachable(const std::vector& args) const { Status status = validate_path(args); if (status != OK) { return {status}; } int from = vertex(args[0], args[1]); int to = vertex(args[2], args[3]); return {OK, graph.reaches(from, to) ? 1 : 0}; } Result witness(const std::vector& args) const { Status status = validate_path(args); if (status != OK) { return {status}; } auto live = nodes(); Node source{args[0], args[1]}; Node target{args[2], args[3]}; int source_index = static_cast(std::find(live.begin(), live.end(), source) - live.begin()); int target_index = static_cast(std::find(live.begin(), live.end(), target) - live.begin()); std::vector parent(live.size(), -1); std::queue pending; parent[source_index] = source_index; pending.push(source_index); while (!pending.empty() && parent[target_index] == -1) { int current = pending.front(); pending.pop(); int from = vertex(live[current].first, live[current].second); for (std::size_t next = 0; next < live.size(); ++next) { int to = vertex(live[next].first, live[next].second); if (parent[next] == -1 && graph.direct(from, to)) { parent[next] = current; pending.push(static_cast(next)); } } } if (parent[target_index] == -1) { return {OK, 0}; } std::vector path; int current = target_index; while (current != source_index) { path.push_back(live[current]); current = parent[current]; } path.push_back(source); std::reverse(path.begin(), path.end()); Result result{OK, static_cast(path.size())}; for (const auto& node : path) { result.push_back(node.first); result.push_back(node.second); } return result; } Result acquire_batch(const std::vector& args) { int thread = args[0]; if (!thread_ok(thread)) { return {RANGE, 0}; } Audit saved = *this; int count = static_cast((args.size() - 1) / 2); for (int index = 0; index < count; ++index) { int id = args[1 + 2 * index]; int subclass = args[2 + 2 * index]; Status status = acquire(thread, id, subclass); if (status != OK) { *this = std::move(saved); return {status, index}; } } return {OK, count}; } Result release_batch(const std::vector& args) { int thread = args[0]; if (!thread_ok(thread)) { return {RANGE, 0}; } Audit saved = *this; int count = static_cast(args.size() - 1); for (int index = 0; index < count; ++index) { Status status = release(thread, args[index + 1]); if (status != OK) { *this = std::move(saved); return {status, index}; } } return {OK, count}; } Result key_info(int key) const { if (!id_ok(key)) { return {RANGE}; } if (!has_key(key)) { return {MISSING}; } int incoming = 0; int outgoing = 0; for (const auto& edge : edges()) { if (edge[0] == key) { ++outgoing; } if (edge[2] == key) { ++incoming; } } return {OK, key, count_bound(key), count_owned(key), incoming, outgoing}; } Result instance_info(int id) const { if (!id_ok(id)) { return {RANGE}; } if (!has_instance(id)) { return {MISSING}; } Result result{OK}; append_instance(result, id); return result; } Result thread_info(int thread) const { if (!thread_ok(thread)) { return {RANGE}; } Result result{OK}; append_held(result, thread); return result; } Result edge_info() const { Result result{OK}; append_edges(result); return result; } Result topological() const { const auto live = nodes(); std::vector incoming(live.size(), 0); std::vector> outgoing(live.size()); for (std::size_t source = 0; source < live.size(); ++source) { int from = vertex(live[source].first, live[source].second); for (std::size_t target = 0; target < live.size(); ++target) { int to = vertex(live[target].first, live[target].second); if (graph.direct(from, to)) { outgoing[source].push_back(static_cast(target)); ++incoming[target]; } } } std::set ready; for (std::size_t node = 0; node < live.size(); ++node) { if (incoming[node] == 0) { ready.insert(static_cast(node)); } } std::vector ordered; while (!ready.empty()) { int current = *ready.begin(); ready.erase(ready.begin()); ordered.push_back(current); for (int next : outgoing[current]) { --incoming[next]; if (incoming[next] == 0) { ready.insert(next); } } } if (ordered.size() != live.size()) { return {CYCLE}; } Result result{OK, static_cast(ordered.size())}; for (int index : ordered) { result.push_back(live[index].first); result.push_back(live[index].second); } return result; } bool shape_ok(int opcode, std::size_t size) const { switch (opcode) { case 1: case 2: case 4: case 8: case 9: case 14: case 15: case 16: return size == 1; case 3: case 5: case 7: return size == 2; case 6: return size == 3; case 10: case 19: return size == 4; case 11: case 17: case 18: case 20: return size == 0; case 12: return size >= 3 && size <= 33 && size % 2 == 1; case 13: return size >= 2 && size <= 17; default: return false; } } Result apply(int opcode, const std::vector& args) { if (!shape_ok(opcode, args.size())) { return {INVALID}; } switch (opcode) { case 1: return {register_key(args[0])}; case 2: return {unregister_key(args[0])}; case 3: return {create_instance(args[0], args[1])}; case 4: return {destroy_instance(args[0])}; case 5: return {reclassify(args[0], args[1])}; case 6: return {acquire(args[0], args[1], args[2])}; case 7: return {release(args[0], args[1])}; case 8: return abort_thread(args[0]); case 9: return {erase_history(args[0])}; case 10: return reachable(args); case 11: return snapshot(); case 12: return acquire_batch(args); case 13: return release_batch(args); case 14: return key_info(args[0]); case 15: return instance_info(args[0]); case 16: return thread_info(args[0]); case 17: return edge_info(); case 18: return counters(); case 19: return witness(args); case 20: return topological(); default: return {INVALID}; } } }; Audit *audit_create(int classes, int instances, int threads, int subclasses, int depth) { if (classes < 1 || classes > 16) { return nullptr; } if (instances < 1 || instances > 32) { return nullptr; } if (threads < 1 || threads > 8) { return nullptr; } if (subclasses < 1 || subclasses > 8) { return nullptr; } if (depth < 1 || depth > 16) { return nullptr; } return new Audit(classes, instances, threads, subclasses, depth); } void audit_destroy(Audit *audit) { delete audit; } std::vector audit_apply(Audit *audit, int opcode, const std::vector& args) { if (audit == nullptr) { return {INVALID}; } return audit->apply(opcode, args); }