/* Copyright 2021 Nedelcu Horia ([email protected]) */

#include <stdio.h>
#include <stdlib.h>


#ifndef UTILS_H
#define UTILS_H 

#include <errno.h>
#include <stdio.h>

#define DIE(assertion, call_description)				\
	do {								\
		if (assertion) {					\
			fprintf(stderr, "(%s, %d): ",			\
					__FILE__, __LINE__);		\
			perror(call_description);			\
			/* exit(errno); */				\
                        return errno;					\
		}							\
	} while (0)

#endif /* UTILS_H */


#ifndef LIST_H
#define LIST_H

#include <stddef.h>
#include <stdlib.h>
#include <string.h>


struct node {
	void *data_;
	struct node *link_;	
};

struct list {
	struct node *head_;
};


void init_list(struct list *list);
void delete_list(struct list *list);
int push_front(struct list *list, const void *data, size_t data_size);
void* get_data(const struct list *list, const void *data, size_t data_size);
int delete_data(struct list *list, const void *data, size_t data_size);

#endif /* LIST_H */

void init_list(struct list *list)
{
	list->head_ = NULL;
}

void delete_list(struct list *list)
{
	struct node *next_it, *it = list->head_;

	while (it != NULL) {
		next_it = it->link_;
		free(it->data_);
		free(it);
		it = next_it;
	}

	list->head_ = NULL;
}

int push_front(struct list *list, const void *data, size_t data_size)
{
	struct node *new_node = malloc(sizeof(struct node));
	DIE(new_node == NULL, "malloc failed");

	new_node->data_ = malloc(data_size);
	DIE(new_node->data_ == NULL, "malloc failed");

	memcpy(new_node->data_, data, data_size);
	new_node->link_ = list->head_;
	list->head_ = new_node;

	return 0;
}

void* get_data(const struct list *list, const void *data, size_t data_size)
{
	const struct node *it = list->head_;

	for (; it != NULL; it = it->link_) {
		if (memcmp(it->data_, data, data_size) == 0)
			return it->data_;
	}

	return NULL;
}

int delete_data(struct list *list, const void *data, size_t data_size)
{
	struct node *last_it = NULL, *it = list->head_;

	for (; it != NULL; it = it->link_) {
		if (memcmp(it->data_, data, data_size) == 0) {
			if (last_it != NULL) {
				last_it->link_ = it->link_;
			} else {
				list->head_ = it->link_;
			}

			free(it->data_);
			free(it);

			return 0;
		}

		last_it = it;
	}

	return 1;
}


#ifndef HASHMAP_H
#define HASHMAP_H

#define PRIME_BUCKETS_SIZE 1002797


struct hashmap {
	size_t key_size_, value_size_;
	struct list *buckets_;
	size_t (*hash_)(const char *, size_t);
};


size_t default_hash(const char *data, size_t key_size);
int init_hashmap(struct hashmap *hashmap, size_t key_size, size_t value_size,
	size_t (*hash)(const char *, size_t));
void delete_hashmap(struct hashmap *hashmap);
int insert(const struct hashmap *hashmap, const void *data);
void* get(const struct hashmap *hashmap, const void *data);
int delete(const struct hashmap *hashmap, const void *data);

#endif /* HASHMAP_H */

size_t default_hash(const char *data, size_t key_size)
{
	size_t hash, i;
	
	for(hash = i = 0; i < key_size; ++i) {
		hash += data[i];
		hash += (hash << 10);
		hash ^= (hash >> 6);
	}

	hash += (hash << 3);
	hash ^= (hash >> 11);
	hash += (hash << 15);

	return hash;
}

int init_hashmap(struct hashmap *hashmap, size_t key_size, size_t value_size,
	size_t (*hash)(const char *, size_t))
{
	hashmap->key_size_ = key_size;
	hashmap->value_size_ = value_size;

	/* (hashmap->buckets_[i].head = 0) == NULL */
	hashmap->buckets_ = calloc(PRIME_BUCKETS_SIZE, sizeof(struct list));
	DIE(hashmap->buckets_ == NULL, "calloc failed");

	hashmap->hash_ = (hash == NULL)? default_hash: hash;

	return 0;
}

void delete_hashmap(struct hashmap *hashmap)
{
	size_t i;

	for (i = 0; i < PRIME_BUCKETS_SIZE; ++i) {
		delete_list(&hashmap->buckets_[i]);
	}

	free(hashmap->buckets_);
	hashmap->buckets_ = NULL;
}

int insert(const struct hashmap *hashmap, const void *data)
{
	void *old_addr = get(hashmap, data);
	size_t ret, index = hashmap->hash_(data, hashmap->key_size_)
		% PRIME_BUCKETS_SIZE;

	if (old_addr == NULL) {
		ret = push_front(&hashmap->buckets_[index], data,
			hashmap->key_size_ + hashmap->value_size_);
		DIE(ret, "push_front list failed");
	} else {
		memcpy((char *) old_addr + hashmap->key_size_, (char *) data
			+ hashmap->key_size_, hashmap->value_size_);
	}

	return 0;
}

void* get(const struct hashmap *hashmap, const void *data)
{
	size_t index = hashmap->hash_(data, hashmap->key_size_)
		% PRIME_BUCKETS_SIZE;
	return get_data(&hashmap->buckets_[index], data, hashmap->key_size_);
}

int delete(const struct hashmap *hashmap, const void *data)
{
	size_t index = hashmap->hash_(data, hashmap->key_size_)
		% PRIME_BUCKETS_SIZE;
	return delete_data(&hashmap->buckets_[index], data, hashmap->key_size_);
}


int main() {
	FILE *fin, *fout;
	struct hashmap hashmap;
	int ret, n, q, x, i;

	ret = init_hashmap(&hashmap, sizeof(int), 0, NULL);
	DIE(ret, "init_hashmap failed");

	fin = fopen("./hashuri.in", "r");
	DIE(fin == NULL, "fopen failed");

	fout = fopen("./hashuri.out", "w");
	DIE(fout == NULL, "fopen failed");

	fscanf(fin, "%d", &n);

	for (i = 0; i < n; ++i) {
		fscanf(fin, "%d %d", &q, &x);

		switch (q)
		{
		case 1:
			insert(&hashmap, &x);
			break;
		
		case 2:
			delete(&hashmap, &x);
			break;

		case 3:
			fprintf(fout, "%d\n", get(&hashmap, &x) != NULL);
			break;
		default:
			break;
		}
	}

	delete_hashmap(&hashmap);
	fclose(fin);
	fclose(fout);

	return 0;
}