116 lines
2.4 KiB
C
116 lines
2.4 KiB
C
#include "Dict.h"
|
||
|
||
#ifdef DICT_HASH_CHAIN_C
|
||
|
||
#define _CRT_SECURE_NO_WARNINGS
|
||
#include <string.h>
|
||
#include <stdlib.h>
|
||
#include <stdbool.h>
|
||
#include "fnvhash_32a.h"
|
||
#include "jhash.h"
|
||
|
||
struct Node {
|
||
char* word;
|
||
struct Node* next;
|
||
};
|
||
|
||
#define FNV_HASH
|
||
|
||
#if defined VLASENKO_HASH
|
||
|
||
#define MAX_HASH 13267
|
||
|
||
// Ìàññèâ ñïèñêîâ
|
||
struct Node* first[MAX_HASH];
|
||
|
||
// Âû÷èñëåíèå õýøà äëÿ ñòðîêè word
|
||
int hash(char* word) {
|
||
unsigned long hash_value = 0;
|
||
int i = 0;
|
||
while (word[i] != '\0') {
|
||
hash_value = 31 * hash_value + ((unsigned)(word[i]));
|
||
i++;
|
||
}
|
||
return hash_value % MAX_HASH;
|
||
}
|
||
|
||
#elif defined JHASH
|
||
|
||
#define MAX_HASH 16384
|
||
|
||
// Ìàññèâ ñïèñêîâ
|
||
struct Node* first[MAX_HASH];
|
||
|
||
int hash(char* word) {
|
||
int hash_value = (int)jhash(word, (ub4)strlen(word) + 1, FNV1_32A_INIT);
|
||
hash_value = hash_value & hashmask(14);
|
||
return hash_value;
|
||
}
|
||
|
||
#elif defined FNV_HASH
|
||
#define MAX_HASH 16384
|
||
|
||
// Ìàññèâ ñïèñêîâ
|
||
struct Node* first[MAX_HASH];
|
||
|
||
int hash(char* word) {
|
||
int hash_value = (int)fnv_32a_str(word, FNV1_32A_INIT);
|
||
hash_value = TINY_FNV(14, hash_value);
|
||
return hash_value;
|
||
}
|
||
|
||
#endif
|
||
|
||
/* INSERT – äîáàâëÿåò ýëåìåíò â ìíîæåñòâî.
|
||
Ìíîæåñòâî – ñîäåðæèò òîëüêî óíèêàëüíûå ýëåìåíòû.
|
||
Ïðè ïîâòîðíîì äîáàâëåíèè ýëåìåíòà â ìíîæåñòâî, ìíîæåñòâî íå èçìåíÿåòñÿ.
|
||
Íåò çàùèòû îò äâîéíîãî âêëþ÷åíèÿ */
|
||
void Insert(char* word) {
|
||
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
|
||
|
||
int hash_value = hash(word);
|
||
|
||
newNode->next = first[hash_value];
|
||
newNode->word = (char*)calloc(strlen(word) + 1, sizeof(char));
|
||
strcpy(newNode->word, word);
|
||
first[hash_value] = newNode;
|
||
}
|
||
|
||
/* MEMBER – ñîîáùàåò, ÿâëÿåòñÿ ëè óêàçàííûé ýëåìåíò ÷ëåíîì äàííîãî ìíîæåñòâà èëè íåò. */
|
||
int Member(char* word) {
|
||
int hash_value = hash(word);
|
||
|
||
struct Node* ptr = first[hash_value];
|
||
while (ptr != NULL) {
|
||
if (strcmp(ptr->word, word) == 0) {
|
||
return 1;
|
||
}
|
||
ptr = ptr->next;
|
||
}
|
||
return 0;
|
||
}
|
||
|
||
/* CREATE - ñîçäàåò ñëîâàðü.
|
||
Âûçûâàåòñÿ ïåðåä íà÷àëîì èñïîëüçîâàíèÿ ñëîâàðÿ. */
|
||
void Create() {
|
||
for (int i = 0; i < MAX_HASH; i++)
|
||
first[i] = NULL;
|
||
}
|
||
|
||
/* DESTROY - óíè÷òîæàåò ñëîâàðü.
|
||
Âûçûâàåòñÿ ïîñëå îêîí÷àíèÿ èñïîëüçîâàíèÿ ñëîâàðÿ. */
|
||
void Destroy() {
|
||
for (int i = 0; i < MAX_HASH; i++) {
|
||
|
||
while (first[i] != NULL) {
|
||
struct Node* delNode = first[i];
|
||
first[i] = first[i]->next;
|
||
|
||
free(delNode->word);
|
||
free(delNode);
|
||
}
|
||
}
|
||
}
|
||
|
||
#endif
|