Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #ifdef __STDC_LIB_EXT1__
- #define __STDC_WANT_LIB_EXT1__ 1
- #define scanf scanf_s // Bit hacky ngl.
- #endif
- #include <stddef.h> // size_t, NULL
- #include <stdint.h> // uint64_t
- #include <stdbool.h> // bool
- #include <stdio.h> // scanf()/scanf_s(), puts()
- #include <stdlib.h> // malloc(), calloc(), free()
- #include <string.h> // memset(), strcmp()
- typedef struct {
- unsigned short year;
- unsigned char month, day;
- char *name;
- } User;
- typedef struct Bucket {
- User user;
- struct Bucket *collision;
- bool valid: 1;
- } Bucket;
- #define FNV1A_OFFSET 0xCBF29CE484222325
- #define FNV1A_PRIME 0x00000100000001B3
- static inline uint64_t fnv1a_hash_user(User user) {
- uint64_t hash = FNV1A_OFFSET;
- hash = (hash ^ user.year) * FNV1A_PRIME;
- hash = (hash ^ user.month) * FNV1A_PRIME;
- hash = (hash ^ user.day) * FNV1A_PRIME;
- while (*user.name)
- hash = (hash ^ *user.name++) * FNV1A_PRIME;
- return hash;
- }
- #define HASHMAP_HEAP
- #ifdef HASHMAP_HEAP
- #define HASHMAP_SIZE 10000000 / sizeof(Bucket) // RAM is limited to 35 MB. God and virtual memmory, please save me.
- #else
- #define HASHMAP_SIZE 10000000 / sizeof(Bucket) // RAM is limited to 35 MB. God and virtual memmory, please save me.
- #endif
- int main() {
- #ifdef HASHMAP_HEAP
- Bucket *hashmap = (Bucket *) calloc(HASHMAP_SIZE, sizeof(Bucket)); // false == 0, NULL == 0
- #else
- Bucket hashmap[HASHMAP_SIZE];
- memset(&hashmap, 0, sizeof(hashmap)); // false == 0, NULL == 0
- #endif
- char operation;
- User user;
- while (5 == scanf(" %c : %hu %hhu %hhu %m[^\n]",
- &operation,
- &user.year,
- &user.month,
- &user.day,
- &user.name)) {
- Bucket *bucket = &hashmap[fnv1a_hash_user(user) % HASHMAP_SIZE], *prev_bucket = NULL;
- switch (operation) {
- case 'S': store: {
- if (!bucket->valid) {
- bucket->user = user;
- bucket->collision = NULL;
- bucket->valid = true;
- if (prev_bucket)
- prev_bucket->collision = bucket;
- puts("Stored");
- }
- else if (bucket->user.year == user.year &&
- bucket->user.month == user.month &&
- bucket->user.day == user.day &&
- !strcmp(bucket->user.name, user.name))
- puts("Already stored");
- else if (!bucket->collision) {
- prev_bucket = bucket;
- prev_bucket->collision = bucket = bucket->collision = malloc(sizeof(Bucket));
- bucket->user = user;
- bucket->collision = NULL;
- bucket->valid = true;
- puts("Stored");
- }
- else {
- prev_bucket = bucket;
- bucket = bucket->collision;
- goto store;
- }
- }
- break;
- case 'F': find: {
- if (!bucket->valid)
- puts("Not found");
- else if (bucket->user.year == user.year &&
- bucket->user.month == user.month &&
- bucket->user.day == user.day &&
- !strcmp(bucket->user.name, user.name))
- puts("Found");
- else if (!bucket->collision)
- puts("Not found");
- else {
- // prev_bucket = bucket;
- bucket = bucket->collision;
- goto find;
- }
- }
- break;
- case 'D': delete: {
- if (!bucket->valid)
- puts("Not found");
- else if (bucket->user.year == user.year &&
- bucket->user.month == user.month &&
- bucket->user.day == user.day &&
- !strcmp(bucket->user.name, user.name)) {
- prev_bucket = bucket->collision;
- bucket->valid = false;
- free(bucket->user.name);
- puts("Deleted");
- }
- else if (!bucket->collision)
- puts("Not found");
- else {
- prev_bucket = bucket;
- bucket = bucket->collision;
- goto delete;
- }
- }
- break;
- }
- }
- for (size_t idx = 0; HASHMAP_SIZE > idx; idx++)
- if (hashmap[idx].valid) {
- free(hashmap[idx].user.name);
- Bucket *collision = &hashmap[idx];
- while ((collision = collision->collision))
- free(collision);
- }
- #ifdef HASHMAP_HEAP
- free(hashmap);
- #endif
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement