/*
 * Copyright (c) 2022 Hong Jiahua
 * https://gitee.com/arrco/ekvdb
 * 
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 * 
 * The above copyright notice and this permission notice shall be included in all
 * copies or substantial portions of the Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */
#include <stdio.h>
#include <string.h>
#include <stdint.h>

#include "ekvdb.h"
/************************************************************************/
/*                                                                      */
/************************************************************************/
#define EKVDB_HEADER_MAGIC  0x6EADEAEA
#define EKVDB_EXIST_MAGIC   0xE35157EA
#define EKVDB_COUNT_MAGIC   0xFFFFFFFF
#define EKVDB_INDEX         "/ekvdb.index"
#define EKVDB_DATA          "/ekvdb.data"
#define EKVDB_MAX_NAME      EKVDB_INDEX
#define EKVDB_INDEX_BACK    "/ekvdb.index.back"
#define EKVDB_DATA_BACK     "/ekvdb.data.back"
#define EKVDB_MAX_NAME_BACK EKVDB_INDEX_BACK
#define EKVDB_LIST_NULL     0
#define EKVDB_TEMPBUF_LEN   512
#define EKVDB_HASH          hash

typedef struct
{
    uint32_t header;
    uint32_t len;
    uint32_t revlen;
    uint32_t listlen;
    uint32_t revlistlen;
    uint32_t threshold;
    uint32_t count;
    uint32_t redundant;
} ekvdb_index_header_t;

typedef struct
{
    uint32_t hash_a;
    uint32_t hash_b;
    uint32_t exist;
    uint32_t keyoffset;
    uint32_t dataoffset;
    uint32_t datalen;
    uint32_t next;
} ekvdb_index_t;

static uint32_t ekvdb_FNV_hash(char *str)
{
    uint32_t hash = 2166136261;

    while (*str) {
        hash *= 16777619;
        hash ^= (*str++);
    }

    return hash;
}

static uint32_t ekvdb_FNV_hash_next(uint32_t hash, char *str)
{
    while (*str) {
        hash *= 16777619;
        hash ^= (*str++);
    }

    return hash;
}

static uint32_t ekvdb_RS_hash(char *str)
{
    uint32_t hash = 0;
    uint32_t magic = 63689;

    while (*str) {
        hash = hash * magic + (*str++);
        magic *= 378551;
    }

    return hash;
}

static uint32_t ekvdb_DJB2_hash(char *str)
{
    uint32_t hash = 5381;

    while (*str) {
        hash = hash * 33 ^ (*str++);
    }

    return hash;
}

/************************************************************************/
/*                                                                      */
/************************************************************************/
static inline uint32_t ekvdb_hash_table(char *str)
{
    return ekvdb_FNV_hash(str);
}

static inline uint32_t ekvdb_hash_table_next(uint32_t hash, char *str)
{
    return ekvdb_FNV_hash_next(hash, str);
}

static inline uint32_t ekvdb_hash_a(char *str)
{
    return ekvdb_RS_hash(str);
}

static inline uint32_t ekvdb_hash_b(char *str)
{
    return ekvdb_DJB2_hash(str);
}

/**
  * @brief      创建数据库
  * @param[in]  path        路径
  * @param[in]  len         数据库存储键值对的数量
  * @param[in]  threshold   自动清除冗余数据的阈值
  *
  * @return     errcode
  * @retval      0      成功
  * @retval     -1      失败
  */
int ekvdb_create(char* path, uint32_t len, uint32_t threshold)
{
    FILE * dbindex_fp;
    char filename[strlen(path) + strlen(EKVDB_MAX_NAME) + 1];
    sprintf(filename, "%s%s", path, EKVDB_INDEX);
    
    dbindex_fp = fopen(filename, "w+");
    if(dbindex_fp == NULL) {
        return -1;
    }
    ekvdb_index_header_t header = {0};
    ekvdb_index_t filldata = {0};
    fseek(dbindex_fp, 0, SEEK_SET);
    header.header = EKVDB_HEADER_MAGIC;
    header.len = len * 4 / 3;   //load factor (0.75)
    header.revlen = ~header.len;
    header.listlen = len;
    header.revlistlen = ~header.listlen;
    header.threshold = threshold;
#if EKVDB_AUTO_COUNT_SUPPORT
    header.count = 0;
#else
    header.count = EKVDB_COUNT_MAGIC;
#endif
    header.redundant = 0;
    fwrite(&header, 1, sizeof(ekvdb_index_header_t), dbindex_fp);
    for(int i = 0; i < (header.len + header.listlen); i++)
        fwrite(&filldata, 1, sizeof(ekvdb_index_t), dbindex_fp);
    fclose(dbindex_fp);
    return 0;
}

/**
  * @brief      读数据库记录
  * @param[in]  path    路径
  * @param[in]  key     键
  * @param[in]  val     值
  * @param[in]  vallen  值的长度
  *
  * @return     errcode
  * @retval     >=0     成功读取的值长度
  * @retval     -1      失败
  */
int ekvdb_read(char* path, char* key, void* val, uint32_t vallen)
{
    FILE * dbindex_fp;
    FILE * dbdata_fp;
    int ret;
    
    char filename[strlen(path) + strlen(EKVDB_MAX_NAME) + 1];
    sprintf(filename, "%s%s", path, EKVDB_INDEX);
    dbindex_fp = fopen(filename, "r");
    if(dbindex_fp == NULL) {
        return -1;
    }
    
    ekvdb_index_header_t header = {0};
    fseek(dbindex_fp, 0, SEEK_SET);
    ret = fread(&header, 1, sizeof(ekvdb_index_header_t), dbindex_fp);
    if(ret != sizeof(ekvdb_index_header_t) || header.header != EKVDB_HEADER_MAGIC || header.revlen != (~header.len) || header.revlistlen != (~header.listlen)) {
        fclose(dbindex_fp);
        return -1;
    }
    
    sprintf(filename, "%s%s", path, EKVDB_DATA);
    dbdata_fp = fopen(filename, "r");
    if(dbdata_fp == NULL) {
        fclose(dbindex_fp);
        return -1;
    }
    
    uint32_t hash = ekvdb_hash_table(key);
    uint32_t hash_a = ekvdb_hash_a(key);
    uint32_t hash_b = ekvdb_hash_b(key);
    uint32_t hash_pos = EKVDB_HASH % header.len;
    ekvdb_index_t readdata;
    
    do {
        fseek(dbindex_fp, sizeof(ekvdb_index_header_t) + hash_pos * sizeof(ekvdb_index_t), SEEK_SET);
        ret = fread(&readdata, 1, sizeof(ekvdb_index_t), dbindex_fp);
        if(ret != sizeof(ekvdb_index_t)) {
            goto error_end;
        }
        
        if(readdata.exist == EKVDB_EXIST_MAGIC) {
            if (readdata.hash_a == hash_a && readdata.hash_b == hash_b) {
                break;
            } else {
                hash_pos = readdata.next;
                if (hash_pos == EKVDB_LIST_NULL) {
                    goto error_end;
                }
            }
        } else {
            goto error_end;
        }
    } while(1);
    
    fseek(dbdata_fp, readdata.dataoffset, SEEK_SET);
    ret = fread(val, 1, readdata.datalen <= vallen ? readdata.datalen : vallen, dbdata_fp);
    
    fclose(dbindex_fp);
    fclose(dbdata_fp);
    return ret;

error_end:
    fclose(dbindex_fp);
    fclose(dbdata_fp);
    return -1;
}

/**
  * @brief      写数据库数据
  * @param[in]  path    路径
  * @param[in]  key     键
  * @param[in]  val     值
  * @param[in]  vallen  值的长度
  *
  * @return     errcode
  * @retval     >=0     成功写入的值长度
  * @retval     -1      失败
  */
int ekvdb_write(char* path, char* key, void* val, uint32_t vallen)
{
    FILE * dbindex_fp;
    FILE * dbdata_fp;
    int ret;
    
    char filename[strlen(path) + strlen(EKVDB_MAX_NAME) + 1];
    sprintf(filename, "%s%s", path, EKVDB_INDEX);
    dbindex_fp = fopen(filename, "rw+");
    if(dbindex_fp == NULL) {
        return -1;
    }
    
    ekvdb_index_header_t header = {0};
    fseek(dbindex_fp, 0, SEEK_SET);
    ret = fread(&header, 1, sizeof(ekvdb_index_header_t), dbindex_fp);
    if(ret != sizeof(ekvdb_index_header_t) || header.header != EKVDB_HEADER_MAGIC || header.revlen != (~header.len) || header.revlistlen != (~header.listlen)) {
        fclose(dbindex_fp);
        return -1;
    }
    
    sprintf(filename, "%s%s", path, EKVDB_DATA);
    dbdata_fp = fopen(filename, "rw+");
    if(dbdata_fp == NULL) {
        dbdata_fp = fopen(filename, "w+");
        if(dbdata_fp == NULL) {
            fclose(dbindex_fp);
            return -1;
        }
    }
    fseek(dbdata_fp, 0, SEEK_END);
    uint32_t offset = ftell(dbdata_fp);
    uint32_t hash = ekvdb_hash_table(key);
    uint32_t hash_a = ekvdb_hash_a(key);
    uint32_t hash_b = ekvdb_hash_b(key);
    uint32_t hash_pos = EKVDB_HASH % header.len;
    ekvdb_index_t data = {0};
    
    do {
        fseek(dbindex_fp, sizeof(ekvdb_index_header_t) + hash_pos * sizeof(ekvdb_index_t), SEEK_SET);
        ret = fread(&data, 1, sizeof(ekvdb_index_t), dbindex_fp);
        if(ret != sizeof(ekvdb_index_t)) {
            memset(&data, 0, sizeof(ekvdb_index_t));
            break;
        }
        
        if(data.exist == EKVDB_EXIST_MAGIC) {
            if (data.hash_a == hash_a && data.hash_b == hash_b) {
                break;
            } else {
                if (data.next == EKVDB_LIST_NULL) {
                    uint32_t hash_list_start = hash % header.listlen;
                    uint32_t hash_list_pos = hash_list_start;
                    
                    ekvdb_index_t newdata;
                    #if EKVDB_AUTO_EXTEND_SUPPORT
                    int extend_flag = 0;
                    #endif
                    do {
                        fseek(dbindex_fp, sizeof(ekvdb_index_header_t) + (hash_list_pos + header.len) * sizeof(ekvdb_index_t), SEEK_SET);
                        ret = fread(&newdata, 1, sizeof(ekvdb_index_t), dbindex_fp);
                        if(ret != sizeof(ekvdb_index_t)) {
                            memset(&newdata, 0, sizeof(ekvdb_index_t));
                            break;
                        }
                        
                        if(newdata.exist == EKVDB_EXIST_MAGIC) {
                            hash_list_pos = (hash_list_pos + 1) % header.listlen;
                            if (hash_list_pos == hash_list_start) {
                                fclose(dbindex_fp);
                                
                                #if EKVDB_AUTO_EXTEND_SUPPORT
                                if(extend_flag) {
                                    fclose(dbdata_fp);
                                    return -1;
                                }
                                extend_flag = 1;
                                
                                ret = ekvdb_quick_extend(path);
                                if(ret < 0) {
                                    fclose(dbdata_fp);
                                    return -1;
                                }
                                
                                sprintf(filename, "%s%s", path, EKVDB_INDEX);
                                dbindex_fp = fopen(filename, "rw+");
                                if(dbindex_fp == NULL) {
                                    fclose(dbdata_fp);
                                    return -1;
                                }
                                
                                memset(&header, 0, sizeof(ekvdb_index_header_t));
                                fseek(dbindex_fp, 0, SEEK_SET);
                                ret = fread(&header, 1, sizeof(ekvdb_index_header_t), dbindex_fp);
                                if(ret != sizeof(ekvdb_index_header_t) || header.header != EKVDB_HEADER_MAGIC || header.revlen != (~header.len) || header.revlistlen != (~header.listlen)) {
                                    fclose(dbindex_fp);
                                    fclose(dbdata_fp);
                                    return -1;
                                }
                                
                                hash_list_start = hash % header.listlen;
                                hash_list_pos = hash_list_start;
                                
                                #else
                                    
                                fclose(dbdata_fp);
                                return -1;
                                
                                #endif
                            }
                        } else {
                            break;
                        }
                    } while(1);
                    
                    data.next = hash_list_pos + header.len;
                    fseek(dbindex_fp, sizeof(ekvdb_index_header_t) + hash_pos * sizeof(ekvdb_index_t), SEEK_SET);
                    fwrite(&data, 1, sizeof(ekvdb_index_t), dbindex_fp);
                    
                    hash_pos = data.next;
                    break;
                } else {
                    hash_pos = data.next;
                    continue;
                }
            }
        } else {
            break;
        }
    } while(1);
    
    if(data.exist != EKVDB_EXIST_MAGIC || data.hash_a != hash_a || data.hash_b != hash_b) {
        data.exist = EKVDB_EXIST_MAGIC;
        data.hash_a = hash_a;
        data.hash_b = hash_b;
        data.next = EKVDB_LIST_NULL;
    }
#if EKVDB_REDUNDANT_SUPPORT
    else {
        header.redundant += (data.datalen + (data.dataoffset - data.keyoffset));
    }
#endif
  
    uint32_t writelen;
    data.keyoffset = offset;
    writelen = fwrite(key, 1, strlen(key) + 1, dbdata_fp);
    data.dataoffset = offset + writelen;
    data.datalen = fwrite(val, 1, vallen, dbdata_fp);
    
    fseek(dbindex_fp, sizeof(ekvdb_index_header_t) + hash_pos * sizeof(ekvdb_index_t), SEEK_SET);
    ret = fwrite(&data, 1, sizeof(ekvdb_index_t), dbindex_fp);
    
#if EKVDB_AUTO_COUNT_SUPPORT
    if(header.count != EKVDB_COUNT_MAGIC) {
        header.count++;
        fseek(dbindex_fp, 0, SEEK_SET);
        fwrite(&header, 1, sizeof(ekvdb_index_header_t), dbindex_fp);
    }
#else
    if(header.count != EKVDB_COUNT_MAGIC) {
        header.count = EKVDB_COUNT_MAGIC;
        fseek(dbindex_fp, 0, SEEK_SET);
        fwrite(&header, 1, sizeof(ekvdb_index_header_t), dbindex_fp);
    }
#endif
    
    fclose(dbindex_fp);
    fclose(dbdata_fp);
    
#if EKVDB_AUTO_COMPACT_SUPPORT
    if(header.threshold && (header.redundant > header.threshold)) {
        ekvdb_compact(path);
    }
#endif
    
    return data.datalen;
}

/**
  * @brief      删除数据库记录
  * @param[in]  path    路径
  * @param[in]  key     键
  *
  * @return     errcode
  * @retval      0      成功
  * @retval     -1      失败
  */
int ekvdb_delete(char* path, char* key)
{
    FILE * dbindex_fp;
    int ret;
    
    char filename[strlen(path) + strlen(EKVDB_MAX_NAME) + 1];
    sprintf(filename, "%s%s", path, EKVDB_INDEX);
    dbindex_fp = fopen(filename, "rw+");
    if(dbindex_fp == NULL) {
        return -1;
    }
    
    ekvdb_index_header_t header = {0};
    fseek(dbindex_fp, 0, SEEK_SET);
    ret = fread(&header, 1, sizeof(ekvdb_index_header_t), dbindex_fp);
    if(ret != sizeof(ekvdb_index_header_t) || header.header != EKVDB_HEADER_MAGIC || header.revlen != (~header.len) || header.revlistlen != (~header.listlen)) {
        fclose(dbindex_fp);
        return -1;
    }
    
    uint32_t hash = ekvdb_hash_table(key);
    uint32_t hash_a = ekvdb_hash_a(key);
    uint32_t hash_b = ekvdb_hash_b(key);
    uint32_t hash_pos = EKVDB_HASH % header.len;
    uint32_t hash_last_pos = hash_pos;
    ekvdb_index_t readdata;
    
    do {
        fseek(dbindex_fp, sizeof(ekvdb_index_header_t) + hash_pos * sizeof(ekvdb_index_t), SEEK_SET);
        ret = fread(&readdata, 1, sizeof(ekvdb_index_t), dbindex_fp);
        if(ret != sizeof(ekvdb_index_t)) {
            fclose(dbindex_fp);
            return -1;
        }
        
        if(readdata.exist == EKVDB_EXIST_MAGIC) {
            if (readdata.hash_a == hash_a && readdata.hash_b == hash_b) {
                uint32_t tmpnext = readdata.next;
                
#if EKVDB_REDUNDANT_SUPPORT
                header.redundant += (readdata.datalen + (readdata.dataoffset - readdata.keyoffset));
#endif
                
                readdata.exist = 0;
                readdata.hash_a = 0;
                readdata.hash_b = 0;
                readdata.keyoffset = 0;
                readdata.dataoffset = 0;
                readdata.datalen = 0;
                readdata.next = EKVDB_LIST_NULL;
                
                if(hash_last_pos == hash_pos && tmpnext != EKVDB_LIST_NULL) {
                    ekvdb_index_t lastdata;
                    fseek(dbindex_fp, sizeof(ekvdb_index_header_t) + tmpnext * sizeof(ekvdb_index_t), SEEK_SET);
                    fread(&lastdata, 1, sizeof(ekvdb_index_t), dbindex_fp);
                    fseek(dbindex_fp, sizeof(ekvdb_index_header_t) + tmpnext * sizeof(ekvdb_index_t), SEEK_SET);
                    fwrite(&readdata, 1, sizeof(ekvdb_index_t), dbindex_fp);
                    
                    readdata = lastdata;
                }
                
                fseek(dbindex_fp, sizeof(ekvdb_index_header_t) + hash_pos * sizeof(ekvdb_index_t), SEEK_SET);
                fwrite(&readdata, 1, sizeof(ekvdb_index_t), dbindex_fp);
                
                if(hash_last_pos != hash_pos) {
                    ekvdb_index_t lastdata;
                    fseek(dbindex_fp, sizeof(ekvdb_index_header_t) + hash_last_pos * sizeof(ekvdb_index_t), SEEK_SET);
                    fread(&lastdata, 1, sizeof(ekvdb_index_t), dbindex_fp);
                    lastdata.next = tmpnext;
                    fseek(dbindex_fp, sizeof(ekvdb_index_header_t) + hash_last_pos * sizeof(ekvdb_index_t), SEEK_SET);
                    fwrite(&lastdata, 1, sizeof(ekvdb_index_t), dbindex_fp);
                }
                
                break;
            } else {
                hash_last_pos = hash_pos;
                hash_pos = readdata.next;
                if (hash_pos == EKVDB_LIST_NULL) {
                    fclose(dbindex_fp);
                    return -1;
                }
            }
        } else {
            fclose(dbindex_fp);
            return -1;
        }
    } while(1);
    
#if EKVDB_AUTO_COUNT_SUPPORT
    if(header.count > 0 && header.count != EKVDB_COUNT_MAGIC) {
        header.count--;
        fseek(dbindex_fp, 0, SEEK_SET);
        fwrite(&header, 1, sizeof(ekvdb_index_header_t), dbindex_fp);
    }
#else
    if(header.count != EKVDB_COUNT_MAGIC) {
        header.count = EKVDB_COUNT_MAGIC;
        fseek(dbindex_fp, 0, SEEK_SET);
        fwrite(&header, 1, sizeof(ekvdb_index_header_t), dbindex_fp);
    }
#endif
    
    fclose(dbindex_fp);
    
    return 0;
}

/**
  * @brief      清除数据库的冗余记录
  * @param[in]  path    路径
  *
  * @return     errcode
  * @retval      0      成功
  * @retval     -1      失败
  */
int ekvdb_compact(char* path)
{
    FILE * dbindex_fp;
    FILE * dbdata_fp;
    FILE * dbindex_back_fp;
    FILE * dbdata_back_fp;
    char tempbuf[EKVDB_TEMPBUF_LEN];
    int ret;
    
    char filename[strlen(path) + strlen(EKVDB_MAX_NAME) + 1];
    sprintf(filename, "%s%s", path, EKVDB_INDEX);
    dbindex_fp = fopen(filename, "r");
    if(dbindex_fp == NULL) {
        return -1;
    }
    
    ekvdb_index_header_t header = {0};
    fseek(dbindex_fp, 0, SEEK_SET);
    ret = fread(&header, 1, sizeof(ekvdb_index_header_t), dbindex_fp);
    if(ret != sizeof(ekvdb_index_header_t) || header.header != EKVDB_HEADER_MAGIC || header.revlen != (~header.len) || header.revlistlen != (~header.listlen)) {
        fclose(dbindex_fp);
        return -1;
    }
    
    sprintf(filename, "%s%s", path, EKVDB_DATA);
    dbdata_fp = fopen(filename, "r");
    if(dbdata_fp == NULL) {
        fclose(dbindex_fp);
        return -1;
    }
    
    char backfilename[strlen(path) + strlen(EKVDB_MAX_NAME_BACK) + 1];
    sprintf(backfilename, "%s%s", path, EKVDB_INDEX_BACK);
    dbindex_back_fp = fopen(backfilename, "w+");
    if(dbindex_back_fp == NULL) {
        fclose(dbindex_fp);
        fclose(dbdata_fp);
        return -1;
    }
    ekvdb_index_t filldata = {0};
#if EKVDB_REDUNDANT_SUPPORT
    header.redundant = 0;
#endif
    fseek(dbindex_back_fp, 0, SEEK_SET);
    fwrite(&header, 1, sizeof(ekvdb_index_header_t), dbindex_back_fp);
    for(int i = 0; i < (header.len + header.listlen); i++)
        fwrite(&filldata, 1, sizeof(ekvdb_index_t), dbindex_back_fp);
    
    sprintf(backfilename, "%s%s", path, EKVDB_DATA_BACK);
    dbdata_back_fp = fopen(backfilename, "w+");
    if(dbdata_back_fp == NULL) {
        fclose(dbindex_fp);
        fclose(dbdata_fp);
        
        fclose(dbindex_back_fp);
        sprintf(backfilename, "%s%s", path, EKVDB_INDEX_BACK);
        remove(backfilename);
        return -1;
    }
    
    ekvdb_index_t readdata;
    uint32_t write_pos = 0;
    for(int i = 0; i < header.len; i++) {
        fseek(dbindex_fp, sizeof(ekvdb_index_header_t) + i * sizeof(ekvdb_index_t), SEEK_SET);
        ret = fread(&readdata, 1, sizeof(ekvdb_index_t), dbindex_fp);
        if(ret != sizeof(ekvdb_index_t)) {
            fclose(dbindex_fp);
            fclose(dbdata_fp);
            
            fclose(dbdata_back_fp);
            remove(backfilename);
            
            fclose(dbindex_back_fp);
            sprintf(backfilename, "%s%s", path, EKVDB_INDEX_BACK);
            remove(backfilename);
            return -1;
        }
        
        if(readdata.exist == EKVDB_EXIST_MAGIC) {
            uint32_t readlen = readdata.datalen + (readdata.dataoffset - readdata.keyoffset);
            uint32_t writelen;
            
            fseek(dbdata_fp, readdata.keyoffset, SEEK_SET);
            
            fseek(dbindex_back_fp, sizeof(ekvdb_index_header_t) + i * sizeof(ekvdb_index_t), SEEK_SET);
            readdata.dataoffset = write_pos + (readdata.dataoffset - readdata.keyoffset);
            readdata.keyoffset = write_pos;
            fwrite(&readdata, 1, sizeof(ekvdb_index_t), dbindex_back_fp);
            
            while(readlen) {
                writelen = readlen > EKVDB_TEMPBUF_LEN ? EKVDB_TEMPBUF_LEN : readlen;
                fread(tempbuf, 1, writelen, dbdata_fp);
                fwrite(tempbuf, 1, writelen, dbdata_back_fp);
                readlen -= writelen;
                write_pos += writelen;
            }
            
            while(readdata.next != EKVDB_LIST_NULL) {
                fseek(dbindex_fp, sizeof(ekvdb_index_header_t) + readdata.next * sizeof(ekvdb_index_t), SEEK_SET);
                fseek(dbindex_back_fp, sizeof(ekvdb_index_header_t) + readdata.next * sizeof(ekvdb_index_t), SEEK_SET);
                
                fread(&readdata, 1, sizeof(ekvdb_index_t), dbindex_fp);
                fseek(dbdata_fp, readdata.keyoffset, SEEK_SET);
                readlen = readdata.datalen + readdata.dataoffset - readdata.keyoffset;
                
                readdata.dataoffset = write_pos + (readdata.dataoffset - readdata.keyoffset);
                readdata.keyoffset = write_pos;
                fwrite(&readdata, 1, sizeof(ekvdb_index_t), dbindex_back_fp);
                
                while(readlen) {
                    writelen = readlen > EKVDB_TEMPBUF_LEN ? EKVDB_TEMPBUF_LEN : readlen;
                    fread(tempbuf, 1, writelen, dbdata_fp);
                    fwrite(tempbuf, 1, writelen, dbdata_back_fp);
                    readlen -= writelen;
                    write_pos += writelen;
                }
            }
        }
    }
    
    fclose(dbindex_fp);
    fclose(dbdata_fp);
    
    fclose(dbindex_back_fp);
    sprintf(filename, "%s%s", path, EKVDB_INDEX);
    remove(filename);
    sprintf(backfilename, "%s%s", path, EKVDB_INDEX_BACK);
    rename(backfilename, filename);
    
    fclose(dbdata_back_fp);
    sprintf(filename, "%s%s", path, EKVDB_DATA);
    remove(filename);
    sprintf(backfilename, "%s%s", path, EKVDB_DATA_BACK);
    rename(backfilename, filename);
    
    return 0;
}

/**
  * @brief      快速扩展数据库容量
  * @param[in]  path    路径
  *
  * @return     errcode
  * @retval      0      成功
  * @retval     -1      失败
  */
int ekvdb_quick_extend(char* path)
{
    FILE * dbindex_fp;
    uint32_t oldlistlen;
    int ret;
    
    char filename[strlen(path) + strlen(EKVDB_MAX_NAME) + 1];
    sprintf(filename, "%s%s", path, EKVDB_INDEX);
    dbindex_fp = fopen(filename, "rw+");
    if(dbindex_fp == NULL) {
        return -1;
    }
    
    ekvdb_index_header_t header = {0};
    ekvdb_index_t filldata = {0};
    fseek(dbindex_fp, 0, SEEK_SET);
    ret = fread(&header, 1, sizeof(ekvdb_index_header_t), dbindex_fp);
    if(ret != sizeof(ekvdb_index_header_t) || header.header != EKVDB_HEADER_MAGIC || header.revlen != (~header.len) || header.revlistlen != (~header.listlen)) {
        fclose(dbindex_fp);
        return -1;
    }
    
    oldlistlen = header.listlen;
    header.listlen <<= 1;
    header.revlistlen = ~header.listlen;
    
    fseek(dbindex_fp, 0, SEEK_SET);
    fwrite(&header, 1, sizeof(ekvdb_index_header_t), dbindex_fp);
    fseek(dbindex_fp, sizeof(ekvdb_index_header_t) + (header.len + oldlistlen) * sizeof(ekvdb_index_t), SEEK_SET);
    for(int i = 0; i < (header.listlen - oldlistlen); i++)
        fwrite(&filldata, 1, sizeof(ekvdb_index_t), dbindex_fp);
    fclose(dbindex_fp);
    
    return 0;
}

/**
  * @brief      扩展数据库容量
  * @param[in]  path    路径
  *
  * @return     errcode
  * @retval      0      成功
  * @retval     -1      失败
  */
int ekvdb_extend(char* path)
{
    FILE * dbindex_fp;
    FILE * dbdata_fp;
    FILE * dbindex_back_fp;
    char tempbuf[EKVDB_TEMPBUF_LEN];
    int ret;
    
    char filename[strlen(path) + strlen(EKVDB_MAX_NAME) + 1];
    sprintf(filename, "%s%s", path, EKVDB_INDEX);
    dbindex_fp = fopen(filename, "r");
    if(dbindex_fp == NULL) {
        return -1;
    }
    
    ekvdb_index_header_t header = {0};
    fseek(dbindex_fp, 0, SEEK_SET);
    ret = fread(&header, 1, sizeof(ekvdb_index_header_t), dbindex_fp);
    if(ret != sizeof(ekvdb_index_header_t) || header.header != EKVDB_HEADER_MAGIC || header.revlen != (~header.len) || header.revlistlen != (~header.listlen)) {
        fclose(dbindex_fp);
        return -1;
    }
    
    sprintf(filename, "%s%s", path, EKVDB_DATA);
    dbdata_fp = fopen(filename, "r");
    if(dbdata_fp == NULL) {
        fclose(dbindex_fp);
        return -1;
    }
    
    char backfilename[strlen(path) + strlen(EKVDB_MAX_NAME_BACK) + 1];
    sprintf(backfilename, "%s%s", path, EKVDB_INDEX_BACK);
    dbindex_back_fp = fopen(backfilename, "w+");
    if(dbindex_back_fp == NULL) {
        fclose(dbindex_fp);
        fclose(dbdata_fp);
        return -1;
    }
    
    ekvdb_index_t filldata = {0};
    uint32_t headerlen = header.len;
    
    if(header.listlen > header.len) {
        header.len = header.listlen * 4 / 3;
        header.revlen = ~header.len;
    } else {
        header.len <<= 1;
        header.revlen = ~header.len;
        header.listlen <<= 1;
        header.revlistlen = ~header.listlen;
    }
    
    fseek(dbindex_back_fp, 0, SEEK_SET);
    fwrite(&header, 1, sizeof(ekvdb_index_header_t), dbindex_back_fp);
    for(int i = 0; i < (header.len + header.listlen); i++)
        fwrite(&filldata, 1, sizeof(ekvdb_index_t), dbindex_back_fp);
    
    uint32_t table_pos, hash_pos;
    ekvdb_index_t readdata = {0};
    ekvdb_index_t checkdata = {0};
    uint32_t key_len = 0;
    uint32_t hash;
    uint32_t read_next;
    for(int i = 0; i < headerlen; i++) {
        table_pos = i;
        
        do {
            fseek(dbindex_fp, sizeof(ekvdb_index_header_t) + table_pos * sizeof(ekvdb_index_t), SEEK_SET);
            ret = fread(&readdata, 1, sizeof(ekvdb_index_t), dbindex_fp);
            if(ret != sizeof(ekvdb_index_t)) {
                goto error_end;
            }
            
            if(readdata.exist == EKVDB_EXIST_MAGIC) {
                key_len = readdata.dataoffset - readdata.keyoffset;
                fseek(dbdata_fp, readdata.keyoffset, SEEK_SET);
                if(EKVDB_TEMPBUF_LEN >= key_len) {
                    fread(tempbuf, 1, key_len, dbdata_fp);
                    hash = ekvdb_hash_table(tempbuf);
                } else {
                    uint32_t read_pos = key_len, read_len = 0;
                    read_len = EKVDB_TEMPBUF_LEN - 1;
                    read_pos -= read_len;
                    fread(tempbuf, 1, read_len, dbdata_fp);
                    tempbuf[EKVDB_TEMPBUF_LEN - 1] = 0;
                    hash = ekvdb_hash_table(tempbuf);
                    do {
                        read_len = read_pos > EKVDB_TEMPBUF_LEN - 1 ? EKVDB_TEMPBUF_LEN - 1 : read_pos;
                        read_pos -= read_len;
                        fread(tempbuf, 1, read_len, dbdata_fp);
                        tempbuf[EKVDB_TEMPBUF_LEN - 1] = 0;
                        hash = ekvdb_hash_table_next(hash, tempbuf);
                    } while(read_pos);
                }
                hash_pos = hash % header.len;
                
                do {
                    fseek(dbindex_back_fp, sizeof(ekvdb_index_header_t) + hash_pos * sizeof(ekvdb_index_t), SEEK_SET);
                    ret = fread(&checkdata, 1, sizeof(ekvdb_index_t), dbindex_back_fp);
                    if(ret != sizeof(ekvdb_index_t)) {
                        goto error_end;
                    }
                    
                    if(checkdata.exist == EKVDB_EXIST_MAGIC) {
                        if (checkdata.next == EKVDB_LIST_NULL) {
                            uint32_t hash_list_start = hash % header.listlen;
                            uint32_t hash_list_pos = hash_list_start;
                            
                            ekvdb_index_t newdata;
                            do {
                                fseek(dbindex_back_fp, sizeof(ekvdb_index_header_t) + (hash_list_pos + header.len) * sizeof(ekvdb_index_t), SEEK_SET);
                                ret = fread(&newdata, 1, sizeof(ekvdb_index_t), dbindex_back_fp);
                                if(ret != sizeof(ekvdb_index_t)) {
                                    goto error_end;
                                }
                                
                                if(newdata.exist == EKVDB_EXIST_MAGIC) {
                                    hash_list_pos = (hash_list_pos + 1) % header.listlen;
                                    if (hash_list_pos == hash_list_start) {
                                        goto error_end;
                                    }
                                } else {
                                    break;
                                }
                            } while(1);
                            
                            checkdata.next = hash_list_pos + header.len;
                            fseek(dbindex_back_fp, sizeof(ekvdb_index_header_t) + hash_pos * sizeof(ekvdb_index_t), SEEK_SET);
                            fwrite(&checkdata, 1, sizeof(ekvdb_index_t), dbindex_back_fp);
                            
                            hash_pos = checkdata.next;
                            break;
                        } else {                        
                            hash_pos = checkdata.next;
                        }
                    } else {
                        break;
                    }
                } while(1);
                
                read_next = readdata.next;
                readdata.next = EKVDB_LIST_NULL;
                
                fseek(dbindex_back_fp, sizeof(ekvdb_index_header_t) + hash_pos * sizeof(ekvdb_index_t), SEEK_SET);
                fwrite(&readdata, 1, sizeof(ekvdb_index_t), dbindex_back_fp);
                
                if(read_next != EKVDB_LIST_NULL) {
                    table_pos = read_next;
                } else {
                    break;
                }
            } else {
                break;
            }
        } while(1);
    }
    
    fclose(dbindex_fp);
    fclose(dbdata_fp);
    fclose(dbindex_back_fp);
    sprintf(filename, "%s%s", path, EKVDB_INDEX);
    remove(filename);
    sprintf(backfilename, "%s%s", path, EKVDB_INDEX_BACK);
    rename(backfilename, filename);
    
    return 0;

error_end:
    fclose(dbindex_fp);
    fclose(dbdata_fp);
    fclose(dbindex_back_fp);
    
    sprintf(backfilename, "%s%s", path, EKVDB_INDEX_BACK);
    remove(backfilename);
    return -1;
}

/**
  * @brief      重置数据库
  * @param[in]  path    路径
  *
  * @return     errcode
  * @retval      0      成功
  * @retval     -1      失败
  */
int ekvdb_reset(char* path)
{
    FILE * dbindex_fp;
    int ret;
    
    char filename[strlen(path) + strlen(EKVDB_MAX_NAME) + 1];
    sprintf(filename, "%s%s", path, EKVDB_INDEX);
    dbindex_fp = fopen(filename, "rw+");
    if(dbindex_fp == NULL) {
        return -1;
    }
    
    ekvdb_index_header_t header = {0};
    ekvdb_index_t filldata = {0};
    fseek(dbindex_fp, 0, SEEK_SET);
    ret = fread(&header, 1, sizeof(ekvdb_index_header_t), dbindex_fp);
    if(ret != sizeof(ekvdb_index_header_t) || header.header != EKVDB_HEADER_MAGIC || header.revlen != (~header.len) || header.revlistlen != (~header.listlen)) {
        fclose(dbindex_fp);
        return -1;
    }
    fclose(dbindex_fp);
    
    dbindex_fp = fopen(filename, "w+");
    if(dbindex_fp == NULL) {
        return -1;
    }
    
#if EKVDB_AUTO_COUNT_SUPPORT
    header.count = 0;
#else
    header.count = EKVDB_COUNT_MAGIC;
#endif
    
    fseek(dbindex_fp, 0, SEEK_SET);
    fwrite(&header, 1, sizeof(ekvdb_index_header_t), dbindex_fp);
    for(int i = 0; i < (header.len + header.listlen); i++)
        fwrite(&filldata, 1, sizeof(ekvdb_index_t), dbindex_fp);
    fclose(dbindex_fp);
    
    sprintf(filename, "%s%s", path, EKVDB_DATA);
    remove(filename);
    
    return 0;
}

/**
  * @brief      清空数据库
  * @param[in]  path    路径
  *
  * @return     无
  */
void ekvdb_clear(char* path)
{
    char filename[strlen(path) + strlen(EKVDB_MAX_NAME) + 1];
    sprintf(filename, "%s%s", path, EKVDB_INDEX);
    remove(filename);
    sprintf(filename, "%s%s", path, EKVDB_DATA);
    remove(filename);
}

/**
  * @brief      数据库计数
  * @param[in]  path    路径
  *
  * @return     errcode
  * @retval     >=0     数据库内存储的数据数量
  * @retval     -1      失败
  */
int ekvdb_count(char* path)
{
#if EKVDB_AUTO_COUNT_SUPPORT
    FILE * dbindex_fp;
    int ret;
    
    char filename[strlen(path) + strlen(EKVDB_MAX_NAME) + 1];
    sprintf(filename, "%s%s", path, EKVDB_INDEX);
    dbindex_fp = fopen(filename, "r");
    if(dbindex_fp == NULL) {
        return -1;
    }
    
    ekvdb_index_header_t header = {0};
    fseek(dbindex_fp, 0, SEEK_SET);
    ret = fread(&header, 1, sizeof(ekvdb_index_header_t), dbindex_fp);
    if(ret != sizeof(ekvdb_index_header_t) || header.header != EKVDB_HEADER_MAGIC || header.revlen != (~header.len) || header.revlistlen != (~header.listlen)) {
        fclose(dbindex_fp);
        return -1;
    }
    
    fclose(dbindex_fp);
    
    if(header.count != EKVDB_COUNT_MAGIC)
        return header.count;
    else
        return -1;
#else
    return -1;
#endif
}

/**
  * @brief      数据库容量
  * @param[in]  path    路径
  *
  * @return     errcode
  * @retval     >=0     数据库的容量
  * @retval     -1      失败
  */
int ekvdb_capacity(char* path)
{
    FILE * dbindex_fp;
    int ret;
    
    char filename[strlen(path) + strlen(EKVDB_MAX_NAME) + 1];
    sprintf(filename, "%s%s", path, EKVDB_INDEX);
    dbindex_fp = fopen(filename, "r");
    if(dbindex_fp == NULL) {
        return -1;
    }
    
    ekvdb_index_header_t header = {0};
    fseek(dbindex_fp, 0, SEEK_SET);
    ret = fread(&header, 1, sizeof(ekvdb_index_header_t), dbindex_fp);
    if(ret != sizeof(ekvdb_index_header_t) || header.header != EKVDB_HEADER_MAGIC || header.revlen != (~header.len) || header.revlistlen != (~header.listlen)) {
        fclose(dbindex_fp);
        return -1;
    }
    
    fclose(dbindex_fp);
    
    return header.listlen;
}

/**
  * @brief      数据库数据冗余
  * @param[in]  path    路径
  *
  * @return     errcode
  * @retval     >=0     数据库的冗余
  * @retval     -1      失败
  */
int ekvdb_redundant(char* path)
{
#if EKVDB_REDUNDANT_SUPPORT
    FILE * dbindex_fp;
    int ret;
    
    char filename[strlen(path) + strlen(EKVDB_MAX_NAME) + 1];
    sprintf(filename, "%s%s", path, EKVDB_INDEX);
    dbindex_fp = fopen(filename, "r");
    if(dbindex_fp == NULL) {
        return -1;
    }
    
    ekvdb_index_header_t header = {0};
    fseek(dbindex_fp, 0, SEEK_SET);
    ret = fread(&header, 1, sizeof(ekvdb_index_header_t), dbindex_fp);
    if(ret != sizeof(ekvdb_index_header_t) || header.header != EKVDB_HEADER_MAGIC || header.revlen != (~header.len) || header.revlistlen != (~header.listlen)) {
        fclose(dbindex_fp);
        return -1;
    }
    
    fclose(dbindex_fp);
    
    return header.redundant;
#else
    return -1;
#endif
}

/**
  * @brief      数据库迭代初始化
  * @param[in]  path        路径
  * @param[in]  iterator    迭代器
  *
  * @return     errcode
  * @retval      0      成功
  * @retval     -1      失败
  */
int ekvdb_iterator_init(char* path, ekvdb_iterator_t* iterator)
{
    if(iterator == NULL)
        return -1;
    
    iterator->pos = 0;
    iterator->next = EKVDB_LIST_NULL;
    
    return 0;
}

/**
  * @brief      数据库迭代获取下一个键值对
  * @param[in]  path        路径
  * @param[in]  iterator    迭代器
  * @param[in]  key         键的缓冲区，用于存放下一个键，如果键的缓冲区大小无法存放下键，则最后一个Byte的值不为0
  * @param[in]  keymaxlen   键的缓冲区大小
  * @param[in]  val         值的缓冲区，用于存放下一个值
  * @param[in]  valmaxlen   值的缓冲区大小
  *
  * @return     errcode
  * @retval     >=0     获取值的大小
  * @retval     -1      失败
  */
int ekvdb_iterator_next(char* path, ekvdb_iterator_t* iterator, char* key, uint32_t keymaxlen, void* val, uint32_t valmaxlen)
{
    FILE * dbindex_fp;
    int ret;
    
    char filename[strlen(path) + strlen(EKVDB_MAX_NAME) + 1];
    sprintf(filename, "%s%s", path, EKVDB_INDEX);
    dbindex_fp = fopen(filename, "r");
    if(dbindex_fp == NULL) {
        return -1;
    }
    
    ekvdb_index_header_t header = {0};
    fseek(dbindex_fp, 0, SEEK_SET);
    ret = fread(&header, 1, sizeof(ekvdb_index_header_t), dbindex_fp);
    if(ret != sizeof(ekvdb_index_header_t) || header.header != EKVDB_HEADER_MAGIC || header.revlen != (~header.len) || header.revlistlen != (~header.listlen)) {
        fclose(dbindex_fp);
        return -1;
    }
    
    if(iterator->pos >= header.len) {
        fclose(dbindex_fp);
        return -1;
    }
    
    ekvdb_index_t readdata = {0};
    
    if(iterator->next != EKVDB_LIST_NULL) {
        fseek(dbindex_fp, sizeof(ekvdb_index_header_t) + iterator->next * sizeof(ekvdb_index_t), SEEK_SET);
        ret = fread(&readdata, 1, sizeof(ekvdb_index_t), dbindex_fp);
        if(ret != sizeof(ekvdb_index_t)) {
            fclose(dbindex_fp);
            return -1;
        }
        
        iterator->next = readdata.next;
    } else {
        for(; iterator->pos < header.len; iterator->pos++) {
            fseek(dbindex_fp, sizeof(ekvdb_index_header_t) + iterator->pos * sizeof(ekvdb_index_t), SEEK_SET);
            ret = fread(&readdata, 1, sizeof(ekvdb_index_t), dbindex_fp);
            if(ret != sizeof(ekvdb_index_t)) {
                fclose(dbindex_fp);
                return -1;
            }
            
            if(readdata.exist == EKVDB_EXIST_MAGIC) {
                iterator->next = readdata.next;
                break;
            }
        }
    }
    
    if(iterator->next == EKVDB_LIST_NULL) {
        iterator->pos++;
    }

    if(readdata.exist == EKVDB_EXIST_MAGIC) {
        FILE * dbdata_fp;
        
        sprintf(filename, "%s%s", path, EKVDB_DATA);
        dbdata_fp = fopen(filename, "r");
        if(dbdata_fp == NULL) {
            fclose(dbindex_fp);
            return -1;
        }
        
        uint32_t keylen = readdata.dataoffset - readdata.keyoffset;
        key[keymaxlen - 1] = 0;
        fseek(dbdata_fp, readdata.keyoffset, SEEK_SET);
        ret = fread(key, 1, keylen <= keymaxlen ? keylen : keymaxlen, dbdata_fp);
        
        fseek(dbdata_fp, readdata.dataoffset, SEEK_SET);
        ret = fread(val, 1, readdata.datalen <= valmaxlen ? readdata.datalen : valmaxlen, dbdata_fp);
        
        fclose(dbdata_fp);
    } else {
        ret = -1;
    }
    
    fclose(dbindex_fp);
    
    return ret;
}