| hash-table.cc (58551) | hash-table.cc (67064) |
|---|---|
| 1/* Hash table for checking keyword links. Implemented using double hashing. | 1/* Hash table for checking keyword links. Implemented using double hashing. |
| 2 Copyright (C) 1989-1998 Free Software Foundation, Inc. | 2 Copyright (C) 1989-1998, 2000 Free Software Foundation, Inc. |
| 3 written by Douglas C. Schmidt (schmidt@ics.uci.edu) 4 5This file is part of GNU GPERF. 6 7GNU GPERF is free software; you can redistribute it and/or modify 8it under the terms of the GNU General Public License as published by 9the Free Software Foundation; either version 1, or (at your option) 10any later version. --- 10 unchanged lines hidden (view full) --- 21#include "hash-table.h" 22 23#include <stdio.h> 24#include <string.h> /* declares memset(), strcmp() */ 25#include <hash.h> 26#include "options.h" 27#include "trace.h" 28 | 3 written by Douglas C. Schmidt (schmidt@ics.uci.edu) 4 5This file is part of GNU GPERF. 6 7GNU GPERF is free software; you can redistribute it and/or modify 8it under the terms of the GNU General Public License as published by 9the Free Software Foundation; either version 1, or (at your option) 10any later version. --- 10 unchanged lines hidden (view full) --- 21#include "hash-table.h" 22 23#include <stdio.h> 24#include <string.h> /* declares memset(), strcmp() */ 25#include <hash.h> 26#include "options.h" 27#include "trace.h" 28 |
| 29#define NIL(TYPE) (TYPE *)0 30 | |
| 31/* The size of the hash table is always the smallest power of 2 >= the size 32 indicated by the user. This allows several optimizations, including 33 the use of double hashing and elimination of the mod instruction. 34 Note that the size had better be larger than the number of items 35 in the hash table, else there's trouble!!! Note that the memory 36 for the hash table is allocated *outside* the intialization routine. 37 This compromises information hiding somewhat, but greatly reduces 38 memory fragmentation, since we can now use alloca! */ 39 | 29/* The size of the hash table is always the smallest power of 2 >= the size 30 indicated by the user. This allows several optimizations, including 31 the use of double hashing and elimination of the mod instruction. 32 Note that the size had better be larger than the number of items 33 in the hash table, else there's trouble!!! Note that the memory 34 for the hash table is allocated *outside* the intialization routine. 35 This compromises information hiding somewhat, but greatly reduces 36 memory fragmentation, since we can now use alloca! */ 37 |
| 40Hash_Table::Hash_Table (List_Node **table_ptr, int s): 41 table (table_ptr), size (s), collisions (0) | 38Hash_Table::Hash_Table (List_Node **table_ptr, int s, int ignore_len): 39 table (table_ptr), size (s), collisions (0), ignore_length (ignore_len) |
| 42{ 43 T (Trace t ("Hash_Table::Hash_Table");) 44 memset ((char *) table, 0, size * sizeof (*table)); 45} 46 47Hash_Table::~Hash_Table (void) 48{ 49 T (Trace t ("Hash_Table::~Hash_Table");) --- 5 unchanged lines hidden (view full) --- 55 "\ndumping the hash table\n" 56 "total available table slots = %d, total bytes = %d, total collisions = %d\n" 57 "location, %*s, keyword\n", 58 size, size * (int) sizeof (*table), collisions, 59 field_width, "keysig"); 60 61 for (int i = size - 1; i >= 0; i--) 62 if (table[i]) | 40{ 41 T (Trace t ("Hash_Table::Hash_Table");) 42 memset ((char *) table, 0, size * sizeof (*table)); 43} 44 45Hash_Table::~Hash_Table (void) 46{ 47 T (Trace t ("Hash_Table::~Hash_Table");) --- 5 unchanged lines hidden (view full) --- 53 "\ndumping the hash table\n" 54 "total available table slots = %d, total bytes = %d, total collisions = %d\n" 55 "location, %*s, keyword\n", 56 size, size * (int) sizeof (*table), collisions, 57 field_width, "keysig"); 58 59 for (int i = size - 1; i >= 0; i--) 60 if (table[i]) |
| 63 fprintf (stderr, "%8d, %*s, %s\n", 64 i, field_width, table[i]->char_set, table[i]->key); | 61 fprintf (stderr, "%8d, %*.*s, %.*s\n", 62 i, 63 field_width, table[i]->char_set_length, table[i]->char_set, 64 table[i]->key_length, table[i]->key); |
| 65 66 fprintf (stderr, "\nend dumping hash table\n\n"); 67 } 68} 69 70/* If the ITEM is already in the hash table return the item found 71 in the table. Otherwise inserts the ITEM, and returns FALSE. 72 Uses double hashing. */ 73 74List_Node * | 65 66 fprintf (stderr, "\nend dumping hash table\n\n"); 67 } 68} 69 70/* If the ITEM is already in the hash table return the item found 71 in the table. Otherwise inserts the ITEM, and returns FALSE. 72 Uses double hashing. */ 73 74List_Node * |
| 75Hash_Table::operator() (List_Node *item, int ignore_length) | 75Hash_Table::insert (List_Node *item) |
| 76{ 77 T (Trace t ("Hash_Table::operator()");) | 76{ 77 T (Trace t ("Hash_Table::operator()");) |
| 78 unsigned hash_val = hashpjw (item->char_set); 79 int probe = hash_val & size - 1; 80 int increment = (hash_val ^ item->length | 1) & size - 1; | 78 unsigned hash_val = hashpjw (item->char_set, item->char_set_length); 79 int probe = hash_val & (size - 1); 80 int increment = ((hash_val ^ item->key_length) | 1) & (size - 1); |
| 81 | 81 |
| 82 while (table[probe] 83 && (strcmp (table[probe]->char_set, item->char_set) 84 || (!ignore_length && table[probe]->length != item->length))) | 82 while (table[probe]) |
| 85 { | 83 { |
| 84 if (table[probe]->char_set_length == item->char_set_length 85 && memcmp (table[probe]->char_set, item->char_set, item->char_set_length) == 0 86 && (ignore_length || table[probe]->key_length == item->key_length)) 87 return table[probe]; 88 |
|
| 86 collisions++; | 89 collisions++; |
| 87 probe = probe + increment & size - 1; | 90 probe = (probe + increment) & (size - 1); |
| 88 } 89 | 91 } 92 |
| 90 return table[probe] ? table[probe] : (table[probe] = item, NIL (List_Node)); | 93 table[probe] = item; 94 return (List_Node *) 0; |
| 91} | 95} |