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 | 19756 | int samestr(const char *s1, const char *s2) | |
| 25 | { | ||
| 26 | int i; | ||
| 27 |
8/10✓ Branch 0 taken 9484 times.
✓ Branch 1 taken 129846 times.
✓ Branch 2 taken 9484 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 9489 times.
✓ Branch 5 taken 129841 times.
✓ Branch 6 taken 9489 times.
✗ Branch 7 not taken.
✓ Branch 8 taken 139194 times.
✓ Branch 9 taken 136 times.
|
139330 | for (i=0; UCHAR(s1[i]) == UCHAR(s2[i]); i++) |
| 28 |
3/4✓ Branch 0 taken 19620 times.
✓ Branch 1 taken 119574 times.
✓ Branch 2 taken 19620 times.
✗ Branch 3 not taken.
|
139194 | if (!s1[i+1] && !s2[i+1]) return(1); |
| 29 | 136 | return(0); | |
| 30 | } /* End of samestr */ | ||
| 31 | |||
| 32 | /* Use Fletcher's checksum to compute 2-byte hash of string */ | ||
| 33 | 22586 | unsigned int hash(const char *str) | |
| 34 | { | ||
| 35 | 22586 | unsigned int sum1= 0, check1; | |
| 36 | 22586 | unsigned long sum2= 0L; | |
| 37 |
2/2✓ Branch 0 taken 155602 times.
✓ Branch 1 taken 22586 times.
|
178188 | while( '\0' != *str ) |
| 38 | { | ||
| 39 |
3/4✓ Branch 0 taken 11580 times.
✓ Branch 1 taken 144022 times.
✓ Branch 2 taken 11580 times.
✗ Branch 3 not taken.
|
155602 | sum1 += UCHAR(*str); |
| 40 | 155602 | str++; | |
| 41 |
2/2✓ Branch 0 taken 29181 times.
✓ Branch 1 taken 126421 times.
|
155602 | if ( 255 <= sum1 ) sum1 -= 255; |
| 42 | 155602 | sum2 += sum1; | |
| 43 | } | ||
| 44 | 22586 | check1= sum2; | |
| 45 | 22586 | check1 %= 255; | |
| 46 | 22586 | check1= 255 - (sum1+check1) % 255; | |
| 47 | 22586 | sum1= 255 - (sum1+check1) % 255; | |
| 48 | 22586 | return( ( ( check1 << 8 ) | sum1 ) % HTMAXSIZE); | |
| 49 | } | ||
| 50 | |||
| 51 | 1098 | HTtable *HTcreate() | |
| 52 | { | ||
| 53 | int i; | ||
| 54 | 1098 | HTtable *ht = (HTtable *) calloc(HTMAXSIZE, sizeof(HTtable)); | |
| 55 |
3/4✓ Branch 0 taken 1098 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 2194902 times.
✓ Branch 3 taken 1098 times.
|
2196000 | if (ht != NULL) for (i=0; i<HTMAXSIZE; i++) ht[i] = NULL; |
| 56 | 1098 | return(ht); | |
| 57 | } | ||
| 58 | |||
| 59 | 1250 | int HTinsert(HTtable *ht, char *key, int data) | |
| 60 | { | ||
| 61 | 1250 | unsigned int i = hash(key); | |
| 62 | struct HTentry *entry; | ||
| 63 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 1250 times.
|
1250 | if ( i >= HTMAXSIZE ) return(0); |
| 64 | 1250 | entry = (struct HTentry *) malloc(sizeof(struct HTentry)); | |
| 65 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 1250 times.
|
1250 | if (entry == NULL) return(0); |
| 66 | 1250 | entry->key = key; | |
| 67 | 1250 | entry->data = data; | |
| 68 | 1250 | entry->next = ht[i]; | |
| 69 | 1250 | ht[i] = entry; | |
| 70 | 1250 | return(1); | |
| 71 | } | ||
| 72 | |||
| 73 | 20085 | int HTfind(HTtable *ht, const char *key) | |
| 74 | { | ||
| 75 | 20085 | unsigned int i = hash(key); | |
| 76 | struct HTentry *entry; | ||
| 77 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 20085 times.
|
20085 | if ( i >= HTMAXSIZE ) return(NOTFOUND); |
| 78 | 20085 | entry = ht[i]; | |
| 79 |
2/2✓ Branch 0 taken 18490 times.
✓ Branch 1 taken 1716 times.
|
20206 | while (entry != NULL) |
| 80 | { | ||
| 81 |
2/2✓ Branch 1 taken 18369 times.
✓ Branch 2 taken 121 times.
|
18490 | if ( samestr(entry->key,key) ) return(entry->data); |
| 82 | 121 | entry = entry->next; | |
| 83 | } | ||
| 84 | 1716 | return(NOTFOUND); | |
| 85 | } | ||
| 86 | |||
| 87 | 1251 | char *HTfindKey(HTtable *ht, const char *key) | |
| 88 | { | ||
| 89 | 1251 | unsigned int i = hash(key); | |
| 90 | struct HTentry *entry; | ||
| 91 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 1251 times.
|
1251 | if ( i >= HTMAXSIZE ) return(NULL); |
| 92 | 1251 | entry = ht[i]; | |
| 93 |
1/2✓ Branch 0 taken 1266 times.
✗ Branch 1 not taken.
|
1266 | while (entry != NULL) |
| 94 | { | ||
| 95 |
2/2✓ Branch 1 taken 1251 times.
✓ Branch 2 taken 15 times.
|
1266 | if ( samestr(entry->key,key) ) return(entry->key); |
| 96 | 15 | entry = entry->next; | |
| 97 | } | ||
| 98 | ✗ | return(NULL); | |
| 99 | } | ||
| 100 | |||
| 101 | 1098 | void HTfree(HTtable *ht) | |
| 102 | { | ||
| 103 | struct HTentry *entry, | ||
| 104 | *nextentry; | ||
| 105 | int i; | ||
| 106 |
2/2✓ Branch 0 taken 2194902 times.
✓ Branch 1 taken 1098 times.
|
2196000 | for (i=0; i<HTMAXSIZE; i++) |
| 107 | { | ||
| 108 | 2194902 | entry = ht[i]; | |
| 109 |
2/2✓ Branch 0 taken 1250 times.
✓ Branch 1 taken 2194902 times.
|
2196152 | while (entry != NULL) |
| 110 | { | ||
| 111 | 1250 | nextentry = entry->next; | |
| 112 | 1250 | free(entry); | |
| 113 | 1250 | entry = nextentry; | |
| 114 | } | ||
| 115 | } | ||
| 116 | 1098 | free(ht); | |
| 117 | 1098 | } | |
| 118 |