/*

 * Copyright (c) 2001-2020 Mellanox Technologies, Ltd. All rights reserved.

 *

 * This software is available to you under a choice of one of two

 * licenses.  You may choose to be licensed under the terms of the GNU

 * General Public License (GPL) Version 2, available from the file

 * COPYING in the main directory of this source tree, or the

 * BSD license below:

 *

 *     Redistribution and use in source and binary forms, with or

 *     without modification, are permitted provided that the following

 *     conditions are met:

 *

 *      - Redistributions of source code must retain the above

 *        copyright notice, this list of conditions and the following

 *        disclaimer.

 *

 *      - Redistributions in binary form must reproduce the above

 *        copyright notice, this list of conditions and the following

 *        disclaimer in the documentation and/or other materials

 *        provided with the distribution.

 *

 * 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 <stdlib.h>

#include <stdint.h>

#include "hash.h"

#define HASH_KEY_INVALID    (hash_key_t)(-1)

/**

 * @struct hash_element

 * @brief It is an object to be stored in a hash container

 */

struct hash_element {

	hash_key_t key; /**< key */

	void *value;    /**< value */

};

/**

 * @struct hash_object

 * @brief hash container

 */

struct hash_object {

	struct hash_element *hash_table; /**< hash table */

	struct hash_element *last;       /**< last accessed */

	int size;                        /**< maximum number of elements */

	int count;                       /**< current count of elements */

	hash_freefunc_t free;            /**< free function */

};

static struct hash_element* hash_find(hash_t ht, hash_key_t key, int flag);

static int check_prime(int value);

hash_t hash_create(hash_freefunc_t free_func, size_t size)

{

	hash_t ht = NULL;

	/* Check passed size */

	if (!check_prime(size)) {

		return NULL;

	}

	ht = (struct hash_object *)malloc(sizeof(*ht));

	if (ht) {

		ht->size = size;

		ht->hash_table = (struct hash_element *)calloc(ht->size,

				sizeof(*ht->hash_table));

		if (ht->hash_table) {

			int i = 0;

			ht->last = NULL;

			ht->count = 0;

			ht->free = free_func;

			for (i = 0; i < ht->size; i++) {

				ht->hash_table[i].key = HASH_KEY_INVALID;

			}

		} else {

			free(ht);

			ht = NULL;

		}

	}

	return ht;

}

void hash_destroy(hash_t ht)

{

	if (ht) {

		if (ht->hash_table) {

			int i = 0;

			for (i = 0; i < ht->size; i++) {

				if (ht->hash_table[i].key != HASH_KEY_INVALID) {

					if (ht->free && ht->hash_table[i].value) {

						ht->free(ht->hash_table[i].value);

					}

					ht->hash_table[i].key = HASH_KEY_INVALID;

					ht->hash_table[i].value = NULL;

				}

			}

			free(ht->hash_table);

			ht->hash_table = NULL;

		}

		free(ht);

		ht = NULL;

	}

}

int hash_count(hash_t ht)

{

	return ht->count;

}

int hash_size(hash_t ht)

{

	return ht->size;

}

void *hash_get(hash_t ht, hash_key_t key)

{

	if (ht) {

		struct hash_element *entry = NULL;

		entry = hash_find(ht, key, 0);

		if (entry) {

			return entry->value;

		}

	}

	return NULL;

}

void *hash_enum(hash_t ht, size_t index)

{

	if (ht) {

		struct hash_element *entry = NULL;

		entry = &(ht->hash_table[index]);

		if (entry) {

			return entry->value;

		}

	}

	return NULL;

}

void *hash_put(hash_t ht, hash_key_t key, void *value)

{

	if (ht && (ht->count < ht->size)) {

		struct hash_element *entry = NULL;

		entry = hash_find(ht, key, 0);

		if (NULL == entry) {

			entry = hash_find(ht, key, 1);

		}

		if (entry) {

			if (ht->free && entry->value) {

				ht->free(entry->value);

			}

			if (entry->key == HASH_KEY_INVALID) {

				ht->count++;

			}

			entry->key = key;

			entry->value = value;

			return value;

		}

	}

	return NULL;

}

void hash_del(hash_t ht, hash_key_t key)

{

	if (ht) {

		struct hash_element *entry = NULL;

		entry = hash_find(ht, key, 0);

		if (entry) {

			if (ht->free && entry->value) {

				ht->free(entry->value);

			}

			if (entry->key != HASH_KEY_INVALID) {

				ht->count--;

			}

			entry->key = HASH_KEY_INVALID;

			entry->value = NULL;

		}

	}

}

/* hash_find():

 *

 * Find a place (hash element) in the hash related key or

 * new element.

 * @param ht - point to hash object

 * @param key - key identified data

 * @param flag - 1 - add new, 0 - find existing

 * @return hash element or NULL in case there is no place.

 */

static struct hash_element* hash_find(hash_t ht, hash_key_t key, int flag)

{

	struct hash_element *entry = NULL;

	int attempts = 0;

	int idx = 0;

	hash_key_t expect_key;

	if (ht->last && ht->last->key == key)

		return ht->last;

	expect_key = (flag ? HASH_KEY_INVALID : key);

	idx = key % ht->size;

	do {

		entry = &(ht->hash_table[idx]);

		if (entry->key == expect_key) {

			break;

		} else {

			if (attempts >= (ht->size - 1)) {

				entry = NULL;

				break;

			}

			attempts++;

			idx = (idx + 1) % ht->size;

		}

	} while (1);

	ht->last = (entry ? entry : ht->last);

	return entry;

}

static int check_prime(int value)

{

	int i = 0;

	for (i = 2; i <= value / 2; i++) {

		if ((value % i) == 0) {

			return 0;

		}

	}

	return 1;

}