view release on metacpan or  search on metacpan

bpc_hashtable.c  view on Meta::CPAN

/*
 * Routines to provide a memory-efficient hashtable.
 *
 * Copyright (C) 2007-2009 Wayne Davison
 *
 * Modified for BackupPC to use arbitrary-length binary keys, and supporting
 * a rudimentary delete feature by Craig Barratt.  In 6/2016 rewrote to
 * make the storage an array of pointers to entries, instead of inplace.
 * That way entries fetched from the hashtable are still value after a
 * resize.  Still no chaining.
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License along
 * with this program; if not, visit the http://fsf.org website.
 */

#include "backuppc.h"

/*
 * Simple freelist of hash table entries.  We maintain a single linked list of
 * unused entries of each size, indexed by the FREELIST_SIZE2IDX() macro.
 *
 * FreeList[0] isn't used,
 * FreeList[1] is a free list of blocks of size 8,
 * FreeList[2] is a free list of blocks of size 16, ...
 *
 * eg, if you ask for a block of size 9, a block of size 16 will be returned.
 */
static bpc_hashtable_key **FreeList;
static uint32 FreeListSz;

/*
 * to map size to the FreeList index we round up to the nearest multiple of 8
 */
#define FREELIST_SIZE2IDX(size)         (((size) + 7) / 8)
#define FREELIST_IDX2SIZE(idx)          ((idx) * 8)
/*
 * how many new blocks to allocate when the free list is empty
 */
#define FREELIST_ALLOC_CNT              (512)

/*
 * allocate a single block of a given size by grabbing one off the FreeList
 */
static bpc_hashtable_key *bpc_hashtable_entryAlloc(uint32 size)
{
    uint32 freeListIdx = FREELIST_SIZE2IDX(size);
    bpc_hashtable_key *key;

    size = FREELIST_IDX2SIZE(freeListIdx);
    if ( freeListIdx >= FreeListSz ) {
        /*
         * need a bigger array of freelists
         */
        if ( !(FreeList = (bpc_hashtable_key**)realloc(FreeList, 2 * freeListIdx * sizeof(bpc_hashtable_key*))) ) {
            bpc_logErrf("bpc_hashtable_entryAlloc: out of memory\n");
            return NULL;
        }
        memset(FreeList + FreeListSz, 0, (2 * freeListIdx - FreeListSz) * sizeof(bpc_hashtable_key*));
        FreeListSz = 2 * freeListIdx;
    }
    if ( !FreeList[freeListIdx] ) {
        char *newBuf;
        uint32 i;
        /*
         * need to populate the freelist with more blocks
         */
        if ( !(newBuf = (char*)malloc(size * FREELIST_ALLOC_CNT)) ) {
            bpc_logErrf("bpc_hashtable_entryAlloc: out of memory\n");
            return NULL;
        }
        FreeList[freeListIdx] = (bpc_hashtable_key*)newBuf;
        /*
         * chain all the buffers together in a linked list
         */
        key = (bpc_hashtable_key*)newBuf;
        for ( i = 0 ; i < FREELIST_ALLOC_CNT - 1 ; i++ ) {