StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
primarykey
Id
12208232
data
AcceptedAnswerId
0
AnswerCount
0
ClosedDate
CommentCount
2
CommunityOwnedDate
CreationDate
2012-08-31T02:45:07.270
FavoriteCount
0
LastActivityDate
2012-08-31T04:46:48.553
LastEditDate
2012-08-31T04:46:48.553
LastEditorUserId
15168
OwnerUserId
15168
ParentId
12208030
PostTypeId
2
Score
0
ViewCount
0
LastEditorDisplayName
text
Body
<p>Some of your problems are in the <code>for</code> loop inside <code>htable_insert()</code>:</p> <ol> <li>You don't include <code>return 1;</code> after you insert a new entry in a previously NULL entry.</li> <li><p>Your wraparound code is modifying the wrong variable (<code>i</code>). I think it should be:</p> <pre><code>if (remainder >= h->capacity - 1) remainder = 0; else remainder++; </code></pre></li> <li><p>You have roughly the same problem in the search code, too.</p></li> </ol> <hr> <p>Suggestion:</p> <p>If you have a relatively complex data structure such as the hash table, it is worth creating (and debugging) a function of the form <code>void dump_htable(FILE *fp, const char *tag, const htable h)</code>. The function will print a diagnostic dump of the contents of the structure to the given file (often <code>stdout</code>, but sometimes <code>stderr</code> or a log file), prefixing the information with the <code>tag</code> so that you can tell which particular call to the dump function the output comes from. The function can also do basic validation — for example, it should ensure that the pointer it is given is not null (though it will print it out regardless), and should clearly only vet the contents of the structure if the pointer is not null. You can call this function immediately after the hash table is created, and again after each insert operation. This will allow you to check that the code is working as you expect.</p> <p>Keep the function in the code; make sure it is compiled routinely (so it doesn't get stale) and use it whenever you run into problems with a hash table.</p> <hr> <h2>SSCCE — Working Code</h2> <h3>htable.h</h3> <pre><code>#ifndef HTABLE_H_INCLUDED #define HTABLE_H_INCLUDED struct htablerec { char **key; int *frequencies; int num_keys; int capacity; }; typedef struct htablerec *htable; extern int htable_insert(htable h, char *str); extern htable htable_new(unsigned size); extern int htable_search(htable h, char *str); extern void htable_free(htable h); #endif /* HTABLE_H_INCLUDED */ </code></pre> <h3>htable.c</h3> <pre><code>#include "htable.h" #include <stdlib.h> #include <stdio.h> #include <string.h> static void *emalloc(size_t size) { void *space = malloc(size); if (space == 0) { fprintf(stderr, "Failed to allocate %zu bytes of memory\n", size); exit(EXIT_FAILURE); } return space; } static unsigned int htable_word_to_int(const char *word) { unsigned int result = 0; while (*word != '\0') { result = (*word++ + 31 * result); } return result; } htable htable_new(unsigned size) { htable h = emalloc(sizeof(*h)); size_t nbytes = size * sizeof(*h->key); h->key = emalloc(nbytes); memset(h->key, '\0', nbytes); h->frequencies = emalloc(size * sizeof(*h->frequencies)); h->capacity = size; h->num_keys = 0; return h; } void htable_free(htable h) { if (h != 0) { free(h->frequencies); free(h->key); free(h); } } int htable_insert(htable h, char *str) { int i; unsigned int index = htable_word_to_int(str); int remainder = index % h->capacity; for (i = 0; i < h->capacity; i++) { /* 1. No string at this position */ if (h->key[remainder] == NULL) { char *key = emalloc(strlen(str) + 1); strcpy(key, str); h->key[remainder] = key; h->frequencies[remainder] = 1; h->num_keys++; return 1; } /* 2. the same string is already there */ if (strcmp(str, h->key[remainder]) == 0) { h->frequencies[remainder]++; return h->frequencies[remainder]; } /* 3. Keep searching */ if (remainder >= h->capacity - 1) remainder = 0; else remainder++; } /* No match and no empty spaces left - hash table is full */ return 0; } int htable_search(htable h, char *str) { unsigned int index = htable_word_to_int(str); int remainder = index % h->capacity; for (int i = 0; i < h->capacity; i++) { if (h->key[remainder] == NULL) return -1; /* Definitively not present */ if (strcmp(str, h->key[remainder]) == 0) return remainder; /* Definitively present */ if (remainder >= h->capacity - 1) remainder = 0; else remainder++; } /* Table's full and key not found */ return -1; } </code></pre> <h3>test.htable.c</h3> <pre><code>#include "htable.h" #include <assert.h> #include <inttypes.h> #include <stdio.h> #include <stdlib.h> static void dump_htable(FILE *fp, const char *tag, const htable h) { fprintf(fp, "HASHTABLE: %s (0x%" PRIXPTR "\n", tag, (uintptr_t)h); if (h != 0) { fprintf(fp, "Capacity: %d; Number of keys: %d\n", h->capacity, h->num_keys); fprintf(fp, "Keys: 0x%" PRIXPTR "; Freq: 0x%" PRIXPTR "\n", (uintptr_t)h->key, (uintptr_t)h->frequencies); assert(h->key != 0 && h->frequencies != 0); if (h->num_keys > 0) { for (int i = 0; i < h->capacity; i++) { if (h->frequencies[i] != 0) { assert(h->key[i] != 0); fprintf(fp, "%3d: %2d %s\n", i, h->frequencies[i], h->key[i]); } } } } fflush(fp); } int main(void) { htable h = htable_new(113); char word[256]; char op; /*We must have a space before the %c*/ while(2 == scanf(" %c %255s", &op, word)) { if ('+' == op) { if (htable_insert(h, word) <= 0) printf("Error: failed to insert %s\n", word); else dump_htable(stdout, word, h); } else if ('?' == op) printf("%d %s\n", htable_search(h, word), word); else printf("Bogus: %c %s\n", op, word); } htable_free(h); return EXIT_SUCCESS; } </code></pre> <h3>Sample output</h3> <p>Last dump of hash table — for checking — and results.</p> <pre><code>HASHTABLE: unloaded (0x10F100910 Capacity: 113; Number of keys: 50 Keys: 0x10F100930; Freq: 0x10F100CC0 2: 1 wakes 7: 1 necrosis 8: 1 galleries 9: 1 Russia 10: 1 Georges 11: 1 outright 13: 1 brokers 16: 1 factoring 17: 1 keypad 18: 1 Latinizers 19: 1 rhythmically 20: 1 binders 27: 1 sociable 30: 1 Riemannian 33: 1 gentler 38: 1 segregation 39: 1 invalidity 43: 1 snowily 47: 1 cupful 48: 1 zebras 49: 1 Capet 50: 1 dominating 51: 1 unloaded 52: 1 unsound 53: 1 revocable 54: 1 tied 58: 1 combed 59: 1 leadings 60: 1 bran 61: 1 contented 62: 1 sequences 64: 1 replaced 69: 1 escorted 70: 1 infringing 71: 1 onslaught 72: 1 tiring 75: 1 screamer 80: 1 admire 84: 1 build 87: 1 Ottawa 92: 1 Malawi 93: 1 kidded 94: 1 files 95: 1 disconnects 96: 1 puzzles 97: 1 attendances 103: 1 diversification 104: 1 digressed 111: 1 swarthy 112: 1 thickness -1 insincere -1 constants -1 unordered -1 Toland -1 butterfly -1 suburban -1 overtone -1 Hauser -1 numbers -1 disadvantageous -1 saintly -1 Dutton -1 homomorphic -1 corporation -1 climaxes -1 dietitian -1 manifestly -1 greyest -1 challenge -1 tentacle -1 Bernice -1 bottle -1 involve -1 resisted -1 wholesale -1 trustworthiness -1 Poole -1 fourfold -1 relentlessly -1 fittingly -1 doctorates -1 cowlick -1 Missoula -1 curtsy -1 calmness -1 reallocate -1 bossed -1 scarce -1 catheters -1 regained -1 autographing -1 unobservable -1 apprise -1 lancer -1 chicken -1 crunches -1 scrambled -1 reared -1 pealing -1 violate 27 sociable 8 galleries 9 Russia 75 screamer 112 thickness 58 combed 69 escorted 53 revocable 104 digressed 92 Malawi 70 infringing 71 onslaught 94 files 93 kidded 52 unsound 54 tied 87 Ottawa 96 puzzles 84 build 7 necrosis 80 admire 47 cupful 13 brokers 38 segregation 49 Capet 10 Georges 60 bran 20 binders 48 zebras 61 contented 17 keypad 43 snowily 64 replaced 50 dominating 11 outright 18 Latinizers 39 invalidity 2 wakes 103 diversification 30 Riemannian 59 leadings 19 rhythmically 33 gentler 111 swarthy 95 disconnects 16 factoring 62 sequences 72 tiring 97 attendances 51 unloaded </code></pre>
Tags
Title
singulars
PostAcceptedAnswerId
1. This table or related slice is empty.
PostParentId
1. POHashtable searching, and command prompt weird error
  singulars
  PostTypePostTypeId
  PTQuestion
PostTypePostTypeId
1. PTAnswer
UserLastEditorUserId
1. USJonathan Leffler
UserOwnerUserId
1. USJonathan Leffler
plurals
PostLinksPostIdRelatedPostId
1. This table or related slice is empty.
PostLinksRelatedPostIdPostId
1. This table or related slice is empty.
PostsAcceptedAnswerId
1. POHashtable searching, and command prompt weird error
  singulars
  PostTypePostTypeId
  PTQuestion
PostsParentIdCreationDate
1. This table or related slice is empty.
VotesPostIdCreationDate
1. VO
  singulars
  PostPostId
  PO
  UserUserId
  This table or related slice is empty.
  VoteTypeVoteTypeId
  VTAcceptedByOriginator
CommentsPostId
1. COoh i think the code messed up a little bit when i put it in the file, the } and return 1 are both there, but thank you, i will have a look into that.
  singulars
  PostPostId
  PO
  UserUserId
  UScourtney
2. COOK - if what's in the question isn't exactly what you're compiling, that makes it extra hard for us to work out what's wrong. But if you fix the code, I'll probably remove this answer. The advice to create a `dump_htable()` function is still valid; it's what I'd create to debug your code, and it's what I do with my own data structures.
  singulars
  PostPostId
  PO
  UserUserId
  USJonathan Leffler

Querying!

Guidance

A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.