Table of Contents
Overview
HAllocator is a C++ memory allocator implementation that provides memory management through advanced data structures and algorithms. This documentation is intended for developers who want to understand the internals, extend the functionality, or integrate HAllocator into their projects.
Key Features
- Best-Fit Allocation: Uses a Red-Black Tree for O(log n) best-fit search
- Memory Coalescing: Automatically merges adjacent free blocks using a doubly-linked list
- Multi-Block Management: High-level container for managing multiple memory blocks
- STL Compatibility: Fully compatible with STL containers as a custom allocator
- Thread-Safe Operations: (if enabled) Safe for concurrent usage
- Zero External Dependencies: Pure C++23 implementation
Architecture
Core Components
The fundamental unit of memory management. Each Block represents a contiguous region of memory that can be subdivided into smaller allocations.
Key Responsibilities:
- Manages a single large memory region
- Tracks free/used regions using a Red-Black Tree
- Handles allocation and deallocation requests
- Performs memory coalescing
Public API:
class Block {
public:
explicit Block(size_t size);
void* allocate(size_t size, void* hint = nullptr);
void deallocate(void* ptr, size_t size);
MemoryNode* best_fit(size_t size);
void log_block_state(std::ofstream& logfile) const;
};
A container that manages multiple Block instances, providing a higher-level allocation interface.
Key Responsibilities:
- Manages multiple memory blocks
- Routes allocation requests to appropriate blocks
- Expands capacity by adding new blocks when needed
- Provides aggregated statistics
Public API:
template<size_t BlockSize, size_t MaxBlocks>
class BlocksContainer {
public:
BlocksContainer();
void* allocate(size_t size);
void deallocate(void* ptr, size_t size);
void log_container_state(std::ofstream& logfile) const;
};
The main allocator interface that provides STL-compatible memory allocation.
Key Responsibilities:
- STL allocator interface implementation
- Type-safe allocation/deallocation
- Compatible with std::vector, std::list, std::set, etc.
- Manages object construction and destruction
Template Parameters:
template<typename T, size_t BlockSize = 1024 * 1024, size_t MaxBlocks = 4>
class Halloc {
public:
using value_type = T;
Halloc();
template<typename U>
Halloc(const Halloc<U, BlockSize, MaxBlocks>& other);
T* allocate(size_t n);
void deallocate(T* p, size_t n);
void log_container_state(const char* logfile_dir) const;
};
4. RBTreeDriver (rb-tree/)
A Red-Black Tree implementation optimized for memory region management.
Key Responsibilities:
- Maintains balanced tree of free memory regions
- Provides O(log n) search, insert, and delete operations
- Supports custom comparison for best-fit search
- Memory-efficient node storage
Implementation Details
Memory Layout
Each Block maintains its memory in the following structure:
┌──────────────────────────────────────────────────────┐
│ Block Header │
│ (metadata: size, free list head, RB tree root) │
├──────────────────────────────────────────────────────┤
│ │
│ Allocatable Memory Region │
│ │
│ ┌──────────┐ ┌──────────┐ ┌──────────┐ │
│ │ Region │ │ Region │ │ Region │ ... │
│ │ Header │ │ Header │ │ Header │ │
│ ├──────────┤ ├──────────┤ ├──────────┤ │
│ │ Data │ │ Data │ │ Data │ │
│ └──────────┘ └──────────┘ └──────────┘ │
│ │
└──────────────────────────────────────────────────────┘
Allocation Algorithm
This is more of a Buffer Manager, we request the spacifed block size from the OS and then we manage allocations within that block.
When an allocation request is made, HAllocator performs the following steps:
- Construction: It constructs a
BlocksContainer instance that manages multiple Block instances.
- allocation:
- Searches the RB tree for the best-fit free region that can satisfy the request.
- If a suitable region is found, it splits the region if it's larger than needed.
- Updates the free list and RB tree to reflect the allocation.
- Returns a pointer to the allocated memory.
- IF NO SUITABLE REGION IS FOUND, IT MAKES AN
mmap CALL TO THE OS TO GET MORE MEMORY FOR THIS SPECIFIC ALLOCATION
- Deallocation:
- Marks the region as free.
- Attempts to coalesce with adjacent free regions.
- Updates the free list and RB tree accordingly.
T* Halloc::allocate(std::size_t count) {
size_t size = count * sizeof(T);
void* ptr = blocks->allocate(size);
return static_cast<T*>(ptr);
}
Deallocation and Coalescing
When memory is freed, HAllocator attempts to merge it with adjacent free blocks and updates the RB tree and free list accordingly.
void Halloc::deallocate(T* p, std::size_t count) {
size_t size = count * sizeof(T);
blocks->deallocate(static_cast<void*>(p), size);
}
Red-Black Tree Properties
The RB tree maintains these invariants:
- Every node is either red or black
- The root is black
- All leaves (NIL) are black
- Red nodes have black children
- All paths from root to leaves contain the same number of black nodes
This ensures O(log n) performance for all operations.
Usage Examples
Basic Block Usage
void* ptr1 = block.allocate(128, block.best_fit(128));
void* ptr2 = block.allocate(256, block.best_fit(256));
block.deallocate(ptr1, 128);
block.deallocate(ptr2, 256);
Memory block management with Red-Black tree based allocator.
Manages a contiguous memory block with RB-tree based allocation.
Definition Block.hpp:86
Using BlocksContainer
Container managing multiple memory blocks for large-scale allocations.
Type-safe allocator using Red-Black tree for best-fit allocation.
Definition Halloc.hpp:47
void deallocate(T *ptr, std::size_t count)
Deallocates memory previously allocated for 'count' objects.
Definition Halloc.hpp:253
T * allocate(std::size_t count)
Allocates memory for 'count' objects of type T.
Definition Halloc.hpp:233
STL Container Integration
#include <vector>
#include <map>
std::vector<int, hh::halloc::Halloc<int, 1024 * 1024>> vec;
vec.push_back(42);
vec.push_back(100);
using MyMap = std::map<
std::string,
int,
std::less<std::string>,
>;
MyMap myMap;
myMap["hello"] = 1;
myMap["world"] = 2;
High-level allocator interface using Red-Black tree for efficient memory management.
Custom Allocator Example
std::vector<int, IntAllocator> numbers;
for (int i = 0; i < 1000; ++i) {
numbers.push_back(i * i);
}
Testing
HAllocator includes comprehensive unit tests using GoogleTest.
Running Tests
# Build with tests
cmake -S . -B build
cmake --build build
# Run all tests
cd build
ctest --output-on-failure
# Or use the helper script
./scripts.sh test
Test Coverage
Tests cover:
- Basic allocation/deallocation
- Boundary conditions (empty, full blocks)
- Coalescing behavior
- RB tree operations
- STL container integration
- Multi-threaded scenarios (if enabled)
- Memory corruption detection
Writing New Tests
Example test structure:
#include <gtest/gtest.h>
TEST(BlockTest, BasicAllocation) {
void* ptr = block.allocate(128, nullptr);
ASSERT_NE(ptr, nullptr);
block.deallocate(ptr, 128);
EXPECT_EQ(block.available(), 1024);
}
Time Complexity
| Operation | Best Case | Average Case | Worst Case |
| Allocate | O(1) | O(log n) | O(log n) |
| Deallocate | O(1) | O(log n) | O(log n) |
| Best-Fit | O(log n) | O(log n) | O(log n) |
| Coalesce | O(1) | O(1) | O(1) |
Space Complexity
- Per Block: O(1) overhead + O(n) for free regions tracking
- RB Tree: O(n) where n is number of free regions
- Free List: O(n) for doubly-linked list of free regions
Optimization Tips
- Pre-allocate Blocks: Create BlocksContainer with sufficient capacity
- Size Classes: Use multiple allocators for different size ranges
- Alignment: Request aligned memory for better cache performance
- Batch Operations: Allocate multiple objects at once when possible
Building from Source
Prerequisites
- CMake 3.10+
- C++23 compatible compiler (GCC 11+, Clang 14+, MSVC 19.30+)
- Git
Build Steps
# Clone the repository
git clone https://github.com/HamzaHassanain/HAllocator.git
cd HAllocator
# Configure with CMake
cmake -S . -B build -DCMAKE_BUILD_TYPE=Release
# Build
cmake --build build --parallel
# Install (optional)
sudo cmake --install build
CMake Options
# Enable/disable tests
-DBUILD_TESTING=ON
# Enable documentation generation
-DBUILD_DOC=ON
# Set build type
-DCMAKE_BUILD_TYPE=Release|Debug|RelWithDebInfo
# Enable sanitizers (debug builds)
-DENABLE_ASAN=ON # Address Sanitizer
-DENABLE_UBSAN=ON # Undefined Behavior Sanitizer
-DENABLE_TSAN=ON # Thread Sanitizer
HAllocator uses a comprehensive set of modern development tools to ensure code quality, consistency, and maintainability. This section covers all the essential tools integrated into the project.
scripts.sh - Build & Development Helper
The scripts.sh is a unified command-line interface for all common development tasks. It simplifies building, testing, formatting, linting, and debugging operations.
Available Commands
1. <strong>clean</strong> - Remove Build Artifacts
- Removes the entire
build/ directory
- Useful for fresh builds or cleaning up disk space
- Often combined with build:
./scripts.sh clean build
2. <strong>build</strong> - Build the Project
./scripts.sh build
# or simply
./scripts.sh
- Creates and configures the
build/ directory if it doesn't exist
- Runs CMake configuration
- Builds the project using all available CPU cores (
-j$(nproc))
- Default command if no arguments are provided
Output:
Building project...
Configuring CMake...
Building project...
Build completed successfully!
3. <strong>test</strong> - Run Unit Tests
# you have to build first
./scripts.sh build
# Run all tests
./scripts.sh test
# Run tests matching a pattern
./scripts.sh build test BasicAllocatorTest
./scripts.sh build test "STRESS_*"
# Run only small/fast tests
./scripts.sh build test small-only
- Runs all GoogleTest unit tests using CTest
- Supports filtering tests by name pattern
- Provides detailed output on failures (
--output-on-failure)
- Note: Must build first before running tests
4. <strong>format</strong> - Format Code with clang-format
- Automatically formats all
.cpp, .hpp, .h, and .ipp files
- Uses Google C++ Style Guide with custom modifications
- Applies formatting in-place (modifies files)
- Excludes
build/ and out/ directories
- Should be run before every commit
What it does:
- Fixes indentation (4 spaces)
- Aligns code consistently
- Applies proper spacing around operators
- Organizes includes
- Wraps lines at 100 characters
5. <strong>format-check</strong> - Verify Code Formatting
./scripts.sh format-check
- Checks if code is properly formatted without modifying files
- Exits with error code if formatting is needed
- Perfect for CI/CD pipelines
- Lists all files that need formatting
Exit codes:
0 - All files properly formatted1 - Some files need formatting
Output:
All files are properly formatted!
or
Some files need formatting:
halloc/src/Block.cpp
rb-tree/rb-tree.hpp
Run './scripts.sh format' to fix formatting issues.
6. <strong>lint</strong> - Run Static Analysis with clang-tidy
- Performs comprehensive static code analysis
- Checks for bugs, performance issues, and style violations
- Uses
compile_commands.json for accurate analysis
- Examines all source/header files except tests and examples
- Recommended to run before pull requests
What it checks:
- Potential bugs and logic errors
- Performance inefficiencies
- Modern C++ best practices
- Code style consistency
- Memory safety issues
- Undefined behavior risks
7. <strong>sanitize</strong> - Build with Sanitizers
# Address Sanitizer (default) - detects memory errors
./scripts.sh sanitize
./scripts.sh sanitize address
# Thread Sanitizer - detects data races
./scripts.sh sanitize thread
# Undefined Behavior Sanitizer - detects UB
./scripts.sh sanitize undefined
# Memory Sanitizer - detects uninitialized memory reads
./scripts.sh sanitize memory
# Leak Sanitizer - detects memory leaks
./scripts.sh sanitize leak
- Builds the project with compiler sanitizers enabled
- Essential for finding runtime bugs during development
- Always run tests with sanitizers before releasing
After building with sanitizer:
cd build
ctest --output-on-failure
Sanitizer Types:
| Sanitizer | Flag | Detects |
| Address | -fsanitize=address | Buffer overflows, use-after-free, memory leaks |
| Thread | -fsanitize=thread | Data races, deadlocks |
| Undefined | -fsanitize=undefined | Undefined behavior, integer overflow |
| Memory | -fsanitize=memory | Uninitialized memory reads |
| Leak | -fsanitize=leak | Memory leaks only |
8. <strong>help</strong> - Show Usage Information
./scripts.sh help
./scripts.sh -h
./scripts.sh --help
- Displays comprehensive usage information
- Lists all available commands with examples
Common Workflows
Starting fresh:
./scripts.sh clean build test
Before committing:
./scripts.sh format
./scripts.sh lint
./scripts.sh build test
Debugging memory issues:
./scripts.sh clean
./scripts.sh sanitize address
cd build && ctest --output-on-failure
Quick validation:
./scripts.sh format-check
./scripts.sh build test small-only
HAllocator uses clang-format with a customized Google C++ Style Guide for consistent code formatting.
Configuration File: <tt>.clang-format</tt>
BasedOnStyle: Google
IndentWidth: 4 # 4-space indentation
ColumnLimit: 100 # Max line length
PointerAlignment: Left # int* ptr (not int *ptr)
BreakBeforeBraces: Attach # Opening brace on same line
Key Style Rules
- Indentation: 4 spaces (no tabs)
- Line Length: Maximum 100 characters
- Braces: Attached style (
if (condition) {)
- Pointers: Left-aligned (
int* ptr)
- Includes: Sorted and grouped
- Comments: 2 spaces before trailing comments
- Templates: Always break template declarations
Example Formatting
Before:
int*foo(int x,int y){
if(x>y)return x;
else return y;}
After:
int* foo(int x, int y) {
if (x > y)
return x;
else
return y;
}
Integration with Editors
VS Code: Install "C/C++" extension and add to settings.json:
{
"editor.formatOnSave": true,
"[cpp]": {
"editor.defaultFormatter": "ms-vscode.cpptools"
}
}
Vim/Neovim:
" Format on save
autocmd BufWritePre *.cpp,*.hpp,*.h :!clang-format -i %
CLion/IntelliJ: Settings → Editor → Code Style → Enable ClangFormat
clang-tidy is a powerful static analysis tool that catches bugs, suggests modern C++ practices, and enforces code quality standards.
Configuration File: <tt>.clang-tidy</tt>
The project uses a comprehensive set of checks:
Checks: >
bugprone-*, # Detect common bugs
clang-analyzer-*, # Deep static analysis
cppcoreguidelines-*, # C++ Core Guidelines
google-*, # Google style guide
modernize-*, # Modern C++ features
performance-*, # Performance optimization
readability-* # Code readability
Check Categories
1. <strong>bugprone-</strong> - Bug Detection
Catches common programming errors:
- Use-after-move
- Suspicious string comparisons
- Incorrect sizeof() usage
- Forward declaration mismatches
2. <strong>clang-analyzer-</strong> - Deep Analysis
Performs path-sensitive analysis:
- Null pointer dereferences
- Memory leaks
- Dead code
- Logic errors
3. <strong>cppcoreguidelines-</strong> - Best Practices
Enforces C++ Core Guidelines:
- Special member functions rule of 5/0
- Proper use of const
- Avoid naked new/delete
- RAII compliance
4. <strong>google-</strong> - Google Style
Google C++ style conformance:
- Naming conventions
- Include order
- Proper use of namespaces
- Readability improvements
5. <strong>modernize-</strong> - Modern C++
Suggests modern C++ features:
- Use
nullptr instead of NULL
- Use
override keyword
- Use range-based for loops
- Use
auto where appropriate
6. <strong>performance-</strong> - Optimization
Identifies performance issues:
- Unnecessary copies
- Move semantics opportunities
- Inefficient string concatenation
- Container operations
7. <strong>readability-</strong> - Code Clarity
Improves code readability:
- Naming conventions (snake_case, CamelCase)
- Function complexity
- Magic numbers
- Identifier length
Naming Conventions Enforced
namespace my_namespace {}
class MyClass {};
struct MyStruct {};
void my_function() {}
int my_variable = 0;
const int MY_CONSTANT = 42;
enum class Color { RED, GREEN };
template<typename T> class Vec{};
Example Checks
Before (flagged by clang-tidy):
int* allocate(int size) {
int* p = (int*)malloc(size);
if (p == NULL)
return 0;
return p;
}
After (clean):
std::unique_ptr<int[]> allocate(size_t size) {
auto p = std::make_unique<int[]>(size);
if (p == nullptr)
return nullptr;
return p;
}
Running clang-tidy Manually
# On a specific file
clang-tidy -p build halloc/src/Block.cpp
# On all files with auto-fix
clang-tidy -p build --fix-errors halloc/src/*.cpp
# With specific checks only
clang-tidy -p build -checks="modernize-*" halloc/src/Block.cpp
clangd is the language server that powers intelligent code completion, navigation, and real-time diagnostics in your editor.
Configuration File: <tt>.clangd</tt>
CompileFlags:
Add:
- "-std=c++23" # C++23 standard
- "-Wall" # All warnings
- "-Wextra" # Extra warnings
- "-pedantic" # Strict ISO C++
Diagnostics:
ClangTidy:
# Enables all checks from .clang-tidy
InlayHints:
Enabled: Yes # Show hints in editor
ParameterNames: Yes # Show parameter names
DeducedTypes: Yes # Show auto types
Hover:
ShowAKA: Yes # Show type aliases
Features
1. Code Completion
Intelligent autocomplete based on actual code analysis:
Block block(1024);
block.al|
2. Go to Definition (F12 / Ctrl+Click)
Jump to where functions/classes are defined:
3. Find References (Shift+F12)
Find all usages of a symbol across the codebase:
void* allocate(size_t size);
4. Real-time Diagnostics
Shows errors and warnings as you type:
int* ptr = nullptr;
*ptr = 42;
5. Inlay Hints
Shows parameter names and deduced types inline:
block.allocate(128, nullptr);
auto ptr = get_pointer();
6. Code Actions (Ctrl+.)
Quick fixes and refactorings:
- Extract function
- Add missing includes
- Implement pure virtual methods
- Generate getters/setters
7. Symbol Outline
View document structure:
- Classes and methods
- Functions
- Variables
- Namespaces
Editor Setup
VS Code:
- Install "clangd" extension
- Disable built-in IntelliSense (conflicts with clangd)
- Add to
.vscode/settings.json:
{
"clangd.arguments": [
"--background-index",
"--clang-tidy",
"--header-insertion=iwyu"
]
}
Neovim (with nvim-lspconfig):
require('lspconfig').clangd.setup{
cmd = {
"clangd",
"--background-index",
"--clang-tidy",
"--header-insertion=iwyu"
}
}
Emacs (with eglot):
(add-hook 'c++-mode-hook 'eglot-ensure)
Contributing
We welcome contributions! Please see CONTRIBUTING.md for guidelines.
Development Workflow
- Fork the repository
- Create a feature branch (
git checkout -b feature/amazing-feature)
- Make your changes
- Run tests (
./scripts.sh test)
- Format code (
./scripts.sh format)
- Run linter (
./scripts.sh lint)
- Commit changes (‘git commit -m 'Add amazing feature’
)
Push to branch (git push origin feature/amazing-feature`)- Open a Pull Request
Code Style
We follow the Google C++ Style Guide with minor modifications.
Use clang-format to format your code:
License
HAllocator is licensed under the MIT License with Non-Commercial Clause. You are free to use, modify, and distribute this software for non-commercial purposes. Commercial use requires explicit written permission from the copyright holder. See [LICENSE](LICENSE) for full details.
Acknowledgments
- GoogleTest for unit testing framework
- Doxygen for documentation generation
- The C++ community for inspiration and best practices
This documentation was generated for HAllocator. For the latest updates, visit the GitHub repository.
