Lesson 1Choosing collision strategy for static contexts: open addressing vs static separate chaining with arraysCompares open addressing and static separate chaining for fixed-memory setups, looking at cache behaviour, fragmentation, setup complexity, and tips for picking collision methods in embedded C work.
Review of open addressing propertiesReview of static separate chainingMemory layout and cache friendlinessComplexity and implementation effortGuidelines for strategy selectionLesson 2Memory and time complexity: documenting worst and expected probes, table load factor recommendations for embeddedLooks at memory and time complexity of static hash tables, noting worst-case and expected probe counts, load factor limits, and practical size tips for embedded sensor uses.
Worst-case probe length analysisExpected probes under random hashingImpact of load factor on performanceMemory footprint and table sizingEmbedded-specific tuning guidelinesLesson 3Safe pointer handling: using indices instead of pointers, bounds checks, and avoiding NULL dereferencesCovers safe pointer use in static hash tables by using indices not raw pointers, bounds checks, and APIs that stop NULL dereferences and loose references in C code.
Indices vs pointers in static tablesImplementing robust bounds checkingAvoiding NULL and dangling referencesConverting indices to pointers safelyAPI patterns that enforce safetyLesson 4Open addressing techniques: linear probing, quadratic probing, tombstones, and deletion semantics without dynamic memoryDetails open addressing in static tables, including linear and quadratic probing, tombstone markers, and deletion rules avoiding dynamic allocation while keeping probe chains and steady performance in C.
Linear probing: algorithm and trade-offsQuadratic probing: clustering behaviorDesigning and using tombstone markersDeletion semantics and probe chain repairDetecting full table and failure modesLesson 5Integration with circular buffer: keeping most recent reading and policies for consistency (write-order, timestamps)Looks at how a static hash table works with a circular buffer to hold latest sensor data, set write order, use timestamps for freshness, and keep steady updates or similar accesses.
Mapping sensor IDs to circular buffer slotsStoring only most recent reading per sensorTimestamp fields and monotonic orderingHandling overwrite and wrap-around casesConsistency rules for concurrent-style accessLesson 6init_table: setting empty markers, initializing free lists or tombstonesExplains init_table tasks, like setting empty markers, starting free lists or tombstones, clearing metadata, and ensuring steady, checkable state before first use.
Choosing and setting empty markersInitializing tombstone and state flagsBuilding initial free-list structuresZeroing or sanitizing table memoryValidation checks after initializationLesson 7insert_or_update_reading: insert, update, handling full table, and return codesDescribes the insert_or_update_reading API, covering insert, update in place, full table handling, return codes, and collision handling with simple, strong interface in C.
Function prototype and parameter choicesInsert path for new sensor IDsUpdate path for existing sensor IDsHandling full table and error returnsDesigning clear status and error codesLesson 8Designing the bucket array: table size selection, prime sizing, and compile-time constantsDescribes bucket array design, including table size choice, prime or power-of-two sizing, compile-time constants, and trade-offs in memory, speed, and hash simplicity.
Prime vs power-of-two table sizesRelating table size to key capacityUsing compile-time constants in CBalancing memory and performancePlanning for future size adjustmentsLesson 9Static chaining with arrays: node pool design, next indexes, and free-list management in static memoryCovers static separate chaining with arrays, including node pool layout, next index links, free-list handling, and insert, delete, traverse without heap in tight setups.
Designing the node pool array layoutUsing next indexes instead of pointersManaging a free-list in static memoryInsertion and deletion in static chainsDetecting pool exhaustion and errorsLesson 10Key and value representations: using uint8_t sensor id and SensorReading copy semanticsExplains key and value setup using uint8_t sensor IDs and SensorReading structs, focusing on copy rules, alignment, padding, and dodging aliasing or lifetime issues in static hash tables.
Choosing uint8_t for sensor ID keysDesigning the SensorReading structCopy semantics vs pointer semanticsAlignment, padding, and struct layoutValidating and normalizing sensor IDsLesson 11Hash function choices for small keyspace: identity, multiplicative, and masking for 0–255 idsDiscusses hash functions for small uint8_t keyspaces, including identity mapping, multiplicative hashing, masking, and balancing simplicity, spread quality, and cost for 0–255 sensor IDs.
Identity hash for dense ID rangesMultiplicative hashing for uint8_t keysBit masking and table index derivationAvoiding systematic clustering patternsTesting distribution with sample dataLesson 12find_reading_by_id: probe sequences, not-found vs found responses, and safe copy-out patternsFocuses on find_reading_by_id, including probe sequences, found vs not-found, safe SensorReading copy from table, and avoiding bad behaviour or old data in C.
Function signature and return patternsImplementing probe sequences for lookupHandling not-found vs found resultsSafe copy-out of SensorReading valuesAvoiding stale or partially written data
