aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorzlg <zlg@zlg.space>2015-11-20 23:28:24 -0800
committerzlg <zlg@zlg.space>2015-11-20 23:28:24 -0800
commitfa70b1c7303cce993ed6a1785b72bf11b21cc6b6 (patch)
tree3cf3afd36aa76b2862cdc837a0e9f0ff433e7a2d
parentSolve Exercise 6-4: Highest Word Frequency (diff)
downloadknr-fa70b1c7303cce993ed6a1785b72bf11b21cc6b6.tar.gz
knr-fa70b1c7303cce993ed6a1785b72bf11b21cc6b6.tar.bz2
knr-fa70b1c7303cce993ed6a1785b72bf11b21cc6b6.tar.xz
knr-fa70b1c7303cce993ed6a1785b72bf11b21cc6b6.zip
Solve Exercise 6-5: undef()
We're getting close to more useful data structures! Wee!
Diffstat (limited to '')
-rw-r--r--ch6/6-05_undef.c107
1 files changed, 107 insertions, 0 deletions
diff --git a/ch6/6-05_undef.c b/ch6/6-05_undef.c
new file mode 100644
index 0000000..9ffd248
--- /dev/null
+++ b/ch6/6-05_undef.c
@@ -0,0 +1,107 @@
+#include <stdio.h>
+#include <string.h> // strdup, strcmp
+#include <stdlib.h> // malloc, free
+
+/* The C Programming Language: 2nd Edition
+ *
+ * Exercise 6-5: Write a function `undef` that will remove a name and
+ * definition from the table maintai\ed by lookup() and install().
+ *
+ * Notes: since undef() operates on the same data structure as lookup()
+ * and install(), I chose to depend on lookup() to find the correct node
+ * to remove. The tricky part is juggling two pointers and cleaning up
+ * the pointers to other nodes on the list.
+ */
+
+#define HASHSIZE 101
+
+struct nlist {
+ struct nlist *next;
+ char *name;
+ char *defn;
+};
+
+static struct nlist *hashtab[HASHSIZE];
+
+unsigned hash(char *);
+struct nlist *install(char *, char *);
+struct nlist *lookup(char *);
+int undef(char *);
+void print_table(struct nlist *);
+
+int main(int argc, char **argv) {
+ /* Install a few words */
+ install("foo", "1");
+ install("bar", "2");
+ install("baz", "4");
+ /* Make up scenarios for changing and removing values */
+ printf("We don't like baz, because his value is %s.\n", hashtab[hash("baz")]->defn);
+ printf("Let's ressign baz to 3.\n");
+ install("baz", "3");
+ printf("baz is now %s.\n", hashtab[hash("baz")]->defn);
+ printf("baz is a weird name. Let's try removing it.\n");
+ undef("baz") ? : printf("baz was removed from the table! Let's check to make sure it's gone...\n");
+ if (lookup("baz") == NULL) {
+ printf("Success! baz is gone!\n");
+ }
+ return 0;
+}
+
+/* form hash value for string s */
+unsigned hash(char *s) {
+ unsigned hashval;
+ for (hashval = 0; *s != '\0'; s++) {
+ hashval = *s + 31 * hashval;
+ }
+ return hashval % HASHSIZE;
+}
+
+/* Look for s in hashtab */
+struct nlist *lookup(char *s) {
+ struct nlist *np;
+ for (np = hashtab[hash(s)]; np != NULL; np = np->next) {
+ if (strcmp(s, np->name) == 0) {
+ return np;
+ }
+ }
+ return NULL;
+}
+
+/* put name and defn in hashtab */
+struct nlist *install(char *name, char *defn) {
+ struct nlist *np;
+ unsigned hashval;
+ if ((np = lookup(name)) == NULL) {
+ np = (struct nlist *) malloc(sizeof(*np));
+ if (np == NULL || (np->name = strdup(name)) == NULL) {
+ return NULL;
+ }
+ hashval = hash(name);
+ np->next = hashtab[hashval];
+ hashtab[hashval] = np;
+ } else {
+ free ((void *) np->defn);
+ }
+ if ((np->defn = strdup(defn)) == NULL) {
+ return NULL;
+ }
+ return np;
+}
+
+int undef(char *name) {
+ struct nlist *np, *np2;
+ if ((np = lookup(name)) == NULL) {
+ return 1;
+ }
+ for (np = np2 = hashtab[hash(name)]; np != NULL; np2 = np, np = np->next) {
+ if (np == np2) {
+ hashtab[hash(name)] = np->next;
+ } else {
+ np2->next = np->next;
+ }
+ free(np->name);
+ free(np->defn);
+ free(np);
+ return 0;
+ }
+}