hash.c

文件系统源代码!!!!! 文件系统源代码

		{
			pHash->is_malloc_capacity = \
					(pHash->capacity == new_capacity);
			*pHash->capacity = old_capacity;
			return -1 * result;
		}

		old_capacity = *new_capacity;
		/*printf("rehash, conflict_count=%d, old_capacity=%d, " \
			"new_capacity=%d\n", conflict_count, \
			old_capacity, *new_capacity);
		*/
	} while ((conflict_count=_hash_conflict_count(pHash)) > 0);

	pHash->is_malloc_capacity = true;

	//hash_stat_print(pHash);
	return 1;
}

HashData *_chain_find_entry(ChainList *plist, const void *key, \
		const int key_len, const unsigned int hash_code)
{
	ChainNode *pnode;
	HashData *hash_data;

	pnode = plist->head;
	while (pnode != NULL)
	{
		hash_data = (HashData *)pnode->data;
		if (key_len == hash_data->key_len && \
			memcmp(key, hash_data->key, key_len) == 0)
		{
			return hash_data;
		}

		pnode = pnode->next;
	}

	return NULL;
}

void *hash_find(HashArray *pHash, const void *key, const int key_len)
{
	unsigned int hash_code;
	ChainList *plist;
	HashData *hash_data;

	if (pHash == NULL || key == NULL || key_len < 0)
	{
		return NULL;
	}

	hash_code = pHash->hash_func(key, key_len);
	plist = pHash->items + (hash_code % (*pHash->capacity));

	hash_data = _chain_find_entry(plist, key, key_len, hash_code);
	if (hash_data != NULL)
	{
		return hash_data->value;
	}
	else
	{
		return NULL;
	}
}

int hash_insert(HashArray *pHash, const void *key, const int key_len, \
		void *value)
{
	unsigned int hash_code;
	ChainList *plist;
	HashData *hash_data;
	char *pBuff;
	int result;

	if (pHash == NULL || key == NULL || key_len < 0)
	{
		return -EINVAL;
	}

	hash_code = pHash->hash_func(key, key_len);
	plist = pHash->items + (hash_code % (*pHash->capacity));
	hash_data = _chain_find_entry(plist, key, key_len, hash_code);
	if (hash_data != NULL)
	{
		hash_data->value = value;
		return 0; 
	}

	pBuff = (char *)malloc(sizeof(HashData) + key_len);
	if (pBuff == NULL)
	{
		return -ENOMEM;
	}

	hash_data = (HashData *)pBuff;
	hash_data->key = pBuff + sizeof(HashData);

	hash_data->key_len = key_len;
	memcpy(hash_data->key, key, key_len);
	hash_data->hash_code = hash_code;
	hash_data->value = value;

	if ((result=addNode(plist, hash_data)) != 0) //fail to add node
	{
		free(hash_data);
		return -1 * result;
	}

	pHash->item_count++;

	if ((double)pHash->item_count / (double)*pHash->capacity >= \
		pHash->load_factor)
	{
		_rehash(pHash);
	}

	return 1;
}

int hash_delete(HashArray *pHash, const void *key, const int key_len)
{
	unsigned int hash_code;
	ChainList *plist;
	ChainNode *previous;
	ChainNode *pnode;
	HashData *hash_data;

	if (pHash == NULL || key == NULL || key_len < 0)
	{
		return -EINVAL;
	}

	hash_code = pHash->hash_func(key, key_len);
	plist = pHash->items + (hash_code % (*pHash->capacity));

	previous = NULL;
	pnode = plist->head;
	while (pnode != NULL)
	{
		hash_data = (HashData *)pnode->data;
		if (key_len == hash_data->key_len && \
			memcmp(key, hash_data->key, key_len) == 0)
		{
			deleteNodeEx(plist, previous, pnode);
			pHash->item_count--;
			return 1;
		}

		previous = pnode;
		pnode = pnode->next;
	}

	return 0;
}

void hash_walk(HashArray *pHash, HashWalkFunc walkFunc, void *args)
{
	ChainList *plist;
	ChainList *list_end;
	ChainNode *pnode;
	HashData *hash_data;
	int index;

	if (pHash == NULL || pHash->items == NULL || walkFunc == NULL)
	{
		return;
	}

	index = 0;
	list_end = pHash->items + (*pHash->capacity);
	for (plist=pHash->items; plist!=list_end; plist++)
	{
		pnode = plist->head;
		while (pnode != NULL)
		{
			hash_data = (HashData *) pnode->data;
			walkFunc(index, hash_data, args);

			pnode = pnode->next;
			index++;
		}
	}
}

// RS Hash Function
unsigned int RSHash(const void *key, const int key_len)
{
    unsigned char *pKey;
    unsigned char *pEnd;
    unsigned int b = 378551;
    unsigned int a = 63689;
    unsigned int hash = 0;

    pEnd = (unsigned char *)key + key_len;
    for (pKey = (unsigned char *)key; pKey != pEnd; pKey++)
    {
        hash = hash * a + (*pKey);
        a *= b;
    }

    return hash;
} 
 
// JS Hash Function
unsigned int JSHash(const void *key, const int key_len)
{
    unsigned char *pKey;
    unsigned char *pEnd;
    unsigned int hash = 1315423911;

    pEnd = (unsigned char *)key + key_len;
    for (pKey = (unsigned char *)key; pKey != pEnd; pKey++)
    {
        hash ^= ((hash << 5) + (*pKey) + (hash >> 2));
    }

    return hash;
}
 
// P.J.Weinberger Hash Function
unsigned int PJWHash(const void *key, const int key_len)
{
    unsigned char *pKey;
    unsigned char *pEnd;
    unsigned int BitsInUnignedInt = (unsigned int)(sizeof(unsigned int) * 8);
    unsigned int ThreeQuarters    = (unsigned int)((BitsInUnignedInt * 3) / 4);
    unsigned int OneEighth        = (unsigned int)(BitsInUnignedInt / 8);

    unsigned int HighBits         = (unsigned int)(0xFFFFFFFF) << \
				(BitsInUnignedInt - OneEighth);
    unsigned int hash             = 0;
    unsigned int test             = 0;

    pEnd = (unsigned char *)key + key_len;
    for (pKey = (unsigned char *)key; pKey != pEnd; pKey++)
    {
        hash = (hash << OneEighth) + (*(pKey));
        if ((test = hash & HighBits) != 0)
        {
            hash = ((hash ^ (test >> ThreeQuarters)) & (~HighBits));
        }
    }

    return hash;
} 
 
// ELF Hash Function
unsigned int ELFHash(const void *key, const int key_len)
{
    unsigned char *pKey;
    unsigned char *pEnd;
    unsigned int hash = 0;
    unsigned int x    = 0;

    pEnd = (unsigned char *)key + key_len;
    for (pKey = (unsigned char *)key; pKey != pEnd; pKey++)
    {
        hash = (hash << 4) + (*pKey);
        if ((x = hash & 0xF0000000L) != 0)
        {
            hash ^= (x >> 24);
            hash &= ~x;
        }
    }

    return hash;
}

// BKDR Hash Function
unsigned int BKDRHash(const void *key, const int key_len)
{
    unsigned char *pKey;
    unsigned char *pEnd;
    unsigned int seed = 131;  //  31 131 1313 13131 131313 etc..
    unsigned int hash = 0;

    pEnd = (unsigned char *)key + key_len;
    for (pKey = (unsigned char *)key; pKey != pEnd; pKey++)
    {
        hash = hash * seed + (*pKey);
    }

    return hash;
}

// SDBM Hash Function
unsigned int SDBMHash(const void *key, const int key_len)
{
    unsigned char *pKey;
    unsigned char *pEnd;
    unsigned int hash = 0;

    pEnd = (unsigned char *)key + key_len;
    for (pKey = (unsigned char *)key; pKey != pEnd; pKey++)
    {
        hash = (*pKey) + (hash << 6) + (hash << 16) - hash;
    }

    return hash;
}

unsigned int Time33Hash(const void *key, const int key_len)
{
	unsigned int nHash;
	unsigned char *pKey;
	unsigned char *pEnd;

	nHash = 0;
	pEnd = (unsigned char *)key + key_len;
	for (pKey = (unsigned char *)key; pKey != pEnd; pKey++)
	{
		nHash = (nHash << 5) + nHash + (*pKey);
	}

	return nHash;
}

// DJB Hash Function
unsigned int DJBHash(const void *key, const int key_len)
{
    unsigned char *pKey;
    unsigned char *pEnd;
    unsigned int hash = 5381;

    pEnd = (unsigned char *)key + key_len;
    for (pKey = (unsigned char *)key; pKey != pEnd; pKey++)
    {
        hash += (hash << 5) + (*pKey);
    }

    return hash;
}

// AP Hash Function
unsigned int APHash(const void *key, const int key_len)
{
    unsigned char *pKey;
    unsigned char *pEnd;
    int i;
    unsigned int hash = 0;

    pEnd = (unsigned char *)key + key_len;
    for (pKey = (unsigned char *)key, i=0; pKey != pEnd; pKey++, i++)
    {
        if ((i & 1) == 0)
        {
            hash ^= ((hash << 7) ^ (*pKey) ^ (hash >> 3));
        }
        else
        {
            hash ^= (~((hash << 11) ^ (*pKey) ^ (hash >> 5)));
        }
    }

    return hash;
}

unsigned int calc_hashnr (const void* key, const int key_len)
{
  unsigned char *pKey;
  unsigned char *pEnd;
  unsigned int nr = 1, nr2 = 4;

  pEnd = (unsigned char *)key + key_len;
  for (pKey = (unsigned char *)key; pKey != pEnd; pKey++)
  {
      nr ^= (((nr & 63) + nr2) * (*pKey)) + (nr << 8);
      nr2 += 3;
  }

  return nr;
}

unsigned int calc_hashnr1(const void* key, const int key_len)
{
  unsigned char *pKey;
  unsigned char *pEnd;
  uint hash = 0;

  pEnd = (unsigned char *)key + key_len;
  for (pKey = (unsigned char *)key; pKey != pEnd; pKey++)
    {
      hash *= 16777619;
      hash ^= *pKey;
    }
  return hash;
}

unsigned int simple_hash(const void* key, const int key_len)
{
  unsigned int h;
  unsigned char *p;
  unsigned char *pEnd;

  h = 0;
  pEnd = (unsigned char *)key + key_len;
  for (p = (unsigned char *)key; p!= pEnd; p++)
  {
    h = 31 * h + *p;
  }

  return h;
}