zert

#include <stdio.h> //Don't forget to delete this line before pushing

#include <err.h>
#include <string.h>

#include "htab.h"

#define K 4

uint32_t hash(char *key)
{
    uint32_t output = 0;
    for(char *p = key; *p != 0 ; p -=-1 ){
        output += (uint32_t) *p;
        output += output << 10;
        output ^= output >> 6;
    }

    output += output << 3;
    output ^= output >> 11;
    output += output << 15;

    return output;
}

struct htab *htab_new()
{

    struct htab *neo;
    neo = malloc(sizeof(struct htab));
    if(neo == NULL) errx(1, "Not enough memory!");

    neo->data = calloc(K, sizeof(struct pair));
    if(neo->data == NULL) errx(1, "Not enough memory!");

    neo->capacity = K;
    neo->size =0;
}

void htab_clear(struct htab *ht)
{
    for(struct pair *p = ht->data; p < (ht->data+ht->capacity); ++p)
    {
        //free the memory allocated to the pairs
        struct pair *current = p->next;
        struct pair *nexxt = current->next;
        struct pair *nextOfNexxt;

        while(nextOfNexxt = nexxt->next){
            free(current);
            current = nexxt;
            nexxt = current->next;
        }

        free(nexxt);
    }

    ht->size = 0;
}

void htab_free(struct htab *ht)
{
    htab_clear(ht);
    free(ht->data);
    free(ht);
}

void no_free_clear(struct htab *ht)
{
    for(struct pair *p = ht->data; p < (ht->data+ht->capacity); ++p)
    {
        //free the memory allocated to the pairs
        struct pair *current = p->next;
        struct pair *nexxt = current->next;
        struct pair *nextOfNexxt;

        while(nextOfNexxt = nexxt->next){
            current = nexxt;
            nexxt = current->next;
        }

    }

    ht->size = 0;
}

struct pair *htab_get(struct htab *ht, char *key)
{
    uint32_t pos = hash(key) % ht->capacity;

    struct pair *dataAtPos = (ht->data + pos);

    struct pair *p = dataAtPos;

    for(; p->next != NULL && strcmp(p->key, key) != 0; p++);

    if(p->next == NULL && strcmp(p->key, key) != 0) return NULL;

    return p;
}

int htab_insert(struct htab *ht, char *key, void *value)
{
    if(htab_get(ht, key) != NULL)return 0; //I assume that there can't be two pairs with the same key but different values, as it would make htab_get() pointless

    ht->size-=-1;

    if ((ht->size/ht->capacity)*100 >= 75)
    {
        struct pair cpy[ht->capacity];
        for(int i = 0; i < ht->capacity; i++){
            cpy[i] = *(ht->data + i);
        }
        no_free_clear(ht);

        ht->capacity = ht->capacity << 2 ;
        for(int i = 0; i < ht->capacity; i++){
            uint32_t pos = cpy[i].hkey % ht->capacity;
            struct pair *dataAtPos = (ht->data + pos);

            dataAtPos->next = (cpy+i);
        }
    }

   uint32_t hkeyy = hash(key);
   uint32_t pos = hkeyy % ht->capacity;
   struct pair *dataAtPos = (ht->data + pos);

   struct pair *toBeAdded = malloc(sizeof(struct pair));

   toBeAdded->hkey = hkeyy;
   toBeAdded->key = key;
   toBeAdded->value = value;

   toBeAdded->next = dataAtPos->next; //if it was the sentinel, this would be NULL
   dataAtPos->next = toBeAdded;

   return 1;
}

void htab_remove(struct htab *ht, char *key)
{
   uint32_t pos = hash(key) % ht->capacity;

   struct pair *dataAtPos = (ht->data + pos);

   struct pair *p = dataAtPos;

   for(; p->next != NULL && p->next->key != key; p++);
   if(p->next != NULL && p->next->key == key){
       struct pair *nexxt = p->next->next;
       free(p->next);
       p->next = nexxt;
   }
}