Lesson 1Choosing collision strategy for static contexts: open addressing vs static separate chaining with arraysCompares open addressing and static separate chaining for systems with fixed memory, looking at cache work, fragmentation, how hard to build, and tips for picking a clash strategy 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, writing about worst and usual probe numbers, load limits, and real sizing 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 handling of pointers in static hash tables by using indices not raw pointers, checking bounds, and building APIs that stop NULL errors and bad 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 marks, and deletion rules that skip dynamic allocation while keeping probe chains and steady performance in C builds.
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 the latest sensor readings, set write order, use timestamps for newness, and keep things steady when updates or similar accesses happen.
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 what init_table does, like setting empty marks, starting free lists or tombstones, clearing extra info, and making sure the table starts right and can be checked before 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, including adding new, updating old, dealing with full table, return codes, and how to handle clashes while keeping the interface simple and strong 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 how to build the bucket array, including picking table size, prime or power-of-two sizing, constants at compile time, and choices between memory use, speed, and simple hash functions.
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 using arrays, including node pool setup, next index links, free-list handling, and how to add, remove, and go through without heap use in tight spaces.
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 how to show keys and values using uint8_t sensor IDs and SensorReading structs, focusing on copy rules, alignment, padding, and avoiding mix-ups or time issues in a static hash table.
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 key spaces, including direct mapping, multiplicative hashing, masking, and how to balance ease, 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, telling found from not found, safe copying of SensorReading from the table, and avoiding bad behavior 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
