X-Git-Url: https://git.cworth.org/git?p=mnemon;a=blobdiff_plain;f=mnemon.c;h=ac31422cba7c4eb2f8757e9ed07425250d07ef78;hp=8f735f4d21750073ff5a40f58058f6f18f8b08f5;hb=5ae11041e3b0f7c5a04795c71fe3794d663eb195;hpb=33c6037c59e76bf85487253953aa9d09ea208532 diff --git a/mnemon.c b/mnemon.c index 8f735f4..ac31422 100644 --- a/mnemon.c +++ b/mnemon.c @@ -1,9 +1,10 @@ -/* - * Copyright © 2006 Carl Worth +/* mnemon - A memory training library + * + * Copyright © 2006,2011 Carl Worth * * This program is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by - * the Free Software Foundation; either version 2, or (at your option) + * the Free Software Foundation; either version 3, or (at your option) * any later version. * * This program is distributed in the hope that it will be useful, @@ -16,26 +17,75 @@ * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA." */ +#include "mnemon.h" + /* for asprintf */ #define _GNU_SOURCE #include #include #include +#include +#include #include +#include +#include +#include #include #include #include +#include + +#include +#include + +#define ASSERT_NOT_REACHED \ +do { \ + static const int NOT_REACHED = 0; \ + assert (NOT_REACHED); \ +} while (0) + +static void * +xmalloc (size_t size) +{ + void *ret; + + ret = malloc (size); + if (ret == NULL) { + fprintf (stderr, "Error: out of memory\n"); + exit (1); + } + + return ret; +} + +static void * +xrealloc (void *ptr, size_t size) +{ + void *ret; + + ret = realloc (ptr, size); + if (ret == NULL) { + fprintf (stderr, "Error: out of memory\n"); + exit (1); + } -typedef struct _mnemon { - int dummy; -} mnemon_t; + return ret; +} -typedef struct _ic { - int bin; - char *challenge; - char *response; -} ic_t; +static char * +xstrdup (const char *s) +{ + char *ret; + + ret = strdup (s); + if (ret == NULL) { + fprintf (stderr, "Error: out of memory\n"); + exit (1); + } + + return ret; +} static void xasprintf (char **strp, const char *fmt, ...) @@ -53,6 +103,340 @@ xasprintf (char **strp, const char *fmt, ...) } } +static void +item_init (item_t *item, + int score, + const char *challenge, + const char *response) +{ + item->score = score; + + item->challenge = xmalloc (strlen (challenge) + 1 + + strlen (response) + 1); + item->response = item->challenge + strlen (challenge) + 1; + + strcpy (item->challenge, challenge); + strcpy (item->response, response); +} + +static void +item_fini (item_t *item) +{ + /* item->response shares allocation with item->challenge, so + * doesn't require a separate call to free */ + free (item->challenge); +} + +static void +category_init (category_t *category, + const char *name) +{ + category->name = xstrdup (name); + + category->items_size = 0; + category->num_items = 0; + category->items = NULL; + category->order = CATEGORY_ORDER_RANDOM; + category->time_limit = 0.0; + category->bin_zero_head = 0; + category->challenge_type = xstrdup(""); + category->repeat = 0; +} + +static void +category_fini (category_t *category) +{ + unsigned int i; + + for (i = 0; i < category->num_items; i++) + item_fini (&category->items[i]); + + free (category->items); + + free (category->name); + + free (category->challenge_type); +} + +static void +category_grow (category_t *category) +{ + if (category->items_size) + category->items_size *= 2; + else + category->items_size = 1; + + category->items = xrealloc (category->items, + category->items_size * sizeof (item_t)); +} + +static item_t * +category_add_item (category_t *category, + int score, + const char *challenge, + const char *response) +{ + item_t *item; + + if (category->num_items == category->items_size) + category_grow (category); + + item = &category->items[category->num_items++]; + + item_init (item, score, challenge, response); + + return item; +} + +static item_t * +category_next_bin_zero_item (category_t *category) +{ + unsigned int *i = &category->bin_zero_head; + + for ( ; *i < category->num_items; *i = *i + 1) + if (category->items[*i].score == 0) + return &category->items[*i]; + + return NULL; +} + +static void +category_print (category_t *category, + FILE *file) +{ + unsigned int i; + item_t *item; + + fprintf (file, "order = %s\n\n", + category->order == CATEGORY_ORDER_RANDOM ? "random" : "sequential"); + fprintf (file, "time = %f\n\n", + category->time_limit); + + fprintf (file, "challenge = %s\n\n", category->challenge_type); + + fprintf (file, "repeat = %d\n\n", category->repeat); + + for (i = 0; i < category->num_items; i++) { + item = &category->items[i]; + if (i != 0) + fprintf (file, "\n"); + fprintf (file, "%d\n%s\n%s\n", + item->score, + item->challenge, + item->response); + } +} + +static void +bin_init (bin_t *bin, + int score) +{ + bin->score = score; + + bin->items_size = 0; + bin->num_items = 0; + bin->items = NULL; +} + +static void +bin_fini (bin_t *bin) +{ + free (bin->items); +} + +static void +bin_grow (bin_t *bin) +{ + if (bin->items_size) + bin->items_size *= 2; + else + bin->items_size = 1; + + bin->items = xrealloc (bin->items, + bin->items_size * sizeof (item_t*)); +} + +static void +bin_add_item (bin_t *bin, + item_t *item) +{ + assert (item->score == bin->score); + + if (bin->num_items == bin->items_size) + bin_grow (bin); + + bin->items[bin->num_items++] = item; +} + +static void +bin_remove_item (bin_t *bin, + int item_index) +{ + /* Replace the current item with the last item, (no need to shift + * any more than that since we don't care about the order of the + * items within a bin). */ + bin->num_items--; + if (bin->num_items) + bin->items[item_index] = bin->items[bin->num_items]; +} + +/* Find the index for an item within a bin. + * + * XXX: This is currently a linear search, so is a potential + * performance problem. + */ +static int +bin_item_index (bin_t *bin, + item_t *item) +{ + unsigned int i; + + for (i = 0; i < bin->num_items; i++) + if (bin->items[i] == item) + return i; + + assert (0); +} + +void +mnemon_init (mnemon_t *mnemon) +{ + char *home; + + home = getenv ("HOME"); + if (home == NULL) + home = ""; + + xasprintf (&mnemon->dir_name, "%s/.mnemon", getenv ("HOME")); + + mnemon->categories_size = 0; + mnemon->num_categories = 0; + mnemon->categories = NULL; + + mnemon->bins_size = 0; + mnemon->num_bins = 0; + mnemon->bins = NULL; +} + +void +mnemon_fini (mnemon_t *mnemon) +{ + int i; + + for (i = 0; i < mnemon->num_bins; i++) + bin_fini (&mnemon->bins[i]); + free (mnemon->bins); + + for (i = 0; i < mnemon->num_categories; i++) + category_fini (&mnemon->categories[i]); + free (mnemon->categories); + + free (mnemon->dir_name); +} + +static void +mnemon_categories_grow (mnemon_t *mnemon) +{ + if (mnemon->categories_size) + mnemon->categories_size *= 2; + else + mnemon->categories_size = 1; + + mnemon->categories = xrealloc (mnemon->categories, + mnemon->categories_size * sizeof (category_t)); +} + +/* Get a category by name if it exists */ +category_t * +mnemon_get_category_if_exists (mnemon_t *mnemon, + const char *name) +{ + int i; + + for (i = 0; i < mnemon->num_categories; i++) + if (strcmp (mnemon->categories[i].name, name) == 0) + return &mnemon->categories[i]; + + return NULL; +} + +/* Get a category by name, creating new one if necessary. */ +static category_t * +mnemon_get_category (mnemon_t *mnemon, + const char *name) +{ + category_t *category; + + category = mnemon_get_category_if_exists (mnemon, name); + if (category) + return category; + + mnemon_categories_grow (mnemon); + + category = &mnemon->categories[mnemon->num_categories++]; + + category_init (category, name); + + return category; +} + +static void +mnemon_bins_grow (mnemon_t *mnemon) +{ + if (mnemon->bins_size) + mnemon->bins_size *= 2; + else + mnemon->bins_size = 1; + + mnemon->bins = xrealloc (mnemon->bins, + mnemon->bins_size * sizeof (bin_t)); +} + +static bin_t * +mnemon_get_bin (mnemon_t *mnemon, + int score) +{ + int i; + bin_t *bin; + + for (i = 0; i < mnemon->num_bins; i++) + if (mnemon->bins[i].score == score) + return &mnemon->bins[i]; + else if (mnemon->bins[i].score > score) + break; + + if (mnemon->num_bins == mnemon->bins_size) + mnemon_bins_grow (mnemon); + + bin = &mnemon->bins[i]; + + /* Make room to insert new bin at its sorted location. */ + if (i < mnemon->num_bins) + memmove (bin + 1, bin, (mnemon->num_bins - i) * sizeof (bin_t)); + mnemon->num_bins++; + + bin_init (bin, score); + + return bin; +} + +void +mnemon_remove_bin (mnemon_t *mnemon, int bin_number) +{ + bin_t *bin = mnemon_get_bin (mnemon, bin_number); + int i; + + if (bin == NULL) + return; + + i = bin - mnemon->bins; + + bin_fini (bin); + + memmove (bin, bin + 1, (mnemon->num_bins - i) * sizeof (bin_t)); + mnemon->num_bins--; +} + static void chomp (char *s) { @@ -63,15 +447,42 @@ chomp (char *s) s[len - 1] = '\0'; } -static void -mnemon_load_from_file (mnemon_t *mnemon, - char *path) +static char * +trim_space (char *string) +{ + char *s; + + s = string; + while (*s && isspace (*s)) + s++; + + string = s; + + s = string + strlen (string) - 1; + while (s > string && isspace (*s)) { + *s = '\0'; + s--; + } + + return string; +} + +void +mnemon_load_category (mnemon_t *mnemon, + const char *name) { FILE *file; char *line = NULL, *end; size_t line_size = 0; ssize_t bytes_read; int line_count = 0; + char *path; + category_t *category; + int i; + struct stat st; + + path = xmalloc (strlen (mnemon->dir_name) + 1 + strlen (name) + 1); + sprintf (path, "%s/%s", mnemon->dir_name, name); file = fopen (path, "r"); if (file == NULL) { @@ -80,19 +491,102 @@ mnemon_load_from_file (mnemon_t *mnemon, exit (1); } + fstat (fileno(file), &st); + if (! S_ISREG(st.st_mode)) { + fprintf (stderr, "Error: File %s is not a regular file.\n", path); + exit (1); + } + + category = mnemon_get_category (mnemon, name); + +#define READ_LINE do { \ + bytes_read = getline (&line, &line_size, file); \ + if (bytes_read == -1) \ + goto END_OF_FILE; \ + line_count++; \ + chomp (line); \ +} while (0) + + /* Parse options */ while (1) { - ic_t ic; - - /* Read bin number (ignoring blank separator lines) */ - do { - bytes_read = getline (&line, &line_size, file); - if (bytes_read == -1) - goto END_OF_FILE; - line_count++; - chomp (line); - } while (*line == '\0'); - - ic.bin = strtol (line, &end, 10); + char *name, *equal, *value; + + /* Ignore blank lines */ + READ_LINE; + if (*line == '\0') + continue; + + /* An initial digit means we hit an item. Trigger the + * spaghetti machine. */ + if ((*line >= '0' && *line <= '9') || *line == '-') + goto PARSE_BIN; + + equal = strchr (line, '='); + if (equal == NULL) { + fprintf (stderr, "Malformed option, (expected name=value): \"%s\" at %s:%d\n", + line, path, line_count); + exit (1); + } + + value = equal + 1; + name = line; + *equal = '\0'; + + name = trim_space (name); + value = trim_space (value); + + if (strcmp (name, "order") == 0) { + if (strcmp (value, "sequential") == 0) { + category->order = CATEGORY_ORDER_SEQUENTIAL; + } else if (strcmp (value, "random") == 0) { + category->order = CATEGORY_ORDER_RANDOM; + } else { + fprintf (stderr, "Unknown value for \"order\" option \"%s\" at %s:%d\n", + value, path, line_count); + exit (1); + } + } else if (strcmp (name, "time") == 0) { + double limit; + char *end; + limit = strtod (value, &end); + while (isspace (*end)) + end++; + if (*end == '\0') { + category->time_limit = limit; + } else { + fprintf (stderr, "Failed to parse time value: %s at %s:%d\n", + value, path, line_count); + exit (1); + } + } else if (strcmp (name, "challenge") == 0) { + /* XXX: Need to switch to talloc here. */ + free (category->challenge_type); + category->challenge_type = xstrdup (value); + } else if (strcmp (name, "repeat") == 0) { + if (strcmp (value, "0") == 0) + category->repeat = 0; + else + category->repeat = 1; + } else { + fprintf (stderr, "Unknown option %s at %s:%d\n", + name, path, line_count); + exit (1); + } + } + + /* Parse items */ + while (1) { + int score; + char *challenge, *response; + + /* Ignore blank lines */ + READ_LINE; + if (*line == '\0') + continue; + + /* Read bin number */ + PARSE_BIN: + score = strtol (line, &end, 10); if (*end != '\0') { fprintf (stderr, "Failed to parse bin number from \"%s\" at %s:%d\n", line, path, line_count); @@ -100,44 +594,48 @@ mnemon_load_from_file (mnemon_t *mnemon, } /* Read challenge */ - bytes_read = getline (&line, &line_size, file); - if (bytes_read == -1) - break; - line_count++; - chomp (line); - ic.challenge = strdup (line); + READ_LINE; + challenge = strdup (line); /* Read response */ - bytes_read = getline (&line, &line_size, file); - if (bytes_read == -1) - break; - line_count++; - chomp (line); - ic.response = strdup (line); + READ_LINE; + response = line; - /* XXX: Add ic to mnemon here */ - printf ("%d: %s => %s\n", ic.bin, ic.challenge, ic.response); - free (ic.challenge); - free (ic.response); + category_add_item (category, score, challenge, response); + + free (challenge); } END_OF_FILE: free (line); fclose (file); + free (path); + + /* Resize category items to fit exactly. */ + category->items_size = category->num_items; + category->items = xrealloc (category->items, category->items_size * sizeof (item_t)); + + /* Now that the category is completely loaded, with stable + * pointers to every item, we can add each item to its appropriate + * bin. */ + for (i = 0; i < category->num_items; i++) { + item_t *item = &category->items[i]; + bin_t *bin = mnemon_get_bin (mnemon, item->score); + + bin_add_item (bin, item); + } } -static void -mnemon_load_from_directory_recursive (mnemon_t *mnemon, - char *path) +void +mnemon_load (mnemon_t *mnemon) { DIR *dir; struct dirent *dirent; - char *child_path; - dir = opendir (path); + dir = opendir (mnemon->dir_name); if (dir == NULL) { fprintf (stderr, "Error: Failed to open directory %s: %s\n", - path, strerror (errno)); + mnemon->dir_name, strerror (errno)); exit (1); } @@ -146,51 +644,218 @@ mnemon_load_from_directory_recursive (mnemon_t *mnemon, if (dirent == NULL) break; - xasprintf (&child_path, "%s/%s", path, dirent->d_name); - if (dirent->d_type == DT_DIR) { - if (strcmp (dirent->d_name, ".") && - strcmp (dirent->d_name, "..")) - { - mnemon_load_from_directory_recursive (mnemon, child_path); - } - } else if (dirent->d_type == DT_REG) { + if (dirent->d_type == DT_REG) { /* Ignore files matching *~, (yes, this shouldn't be * hard-coded in such an ad-hoc way, but there you go. */ - if (child_path[strlen(child_path)-1] != '~') - mnemon_load_from_file (mnemon, child_path); - } else { - fprintf (stderr, "Warning: Ignoring file %s\n", child_path); + if (dirent->d_name[strlen(dirent->d_name)-1] != '~') + mnemon_load_category (mnemon, dirent->d_name); } - - free (child_path); } closedir (dir); } -static void -mnemon_init (mnemon_t *mnemon) +void +mnemon_save (mnemon_t *mnemon) { - char *dot_mnemon; - char *home; + int i, err; + char *filename, *lock_filename; + FILE *file; + category_t *category; - home = getenv ("HOME"); - if (home == NULL) - home = ""; + for (i = 0; i < mnemon->num_categories; i++) { + category = &mnemon->categories[i]; + + xasprintf (&filename, "%s/%s", + mnemon->dir_name, category->name); + xasprintf (&lock_filename, "%s/.#%s", + mnemon->dir_name, category->name); + + file = fopen (lock_filename, "w"); + if (file == NULL) { + fprintf (stderr, "Error: Failed to open %s for writing: %s\n", + lock_filename, strerror (errno)); + continue; + } + + category_print (category, file); - xasprintf (&dot_mnemon, "%s/.mnemon", getenv ("HOME")); + fsync (fileno (file)); + fclose (file); - mnemon_load_from_directory_recursive (mnemon, dot_mnemon); + err = rename (lock_filename, filename); + if (err < 0) { + fprintf (stderr, "Error: Failed to rename %s to %s: %s\n", + lock_filename, filename, strerror (errno)); + continue; + } - free (dot_mnemon); + free (filename); + free (lock_filename); + } } -int -main (int argc, char *argv[]) +/* Return a uniformly-distributed pseudo-random integer within the + * range: + * + * 0 <= result < num_values + */ +static int +rand_within (int num_values) { - mnemon_t mnemon; + return (int) (num_values * (rand() / (RAND_MAX + 1.0))); +} + +/* Return an exponentially-distributed pseudo-random integer within + * the range: + * + * 0 <= result < num_values + * + * The distribution is such that each successively larger value will + * occur with a probability of half of the previous value. + */ +static int +rand_within_exponential (int num_values) +{ + static int r; + static uint32_t mask = 0; + int ones; + int bit; + + /* Optimize the constant case. */ + if (num_values == 1) + return 0; + + ones = 0; + + do { + if (mask == 0) { + r = rand (); + mask = 1 << 31; + while (mask > RAND_MAX) + mask >>= 1; + } + bit = r & mask; + mask >>= 1; + if (bit) { + ones++; + if (ones == num_values) + ones = 0; + } + } while (bit); + + return ones; +} + +category_t * +mnemon_item_category (mnemon_t *mnemon, + item_t *item) +{ + category_t *category; + int i, item_index; + + for (i = 0; i < mnemon->num_categories; i++) { + category = &mnemon->categories[i]; + item_index = item - category->items; + if (item_index >= 0 && item_index < category->num_items) + return category; + } + + assert (0); +} + +void +mnemon_select_item (mnemon_t *mnemon, + bin_t **bin_ret, + int *item_index_ret, + category_t **category_ret, + int *introduced_ret) +{ + int bin_index, item_index; + bin_t *bin; + item_t *item; + category_t *category; + + bin_index = rand_within_exponential (mnemon->num_bins); + bin = &mnemon->bins[bin_index]; + + /* The most intuitive understanding of the introduced flag that + * it's tracking never-before-learned items as they are pulled + * from the bin with score 0. But that bin can become empty. So + * the refined rule is that we also set introduced whenever we + * pull from the lowest-indexed bin with a non-negative score. */ + if (bin->score >=0 && + (bin_index == 0 || mnemon->bins[bin_index-1].score < 0)) + { + *introduced_ret = 1; + } + else + { + *introduced_ret = 0; + } + + item_index = rand_within (bin->num_items); + + item = bin->items[item_index]; + category = mnemon_item_category (mnemon, item); + + if (bin->score == 0) { + if (category->order == CATEGORY_ORDER_SEQUENTIAL) { + item = category_next_bin_zero_item (category); + if (item) + item_index = bin_item_index (bin, item); + } + } + + *bin_ret = bin; + *item_index_ret = item_index; + *category_ret = category; +} + +void +mnemon_score_item (mnemon_t *mnemon, + bin_t *bin, + unsigned int item_index, + bool_t correct) +{ + item_t *item; + + if (item_index >= bin->num_items) + return; + + item = bin->items[item_index]; + bin_remove_item (bin, item_index); + + /* If the bin is now empty, we must remove it. */ + if (bin->num_items == 0) + { + mnemon_remove_bin (mnemon, bin->score); + } + + if (correct) + { + item->score++; + /* We reserve an item score of 0 for an item that has + * never been asked. */ + if (item->score == 0) + item->score = 1; + } + else + { + /* Penalize an incorrect response by forcing the score + * negative. */ + if (item->score >= 0) { + /* We go to -2 to force a little extra reinforcement + * when re-learning an item, (otherwise, it will often + * get asked again immediately where it is easy to get + * a correct response without any learning). */ + item->score = -2; + } else { + item->score--; + } + } - mnemon_init (&mnemon); + bin = mnemon_get_bin (mnemon, item->score); - return 0; + bin_add_item (bin, item); }