Untitled
unknown
c_cpp
a year ago
5.9 kB
6
Indexable
#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_
Editor is loading...
Leave a Comment