/* WIDE AREA INFORMATION SERVER SOFTWARE: No guarantees or restrictions. See the readme file for the full standard disclaimer. Brewster@think.com */ /* The memory hashtables for building an index. */ /* -brewster 5/90 */ /* main functions: * add_word * finished_add_word * look_up_word * * The idea is to store up a bunch of words before going to disk. * A word entry points to where it will go on disk, and * accumulates the entries before doing it. * * Some of the policy issues in this file are: * How much weight should the first occurance of a word in a document get * over the other occurances. The first occurance should be worth more * so that words with 3 occurances of "dog" and not "cat"'s should not * win out over 1 "dog" and 1 "cat" if the question is "Tell me about cats * torture dogs" * The extra weight is 5 at this point. * */ /* To Do: * Improve the hashing functions. * done: stop inserting into hash table after max number have been accumulated * done: make flush not flush buffers that are too big. */ #include #include /* for strlen(), memset() */ #include "panic.h" #include "cutil.h" #include "irfiles.h" #include "irhash.h" #include "stoplist.h" #include "irinv.h" #ifdef UNIX #define PRINT_AS_INDEXING true /* also defined in irtfiles.c and irfiles.c */ #else #define PRINT_AS_INDEXING false #endif /*===========================* *=== Hashing Functions ===* *===========================*/ /* #define FAST_HASH */ #ifdef FAST_HASH /* courtesy ses@ccgr.technion.ac.il, but it turns out in informal timings that it increases the index time. sigh. */ static char coeff[] = { 61,59,53,47,43,41,37,31,29,23,17,13,11,7,3,1, 61,59,53,47,43,41,37,31,29,23,17,13,11,7,3,1, 61,59,53,47,43,41,37,31,29,23,17,13,11,7,3,1, 61,59,53,47,43,41,37,31,29,23,17,13,11,7,3,1, 61,59,53,47,43,41,37,31,29,23,17,13,11,7,3,1, 61,59,53,47,43,41,37,31,29,23,17,13,11,7,3,1, 61,59,53,47,43,41,37,31,29,23,17,13,11,7,3,1, 61,59,53,47,43,41,37,31,29,23,17,13,11,7,3,1}; long hash_word(wd,below_n) char *wd; long below_n; { register char *foo; register long hash = 0; register int l; for(l=0,foo=wd;l= word_occurance_block_length + (long)last_word_occurance_buffer){ /* then allocate a new block */ char * new_block = (char *)s_malloc(MAX(word_occurance_block_length, sizeof(size_t)+ size)); *(char **)new_block = NULL; /* set the end of the chain */ *(char **)last_word_occurance_buffer = new_block; word_occurance_free_ptr = new_block + sizeof(size_t); last_word_occurance_buffer = new_block; } /* allocate away */ { char * answer = word_occurance_free_ptr; word_occurance_free_ptr += size; return(answer); } } void free_word_occurance_block(block) char *block; { /* this is not used with the new scheme, but is here in case malloc is a win on some systems */ /* old way s_free(block); */ } static void flush_word_occur_bufs_internal _AP((char* head_of_list)); static void flush_word_occur_bufs_internal(head_of_list) char* head_of_list; /* frees all word occurance buffers. This should be done with care */ { while(1){ char * next_block; if(NULL == head_of_list) break; next_block = *(char **)head_of_list; s_free(head_of_list); head_of_list = next_block; } } void flush_word_occurance_buffers() { /* frees all word occurance buffers. This should be done with care */ flush_word_occur_bufs_internal(first_word_occurance_buffer); first_word_occurance_buffer = NULL; word_occurance_free_ptr = NULL; last_word_occurance_buffer = NULL; } void gc_word_occurance_buffers(the_word_memory_hashtable) word_memory_hashtable * the_word_memory_hashtable; { /* go through the word_memory_hashtable and copy what we need into another list of buffers, the flush the old ones */ /* not needed yet */ } /* =============================== === Word Memory Hashtable === =============================== */ static long find_location _AP((char* word,word_memory_hashtable* the_word_memory_hashtable)); static long find_location(word,the_word_memory_hashtable) char* word; word_memory_hashtable* the_word_memory_hashtable; /* returns the location that the word should go (or is). returns -1 if * the hashtable is full and the word is not there */ { long hash_code = hash_word(word, the_word_memory_hashtable->size); long i; long hash_code_2 = hash_word_2(word); for(i = hash_code; i < (hash_code + the_word_memory_hashtable->size); i++){ long index = i % the_word_memory_hashtable->size; if(NULL == the_word_memory_hashtable->contents[index]){ /* found an open spot, return it */ return(index); } else if(hash_code_2 == the_word_memory_hashtable->contents[index]->hash_code && strcmp(word, the_word_memory_hashtable->contents[index]->word) == 0){ /* we win, return it */ return(index); } /* keep looking */ } return(-1); } /* this pushes all word entries to the top of the word_memory_hashtable * therefore messing up the hashing order, but allows for quick sorting * just before dumping to disk. */ void collapse_word_memory_hashtable(the_word_memory_hashtable) word_memory_hashtable *the_word_memory_hashtable; { long insert_index = 0; long extract_index; for(extract_index = 0; extract_index < the_word_memory_hashtable->size; extract_index++){ word_entry *entry = the_word_memory_hashtable->contents[extract_index]; if(NULL != entry) the_word_memory_hashtable->contents[insert_index++] = entry; } } static int word_entry_compare _AP((word_entry**i,word_entry** j)); static int word_entry_compare(i,j) word_entry **i; word_entry **j; { return(strcmp((*i)->word, (*j)->word)); } /* assumes that the word_memory_hashtable has been compressed */ void sort_word_memory_hashtable(the_word_memory_hashtable) word_memory_hashtable *the_word_memory_hashtable; { qsort(the_word_memory_hashtable->contents, the_word_memory_hashtable->number_of_entries, (size_t)sizeof(char *), word_entry_compare); } /* for debugging */ void print_word_memory_hashtable(the_word_memory_hashtable) word_memory_hashtable* the_word_memory_hashtable; { if (NULL == the_word_memory_hashtable){ cprintf(PRINT_AS_INDEXING, "No Hashtable allocated\n"); return; } cprintf(PRINT_AS_INDEXING, "Number of entries possible: %ld\n", the_word_memory_hashtable->size); cprintf(PRINT_AS_INDEXING, "Number of entries allocated: %ld\n", the_word_memory_hashtable->number_of_entries); if(NULL != the_word_memory_hashtable->contents){ long i; /* print the entries */ printf("The entries are:\n"); for(i = 0; i < the_word_memory_hashtable->size; i++){ if(NULL != the_word_memory_hashtable->contents[i]){ printf(" Position: %ld word: \"%s\" %ld occurances\n", i, the_word_memory_hashtable->contents[i]->word, the_word_memory_hashtable->contents[i]->number_of_occurances); } } } } static word_entry* look_up_word _AP((char* word,word_memory_hashtable* the_word_memory_hashtable)); static word_entry* look_up_word(word,the_word_memory_hashtable) char* word; word_memory_hashtable* the_word_memory_hashtable; { /* looks up the word in the dictionary and returns * a pointer to the word_entry. * If is not present, then it mallocs a new word entry. */ /* this is a pretty dumb hashing scheme XXX */ long index = find_location(word, the_word_memory_hashtable); if(-1 == index){ panic("the hashtable is completely full. It should have been grown\n"); } if(NULL == the_word_memory_hashtable->contents[index]){ /* make a new entry */ word_entry *new_entry = &the_word_memory_hashtable->word_entry_block [the_word_memory_hashtable->number_of_entries++]; if(NULL == new_entry){ panic("malloc failed for word_entry\n"); } strncpy(new_entry->word, word, MAX_WORD_LENGTH); new_entry->hash_code = hash_word_2(word); new_entry->number_of_occurances = 0; new_entry->memory_ptr = make_word_occurrance_block(WORD_MEMORY_INIT_BLOCK_SIZE); new_entry->current_memory_ptr = new_entry->memory_ptr; new_entry->memory_size = WORD_MEMORY_INIT_BLOCK_SIZE; new_entry->current_doc_id = 0; the_word_memory_hashtable->contents[index] = new_entry; return(new_entry); } else{ return(the_word_memory_hashtable->contents[index]); } } static unsigned char add_weight _AP((long current_weight,long new_weight)); static unsigned char add_weight(current_weight,new_weight) long current_weight; long new_weight; /* add a new weight to the existing one */ { /* this should be smarter than this, like doing the log or something */ if(127 < (current_weight + new_weight)){ /* the max char. should be 255, but does not work on all compilers */ return(127); } else{ return(current_weight + new_weight); } } static char* more_memory _AP((char* current_memory_ptr, long current_memory_size, long new_size)); static char* more_memory(current_memory_ptr,current_memory_size,new_size) char* current_memory_ptr; long current_memory_size; long new_size; /* Allocates more memory for a word_entry. It transfers all the bytes * from the old to the new and then returns the new. */ { char* new_memory = NULL; if(current_memory_size > new_size){ panic("trying to contract a word_entry block. This is not right\n"); } new_memory = make_word_occurrance_block(new_size); if(NULL == new_memory){ panic("Out of memory."); } memset(new_memory, 0, new_size); memmove(new_memory, current_memory_ptr, (size_t)current_memory_size); return(new_memory); } static long more_memory_size _AP((long current_size, long number_of_occurances)); static long more_memory_size(current_size,number_of_occurances) long current_size; long number_of_occurances; /* This is pretty important to get right. This is a place holder */ { return(MAX(2 * current_size, WORD_MEMORY_INIT_BLOCK_SIZE)); } static long write_bytes_to_memory _AP((long value,long size,char* ptr)); static long write_bytes_to_memory(value,size,ptr) long value; long size; char* ptr; { /* writes the number into memory lsb first. returns the number of bytes written */ long i; if(size < 0) /* paranoia */ panic("attempting to write a negative number of bytes"); ptr += size; /* start at the end of the block and write backwards */ for (i = 0; i < size; i++){ ptr--; *ptr = value & 0xFF; value = value >> 8; } return(size); } /* adds a word to the word_memory_hashtable. Currently it * ignores the character position XXX. * Returns the 0 if successful. See irext.h for more documentation. */ long add_word(word, char_pos, line_pos, weight, doc_id, date, db) char *word; /* the word to be indexed, this could be a word pair. If NULL there are no more words to be indexed */ long char_pos; /* the position of the start of the word */ long line_pos; /* this is passed for the best section calculation */ long weight; /* how important the word looks syntactically (such as is it bold) NOT used by signature system */ long doc_id; /* current document, this will never be 0 */ time_t date; /* display day of this document, 0 if not known */ database* db; /* database to insert the document */ { /* look up the word in the word_memory_hashtable */ /* creates it if necessary */ word_entry* wrd_entry; word_memory_hashtable * the_word_memory_hashtable = db->the_word_memory_hashtable; /* printf("Word: '%s' doc_id: %ld, pos: %ld, weight: %ld\n", word, doc_id, char_pos, weight); */ if(NULL == db->the_word_memory_hashtable){ panic("The memory word hashtable is not defined."); } /* if we have filled up the hashtable, or if we have indexed enough words flush the memory copies to disk */ if((the_word_memory_hashtable->number_of_entries == the_word_memory_hashtable->word_entry_block_size) || (the_word_memory_hashtable->number_of_words_indexed == the_word_memory_hashtable->flush_after_n_words)) flush_memory_hashtable_to_disk(db, false); the_word_memory_hashtable->number_of_words_indexed ++; wrd_entry = look_up_word(word, the_word_memory_hashtable); wrd_entry->number_of_occurances ++; if(wrd_entry->number_of_occurances > MAX_OCCURANCES){ /* do nothing. we have enough of that word */ } else{ /* we have a word to add */ if(doc_id != wrd_entry->current_doc_id){ /* then we have a new doc_id to add to the memory block */ wrd_entry->current_doc_id = doc_id; /* check to see if we need more memory */ if((wrd_entry->memory_size - (wrd_entry->current_memory_ptr - wrd_entry->memory_ptr) < DICTIONARY_ELEMENT_SIZE)){ /* we need more memory. this makes more and frees the old*/ char* old_memory_ptr = wrd_entry->memory_ptr; long new_size = more_memory_size(wrd_entry->memory_size, wrd_entry->number_of_occurances); /* cprintf(PRINT_AS_INDEXING, "Get more memory %ld bytes for %s\n", new_size, word); */ wrd_entry->memory_ptr = more_memory(wrd_entry->memory_ptr, wrd_entry->memory_size, new_size); wrd_entry->current_memory_ptr = wrd_entry->memory_ptr + /* new offset */ (wrd_entry->current_memory_ptr - old_memory_ptr); /* just being paranoid... no longer illegal if(wrd_entry->current_memory_ptr == wrd_entry->memory_ptr) panic("After allocating more memory, the size went to 0"); */ wrd_entry->memory_size = new_size; } /* finished making more memory */ /* add away */ wrd_entry->current_memory_ptr += write_bytes_to_memory(doc_id, DOCUMENT_ID_SIZE, wrd_entry->current_memory_ptr); wrd_entry->current_memory_ptr += write_bytes_to_memory(char_pos, CHARACTER_POSITION_SIZE, wrd_entry->current_memory_ptr); wrd_entry->current_memory_ptr += write_bytes_to_memory(weight + 5, /* add 5 since for the first one */ WEIGHT_SIZE, wrd_entry->current_memory_ptr); } else{ /* The word is already there, * just increment the weight in the record. * This will change when/if position information is kept (for proximity). */ if(wrd_entry->current_memory_ptr == wrd_entry->memory_ptr){ panic("Memory hashtable error. Recorded doc_id %ld, current doc_id %ld\n", wrd_entry->current_doc_id, doc_id); } *(wrd_entry->current_memory_ptr - 1) = add_weight(*(wrd_entry->current_memory_ptr - 1), weight); } } return(0L); } void add_stop_words(the_word_memory_hashtable) word_memory_hashtable *the_word_memory_hashtable; /* add the stop words to the hashtable. this must be done before adding other words */ { init_stop_list(); while(true){ char *word = next_stop_word(); word_entry* wrd_entry; if(NULL == word) break; wrd_entry = look_up_word(word, the_word_memory_hashtable); wrd_entry->number_of_occurances = STOP_WORD_FLAG; } } /* this clears the contents of the word_memory_hashtable */ void clear_word_memory_hashtable(the_word_memory_hashtable) word_memory_hashtable *the_word_memory_hashtable; { memset((char*)the_word_memory_hashtable->contents, 0, ((long)the_word_memory_hashtable->size * sizeof(size_t))); the_word_memory_hashtable->number_of_entries = 0; the_word_memory_hashtable->number_of_words_indexed = 0; } /* Size is in the number of entries. flush_after_n_words sets the hashtable flush parameter. Returns TRUE if it succeeds. */ word_memory_hashtable * init_word_memory_hashtable(size,flush_after_n_words,the_word_memory_hashtable) long size; long flush_after_n_words; word_memory_hashtable* the_word_memory_hashtable; { if(NULL != the_word_memory_hashtable){ /* then displose of the old one */ if(NULL != the_word_memory_hashtable->contents) s_free(the_word_memory_hashtable->contents); if(NULL != the_word_memory_hashtable->word_entry_block) s_free(the_word_memory_hashtable->word_entry_block); flush_word_occurance_buffers(); } the_word_memory_hashtable = (word_memory_hashtable*)s_malloc((size_t)sizeof(word_memory_hashtable)); the_word_memory_hashtable->size = size; the_word_memory_hashtable->word_entry_block_size = size / 2; the_word_memory_hashtable->contents = (word_entry **)s_malloc((size_t)(the_word_memory_hashtable->size * sizeof(size_t))); the_word_memory_hashtable->word_entry_block = (word_entry *)s_malloc((size_t)(the_word_memory_hashtable->word_entry_block_size * sizeof(word_entry))); if(NULL == the_word_memory_hashtable->contents){ panic("Could not malloc for the word hashtable\n"); return(NULL); } /* clear the hashtable the slow by safe way for(i = 0; i < the_word_memory_hashtable->size; i++){ the_word_memory_hashtable->contents[i] = (word_entry*)NULL; } */ clear_word_memory_hashtable(the_word_memory_hashtable); /* add the stopwords to the index */ add_stop_words(the_word_memory_hashtable); the_word_memory_hashtable->flush_after_n_words = flush_after_n_words; the_word_memory_hashtable->growth_factor = 2.0; the_word_memory_hashtable->grow_when_this_full = .5; return(the_word_memory_hashtable); }