ANTICHAT — форум по информационной безопасности, OSINT и технологиям

#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define BUFF_SIZE 200 
#define TABLE_SIZE 65535
typedef enum{INSERTED, NOT_INSERTED, COUNT_INCREMENTED} insertstatus_t;
typedef struct {
	const char * word; 
	size_t count; 
	size_t hash;
} HASH_ITEM;
/* compare two HASH_ITEM's by words */
static int cmpitems(const void * p1, const void * p2){
	return strcmp(((HASH_ITEM *)p1)->word, ((HASH_ITEM *)p2)->word);
}
/* sorting storage with qsort() function and refreshing HASH_INDEXes*/
void sort(size_t* hash_index,HASH_ITEM* hash_items,size_t items_count){
	
	qsort(hash_items, items_count, sizeof(HASH_ITEM), cmpitems);
	
	for(size_t i = 0; i < items_count; ++i)
		hash_index[hash_items[i].hash]=i;
}
void hash(const char* keyword, size_t * h1, size_t * h2) {
	for(*h1=1, *h2=1; *keyword!= '\0'; keyword++) {
		*h1 *= 17; *h1 += 13*(*keyword); 
        *h2 *= 13; *h2 += 17*(*keyword);
    }
    *h1 %= TABLE_SIZE;
    *h2 %= (TABLE_SIZE-1); *h2 += 1;
}
/* inserting keyword to hash table.
 * Returns 
 * INSERTED - word has been successfully inserted
 * NOT_INSERTED - can't find free hash index 
 * COUNTER_INCREMENTED - word already inserted, just inc word count */
insertstatus_t
insert(size_t* hash_index,HASH_ITEM* hash_items,size_t* items_count,
						const char* keyword) {
	size_t h1,h2,hfirst;
	hash(keyword, &h1, &h2);
	hfirst=h1;//first hash without probe
	/* searching for already inserted word and increment counter*/
	for (size_t i=0; hash_index[h1] != -1 && i<TABLE_SIZE+1; i++) {
        if (strcmp(keyword, hash_items[hash_index[h1]].word) == 0 ) {
           hash_items[ hash_index[h1] ].count++;
           return COUNT_INCREMENTED;
        } 
        h1 += h2; h1 %= TABLE_SIZE; // next hash with probe
        if(h1==hfirst) 
        	return NOT_INSERTED; //free pos not found, word not inserted
    }
    /* if it is the first insert */
    hash_index[h1] = *items_count;
    hash_items[*items_count].word=strcpy(malloc(strlen(keyword)+1),keyword);
    hash_items[ *items_count ].count = 1;
    hash_items[ (*items_count)++ ].hash = h1;
    return INSERTED;
}
void 
print(const size_t* hash_index,const HASH_ITEM* hash_items,
										size_t items_count) {
	size_t i;
	for(i=0; i<items_count; ++i)
		(void)printf("%s %d\n",hash_items[i].word, hash_items[i].count);
	(void)printf("\nCount of different words = %d\n",i);
}
/* returning  1 - word successfulley readed to WORD_BUF
0 -  no words left*/
int getword(char ** word_buf) {
	/*if it is the first using of WORD_BUF*/
	if(*word_buf==NULL)
		*word_buf=malloc(BUFF_SIZE); 
		
	size_t word_len = 0; //current length of string in WORD_BUF
	static size_t wbuf_growth=1;//level of WORD_BUF size,(BUFF_SIZE*WBUF_GROWTH)
	const size_t wbuf_growth_max = 5;//max value of the WBUF_GROWTH
	unsigned char c; //current readed symbol
	int word_started = 0;
	 
	while(fread(&c,1,1,stdin)) {
		if(isalpha((unsigned char)c) || (word_started && c == '\'')) {
			if(!word_started) {
				word_len = 0;
				word_started = 1;
			}
			/* if word buffer is full we must to reallocate it or break 
			 * the cycle if buffer have a maximum length  */
			if(word_len+1 > wbuf_growth*BUFF_SIZE) {
				if(wbuf_growth < wbuf_growth_max)
					*word_buf=realloc(*word_buf,++wbuf_growth*BUFF_SIZE);
				else
					break;
			}
			(*word_buf)[word_len++] = (unsigned char)tolower(c);
		} else if(word_started) {
			/* we found end of the word */
			break;
		}
	}   /* EOF or delimiter(end of word) is reached */
	
	if(word_started) {
		(*word_buf)[word_len]= '\0';
		return 1;
	} else {
		free(*word_buf);
		return 0;
	}
}
int main(void) {
	/* storage for words and their attributes */
	HASH_ITEM hash_items[TABLE_SIZE];
	size_t items_count = 0;
	/* hashes of the words are the indexes of this array, values is the 
	 * indexes of appropriate HASH_ITEM's in storage */
	size_t hash_index[TABLE_SIZE];
	char * word = NULL;
	
	(void)memset(hash_index,-1,TABLE_SIZE*sizeof(size_t));
	while(getword(&word)) {
		if(insert(hash_index,hash_items,&items_count,word)==NOT_INSERTED)
			(void)printf("Warning: keyword can't be inserted %s\n",word);
	}
	sort(hash_index,hash_items,items_count);
	print(hash_index,hash_items,items_count);
	return EXIT_SUCCESS;
}