🍰 Bakery Simulation - API Project

Industrial bakery simulation in C. Features custom Hash Maps and manual memory management without external libraries.

📄 Overview

This project implements a simulation of an industrial bakery environment. The core objective was not only correctness but also minimize execution time and memory usage to handle large inputs.

Developed as the final project for the Algorithms and Principles of Computer Science course, this solution is built entirely from scratch in C11.

Documentation:

• Full Project Specification
• System Design Overview

🧩 The Challenge

• Inventory Management: Ingredients are managed in batches (Lotti) with distinct expiration dates. The system must always select the batch with the nearest expiration date to minimize waste.
• Order Queuing: Orders that cannot be fulfilled immediately are queued and processed as soon as new supplies arrive, respecting chronological order.
• Courier Logic: A courier periodically collects ready orders. The loading process must prioritize heavier orders first, then it proceeds by chronological order.

⚙️ Architecture & Data Structures

To achieve O(N) complexity for critical operations, the project implements the following data structures:

• Hash Maps with Chaining:

  • Used for both the Recipes and the Inventory.
  • Implementation: Fixed-size array (Size: 701) of pointers to Doubly Linked Lists.
  • Hashing Algorithm: Custom polynomial rolling hash function to minimize collisions on string keys.
  • Performance: Guarantees O(1) average time complexity for recipe lookups and ingredient access.

• Priority Queues for Inventory:

  • Ingredient batches are inserted into the Hash Map buckets maintaining a sorted order by expiration date.
  • This eliminates the need for repeated searches.

• Doubly Linked Lists:

  • Utilized for dynamic memory management of recipes and batches.
  • Enables O(1) deletion of empty ingredient batches or removed recipes, preventing memory fragmentation and traversal overhead.

• Custom Parser:

  • To avoid the overhead of standard I/O libraries for complex string manipulation, a custom command parser processes the input stream, converting raw bytes directly into structured data.

🚀 Tech Stack

• Language: C (C11 Standard)
• Libraries: Standard C Library only (no external dependencies).
• Memory Management: Manual (malloc/free).
• Profiling Tools: Valgrind & Callgrind (used for memory leak detection and time/space performance analysis).

🛠️ Build & Run

Prerequisites

• GCC Compiler (supporting C11 standard)
• GNU Make

Compilation

• The project includes a Makefile to automate the build process: make Bakery
• To compile with memory sanitizers to detect leaks and buffer overflows during execution: make Bakery WITH_ASAN=1

Execution

./Bakery < input.txt > output.txt