git.cworth.org Git - mnemon/blob - mnemon.c

   1 /* mnemon - A memory training library
   2  *
   3  * Copyright © 2006,2011 Carl Worth
   4  *
   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)
   8  * any later version.
   9  *
  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.
  14  *
  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."
  18  */
  19
  20 #include "mnemon.h"
  21
  22 /* for asprintf */
  23 #define _GNU_SOURCE
  24 #include <stdio.h>
  25 #include <stdlib.h>
  26 #include <stdarg.h>
  27 #include <stdint.h>
  28 #include <math.h>
  29
  30 #include <sys/types.h>
  31 #include <sys/time.h>
  32 #include <sys/stat.h>
  33 #include <unistd.h>
  34 #include <dirent.h>
  35 #include <errno.h>
  36 #include <string.h>
  37 #include <assert.h>
  38
  39 #include <readline/readline.h>
  40 #include <readline/history.h>
  41
  42 #define ASSERT_NOT_REACHED              \
  43 do {                                    \
  44     static const int NOT_REACHED = 0;   \
  45     assert (NOT_REACHED);               \
  46 } while (0)
  47
  48 static void *
  49 xmalloc (size_t size)
  50 {
  51     void *ret;
  52
  53     ret = malloc (size);
  54     if (ret == NULL) {
  55         fprintf (stderr, "Error: out of memory\n");
  56         exit (1);
  57     }
  58
  59     return ret;
  60 }
  61
  62 static void *
  63 xrealloc (void *ptr, size_t size)
  64 {
  65     void *ret;
  66
  67     ret = realloc (ptr, size);
  68     if (ret == NULL) {
  69         fprintf (stderr, "Error: out of memory\n");
  70         exit (1);
  71     }
  72
  73     return ret;
  74 }
  75
  76 static char *
  77 xstrdup (const char *s)
  78 {
  79     char *ret;
  80
  81     ret = strdup (s);
  82     if (ret == NULL) {
  83         fprintf (stderr, "Error: out of memory\n");
  84         exit (1);
  85     }
  86
  87     return ret;
  88 }
  89
  90 static void
  91 xasprintf (char **strp, const char *fmt, ...)
  92 {
  93     va_list ap;
  94     int ret;
  95
  96     va_start (ap, fmt);
  97     ret = vasprintf (strp, fmt, ap);
  98     va_end (ap);
  99
 100     if (ret < 0) {
 101         fprintf (stderr, "Error: out of memory\n");
 102         exit (1);
 103     }
 104 }
 105
 106 static void
 107 item_init (item_t       *item,
 108            int           score,
 109            const char   *challenge,
 110            const char   *response)
 111 {
 112     item->score = score;
 113
 114     item->challenge = xmalloc (strlen (challenge) + 1 +
 115                                strlen (response) + 1);
 116     item->response = item->challenge + strlen (challenge) + 1;
 117
 118     strcpy (item->challenge, challenge);
 119     strcpy (item->response, response);
 120 }
 121
 122 static void
 123 item_fini (item_t *item)
 124 {
 125     /* item->response shares allocation with item->challenge, so
 126      * doesn't require a separate call to free */
 127     free (item->challenge);
 128 }
 129
 130 static void
 131 category_init (category_t *category,
 132                const char *name)
 133 {
 134     category->name = xstrdup (name);
 135
 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 = xstrdup("");
 143     category->repeat = 0;
 144 }
 145
 146 static void
 147 category_fini (category_t *category)
 148 {
 149     unsigned int i;
 150
 151     for (i = 0; i < category->num_items; i++)
 152         item_fini (&category->items[i]);
 153
 154     free (category->items);
 155
 156     free (category->name);
 157
 158     free (category->challenge_type);
 159 }
 160
 161 static void
 162 category_grow (category_t *category)
 163 {
 164     if (category->items_size)
 165         category->items_size *= 2;
 166     else
 167         category->items_size = 1;
 168
 169     category->items = xrealloc (category->items,
 170                                 category->items_size * sizeof (item_t));
 171 }
 172
 173 static item_t *
 174 category_add_item (category_t   *category,
 175                    int           score,
 176                    const char   *challenge,
 177                    const char   *response)
 178 {
 179     item_t *item;
 180
 181     if (category->num_items == category->items_size)
 182         category_grow (category);
 183
 184     item = &category->items[category->num_items++];
 185
 186     item_init (item, score, challenge, response);
 187
 188     return item;
 189 }
 190
 191 static item_t *
 192 category_next_bin_zero_item (category_t *category)
 193 {
 194     unsigned int *i = &category->bin_zero_head;
 195
 196     for ( ; *i < category->num_items; *i = *i + 1)
 197         if (category->items[*i].score == 0)
 198             return &category->items[*i];
 199
 200     return NULL;
 201 }
 202
 203 static void
 204 category_print (category_t      *category,
 205                 FILE            *file)
 206 {
 207     unsigned int i;
 208     item_t *item;
 209
 210     fprintf (file, "order = %s\n\n",
 211             category->order == CATEGORY_ORDER_RANDOM ? "random" : "sequential");
 212     fprintf (file, "time = %f\n\n",
 213              category->time_limit);
 214
 215     fprintf (file, "challenge = %s\n\n", category->challenge_type);
 216
 217     fprintf (file, "repeat = %d\n\n", category->repeat);
 218
 219     for (i = 0; i < category->num_items; i++) {
 220         item = &category->items[i];
 221         if (i != 0)
 222             fprintf (file, "\n");
 223         fprintf (file, "%d\n%s\n%s\n",
 224                  item->score,
 225                  item->challenge,
 226                  item->response);
 227     }
 228 }
 229
 230 static void
 231 bin_init (bin_t *bin,
 232           int    score)
 233 {
 234     bin->score = score;
 235
 236     bin->items_size = 0;
 237     bin->num_items = 0;
 238     bin->items = NULL;
 239 }
 240
 241 static void
 242 bin_fini (bin_t *bin)
 243 {
 244     free (bin->items);
 245 }
 246
 247 static void
 248 bin_grow (bin_t *bin)
 249 {
 250     if (bin->items_size)
 251         bin->items_size *= 2;
 252     else
 253         bin->items_size = 1;
 254
 255     bin->items = xrealloc (bin->items,
 256                            bin->items_size * sizeof (item_t*));
 257 }
 258
 259 static void
 260 bin_add_item (bin_t     *bin,
 261               item_t    *item)
 262 {
 263     assert (item->score == bin->score);
 264
 265     if (bin->num_items == bin->items_size)
 266         bin_grow (bin);
 267
 268     bin->items[bin->num_items++] = item;
 269 }
 270
 271 static void
 272 bin_remove_item (bin_t  *bin,
 273                  int     item_index)
 274 {
 275     /* Replace the current item with the last item, (no need to shift
 276      * any more than that since we don't care about the order of the
 277      * items within a bin). */
 278     bin->num_items--;
 279     if (bin->num_items)
 280         bin->items[item_index] = bin->items[bin->num_items];
 281 }
 282
 283 /* Find the index for an item within a bin.
 284  *
 285  * XXX: This is currently a linear search, so is a potential
 286  * performance problem.
 287  */
 288 static int
 289 bin_item_index (bin_t   *bin,
 290                 item_t  *item)
 291 {
 292     unsigned int i;
 293
 294     for (i = 0; i < bin->num_items; i++)
 295         if (bin->items[i] == item)
 296             return i;
 297
 298     assert (0);
 299 }
 300
 301 void
 302 mnemon_init (mnemon_t *mnemon)
 303 {
 304     char *home;
 305
 306     home = getenv ("HOME");
 307     if (home == NULL)
 308         home = "";
 309
 310     xasprintf (&mnemon->dir_name, "%s/.mnemon", getenv ("HOME"));
 311
 312     mnemon->categories_size = 0;
 313     mnemon->num_categories = 0;
 314     mnemon->categories = NULL;
 315
 316     mnemon->bins_size = 0;
 317     mnemon->num_bins = 0;
 318     mnemon->bins = NULL;
 319 }
 320
 321 void
 322 mnemon_fini (mnemon_t *mnemon)
 323 {
 324     unsigned int i;
 325
 326     for (i = 0; i < mnemon->num_bins; i++)
 327         bin_fini (&mnemon->bins[i]);
 328     free (mnemon->bins);
 329
 330     for (i = 0; i < mnemon->num_categories; i++)
 331         category_fini (&mnemon->categories[i]);
 332     free (mnemon->categories);
 333
 334     free (mnemon->dir_name);
 335 }
 336
 337 static void
 338 mnemon_categories_grow (mnemon_t *mnemon)
 339 {
 340     if (mnemon->categories_size)
 341         mnemon->categories_size *= 2;
 342     else
 343         mnemon->categories_size = 1;
 344
 345     mnemon->categories = xrealloc (mnemon->categories,
 346                                    mnemon->categories_size * sizeof (category_t));
 347 }
 348
 349 /* Get a category by name if it exists */
 350 category_t *
 351 mnemon_get_category_if_exists (mnemon_t     *mnemon,
 352                                const char   *name)
 353 {
 354     unsigned int i;
 355
 356     for (i = 0; i < mnemon->num_categories; i++)
 357         if (strcmp (mnemon->categories[i].name, name) == 0)
 358             return &mnemon->categories[i];
 359
 360     return NULL;
 361 }
 362
 363 /* Get a category by name, creating new one if necessary. */
 364 static category_t *
 365 mnemon_get_category (mnemon_t   *mnemon,
 366                      const char *name)
 367 {
 368     category_t *category;
 369
 370     category = mnemon_get_category_if_exists (mnemon, name);
 371     if (category)
 372         return category;
 373
 374     mnemon_categories_grow (mnemon);
 375
 376     category = &mnemon->categories[mnemon->num_categories++];
 377
 378     category_init (category, name);
 379
 380     return category;
 381 }
 382
 383 static void
 384 mnemon_bins_grow (mnemon_t *mnemon)
 385 {
 386     if (mnemon->bins_size)
 387         mnemon->bins_size *= 2;
 388     else
 389         mnemon->bins_size = 1;
 390
 391     mnemon->bins = xrealloc (mnemon->bins,
 392                              mnemon->bins_size * sizeof (bin_t));
 393 }
 394
 395 static bin_t *
 396 mnemon_get_bin (mnemon_t        *mnemon,
 397                 int              score)
 398 {
 399     unsigned int i;
 400     bin_t *bin;
 401
 402     for (i = 0; i < mnemon->num_bins; i++)
 403         if (mnemon->bins[i].score == score)
 404             return &mnemon->bins[i];
 405         else if (mnemon->bins[i].score > score)
 406             break;
 407
 408     if (mnemon->num_bins == mnemon->bins_size)
 409         mnemon_bins_grow (mnemon);
 410
 411     bin = &mnemon->bins[i];
 412
 413     /* Make room to insert new bin at its sorted location. */
 414     if (i < mnemon->num_bins)
 415         memmove (bin + 1, bin, (mnemon->num_bins - i) * sizeof (bin_t));
 416     mnemon->num_bins++;
 417
 418     bin_init (bin, score);
 419
 420     return bin;
 421 }
 422
 423 void
 424 mnemon_remove_bin (mnemon_t *mnemon, int bin_number)
 425 {
 426     bin_t *bin = mnemon_get_bin (mnemon, bin_number);
 427     int i;
 428
 429     if (bin == NULL)
 430         return;
 431
 432     i = bin - mnemon->bins;
 433
 434     bin_fini (bin);
 435
 436     memmove (bin, bin + 1, (mnemon->num_bins - i) * sizeof (bin_t));
 437     mnemon->num_bins--;
 438 }
 439
 440 static void
 441 chomp (char *s)
 442 {
 443     int len = strlen (s);
 444     if (len == 0)
 445         return;
 446     if (s[len - 1] == '\n')
 447         s[len - 1] = '\0';
 448 }
 449
 450 static char *
 451 trim_space (char *string)
 452 {
 453     char *s;
 454
 455     s = string;
 456     while (*s && isspace (*s))
 457         s++;
 458
 459     string = s;
 460
 461     s = string + strlen (string) - 1;
 462     while (s > string && isspace (*s)) {
 463         *s = '\0';
 464         s--;
 465     }
 466
 467     return string;
 468 }
 469
 470 void
 471 mnemon_load_category (mnemon_t          *mnemon,
 472                       const char        *name)
 473 {
 474     FILE *file;
 475     char *line = NULL, *end;
 476     size_t line_size = 0;
 477     ssize_t bytes_read;
 478     int line_count = 0;
 479     char *path;
 480     category_t *category;
 481     unsigned int i;
 482     struct stat st;
 483
 484     path = xmalloc (strlen (mnemon->dir_name) + 1 + strlen (name) + 1);
 485     sprintf (path, "%s/%s", mnemon->dir_name, name);
 486
 487     file = fopen (path, "r");
 488     if (file == NULL) {
 489         fprintf (stderr, "Error: Failed to open %s: %s\n",
 490                  path, strerror (errno));
 491         exit (1);
 492     }
 493
 494     fstat (fileno(file), &st);
 495     if (! S_ISREG(st.st_mode)) {
 496         fprintf (stderr, "Error: File %s is not a regular file.\n", path);
 497         exit (1);
 498     }
 499
 500     category = mnemon_get_category (mnemon, name);
 501
 502 #define READ_LINE do {                                  \
 503     bytes_read = getline (&line, &line_size, file);     \
 504     if (bytes_read == -1)                               \
 505         goto END_OF_FILE;                               \
 506     line_count++;                                       \
 507     chomp (line);                                       \
 508 } while (0)
 509
 510     /* Parse options */
 511     while (1) {
 512         char *name, *equal, *value;
 513
 514         /* Ignore blank lines */
 515         READ_LINE;
 516         if (*line == '\0')
 517             continue;
 518
 519         /* An initial digit means we hit an item. Trigger the
 520          * spaghetti machine. */
 521         if ((*line >= '0' && *line <= '9') || *line == '-')
 522             goto PARSE_BIN;
 523
 524         equal = strchr (line, '=');
 525         if (equal == NULL) {
 526             fprintf (stderr, "Malformed option, (expected name=value): \"%s\" at %s:%d\n",
 527                      line, path, line_count);
 528             exit (1);
 529         }
 530
 531         value = equal + 1;
 532         name = line;
 533         *equal = '\0';
 534
 535         name = trim_space (name);
 536         value = trim_space (value);
 537
 538         if (strcmp (name, "order") == 0) {
 539             if (strcmp (value, "sequential") == 0) {
 540                 category->order = CATEGORY_ORDER_SEQUENTIAL;
 541             } else if (strcmp (value, "random") == 0) {
 542                 category->order = CATEGORY_ORDER_RANDOM;
 543             } else {
 544                 fprintf (stderr, "Unknown value for \"order\" option \"%s\" at %s:%d\n",
 545                          value, path, line_count);
 546                 exit (1);
 547             }
 548         } else if (strcmp (name, "time") == 0) {
 549             double limit;
 550             char *end;
 551             limit = strtod (value, &end);
 552             while (isspace (*end))
 553                 end++;
 554             if (*end == '\0') {
 555                 category->time_limit = limit;
 556             } else {
 557                 fprintf (stderr, "Failed to parse time value: %s at %s:%d\n",
 558                          value, path, line_count);
 559                 exit (1);
 560             }
 561         } else if (strcmp (name, "challenge") == 0) {
 562             /* XXX: Need to switch to talloc here. */
 563             free (category->challenge_type);
 564             category->challenge_type = xstrdup (value);
 565         } else if (strcmp (name, "repeat") == 0) {
 566             if (strcmp (value, "0") == 0)
 567                 category->repeat = 0;
 568             else
 569                 category->repeat = 1;
 570         } else {
 571             fprintf (stderr, "Unknown option %s at %s:%d\n",
 572                      name, path, line_count);
 573             exit (1);
 574         }
 575     }
 576
 577     /* Parse items */
 578     while (1) {
 579         int score;
 580         char *challenge, *response;
 581
 582         /* Ignore blank lines */
 583         READ_LINE;
 584         if (*line == '\0')
 585             continue;
 586
 587         /* Read bin number */
 588       PARSE_BIN:
 589         score = strtol (line, &end, 10);
 590         if (*end != '\0') {
 591             fprintf (stderr, "Failed to parse bin number from \"%s\" at %s:%d\n",
 592                      line, path, line_count);
 593             exit (1);
 594         }
 595
 596         /* Read challenge */
 597         READ_LINE;
 598         challenge = strdup (line);
 599
 600         /* Read response */
 601         READ_LINE;
 602         response = line;
 603
 604         category_add_item (category, score, challenge, response);
 605
 606         free (challenge);
 607     }
 608   END_OF_FILE:
 609
 610     free (line);
 611     fclose (file);
 612     free (path);
 613
 614     /* Resize category items to fit exactly. */
 615     category->items_size = category->num_items;
 616     category->items = xrealloc (category->items, category->items_size * sizeof (item_t));
 617
 618     /* Now that the category is completely loaded, with stable
 619      * pointers to every item, we can add each item to its appropriate
 620      * bin. */
 621     for (i = 0; i < category->num_items; i++) {
 622         item_t *item = &category->items[i];
 623         bin_t *bin = mnemon_get_bin (mnemon, item->score);
 624
 625         bin_add_item (bin, item);
 626     }
 627 }
 628
 629 void
 630 mnemon_load (mnemon_t *mnemon)
 631 {
 632     DIR *dir;
 633     struct dirent *dirent;
 634
 635     dir = opendir (mnemon->dir_name);
 636     if (dir == NULL) {
 637         fprintf (stderr, "Error: Failed to open directory %s: %s\n",
 638                  mnemon->dir_name, strerror (errno));
 639         exit (1);
 640     }
 641
 642     while (1) {
 643         dirent = readdir (dir);
 644         if (dirent == NULL)
 645             break;
 646
 647         if (dirent->d_type == DT_REG) {
 648             /* Ignore files matching *~, (yes, this shouldn't be
 649              * hard-coded in such an ad-hoc way, but there you go. */
 650             if (dirent->d_name[strlen(dirent->d_name)-1] != '~')
 651                 mnemon_load_category (mnemon, dirent->d_name);
 652         }
 653     }
 654
 655     closedir (dir);
 656 }
 657
 658 void
 659 mnemon_save (mnemon_t *mnemon)
 660 {
 661     unsigned int i;
 662     int err;
 663     char *filename, *lock_filename;
 664     FILE *file;
 665     category_t *category;
 666
 667     for (i = 0; i < mnemon->num_categories; i++) {
 668         category = &mnemon->categories[i];
 669
 670         xasprintf (&filename, "%s/%s",
 671                    mnemon->dir_name, category->name);
 672         xasprintf (&lock_filename, "%s/.#%s",
 673                    mnemon->dir_name, category->name);
 674
 675         file = fopen (lock_filename, "w");
 676         if (file == NULL) {
 677             fprintf (stderr, "Error: Failed to open %s for writing: %s\n",
 678                      lock_filename, strerror (errno));
 679             continue;
 680         }
 681
 682         category_print (category, file);
 683
 684         fsync (fileno (file));
 685         fclose (file);
 686
 687         err = rename (lock_filename, filename);
 688         if (err < 0) {
 689             fprintf (stderr, "Error: Failed to rename %s to %s: %s\n",
 690                      lock_filename, filename, strerror (errno));
 691             continue;
 692         }
 693
 694         free (filename);
 695         free (lock_filename);
 696     }
 697 }
 698
 699 /* Return a uniformly-distributed pseudo-random integer within the
 700  * range:
 701  *
 702  *      0 <= result < num_values
 703  */
 704 static int
 705 rand_within (int num_values)
 706 {
 707     return (int) (num_values * (rand() / (RAND_MAX + 1.0)));
 708 }
 709
 710 /* Return an exponentially-distributed pseudo-random integer within
 711  * the range:
 712  *
 713  *      0 <= result < num_values
 714  *
 715  * The distribution is such that each successively larger value will
 716  * occur with a probability of half of the previous value.
 717  */
 718 static int
 719 rand_within_exponential (int num_values)
 720 {
 721     static int r;
 722     static uint32_t mask = 0;
 723     int ones;
 724     int bit;
 725
 726     /* Optimize the constant case. */
 727     if (num_values == 1)
 728         return 0;
 729
 730     ones = 0;
 731
 732     do {
 733         if (mask == 0) {
 734             r = rand ();
 735             mask = 1 << 31;
 736             while (mask > RAND_MAX)
 737                 mask >>= 1;
 738         }
 739         bit = r & mask;
 740         mask >>= 1;
 741         if (bit) {
 742             ones++;
 743             if (ones == num_values)
 744                 ones = 0;
 745         }
 746     } while (bit);
 747
 748     return ones;
 749 }
 750
 751 category_t *
 752 mnemon_item_category (mnemon_t  *mnemon,
 753                       item_t    *item)
 754 {
 755     category_t *category;
 756     unsigned int i, item_index;
 757
 758     for (i = 0; i < mnemon->num_categories; i++) {
 759         category = &mnemon->categories[i];
 760         item_index = item - category->items;
 761         if (item_index < category->num_items)
 762             return category;
 763     }
 764
 765     assert (0);
 766 }
 767
 768 void
 769 mnemon_select_item (mnemon_t     *mnemon,
 770                     bin_t       **bin_ret,
 771                     int          *item_index_ret,
 772                     category_t  **category_ret,
 773                     int          *introduced_ret)
 774 {
 775     int bin_index, item_index;
 776     bin_t *bin;
 777     item_t *item;
 778     category_t *category;
 779
 780     bin_index = rand_within_exponential (mnemon->num_bins);
 781     bin = &mnemon->bins[bin_index];
 782
 783     /* The most intuitive understanding of the introduced flag that
 784      * it's tracking never-before-learned items as they are pulled
 785      * from the bin with score 0. But that bin can become empty. So
 786      * the refined rule is that we also set introduced whenever we
 787      * pull from the lowest-indexed bin with a non-negative score. */
 788     if (bin->score >=0 &&
 789         (bin_index == 0 || mnemon->bins[bin_index-1].score < 0))
 790     {
 791         *introduced_ret = 1;
 792     }
 793     else
 794     {
 795         *introduced_ret = 0;
 796     }
 797
 798     item_index = rand_within (bin->num_items);
 799
 800     item = bin->items[item_index];
 801     category = mnemon_item_category (mnemon, item);
 802
 803     if (bin->score == 0) {
 804         if (category->order == CATEGORY_ORDER_SEQUENTIAL) {
 805             item = category_next_bin_zero_item (category);
 806             if (item)
 807                 item_index = bin_item_index (bin, item);
 808         }
 809     }
 810
 811     *bin_ret = bin;
 812     *item_index_ret = item_index;
 813     *category_ret = category;
 814 }
 815
 816 void
 817 mnemon_score_item (mnemon_t *mnemon,
 818                    bin_t *bin,
 819                    unsigned int item_index,
 820                    bool_t correct)
 821 {
 822     item_t *item;
 823
 824     if (item_index >= bin->num_items)
 825         return;
 826
 827     item = bin->items[item_index];
 828     bin_remove_item (bin, item_index);
 829
 830     /* If the bin is now empty, we must remove it. */
 831     if (bin->num_items == 0)
 832     {
 833         mnemon_remove_bin (mnemon, bin->score);
 834     }
 835
 836     if (correct)
 837     {
 838         item->score++;
 839         /* We reserve an item score of 0 for an item that has
 840          * never been asked. */
 841         if (item->score == 0)
 842             item->score = 1;
 843     }
 844     else
 845     {
 846         /* Penalize an incorrect response by forcing the score
 847          * negative. */
 848         if (item->score >= 0) {
 849             /* We go to -2 to force a little extra reinforcement
 850              * when re-learning an item, (otherwise, it will often
 851              * get asked again immediately where it is easy to get
 852              * a correct response without any learning). */
 853             item->score = -2;
 854         } else {
 855             item->score--;
 856         }
 857     }
 858
 859     bin = mnemon_get_bin (mnemon, item->score);
 860
 861     bin_add_item (bin, item);
 862 }