array-doubly-linked-lru.rar_动态数组_基于数组的LRU队列

#include "array-doubly-linked-list-lru.h" #include <stdlib.h> #include <stdio.h> #include <string.h> #define ARAYY_LIST_LOG(...) printf("[ARAYY_LIST]: " __VA_ARGS__) int is_array_list_full( struct array_list * p_array_list ) { return p_array_list->capacity == p_array_list->max_element; } int is_array_list_empty( struct array_list * p_array_list ) { return p_array_list->capacity == 0; } struct array_list * ArrayListCreate(uint32_t size) { struct array_list * p_arrayList = (struct array_list *)malloc(sizeof(struct array_list)); if( p_arrayList == NULL ){ ARAYY_LIST_LOG( "allocate array_list failed\n" ); return NULL; } memset( p_arrayList, 0, sizeof(*p_arrayList) ); p_arrayList->max_element = size; p_arrayList->mapArray = (struct dram_segment_map * )malloc( p_arrayList->max_element * sizeof(struct dram_segment_map) ); if( p_arrayList->mapArray == NULL ){ ARAYY_LIST_LOG( "allocate dram_segment_map failed\n" ); free( p_arrayList ); return NULL; } p_arrayList->head = 0; p_arrayList->tail = 0; return p_arrayList; } int ArrayListInsert(struct array_list * p_arrayList, int value) { uint32_t head = p_arrayList->head; uint32_t tail = p_arrayList->tail; if( is_array_list_empty(p_arrayList) ) { p_arrayList->mapArray[head].prev_index = tail; p_arrayList->mapArray[tail].next_index = head; p_arrayList->mapArray[head].value = value; } else{ // first check whether the array is full, if it is full, we need to evict an element if( is_array_list_full(p_arrayList) ){ uint32_t to_be_tail = p_arrayList->mapArray[tail].prev_index; uint32_t to_be_head = tail; p_arrayList->mapArray[to_be_head].prev_index = to_be_tail; p_arrayList->mapArray[to_be_head].next_index = head; p_arrayList->mapArray[head].prev_index = to_be_head; p_arrayList->mapArray[to_be_tail].next_index = to_be_head; p_arrayList->mapArray[to_be_head].value = value; p_arrayList->head = to_be_head; p_arrayList->tail = to_be_tail; return 0; } else{ p_arrayList->mapArray[capacity].next_index = head; p_arrayList->mapArray[capacity].prev_index = tail; p_arrayList->mapArray[head].prev_index = capacity; p_arrayList->mapArray[tail].next_index = capacity; p_arrayList->head = capacity; } } p_arrayList->capacity += 1; return 0; } int ArrayListPrint(struct array_list * p_arrayList) { uint32_t tmp = p_arrayList->head; while( p_arrayList->mapArray[tmp].next_index != p_arrayList->head ){ ARAYY_LIST_LOG( "value is %u\n", p_arrayList->mapArray[tmp].value ); tmp = p_arrayList->mapArray[tmp].next_index; } ARAYY_LIST_LOG( "value is %u\n", p_arrayList->mapArray[tmp].value ); return 0; } int ArrayListFree(struct array_list * p_arrayList) { if( p_arrayList != NULL ){ if( p_arrayList->mapArray != NULL ){ free( p_arrayList->mapArray ); p_arrayList->mapArray = NULL; } free( p_arrayList ); p_arrayList = NULL; } return 0; }