#include "acf_map.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
const static int PRIMES[72] = {
3, 7, 11, 17, 23, 29, 37, 47, 59, 71, 89, 107, 131, 163, 197, 239, 293, 353, 431, 521, 631, 761, 919,
1103, 1327, 1597, 1931, 2333, 2801, 3371, 4049, 4861, 5839, 7013, 8419, 10103, 12143, 14591,
17519, 21023, 25229, 30293, 36353, 43627, 52361, 62851, 75431, 90523, 108631, 130363, 156437,
187751, 225307, 270371, 324449, 389357, 467237, 560689, 672827, 807403, 968897, 1162687, 1395263,
1674319, 2009191, 2411033, 2893249, 3471899, 4166287, 4999559, 5999471, 7199369 };
static unsigned int murmur_hash2(char* data, int len);
static int getHashCode(void* key, int length, int isptr);
static void acf_map_resize(acf_map* _this, int cap);
static void acf_map_add_internal(acf_map * _this, TKey key, int len, TValue value,int isptr);
static int acf_map_remove_internal(acf_map * _this, TKey key, int len, int isptr);
static int acf_map_get_internal(acf_map * _this, TKey key, int len, TValue * value, int isptr);
void acf_map_init(acf_map *_this)
{
memset(_this, 0, sizeof(acf_map));
_this->_removeList = -1;//Remove的后可用的列表
}
void acf_map_deinit(acf_map * _this)
{
acf_map_clear(_this);
if (_this->_buckets)
{
free(_this->_buckets);
}
if (_this->_entries)
{
free(_this->_entries);
}
}
void acf_map_add(acf_map * _this, TKey key, TValue value)
{
acf_map_add_internal(_this, key, sizeof(TKey), value,0);
}
int acf_map_remove(acf_map * map, TKey key)
{
return acf_map_remove_internal(map, key,sizeof(TKey),0);
}
int acf_map_get(acf_map * map, TKey key, TValue * value)
{
return acf_map_get_internal(map, key, sizeof(TKey),value,0);
}
void acf_map_add_ptr(acf_map* _this, TKey key, int len, TValue value) {
acf_map_add_internal(_this, key, len, value, 1);
}
int acf_map_remove_ptr(acf_map * map, TKey key, int len)
{
return acf_map_remove_internal(map, key, len, 1);
}
int acf_map_get_ptr(acf_map * map, TKey key, int len, TValue * value)
{
return acf_map_get_internal(map, key, len, value, 1);
}
void acf_map_clear(acf_map * _this)
{
if (_this->count > 0)
{
for (int i = 0; i < _this->capacity; i++)
{
if (_this->_entries[i]._hashCode != -1)
{
if (_this->_entries[i]._isptr)
{
free(_this->_entries[i].key);
}
}
_this->_buckets[i] = -1;
_this->_entries[i]._next = -1;
_this->_entries[i]._hashCode = -1;
}
_this->_freeIndex = 0;
_this->_removeList = -1;
_this->count = 0;
}
}
void acf_map_iter_reset(acf_map * _this, acf_map_iter * iter)
{
iter->_map = _this;
iter->_index = 0;
iter->current = 0;
}
int acf_map_iter_next(acf_map_iter * iter)
{
while (iter->_index < iter->_map->capacity) {
if (iter->_map->_entries[iter->_index]._hashCode >= 0) {
iter->current = &iter->_map->_entries[iter->_index];
iter->_index++;
return 1;
}
iter->_index++;
}
iter->_index = iter->_map->count + 1;
return 0;
}
//获取最接近的且大于cap的质数
static int getPrime(int cap) {
for (int i = 0; i < 72; i++)
{
if (PRIMES[i] > cap)
{
return PRIMES[i];
}
}
return cap;
}
static void acf_map_resize(acf_map* dic, int cap)
{
if (cap < dic->count)
{
return;
}
//重新申请空间
int newSize = getPrime(cap);
int* newBuckets = malloc(sizeof(int) * newSize);
acf_map_entry* newEntries = malloc(sizeof(acf_map_entry) * newSize);
for (int i = 0; i < newSize; i++)
{
newBuckets[i] = -1;
newEntries[i]._next = -1;
newEntries[i]._hashCode = -1;
}
if (dic->count > 0)
{
memcpy(newEntries, dic->_entries, dic->count * sizeof(acf_map_entry));
//重新计算哈希碰撞码
for (int i = 0; i < dic->capacity; i++) {
if (newEntries[i]._hashCode >= 0)
{
int bucket = newEntries[i]._hashCode % newSize;
newEntries[i]._next = newBuckets[bucket];
newBuckets[bucket] = i;
}
}
}
if (dic->_buckets)
{
free(dic->_buckets);
}
if (dic->_entries)
{
free(dic->_entries);
}
dic->_buckets = newBuckets;
dic->_entries = newEntries;
dic->capacity = newSize;
}
static int getHashCode(void* key, int length,int isptr)
{
int hashcode;
if (isptr)
{
hashcode = murmur_hash2(key,length);
}
else {
hashcode = key;
}
return hashcode;
}
static unsigned int murmur_hash2(char *data, int len)
{
unsigned int h, k;
h = 0 ^ len;
while (len >= 4) {
k = data[0];
k |= data[1] << 8;
k |= data[2] << 16;
k |= data[3] << 24;
k *= 0x5bd1e995;
k ^= k >> 24;
k *= 0x5bd1e995;
h *= 0x5bd1e995;
h ^= k;
data += 4;
len -= 4;
}
switch (len) {
case 3:
h ^= data[2] << 16;
case 2:
h ^= data[1] << 8;
case 1:
h ^= data[0];
h *= 0x5bd1e995;
}
h ^= h >> 13;
h *= 0x5bd1e995;
h ^= h >> 15;
return h;
}
static int acf_map_find_entry(acf_map* _this,TKey key, int len, int isptr,int * pHashCode,int * pBucket,int*pLast)
{
int hashCode = getHashCode(key, len, isptr) & 0x7FFFFFFF;
int bucket = hashCode % _this->capacity;
*pHashCode = hashCode;
*pBucket = bucket;
*pLast = -1;
if (isptr)
{
for (int i = _this->_buckets[bucket]; i >= 0; i = _this->_entries[i]._next)
{
if (_this->_entries[i]._hashCode == hashCode && _this->_entries[i]._keySize == len&& memcmp(key, _this->_entries[i].key, len)==0)
//找到元素了
{
return i;
}
*pLast = i;
}
}
else
{
for (int i = _this->_buckets[bucket]; i >= 0; i = _this->_entries[i]._next)
{
if (_this->_entries[i]._hashCode == hashCode&&key == _this->_entries[i].key)
//找到元素了
{
return i;
}
*pLast = i;
}
}
return -1;
}
static void acf_map_add_internal(acf_map * _this, TKey key, int len, TValue value, int isptr)
{
int hashCode;
int bucket;
int last;
int index;
if (_this->_buckets == 0)
{
int size = getPrime(0);
_this->_buckets = malloc(sizeof(int)*size);
_this->_entries = malloc(sizeof(acf_map_entry)*size);
for (int i = 0; i < size; i++) {
_this->_buckets[i] = -1;
_this->_entries[i]._next = -1;
_this->_entries[i]._hashCode = -1;
}
_this->capacity = size;
_this->_freeIndex = 0;
hashCode = getHashCode(key, len, isptr) & 0x7FFFFFFF;
bucket = hashCode % _this->capacity;
}
else
{
int findIndex = acf_map_find_entry(_this, key, len, isptr, &hashCode, &bucket, &last);
if (findIndex > -1)
{
_this->_entries[findIndex].value = value;
return;
}
}
if (_this->_freeIndex < _this->capacity)//有可用下标
{
index = _this->_freeIndex++;
}
else if (_this->_removeList >= 0)//有删除可用下标
{
index = _this->_removeList;
_this->_removeList = _this->_entries[_this->_removeList]._next;
}
else//无可用下标,拓展容量
{
acf_map_resize(_this, _this->capacity << 1);
bucket = hashCode % _this->capacity;
index = _this->_freeIndex++;
}
_this->_entries[index]._next = _this->_buckets[bucket];
_this->_entries[index]._hashCode = hashCode;
_this->_entries[index]._isptr = isptr;
if (isptr)
{
_this->_entries[index].key = malloc(len+1);
memcpy(_this->_entries[index].key,key,len);
((char*)(_this->_entries[index].key))[len] = 0;
}
else
{
_this->_entries[index].key = key;
}
_this->_entries[index]._keySize = len;
_this->_entries[index].value = value;
_this->_buckets[bucket] = index;
_this->count++;
}
static int acf_map_remove_internal(acf_map * _this, TKey key, int len, int isptr)
{
if (!_this->_buckets)
{
return 0;
}
int hashCode;
int bucket;
int last;
int findIndex = acf_map_find_entry(_this, key, len, isptr, &hashCode, &bucket, &last);
if (findIndex > -1)
{
if (last == -1)
{
_this->_buckets[bucket] = _this->_entries[findIndex]._next;
}
else
{
_this->_entries[last]._next = _this->_entries[findIndex]._next;
}
if (_this->_entries[findIndex]._isptr)
- 1
- 2
前往页