Packed Struct Offset Lookup

In low-latency systems and binary protocol implementations, understanding memory layout and field offsets is crucial for performance. When dealing with packed binary structures that evolve over time, you need a system to manage field offsets across different versions while maintaining fast lookup performance.

The Problem

Binary protocols often use packed structures where fields are laid out sequentially in memory without padding. As protocols evolve, new fields are added, removed, or reordered, changing the memory layout. You need to:

1. Track field offsets for each version of the structure
2. Calculate offsets efficiently without repeated computation
3. Support versioning to handle backward compatibility
4. Provide fast lookups for performance-critical code

Memory Layout Example

Consider a simple market data packet:

Version 1:

[header:4][timestamp:8][price:8]
  0        4           12       20 bytes

Version 2 (adds symbol field):

[header:4][symbol:8][timestamp:8][price:8]
  0        4        12        20       28 bytes

Notice how adding a field in the middle shifts all subsequent field offsets. The timestamp field moves from offset 4 to offset 12.

Key Concepts

Field Alignment and Packing

• Packed structures have no padding between fields
• Field offsets are cumulative (each field starts where the previous one ends)
• Version changes can affect all downstream field positions

Offset Calculation

// Simple offset calculation for sequential fields
size_t calculateOffset(const std::vector<std::pair<std::string, size_t>>& fields, 
                      const std::string& targetField) {
    size_t offset = 0;
    for (const auto& [name, size] : fields) {
        if (name == targetField) {
            return offset;
        }
        offset += size;
    }
    return SIZE_MAX; // Field not found
}

Versioning Strategy

• Immutable versions: Once created, a version's structure never changes
• Version IDs: Sequential numbering (1, 2, 3, ...) or semantic versioning
• Backward compatibility: Old code can still work with new structures

Performance Considerations

Memoization

Repeated offset lookups should be cached:

// Cache structure: version_id -> (field_name -> offset)
std::unordered_map<uint32_t, std::unordered_map<std::string, size_t>> offsetCache;

Lookup Complexity

• Direct lookup: O(1) with hash map caching
• Field iteration: O(n) for uncached lookups
• Memory overhead: Trade-off between speed and storage

Your Task

Design a PacketStructureManager class that manages field offsets in packed binary structures with versioning support. The class should efficiently handle multiple protocol versions and provide fast offset lookups.

Requirements

1. Constructor: Initialize an empty structure manager
2. modify_structure(fields): Add a new version with the given field structure
3. get_offset(field_name, version_id): Get field offset in a specific version
4. get_offset(field_name): Get field offset in the latest version
5. get_packet_size(version_id): Get total size of a specific version
6. has_field(field_name, version_id): Check if a field exists in a version
7. get_field_names(version_id): Get all field names for a version

Implementation Hints

• Use memoization to cache calculated offsets for fast lookups
• Store version history to support backward compatibility
• Calculate offsets sequentially by summing field sizes
• Handle field insertion and reordering between versions
• Ensure thread safety if needed for concurrent access

Example Usage

PacketStructureManager manager;

// Create V1 structure
std::vector<std::pair<std::string, size_t>> v1_fields = {
    {"header", 4},      // uint32_t
    {"timestamp", 8},   // uint64_t  
    {"price", 8}        // double
};
manager.modify_structure(v1_fields);

// Query V1 offsets
size_t timestamp_offset = manager.get_offset("timestamp", 1);  // Returns 4
size_t v1_size = manager.get_packet_size(1);                  // Returns 20

// Create V2 structure (adds symbol field)
std::vector<std::pair<std::string, size_t>> v2_fields = {
    {"header", 4},      // uint32_t
    {"symbol", 8},      // char[8] - new field
    {"timestamp", 8},   // uint64_t  
    {"price", 8}        // double
};
manager.modify_structure(v2_fields);

// Query V2 offsets
size_t v2_timestamp = manager.get_offset("timestamp", 2);     // Returns 12
size_t v2_size = manager.get_packet_size(2);                  // Returns 28

Testing Considerations

• Version isolation: Changes in V2 shouldn't affect V1
• Field validation: Handle non-existent fields gracefully
• Performance: Second lookup of same field should be O(1)
• Memory efficiency: Avoid storing duplicate field information
• Error handling: Robust handling of invalid version IDs or field names

This system is essential for high-performance binary protocol implementations where every microsecond counts and protocol evolution is inevitable.

Design a PacketStructureManager class that takes a packet structure (unordered_map field-name -> size) and provides API to query field offsets. Support versioning so both v1 and latest offsets are queryable. Include functionality to modify the packet structure. Use memoization for fast offset lookups.

#include <unordered_map>
#include <vector>
#include <string>

// TODO: Design a PacketStructureManager class that manages field offsets
// in packed binary structures with versioning support
//
// Key Methods to Implement:
// - modify_structure(fields): Add new version with modified structure
// - get_offset(field_name, version_id): Get field offset in specific version
// - get_offset(field_name): Get field offset in latest version  
// - get_packet_size(version_id): Get total size of version

class PacketStructureManager {
private:
    // TODO: Design your internal data structures

public:
    // TODO: Constructor
    PacketStructureManager() {
        // Initialize your data structures
    }

    // TODO: Get field offset for a specific version
    size_t get_offset(const std::string& field_name, uint32_t version_id) {
        return 0;
    }

    // TODO: Get field offset for the latest version
    size_t get_offset(const std::string& field_name) {
        return 0;
    }

    // TODO: Get total packet size for a version
    size_t get_packet_size(uint32_t version_id) {
        return 0;
    }

    // TODO: Add a new version by modifying the current structure
    uint32_t modify_structure(std::vector<std::pair<std::string, size_t>> new_fields) {
        return 0;
    }

    // TODO: Check if a field exists in a specific version
    bool has_field(const std::string& field_name, uint32_t version_id) {
        // Return true if field exists in the specified version
        return false;
    }

    // TODO: Get all field names for a version
    std::vector<std::string> get_field_names(uint32_t version_id) {
        // Return list of all fields in deterministic order
        return {};
    }
};