Untitled

#ifndef _WINDOW_BIT_COUNT_APX_
#define _WINDOW_BIT_COUNT_APX_

#include <assert.h>
#include <math.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

uint64_t N_MERGES = 0;  // keep track of how many bucket merges occur

/*
    TODO: You can add code here.
*/
typedef struct{
  uint32_t ts;
}Bucket;

typedef struct {
    // TODO: Fill me.
    uint32_t wnd_size;  // input
    uint32_t k;         // input
    uint32_t now;       // current ts
    uint32_t group_num;    // total number of groups
    uint32_t max_size;
    uint32_t apx_cnt;
    uint32_t *index; // the first m int is ptr to available buckets
    uint32_t *power;
    uint32_t *size;
    Bucket *buckets;
} StateApx;

uint64_t wnd_bit_count_apx_new(StateApx *self, uint32_t wnd_size, uint32_t k){
    assert(wnd_size >= 1 && k >= 1);

    uint32_t group_num = ceil(1 + log2((wnd_size - 1) / k + 1));
    uint32_t slots = group_num * (k + 1);

    size_t indexSize = group_num * sizeof(uint32_t);
    size_t sizeSize = group_num * sizeof(uint32_t); // Size for size array
    size_t powerSize = 32 * sizeof(uint32_t);       // For the power array
    size_t bucketsSize = slots * sizeof(Bucket);    // For the buckets array

    // Total size for all components
    size_t totalSize = sizeof(StateApx) + indexSize + sizeSize + powerSize + bucketsSize;

    // Allocate memory block
    char *block = (char *)malloc(totalSize);
    if (!block)
        return 0; // Allocation failed

    // Setup StateApx structure within the allocated block
    StateApx *apxState = (StateApx *)block;
    apxState->wnd_size = wnd_size;
    apxState->k = k;
    apxState->group_num = group_num;
    apxState->now = 0;          // Initialize as current timestamp not specified
    apxState->apx_cnt = 0;      // Initial count
    apxState->max_size = 0; // Assuming this is the intended maximum size

    // Partition and assign memory for index, size, power, and buckets within the block
    apxState->index = (uint32_t *)(block + sizeof(StateApx));
    apxState->size = (uint32_t *)(block + sizeof(StateApx) + indexSize);
    apxState->power = (uint32_t *)(block + sizeof(StateApx) + indexSize + sizeSize);
    apxState->buckets = (Bucket *)(block + sizeof(StateApx) + indexSize + sizeSize + powerSize);

    // Initialize index and size arrays to 0
    memset(apxState->index, 0, indexSize);
    memset(apxState->size, 0, sizeSize);

    // Initialize power array with 2^i using shift operation
    for (uint32_t i = 0; i < 32; ++i){
        apxState->power[i] = 1U << i;
    }

    // Update the caller's self pointer to point to the newly allocated and initialized structure
    *self = *apxState;

    return totalSize; // Return total bytes allocated
}

void wnd_bit_count_apx_destruct(StateApx *self){
    free(self->buckets);
    free(self->index);
    free(self->size);
    free(self->power);
    return;
}

void wnd_bit_count_apx_print(StateApx *self){
    // This is useful for debugging.
    printf("Max size is %u\n", self->max_size);
    for (int i = 0; i < self->group_num; i++){
        printf("Bucket %d have %u\n", i, self->size[i]);
    }
}

uint32_t find_oldest_ptr(StateApx *self, uint32_t x){
    uint32_t k = self->k;
    uint32_t size = self->size[x];
    uint32_t cur_ptr = self->index[x]; // oldest_bucket_cur_ptr
    uint32_t oldest_ptr = (cur_ptr + k + 1 - size) % (k + 1);
    //printf("Oldest pointer of %u is %u\n", x, oldest_ptr + x * (k + 1));
    return oldest_ptr + x * (k + 1);
}
void clear(StateApx *self, uint32_t x){
    uint32_t k = self->k;
    uint32_t cur_ptr = x * (k + 1) + self->index[x];
    self->buckets[cur_ptr].ts = 0;
    self->index[x] = (self->index[x] - 1) % (k + 1);
    self->size[x]--;
    if(self->size[x] == 0)
        self->max_size--;
    self->apx_cnt -= self->power[x];
    return;
}
void clearPos(StateApx *self, uint32_t x, uint32_t pos){
    uint32_t k = self->k;
    self->buckets[pos].ts = 0;
    self->index[x] = (self->index[x] - 1) % (k + 1);
    self->size[x]--;
    if (self->size[x] == 0)
        self->max_size--;
    self->apx_cnt -= self->power[x];
    return;
}
void add(StateApx *self, uint32_t x, uint32_t time){
    uint32_t k = self->k;
    uint32_t cur_ptr = x * (k+1) + self->index[x];
    self->buckets[cur_ptr].ts = time;
    self->index[x] = (self->index[x] + 1) % (k + 1);
    self->size[x]++;
    self->apx_cnt += self->power[x];
    return;
}
uint32_t wnd_bit_count_apx_next(StateApx *self, bool item){
    // TODO: Fill me.
    self->now += 1;
    if(self->size[self->max_size] > 0){
        uint32_t oldest_ptr = find_oldest_ptr(self, self->max_size);
        printf("Oldest pointer's timestamp = %u\n", self->buckets[oldest_ptr].ts);
        if (self->buckets[oldest_ptr].ts != 0 && self->now - self->buckets[oldest_ptr].ts >= self->wnd_size){
            printf("Over window\n");
            clearPos(self, self->max_size, oldest_ptr);
        }
    }
    if(item){
        uint32_t cur = 0;
        //printf("Item\n");
        while (self->size[cur] >= self->k + 1){
            uint32_t oldest_ptr = find_oldest_ptr(self, cur);
            uint32_t second_oldest_ptr = (oldest_ptr+1)%(self->k+1);
            uint32_t second_oldest_ptr_time = self->buckets[second_oldest_ptr].ts;
            clearPos(self, cur, oldest_ptr);
            clearPos(self, cur, second_oldest_ptr);
            add(self, cur + 1, second_oldest_ptr_time);
            cur++;
            if(self->size[cur] == 1){
                self->max_size = cur;
                break;
            }
            N_MERGES++;
        }
        add(self, 0, self->now);
    }
    return self->apx_cnt;
}

#endif  // _WINDOW_BIT_COUNT_APX_