/* 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 ===* *===========================*/ static long random_char_code _AP((long ch,long offset)); static long random_char_code(ch,offset) long ch; long offset; { static long random_array_3[256] = {142, 176, 108, 210, 109, 223, 214, 251, 102, 86, 91, 9, 247, 139, 115, 71, 63, 35, 126, 77, 209, 175, 120, 28, 44, 198, 21, 125, 245, 250, 10, 119, 127, 60, 81, 226, 216, 182, 172, 72, 151, 178, 116, 224, 244, 41, 212, 73, 190, 248, 173, 18, 82, 27, 97, 26, 79, 169, 74, 170, 83, 189, 101, 141, 230, 55, 135, 220, 187, 201, 95, 39, 186, 131, 105, 36, 255, 203, 155, 84, 160, 75, 254, 235, 51, 243, 158, 14, 148, 167, 149, 96, 68, 161, 45, 233, 11, 19, 3, 38, 195, 48, 144, 15, 171, 94, 180, 29, 252, 181, 80, 4, 20, 213, 23, 143, 7, 236, 76, 110, 22, 58, 17, 253, 66, 246, 40, 112, 179, 130, 87, 124, 240, 193, 107, 165, 202, 31, 106, 43, 93, 99, 147, 199, 129, 197, 32, 229, 150, 46, 157, 128, 136, 153, 121, 113, 237, 194, 218, 104, 78, 184, 62, 159, 227, 222, 47, 53, 1, 24, 118, 177, 49, 185, 98, 90, 34, 192, 200, 221, 232, 146, 114, 137, 67, 225, 154, 241, 50, 56, 145, 5, 188, 207, 231, 228, 6, 183, 219, 217, 156, 30, 174, 205, 103, 37, 133, 152, 117, 196, 164, 249, 239, 64, 242, 59, 168, 2, 162, 13, 92, 85, 70, 0, 52, 65, 166, 163, 215, 69, 140, 25, 33, 100, 42, 54, 88, 206, 122, 57, 16, 208, 134, 132, 138, 89, 8, 234, 12, 238, 111, 204, 61, 211, 191, 123}; return(random_array_3[ (offset + (ch & 0xFF)) % 256]); } /* assumes the word has been downcased already */ static long hash_word(wd,below_n) char *wd; long below_n; { static long random_array_2[256] = {818, 789, 854, 862, 704, 1019, 390, 887, 93, 204, 269, 59, 743, 219, 191, 769, 911, 435, 805, 448, 142, 1000, 149, 264, 639, 504, 699, 934, 266, 661, 318, 211, 117, 549, 90, 536, 378, 944, 400, 599, 592, 883, 985, 606, 759, 456, 581, 119, 106, 310, 412, 931, 233, 561, 973, 870, 377, 349, 334, 354, 249, 585, 799, 899, 545, 553, 848, 625, 438, 890, 791, 1014, 337, 374, 489, 146, 123, 907, 977, 22, 396, 241, 198, 424, 136, 715, 867, 684, 560, 244, 293, 1017, 397, 778, 725, 78, 184, 656, 389, 635, 982, 158, 203, 878, 323, 394, 73, 18, 837, 996, 58, 62, 161, 451, 534, 746, 485, 222, 25, 666, 28, 21, 420, 147, 522, 74, 474, 362, 253, 172, 195, 622, 559, 790, 288, 455, 263, 538, 355, 417, 810, 576, 685, 797, 641, 315, 347, 786, 487, 966, 579, 181, 499, 429, 688, 140, 278, 719, 186, 872, 997, 319, 173, 882, 1008, 573, 431, 830, 774, 654, 235, 121, 925, 529, 593, 92, 954, 434, 213, 79, 284, 510, 763, 655, 300, 447, 4, 461, 506, 88, 99, 459, 220, 780, 523, 178, 303, 578, 287, 827, 419, 521, 114, 703, 664, 892, 304, 876, 352, 331, 35, 896, 341, 450, 812, 350, 316, 705, 815, 935, 15, 572, 503, 467, 306, 976, 118, 760, 807, 809, 339, 442, 758, 546, 327, 527, 537, 383, 82, 531, 728, 428, 768, 675, 814, 919, 133, 682, 906, 163, 716, 692, 174, 464, 708, 922}; long i; long answer = 0; for (i = 0; i < strlen(wd); i++) { answer = answer ^ (random_array_2[i % 256] + ((0 == (i & 1)) ? random_char_code((long)wd[i], i) : (random_char_code((long)wd[i], i)) << 8)); } return(answer % below_n); } static long hash_word_2 _AP((char *wd)); static long hash_word_2(wd) char *wd; { long hash = hash_word(wd, ((1L << (8 * DICTIONARY_ENTRY_HASH_CODE_SIZE)) - 2)); return(1 + hash); } /* ================================ === Word Occurance Buffers === ================================ */ /* Word occurance buffers * This is a simple memory allocator for use with the word memory hashtable. * Since the buffers are tiny, this is done as a copy-sweep GC scheme. * Oh, I long for the storage system of lisp. */ char *first_word_occurance_buffer = NULL; /* allocate blocks out of this */ char *last_word_occurance_buffer = NULL; long word_occurance_block_length = 256000; /* maybe this should be larger? */ char * word_occurance_free_ptr = NULL; char *make_word_occurrance_block(size) long size; { /* allocates a word_occurance_block out of the buffers */ /* old way: s_malloc((size_t)size); */ /* returns a pointer to a piece of memory */ if(NULL == first_word_occurance_buffer){ /* initialize it */ first_word_occurance_buffer = (char *)s_malloc(MAX(word_occurance_block_length, sizeof(size_t)+ size)); *(char **)first_word_occurance_buffer = NULL; /* set the end */ last_word_occurance_buffer = first_word_occurance_buffer; word_occurance_free_ptr = first_word_occurance_buffer + sizeof(size_t); } if((long)word_occurance_free_ptr + size >= 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); }