1 /* mnemon - A memory training library
3 * Copyright © 2006,2011 Carl Worth
5 * This program is free software; you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License as published by
7 * the Free Software Foundation; either version 3, or (at your option)
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
15 * You should have received a copy of the GNU General Public License
16 * along with this program; if not, write to the Free Software Foundation,
17 * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA."
30 #include <sys/types.h>
39 #include <readline/readline.h>
40 #include <readline/history.h>
42 #define ASSERT_NOT_REACHED \
44 static const int NOT_REACHED = 0; \
45 assert (NOT_REACHED); \
55 fprintf (stderr, "Error: out of memory\n");
63 xrealloc (void *ptr, size_t size)
67 ret = realloc (ptr, size);
69 fprintf (stderr, "Error: out of memory\n");
77 xstrdup (const char *s)
83 fprintf (stderr, "Error: out of memory\n");
91 xasprintf (char **strp, const char *fmt, ...)
97 ret = vasprintf (strp, fmt, ap);
101 fprintf (stderr, "Error: out of memory\n");
107 item_init (item_t *item,
109 const char *challenge,
110 const char *response)
114 item->challenge = xmalloc (strlen (challenge) + 1 +
115 strlen (response) + 1);
116 item->response = item->challenge + strlen (challenge) + 1;
118 strcpy (item->challenge, challenge);
119 strcpy (item->response, response);
123 item_fini (item_t *item)
125 /* item->response shares allocation with item->challenge, so
126 * doesn't require a separate call to free */
127 free (item->challenge);
131 category_init (category_t *category,
134 category->name = xstrdup (name);
136 category->items_size = 0;
137 category->num_items = 0;
138 category->items = NULL;
139 category->order = CATEGORY_ORDER_RANDOM;
140 category->time_limit = 0.0;
141 category->bin_zero_head = 0;
142 category->challenge_type = CHALLENGE_TYPE_TEXT;
143 category->repeat = 0;
147 category_fini (category_t *category)
151 for (i = 0; i < category->num_items; i++)
152 item_fini (&category->items[i]);
154 free (category->items);
156 free (category->name);
160 category_grow (category_t *category)
162 if (category->items_size)
163 category->items_size *= 2;
165 category->items_size = 1;
167 category->items = xrealloc (category->items,
168 category->items_size * sizeof (item_t));
172 category_add_item (category_t *category,
174 const char *challenge,
175 const char *response)
179 if (category->num_items == category->items_size)
180 category_grow (category);
182 item = &category->items[category->num_items++];
184 item_init (item, score, challenge, response);
190 category_next_bin_zero_item (category_t *category)
192 int *i = &category->bin_zero_head;
194 for ( ; *i < category->num_items; *i = *i + 1)
195 if (category->items[*i].score == 0)
196 return &category->items[*i];
202 category_print (category_t *category,
208 fprintf (file, "order = %s\n\n",
209 category->order == CATEGORY_ORDER_RANDOM ? "random" : "sequential");
210 fprintf (file, "time = %f\n\n",
211 category->time_limit);
213 fprintf (file, "challenge = ");
214 switch (category->challenge_type) {
215 case CHALLENGE_TYPE_TEXT:
216 fprintf (file, "text");
218 case CHALLENGE_TYPE_IMAGE:
219 fprintf (file, "image");
221 case CHALLENGE_TYPE_AUDIO:
222 fprintf (file, "audio");
224 case CHALLENGE_TYPE_MIDI:
225 fprintf (file, "midi");
227 case CHALLENGE_TYPE_TEXT_TO_SPEECH:
228 fprintf (file, "text-to-speech");
231 fprintf (file, "\n\n");
233 fprintf (file, "repeat = %d\n\n", category->repeat);
235 for (i = 0; i < category->num_items; i++) {
236 item = &category->items[i];
238 fprintf (file, "\n");
239 fprintf (file, "%d\n%s\n%s\n",
247 bin_init (bin_t *bin,
258 bin_fini (bin_t *bin)
264 bin_grow (bin_t *bin)
267 bin->items_size *= 2;
271 bin->items = xrealloc (bin->items,
272 bin->items_size * sizeof (item_t*));
276 bin_add_item (bin_t *bin,
279 assert (item->score == bin->score);
281 if (bin->num_items == bin->items_size)
284 bin->items[bin->num_items++] = item;
288 bin_remove_item (bin_t *bin,
291 /* Replace the current item with the last item, (no need to shift
292 * any more than that since we don't care about the order of the
293 * items within a bin). */
296 bin->items[item_index] = bin->items[bin->num_items];
299 /* Find the index for an item within a bin.
301 * XXX: This is currently a linear search, so is a potential
302 * performance problem.
305 bin_item_index (bin_t *bin,
310 for (i = 0; i < bin->num_items; i++)
311 if (bin->items[i] == item)
318 mnemon_init (mnemon_t *mnemon)
322 home = getenv ("HOME");
326 xasprintf (&mnemon->dir_name, "%s/.mnemon", getenv ("HOME"));
328 mnemon->categories_size = 0;
329 mnemon->num_categories = 0;
330 mnemon->categories = NULL;
332 mnemon->bins_size = 0;
333 mnemon->num_bins = 0;
338 mnemon_fini (mnemon_t *mnemon)
342 for (i = 0; i < mnemon->num_bins; i++)
343 bin_fini (&mnemon->bins[i]);
346 for (i = 0; i < mnemon->num_categories; i++)
347 category_fini (&mnemon->categories[i]);
348 free (mnemon->categories);
350 free (mnemon->dir_name);
354 mnemon_categories_grow (mnemon_t *mnemon)
356 if (mnemon->categories_size)
357 mnemon->categories_size *= 2;
359 mnemon->categories_size = 1;
361 mnemon->categories = xrealloc (mnemon->categories,
362 mnemon->categories_size * sizeof (category_t));
365 /* Get a category by name if it exists */
367 mnemon_get_category_if_exists (mnemon_t *mnemon,
372 for (i = 0; i < mnemon->num_categories; i++)
373 if (strcmp (mnemon->categories[i].name, name) == 0)
374 return &mnemon->categories[i];
379 /* Get a category by name, creating new one if necessary. */
381 mnemon_get_category (mnemon_t *mnemon,
384 category_t *category;
386 category = mnemon_get_category_if_exists (mnemon, name);
390 mnemon_categories_grow (mnemon);
392 category = &mnemon->categories[mnemon->num_categories++];
394 category_init (category, name);
400 mnemon_bins_grow (mnemon_t *mnemon)
402 if (mnemon->bins_size)
403 mnemon->bins_size *= 2;
405 mnemon->bins_size = 1;
407 mnemon->bins = xrealloc (mnemon->bins,
408 mnemon->bins_size * sizeof (bin_t));
412 mnemon_get_bin (mnemon_t *mnemon,
418 for (i = 0; i < mnemon->num_bins; i++)
419 if (mnemon->bins[i].score == score)
420 return &mnemon->bins[i];
421 else if (mnemon->bins[i].score > score)
424 if (mnemon->num_bins == mnemon->bins_size)
425 mnemon_bins_grow (mnemon);
427 bin = &mnemon->bins[i];
429 /* Make room to insert new bin at its sorted location. */
430 if (i < mnemon->num_bins)
431 memmove (bin + 1, bin, (mnemon->num_bins - i) * sizeof (bin_t));
434 bin_init (bin, score);
440 mnemon_remove_bin (mnemon_t *mnemon, int bin_number)
442 bin_t *bin = mnemon_get_bin (mnemon, bin_number);
448 i = bin - mnemon->bins;
452 memmove (bin, bin + 1, (mnemon->num_bins - i) * sizeof (bin_t));
459 int len = strlen (s);
462 if (s[len - 1] == '\n')
467 trim_space (char *string)
472 while (*s && isspace (*s))
477 s = string + strlen (string) - 1;
478 while (s > string && isspace (*s)) {
487 mnemon_load_category (mnemon_t *mnemon,
491 char *line = NULL, *end;
492 size_t line_size = 0;
496 category_t *category;
500 path = xmalloc (strlen (mnemon->dir_name) + 1 + strlen (name) + 1);
501 sprintf (path, "%s/%s", mnemon->dir_name, name);
503 file = fopen (path, "r");
505 fprintf (stderr, "Error: Failed to open %s: %s\n",
506 path, strerror (errno));
510 fstat (fileno(file), &st);
511 if (! S_ISREG(st.st_mode)) {
512 fprintf (stderr, "Error: File %s is not a regular file.\n", path);
516 category = mnemon_get_category (mnemon, name);
518 #define READ_LINE do { \
519 bytes_read = getline (&line, &line_size, file); \
520 if (bytes_read == -1) \
528 char *name, *equal, *value;
530 /* Ignore blank lines */
535 /* An initial digit means we hit an item. Trigger the
536 * spaghetti machine. */
537 if ((*line >= '0' && *line <= '9') || *line == '-')
540 equal = strchr (line, '=');
542 fprintf (stderr, "Malformed option, (expected name=value): \"%s\" at %s:%d\n",
543 line, path, line_count);
551 name = trim_space (name);
552 value = trim_space (value);
554 if (strcmp (name, "order") == 0) {
555 if (strcmp (value, "sequential") == 0) {
556 category->order = CATEGORY_ORDER_SEQUENTIAL;
557 } else if (strcmp (value, "random") == 0) {
558 category->order = CATEGORY_ORDER_RANDOM;
560 fprintf (stderr, "Unknown value for \"order\" option \"%s\" at %s:%d\n",
561 value, path, line_count);
564 } else if (strcmp (name, "time") == 0) {
567 limit = strtod (value, &end);
568 while (isspace (*end))
571 category->time_limit = limit;
573 fprintf (stderr, "Failed to parse time value: %s at %s:%d\n",
574 value, path, line_count);
577 } else if (strcmp (name, "challenge") == 0) {
578 if (strcmp (value, "text") == 0) {
579 category->challenge_type = CHALLENGE_TYPE_TEXT;
580 } else if (strcmp (value, "image") == 0) {
581 category->challenge_type = CHALLENGE_TYPE_IMAGE;
582 } else if (strcmp (value, "audio") == 0) {
583 category->challenge_type = CHALLENGE_TYPE_AUDIO;
584 } else if (strcmp (value, "midi") == 0) {
585 category->challenge_type = CHALLENGE_TYPE_MIDI;
586 } else if (strcmp (value, "text-to-speech") == 0) {
587 category->challenge_type = CHALLENGE_TYPE_TEXT_TO_SPEECH;
589 fprintf (stderr, "Unknown value for \"challenge\" option \"%s\" at %s:%d\n",
590 value, path, line_count);
593 } else if (strcmp (name, "repeat") == 0) {
594 if (strcmp (value, "0") == 0)
595 category->repeat = 0;
597 category->repeat = 1;
599 fprintf (stderr, "Unknown option %s at %s:%d\n",
600 name, path, line_count);
608 char *challenge, *response;
610 /* Ignore blank lines */
615 /* Read bin number */
617 score = strtol (line, &end, 10);
619 fprintf (stderr, "Failed to parse bin number from \"%s\" at %s:%d\n",
620 line, path, line_count);
626 challenge = strdup (line);
632 category_add_item (category, score, challenge, response);
642 /* Resize category items to fit exactly. */
643 category->items_size = category->num_items;
644 category->items = xrealloc (category->items, category->items_size * sizeof (item_t));
646 /* Now that the category is completely loaded, with stable
647 * pointers to every item, we can add each item to its appropriate
649 for (i = 0; i < category->num_items; i++) {
650 item_t *item = &category->items[i];
651 bin_t *bin = mnemon_get_bin (mnemon, item->score);
653 bin_add_item (bin, item);
658 mnemon_load (mnemon_t *mnemon)
661 struct dirent *dirent;
663 dir = opendir (mnemon->dir_name);
665 fprintf (stderr, "Error: Failed to open directory %s: %s\n",
666 mnemon->dir_name, strerror (errno));
671 dirent = readdir (dir);
675 if (dirent->d_type == DT_REG) {
676 /* Ignore files matching *~, (yes, this shouldn't be
677 * hard-coded in such an ad-hoc way, but there you go. */
678 if (dirent->d_name[strlen(dirent->d_name)-1] != '~')
679 mnemon_load_category (mnemon, dirent->d_name);
687 mnemon_save (mnemon_t *mnemon)
690 char *filename, *lock_filename;
692 category_t *category;
694 for (i = 0; i < mnemon->num_categories; i++) {
695 category = &mnemon->categories[i];
697 xasprintf (&filename, "%s/%s",
698 mnemon->dir_name, category->name);
699 xasprintf (&lock_filename, "%s/.#%s",
700 mnemon->dir_name, category->name);
702 file = fopen (lock_filename, "w");
704 fprintf (stderr, "Error: Failed to open %s for writing: %s\n",
705 lock_filename, strerror (errno));
709 category_print (category, file);
711 fsync (fileno (file));
714 err = rename (lock_filename, filename);
716 fprintf (stderr, "Error: Failed to rename %s to %s: %s\n",
717 lock_filename, filename, strerror (errno));
722 free (lock_filename);
726 /* Return a uniformly-distributed pseudo-random integer within the
729 * 0 <= result < num_values
732 rand_within (int num_values)
734 return (int) (num_values * (rand() / (RAND_MAX + 1.0)));
737 /* Return an exponentially-distributed pseudo-random integer within
740 * 0 <= result < num_values
742 * The distribution is such that each successively larger value will
743 * occur with a probability of half of the previous value.
746 rand_within_exponential (int num_values)
749 static uint32_t mask = 0;
753 /* Optimize the constant case. */
763 while (mask > RAND_MAX)
770 if (ones == num_values)
779 mnemon_item_category (mnemon_t *mnemon,
782 category_t *category;
785 for (i = 0; i < mnemon->num_categories; i++) {
786 category = &mnemon->categories[i];
787 item_index = item - category->items;
788 if (item_index >= 0 && item_index < category->num_items)
796 mnemon_select_item (mnemon_t *mnemon,
799 category_t **category_ret,
802 int bin_index, item_index;
805 category_t *category;
807 bin_index = rand_within_exponential (mnemon->num_bins);
808 bin = &mnemon->bins[bin_index];
810 /* The most intuitive understanding of the introduced flag that
811 * it's tracking never-before-learned items as they are pulled
812 * from the bin with score 0. But that bin can become empty. So
813 * the refined rule is that we also set introduced whenever we
814 * pull from the lowest-indexed bin with a non-negative score. */
815 if (bin->score >=0 &&
816 (bin_index == 0 || mnemon->bins[bin_index-1].score < 0))
825 item_index = rand_within (bin->num_items);
827 item = bin->items[item_index];
828 category = mnemon_item_category (mnemon, item);
830 if (bin->score == 0) {
831 if (category->order == CATEGORY_ORDER_SEQUENTIAL) {
832 item = category_next_bin_zero_item (category);
834 item_index = bin_item_index (bin, item);
839 *item_index_ret = item_index;
840 *category_ret = category;
844 mnemon_score_item (mnemon_t *mnemon,
846 unsigned int item_index,
851 if (item_index >= bin->num_items)
854 item = bin->items[item_index];
855 bin_remove_item (bin, item_index);
857 /* If the bin is now empty, we must remove it. */
858 if (bin->num_items == 0)
860 mnemon_remove_bin (mnemon, bin->score);
866 /* We reserve an item score of 0 for an item that has
867 * never been asked. */
868 if (item->score == 0)
873 /* Penalize an incorrect response by forcing the score
875 if (item->score >= 0) {
876 /* We go to -2 to force a little extra reinforcement
877 * when re-learning an item, (otherwise, it will often
878 * get asked again immediately where it is easy to get
879 * a correct response without any learning). */
886 bin = mnemon_get_bin (mnemon, item->score);
888 bin_add_item (bin, item);