hash.c
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | //----------------------------------------------------------------------------- | ||
| 2 | // hash.c | ||
| 3 | // | ||
| 4 | // Implementation of a simple Hash Table for string storage & retrieval | ||
| 5 | // CASE INSENSITIVE | ||
| 6 | // | ||
| 7 | // Written by L. Rossman | ||
| 8 | // Last Updated on 6/19/03 | ||
| 9 | // | ||
| 10 | // The hash table data structure (HTable) is defined in "hash.h". | ||
| 11 | // Interface Functions: | ||
| 12 | // HTcreate() - creates a hash table | ||
| 13 | // HTinsert() - inserts a string & its index value into a hash table | ||
| 14 | // HTfind() - retrieves the index value of a string from a table | ||
| 15 | // HTfree() - frees a hash table | ||
| 16 | //----------------------------------------------------------------------------- | ||
| 17 | |||
| 18 | #include <stdlib.h> | ||
| 19 | #include <string.h> | ||
| 20 | #include "hash.h" | ||
| 21 | #define UCHAR(x) (((x) >= 'a' && (x) <= 'z') ? ((x)&~32) : (x)) | ||
| 22 | |||
| 23 | /* Case-insensitive comparison of strings s1 and s2 */ | ||
| 24 | 334154 | int samestr(const char *s1, const char *s2) | |
| 25 | { | ||
| 26 | int i; | ||
| 27 |
8/10✓ Branch 0 taken 8250 times.
✓ Branch 1 taken 1302905 times.
✓ Branch 2 taken 8250 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 8255 times.
✓ Branch 5 taken 1302900 times.
✓ Branch 6 taken 8255 times.
✗ Branch 7 not taken.
✓ Branch 8 taken 1178105 times.
✓ Branch 9 taken 133050 times.
|
1311155 | for (i=0; UCHAR(s1[i]) == UCHAR(s2[i]); i++) |
| 28 |
4/4✓ Branch 0 taken 201113 times.
✓ Branch 1 taken 976992 times.
✓ Branch 2 taken 201104 times.
✓ Branch 3 taken 9 times.
|
1178105 | if (!s1[i+1] && !s2[i+1]) return(1); |
| 29 | 133050 | return(0); | |
| 30 | } /* End of samestr */ | ||
| 31 | |||
| 32 | /* Use Fletcher's checksum to compute 2-byte hash of string */ | ||
| 33 | 261624 | unsigned int hash(const char *str) | |
| 34 | { | ||
| 35 | 261624 | unsigned int sum1= 0, check1; | |
| 36 | 261624 | unsigned long sum2= 0L; | |
| 37 |
2/2✓ Branch 0 taken 1289325 times.
✓ Branch 1 taken 261624 times.
|
1550949 | while( '\0' != *str ) |
| 38 | { | ||
| 39 |
3/4✓ Branch 0 taken 13275 times.
✓ Branch 1 taken 1276050 times.
✓ Branch 2 taken 13275 times.
✗ Branch 3 not taken.
|
1289325 | sum1 += UCHAR(*str); |
| 40 | 1289325 | str++; | |
| 41 |
2/2✓ Branch 0 taken 229992 times.
✓ Branch 1 taken 1059333 times.
|
1289325 | if ( 255 <= sum1 ) sum1 -= 255; |
| 42 | 1289325 | sum2 += sum1; | |
| 43 | } | ||
| 44 | 261624 | check1= sum2; | |
| 45 | 261624 | check1 %= 255; | |
| 46 | 261624 | check1= 255 - (sum1+check1) % 255; | |
| 47 | 261624 | sum1= 255 - (sum1+check1) % 255; | |
| 48 | 261624 | return( ( ( check1 << 8 ) | sum1 ) % HTMAXSIZE); | |
| 49 | } | ||
| 50 | |||
| 51 | 1044 | HTtable *HTcreate() | |
| 52 | { | ||
| 53 | int i; | ||
| 54 | 1044 | HTtable *ht = (HTtable *) calloc(HTMAXSIZE, sizeof(HTtable)); | |
| 55 |
3/4✓ Branch 0 taken 1044 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 2086956 times.
✓ Branch 3 taken 1044 times.
|
2088000 | if (ht != NULL) for (i=0; i<HTMAXSIZE; i++) ht[i] = NULL; |
| 56 | 1044 | return(ht); | |
| 57 | } | ||
| 58 | |||
| 59 | 26489 | int HTinsert(HTtable *ht, char *key, int data) | |
| 60 | { | ||
| 61 | 26489 | unsigned int i = hash(key); | |
| 62 | struct HTentry *entry; | ||
| 63 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 26489 times.
|
26489 | if ( i >= HTMAXSIZE ) return(0); |
| 64 | 26489 | entry = (struct HTentry *) malloc(sizeof(struct HTentry)); | |
| 65 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 26489 times.
|
26489 | if (entry == NULL) return(0); |
| 66 | 26489 | entry->key = key; | |
| 67 | 26489 | entry->data = data; | |
| 68 | 26489 | entry->next = ht[i]; | |
| 69 | 26489 | ht[i] = entry; | |
| 70 | 26489 | return(1); | |
| 71 | } | ||
| 72 | |||
| 73 | 208645 | int HTfind(HTtable *ht, const char *key) | |
| 74 | { | ||
| 75 | 208645 | unsigned int i = hash(key); | |
| 76 | struct HTentry *entry; | ||
| 77 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 208645 times.
|
208645 | if ( i >= HTMAXSIZE ) return(NOTFOUND); |
| 78 | 208645 | entry = ht[i]; | |
| 79 |
2/2✓ Branch 0 taken 277102 times.
✓ Branch 1 taken 34031 times.
|
311133 | while (entry != NULL) |
| 80 | { | ||
| 81 |
2/2✓ Branch 1 taken 174614 times.
✓ Branch 2 taken 102488 times.
|
277102 | if ( samestr(entry->key,key) ) return(entry->data); |
| 82 | 102488 | entry = entry->next; | |
| 83 | } | ||
| 84 | 34031 | return(NOTFOUND); | |
| 85 | } | ||
| 86 | |||
| 87 | 26490 | char *HTfindKey(HTtable *ht, const char *key) | |
| 88 | { | ||
| 89 | 26490 | unsigned int i = hash(key); | |
| 90 | struct HTentry *entry; | ||
| 91 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 26490 times.
|
26490 | if ( i >= HTMAXSIZE ) return(NULL); |
| 92 | 26490 | entry = ht[i]; | |
| 93 |
1/2✓ Branch 0 taken 57052 times.
✗ Branch 1 not taken.
|
57052 | while (entry != NULL) |
| 94 | { | ||
| 95 |
2/2✓ Branch 1 taken 26490 times.
✓ Branch 2 taken 30562 times.
|
57052 | if ( samestr(entry->key,key) ) return(entry->key); |
| 96 | 30562 | entry = entry->next; | |
| 97 | } | ||
| 98 | ✗ | return(NULL); | |
| 99 | } | ||
| 100 | |||
| 101 | 1044 | void HTfree(HTtable *ht) | |
| 102 | { | ||
| 103 | struct HTentry *entry, | ||
| 104 | *nextentry; | ||
| 105 | int i; | ||
| 106 |
2/2✓ Branch 0 taken 2086956 times.
✓ Branch 1 taken 1044 times.
|
2088000 | for (i=0; i<HTMAXSIZE; i++) |
| 107 | { | ||
| 108 | 2086956 | entry = ht[i]; | |
| 109 |
2/2✓ Branch 0 taken 26489 times.
✓ Branch 1 taken 2086956 times.
|
2113445 | while (entry != NULL) |
| 110 | { | ||
| 111 | 26489 | nextentry = entry->next; | |
| 112 | 26489 | free(entry); | |
| 113 | 26489 | entry = nextentry; | |
| 114 | } | ||
| 115 | } | ||
| 116 | 1044 | free(ht); | |
| 117 | 1044 | } | |
| 118 |