//#include "include/common.h"
#include <string.h>
#include <stdlib.h>
#define _new malloc
#define _delete free
typedef struct{
void* table;
int size, cap, keySize;
} linear_hash_t;
unsigned int _linear_hash_function(void* key, int size);
int _linear_hash_compare(char* A, char* B, int size);
void _linear_hash_inserter(void* key, void* context);
void* _linear_hash_get_key_at(linear_hash_t* hash, int poz);
int _linear_hash_get_label_at(linear_hash_t* hash, int poz);
void _linear_hash_set_label_at(linear_hash_t* hash, int poz, char val);
int _linear_hash_keep_going(linear_hash_t* hash, int poz, void* key, int goIfIsNil);
int _linear_hash_search_for(linear_hash_t* hash, void* key, int goIfIsNil);
void _linear_hash_alloc(linear_hash_t* hash, int cap, int key);
void _linear_hash_calibrate(linear_hash_t* hash);
/// /// /// /// /// /// /// /// /// /// /// /// /// ///
void* linear_hash_new(int keySize);
void linear_hash_clear(linear_hash_t* hash);
void linear_hash_delete(linear_hash_t* hash);
void linear_hash_swap(linear_hash_t* A, linear_hash_t* B);
int linear_hash_contains(linear_hash_t* hash, void* key);
int linear_hash_is_empty(linear_hash_t* hash);
int linear_hash_get_size(linear_hash_t* hash);
int linear_hash_get_capacity(linear_hash_t* hash);
void linear_hash_insert(linear_hash_t* hash, void* key);
void linear_hash_iterate(linear_hash_t* hash, void (*iterate)(void*, void*), void* context);
unsigned int _linear_hash_function(void* key, int size){
unsigned int ans = 0;
char* poz = key;
while (size--){
ans = (ans * 257) + (*poz);
poz++;
}
return ans;
}
int _linear_hash_compare(char* A, char* B, int size){
while (size--){
if ((*A) != (*B))
return 1;
A++;
B++;
}
return 0;
}
void _linear_hash_inserter(void* key, void* context){
linear_hash_insert(context, key);
}
void* _linear_hash_get_key_at(linear_hash_t* hash, int poz){
return hash -> table + poz * (hash -> keySize + 1);
}
int _linear_hash_get_label_at(linear_hash_t* hash, int poz){
return *(char*)( _linear_hash_get_key_at(hash, poz) + hash -> keySize );
}
void _linear_hash_set_label_at(linear_hash_t* hash, int poz, char val){
*(char*)( hash -> table + (hash -> keySize + 1) * poz + hash -> keySize ) = val;
}
int _linear_hash_keep_going(linear_hash_t* hash, int poz, void* key, int goIfIsNil){
char state = _linear_hash_get_label_at(hash, poz);
if (state == 0)
return 0;
if (state == 1)
return goIfIsNil;
return _linear_hash_compare(hash -> table + (hash -> keySize + 1) * poz, key, hash -> keySize);
}
int _linear_hash_search_for(linear_hash_t* hash, void* key, int goIfIsNil){
int poz = _linear_hash_function(key, hash -> keySize) & (hash -> cap - 1), i = 0;
while ( _linear_hash_keep_going(hash, poz, key, goIfIsNil) )
poz = (poz + ( (i++) << 1 ) + 1) & (hash -> cap - 1);
return poz;
}
void _linear_hash_alloc(linear_hash_t* hash, int cap, int key){
hash -> size = 0;
hash -> cap = cap;
hash -> keySize = key;
hash -> table = _new( cap * (key + 1) );
memset(hash -> table, 0, cap * (key + 1));
}
void _linear_hash_calibrate(linear_hash_t* hash){
if ((hash -> size << 1) < hash -> cap)
return;
int cap = hash -> cap << 1;
if (cap == 0) cap = 2;
linear_hash_t* H = linear_hash_new(hash -> keySize);
_linear_hash_alloc(H, cap, hash -> keySize);
linear_hash_iterate(hash, _linear_hash_inserter, H);
linear_hash_swap(H, hash);
linear_hash_delete(H);
}
/// /// /// /// /// /// /// /// /// /// /// /// /// ///
void* linear_hash_new(int keySize){
linear_hash_t* hash = _new(sizeof(linear_hash_t));
_linear_hash_alloc(hash, 0, keySize);
return hash;
}
void linear_hash_clear(linear_hash_t* hash){
memset(hash -> table, 0, sizeof(hash -> table));
}
void linear_hash_delete(linear_hash_t* hash){
_delete(hash -> table);
_delete(hash);
}
void linear_hash_swap(linear_hash_t* A, linear_hash_t* B){
linear_hash_t C = *A;
*A = *B;
*B = C;
}
int linear_hash_contains(linear_hash_t* hash, void* key){
_linear_hash_calibrate(hash);
return _linear_hash_get_label_at(hash, _linear_hash_search_for(hash, key, 1)) == 2;
}
int linear_hash_is_empty(linear_hash_t* hash){
return hash -> size == 0;
}
int linear_hash_get_size(linear_hash_t* hash){
return hash -> size;
}
int linear_hash_get_capacity(linear_hash_t* hash){
return hash -> cap;
}
void linear_hash_insert(linear_hash_t* hash, void* key){
if (linear_hash_contains(hash, key))
return;
int poz = _linear_hash_search_for(hash, key, 0);
hash -> size++;
memcpy(_linear_hash_get_key_at(hash, poz), key, hash -> keySize);
_linear_hash_set_label_at(hash, poz, 2);
}
void linear_hash_erase(linear_hash_t* hash, void* key){
_linear_hash_calibrate(hash);
int poz = _linear_hash_search_for(hash, key, 1);
if (_linear_hash_get_label_at(hash, poz) == 2){
hash -> size--;
_linear_hash_set_label_at(hash, poz, 1);
}
}
void linear_hash_iterate(linear_hash_t* hash, void (*iterate)(void*, void*), void* context){
int i;
for (i = 0 ; i < hash -> cap ; i++)
if ( _linear_hash_get_label_at(hash, i) == 2 )
iterate(_linear_hash_get_key_at(hash, i), context);
}
#include <stdio.h>
int main(){
int times, type, x;
void* hash = linear_hash_new(4);
FILE* in = fopen("hashuri.in", "r");
FILE* out = fopen("hashuri.out", "w");
fscanf(in, "%d", ×);
while (times--){
fscanf(in, "%d%d", &type, &x);
if (type == 1)
linear_hash_insert(hash, &x);
if (type == 2)
linear_hash_erase(hash, &x);
if (type == 3)
fprintf(out, "%d\n", linear_hash_contains(hash, &x));
}
fclose(in);
fclose(out);
return 0;
}