# How to Contribute New Eviction Algorithms to libCacheSim: A Developer's Guide

> Learn how to contribute new eviction algorithms to libCacheSim. Implement the cache_t interface, register your module, and validate with the test harness. A developer's guide for libCacheSim contributions.

- Repository: [Juncheng Yang/libcachesim](https://github.com/1a1a11a/libcachesim)
- Tags: how-to-guide
- Published: 2026-02-23

---

**To contribute a new eviction algorithm to libCacheSim, implement the `cache_t` interface callbacks in a C module under `libCacheSim/cache/eviction/`, register the source file in [`libCacheSim/cache/CMakeLists.txt`](https://github.com/1a1a11a/libcachesim/blob/main/libCacheSim/cache/CMakeLists.txt), and validate your implementation using the test harness in [`test/test_evictionAlgo.c`](https://github.com/1a1a11a/libcachesim/blob/main/test/test_evictionAlgo.c).**

libCacheSim is a high-performance cache simulation framework that treats eviction policies as pluggable C modules. Contributing a new algorithm requires conforming to the generic `cache_t` interface defined in [`include/libCacheSim/cache.h`](https://github.com/1a1a11a/libcachesim/blob/main/include/libCacheSim/cache.h) and integrating your code into the CMake-based build system. This guide provides the complete technical workflow using the existing codebase as reference.

## Understand the libCacheSim Architecture

### The Core cache_t Interface

All eviction algorithms in libCacheSim implement the **cache_t** structure defined in [`include/libCacheSim/cache.h`](https://github.com/1a1a11a/libcachesim/blob/main/include/libCacheSim/cache.h). This structure contains function pointers that your algorithm must populate:

```c
struct cache {
    cache_init_func_ptr    cache_init;
    cache_free_func_ptr    cache_free;
    cache_get_func_ptr     get;
    cache_find_func_ptr    find;
    cache_can_insert_func_ptr can_insert;
    cache_insert_func_ptr  insert;
    cache_evict_func_ptr   evict;
    cache_remove_func_ptr  remove;
    cache_to_evict_func_ptr to_evict;
    cache_get_occupied_byte_func_ptr get_occupied_byte;
    cache_get_n_obj_func_ptr get_n_obj;
    void *eviction_params;   // Algorithm-specific state
};

```

Your implementation must maintain its metadata within the **eviction_params** field and handle all callback invocations according to the interface contract. The framework uses these callbacks to manage cache objects while your algorithm controls the eviction order.

### Algorithm Headers and Prototypes

Public prototypes for all eviction algorithms reside in [`include/libCacheSim/evictionAlgo.h`](https://github.com/1a1a11a/libcachesim/blob/main/include/libCacheSim/evictionAlgo.h). When adding a new policy, you will extend this file with your initialization function (e.g., `MyAlgo_init`) to make it discoverable by the simulator and external applications.

## Step-by-Step Implementation Guide

### Step 1: Create Your Algorithm Source File

Create a new C file under `libCacheSim/cache/eviction/` (e.g., [`MyAlgo.c`](https://github.com/1a1a11a/libcachesim/blob/main/MyAlgo.c)). The following boilerplate, based on the [`SFIFO.c`](https://github.com/1a1a11a/libcachesim/blob/main/SFIFO.c) reference implementation, provides the complete skeleton:

```c
/* MyAlgo.c – sample eviction algorithm for libCacheSim */

#include "libCacheSim/evictionAlgo.h"
#include "dataStructure/hashtable/hashtable.h"

#ifdef __cplusplus
extern "C" {
#endif

/* Parameter struct for tunable options and runtime state */
typedef struct {
    double   my_factor;
    uint64_t max_size;
    cache_obj_t **list_head;
    cache_obj_t **list_tail;
    int64_t  n_objs;
    int64_t  n_bytes;
} MyAlgo_params_t;

/* Forward declarations */
static void   MyAlgo_free(cache_t *cache);
static bool   MyAlgo_get(cache_t *cache, const request_t *req);
static cache_obj_t *MyAlgo_find(cache_t *cache, const request_t *req, bool update_cache);
static cache_obj_t *MyAlgo_insert(cache_t *cache, const request_t *req);
static void   MyAlgo_evict(cache_t *cache, const request_t *req);
static bool   MyAlgo_remove(cache_t *cache, obj_id_t obj_id);
static inline int64_t MyAlgo_get_occupied_byte(const cache_t *cache);
static inline int64_t MyAlgo_get_n_obj(const cache_t *cache);
static inline bool   MyAlgo_can_insert(cache_t *cache, const request_t *req);
static void   MyAlgo_parse_params(cache_t *cache, const char *cache_specific_params);

/* Public init function */
cache_t *MyAlgo_init(const common_cache_params_t ccache_params,
                     const char *cache_specific_params)
{
    cache_t *cache = cache_struct_init("MyAlgo", ccache_params, cache_specific_params);
    cache->cache_init        = MyAlgo_init;
    cache->cache_free        = MyAlgo_free;
    cache->get               = MyAlgo_get;
    cache->find              = MyAlgo_find;
    cache->insert            = MyAlgo_insert;
    cache->evict             = MyAlgo_evict;
    cache->remove            = MyAlgo_remove;
    cache->to_evict          = NULL;
    cache->get_occupied_byte = MyAlgo_get_occupied_byte;
    cache->get_n_obj         = MyAlgo_get_n_obj;
    cache->can_insert        = MyAlgo_can_insert;
    cache->obj_md_size       = 0;

    /* Allocate algorithm-specific state */
    cache->eviction_params = malloc(sizeof(MyAlgo_params_t));
    memset(cache->eviction_params, 0, sizeof(MyAlgo_params_t));
    MyAlgo_params_t *p = (MyAlgo_params_t *)cache->eviction_params;
    p->my_factor = 1.0;

    /* Parse parameters like "my-factor=0.8,max-size=268435456" */
    if (cache_specific_params != NULL)
        MyAlgo_parse_params(cache, cache_specific_params);

    /* Initialize data structures */
    p->list_head = calloc(1, sizeof(cache_obj_t *));
    p->list_tail = calloc(1, sizeof(cache_obj_t *));
    p->max_size  = ccache_params.cache_size;

    return cache;
}

/* Free all allocated resources */
static void MyAlgo_free(cache_t *cache)
{
    MyAlgo_params_t *p = (MyAlgo_params_t *)cache->eviction_params;
    free(p->list_head);
    free(p->list_tail);
    free(cache->eviction_params);
    cache_struct_free(cache);
}

/* Process a cache request */
static bool MyAlgo_get(cache_t *cache, const request_t *req)
{
    return cache_get_base(cache, req);
}

/* Locate an object and optionally update metadata */
static cache_obj_t *MyAlgo_find(cache_t *cache, const request_t *req, bool update_cache)
{
    cache_obj_t *obj = hashtable_find(cache->hashtable, req);
    if (!obj || !update_cache) return obj;
    /* Insert promotion logic here */
    return obj;
}

/* Insert a new object into the cache */
static cache_obj_t *MyAlgo_insert(cache_t *cache, const request_t *req)
{
    MyAlgo_params_t *p = (MyAlgo_params_t *)cache->eviction_params;
    cache_obj_t *obj = cache_insert_base(cache, req);
    prepend_obj_to_head(&(p->list_head[0]), &(p->list_tail[0]), obj);
    p->n_objs++;
    p->n_bytes += obj->obj_size + cache->obj_md_size;
    return obj;
}

/* Evict an object when space is needed */
static void MyAlgo_evict(cache_t *cache, const request_t *req)
{
    MyAlgo_params_t *p = (MyAlgo_params_t *)cache->eviction_params;
    cache_obj_t *obj = p->list_tail[0];
    DEBUG_ASSERT(obj != NULL);
    p->n_objs--;
    p->n_bytes -= obj->obj_size + cache->obj_md_size;
    remove_obj_from_list(&(p->list_head[0]), &(p->list_tail[0]), obj);
    cache_evict_base(cache, obj, true);
}

/* Remove a specific object by ID */
static bool MyAlgo_remove(cache_t *cache, obj_id_t obj_id)
{
    MyAlgo_params_t *p = (MyAlgo_params_t *)cache->eviction_params;
    cache_obj_t *obj = hashtable_find_obj_id(cache->hashtable, obj_id);
    if (!obj) return false;
    cache->occupied_byte -= obj->obj_size + cache->obj_md_size;
    cache->n_obj--;
    remove_obj_from_list(&(p->list_head[0]), &(p->list_tail[0]), obj);
    hashtable_delete(cache->hashtable, obj);
    return true;
}

/* Statistics helpers */
static inline int64_t MyAlgo_get_occupied_byte(const cache_t *cache)
{
    return ((MyAlgo_params_t *)cache->eviction_params)->n_bytes;
}

static inline int64_t MyAlgo_get_n_obj(const cache_t *cache)
{
    return ((MyAlgo_params_t *)cache->eviction_params)->n_objs;
}

static inline bool MyAlgo_can_insert(cache_t *cache, const request_t *req)
{
    MyAlgo_params_t *p = (MyAlgo_params_t *)cache->eviction_params;
    return (req->obj_size + cache->obj_md_size <= p->max_size) &&
           cache_can_insert_default(cache, req);
}

/* Parse comma-separated key=value parameters */
static void MyAlgo_parse_params(cache_t *cache, const char *cache_specific_params)
{
    MyAlgo_params_t *p = (MyAlgo_params_t *)cache->eviction_params;
    char *tmp = strdup(cache_specific_params);
    char *orig = tmp;
    while (tmp && *tmp) {
        char *key   = strsep(&tmp, "=");
        char *value = strsep(&tmp, ",");
        while (tmp && *tmp == ' ') ++tmp;

        if (strcasecmp(key, "my-factor") == 0) {
            p->my_factor = strtod(value, NULL);
        } else if (strcasecmp(key, "max-size") == 0) {
            p->max_size = strtoull(value, NULL, 0);
        } else {
            ERROR("%s does not have parameter %s\n", cache->cache_name, key);
            exit(1);
        }
    }
    free(orig);
}

#ifdef __cplusplus
}
#endif

```

Key implementation patterns from the source code:

- **Use helper functions**: Leverage `cache_get_base`, `cache_insert_base`, `cache_evict_base`, and `cache_struct_init` to maintain consistent bookkeeping across algorithms.
- **Track state internally**: Store algorithm-specific data (like queue pointers or access frequencies) in your custom struct pointed to by **eviction_params**.
- **Parameter parsing**: Accept configuration via comma-separated `key=value` strings passed through `cache_specific_params`.

### Step 2: Register in the Build System

Edit [`libCacheSim/cache/CMakeLists.txt`](https://github.com/1a1a11a/libcachesim/blob/main/libCacheSim/cache/CMakeLists.txt) to include your source file in the **eviction_sources_c** list:

```cmake
set(eviction_sources_c
    # ... existing entries ...

    eviction/MyAlgo.c   # Add your algorithm here

)

```

CMake automatically compiles this into the `cache_lib_c` object library. For C++ implementations, add the file to **eviction_sources_cpp** instead.

### Step 3: Update Public Headers

Add your initialization function prototype to [`include/libCacheSim/evictionAlgo.h`](https://github.com/1a1a11a/libcachesim/blob/main/include/libCacheSim/evictionAlgo.h) to expose the algorithm to external callers:

```c
cache_t *MyAlgo_init(const common_cache_params_t ccache_params,
                     const char *cache_specific_params);

```

### Step 4: Add Test Coverage

Append a test case to [`test/test_evictionAlgo.c`](https://github.com/1a1a11a/libcachesim/blob/main/test/test_evictionAlgo.c) using the existing pattern:

```c
static void test_MyAlgo(gconstpointer user_data) {
    test_cache_algorithm(user_data, &test_data_truth[0]);
}

/* In the test suite registration: */
g_test_add_data_func("/libCacheSim/cacheAlgo_MyAlgo", reader, test_MyAlgo);

```

This ensures continuous integration validates that your algorithm compiles, links, and produces consistent results.

## Practical Usage Example

Once built and installed, instantiate your algorithm using the standard libCacheSim API:

```c
#include "libCacheSim/cache.h"
#include "libCacheSim/evictionAlgo.h"

int main(void) {
    common_cache_params_t params = default_common_cache_params();
    params.cache_size = 256 * MiB;
    params.hashpower = 18;

    const char *algo_params = "my-factor=0.75,max-size=268435456";
    cache_t *my_cache = MyAlgo_init(params, algo_params);
    
    if (!my_cache) {
        fprintf(stderr, "Failed to create MyAlgo cache\n");
        return 1;
    }

    request_t req = {.obj_id = 42, .obj_size = 4096, .obj_time = 0};
    bool hit = my_cache->get(my_cache, &req);
    printf("Cache hit: %s\n", hit ? "yes" : "no");

    my_cache->cache_free(my_cache);
    return 0;
}

```

Compile using:

```bash
gcc -Wall -I/usr/local/include -o demo demo.c -lCacheSim -ldl -lpthread -lm

```

## Summary

- Implement the **cache_t** interface callbacks in a new C file under `libCacheSim/cache/eviction/`.
- Store algorithm-specific state in a custom struct assigned to **eviction_params**.
- Parse configuration via `cache_specific_params` using comma-separated `key=value` syntax.
- Register the source file in [`libCacheSim/cache/CMakeLists.txt`](https://github.com/1a1a11a/libcachesim/blob/main/libCacheSim/cache/CMakeLists.txt) under **eviction_sources_c**.
- Declare the init function in [`include/libCacheSim/evictionAlgo.h`](https://github.com/1a1a11a/libcachesim/blob/main/include/libCacheSim/evictionAlgo.h) for public API exposure.
- Add test cases to [`test/test_evictionAlgo.c`](https://github.com/1a1a11a/libcachesim/blob/main/test/test_evictionAlgo.c) to ensure CI validation.
- Reference existing implementations like [`SFIFO.c`](https://github.com/1a1a11a/libcachesim/blob/main/SFIFO.c) for production-ready patterns regarding parameter parsing and list management.

## Frequently Asked Questions

### What is the minimum set of callbacks I must implement to contribute a new eviction algorithm?

You must implement **cache_init**, **cache_free**, **get**, **find**, **insert**, **evict**, and **remove**. Optional callbacks include **to_evict** (for peeking at the next eviction victim without removing it), **get_occupied_byte**, **get_n_obj**, and **can_insert**. The **get** callback typically delegates to `cache_get_base`, while **insert** and **evict** require your algorithm-specific logic for managing the replacement policy.

### How do I make my algorithm configurable via command-line parameters?

Parse the `cache_specific_params` string in your `*_init` function using `strsep` to split comma-separated `key=value` pairs. Store parsed values in your algorithm's parameter struct (e.g., `MyAlgo_params_t`). Follow the pattern in `SFIFO_parse_params` from [`libCacheSim/cache/eviction/SFIFO.c`](https://github.com/1a1a11a/libcachesim/blob/main/libCacheSim/cache/eviction/SFIFO.c), which handles type conversion and error reporting for unknown keys.

### Can I implement an eviction algorithm in C++ instead of C?

Yes. Place C++ source files in `libCacheSim/cache/eviction/` and add them to **eviction_sources_cpp** in [`libCacheSim/cache/CMakeLists.txt`](https://github.com/1a1a11a/libcachesim/blob/main/libCacheSim/cache/CMakeLists.txt). Wrap C-compatible function declarations in `extern "C"` blocks to ensure the init function is linkable from C code. The `cache_t` interface uses C function pointers, so your methods must conform to C calling conventions while internally using C++ features.

### Where should I add tests for my new eviction algorithm?

Add test functions to [`test/test_evictionAlgo.c`](https://github.com/1a1a11a/libcachesim/blob/main/test/test_evictionAlgo.c) following the **glib** testing framework patterns used throughout the repository. Use `g_test_add_data_func` to register your test with a unique path like `/libCacheSim/cacheAlgo_MyAlgo`. Provide a ground-truth dataset or at minimum verify that your algorithm initializes without errors and processes a sequence of requests without crashing.