From fa70b1c7303cce993ed6a1785b72bf11b21cc6b6 Mon Sep 17 00:00:00 2001 From: zlg Date: Fri, 20 Nov 2015 23:28:24 -0800 Subject: Solve Exercise 6-5: undef() We're getting close to more useful data structures! Wee! --- ch6/6-05_undef.c | 107 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 107 insertions(+) create mode 100644 ch6/6-05_undef.c 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 +#include // strdup, strcmp +#include // 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; + } +} -- cgit v1.2.3-54-g00ecf /span> 2018-11-21Prepare for distributionzlg2-1/+3 2018-10-22vgstash: let backlog filter ignore unbeatable gameszlg1-1/+1 2018-10-18Bump to 0.3beta2 for PyPIzlg1-3/+3 2018-10-18vgstash.DB.__init__: fix error output formattingzlg1-1/+1 2018-10-18README: fix inline <code> formattingzlg1-3/+4 2018-10-18cli: show msg if game to be deleted is not in DBzlg2-2/+12 2018-10-18README: expand on usage, cover shell quotingzlg1-7/+99 2018-10-18cli: Tell the user when a game lacks noteszlg2-3/+15 2018-10-18Catch when an invalid list filter is passedzlg4-3/+24 2018-10-12cli: Add zero-game import/export messageszlg2-11/+18 2018-10-10Bump to 0.3beta1 for PyPIzlg1-1/+1 2018-10-10Move tests and data to dedicated directoryzlg7-10/+26 2018-10-10cli: Add "export" commandzlg2-5/+54 2018-10-10cli: Add "import" commandzlg5-1/+76 2018-10-09Bump to 0.3alpha6 for PyPIzlg1-1/+1 2018-10-09cli: Add "notes" commandzlg2-4/+74 2018-10-09update_game: ensure notes are also savedzlg1-2/+2 2018-10-09cli: add 'update' commandzlg3-20/+92 2018-10-06cli: Add "delete" commandzlg2-0/+19 2018-10-06Remove ID field from DBzlg3-38/+46 2018-10-06cli: change "Status" heading to "Progress"zlg2-36/+40 2018-09-29Bump to 0.3alpha5 for PyPIzlg1-1/+1 2018-09-29cli: Add pretty printing to 'list' commandzlg3-17/+107 2018-09-08setup.py: Bump to alpha4 for PyPIzlg1-1/+1 2018-09-08cli: add '--raw' option to list commandzlg2-9/+45 2018-09-08Add remaining filters to vgstash packagezlg1-2/+11 2018-09-04Update LICENSE to match setup.pyzlg1-80/+67 2018-09-03Branch off from master with pytest, tox, clickzlg16-778/+779 2018-03-18Flesh out filter types and ownership statuszlg3-82/+144 2018-03-18README.mdown: break line correctlyzlg1-1/+1 2018-03-18add 'playlog' list filterzlg2-2/+9 2018-03-13Update helpers a bitzlg1-2/+9 2018-03-13Make VGSTASH_DB_LOCATION point to a filezlg2-21/+20 2016-11-18Remove settings from helpers.shZe Libertine Gamer1-5/+0 2016-11-15Correct phrasing in README.Ze Libertine Gamer1-4/+4 2016-11-13DerpZe Libertine Gamer1-0/+1 2016-11-03Improve error handling in shell scriptsZe Libertine Gamer4-3/+23 2016-10-24Correct run_again, add recursionZe Libertine Gamer1-0/+4 2016-10-21Add quotes to correct behavior for arglistZe Libertine Gamer1-1/+1 2016-10-14updater.sh: add recursion, error handlingZe Libertine Gamer1-43/+101 2016-10-14Correct pipe-handling behaviorZe Libertine Gamer1-1/+9 2016-10-12Clarify a method to move between platformsZe Libertine Gamer1-2/+5