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     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     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     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     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     int i, err;
 662     char *filename, *lock_filename;
 663     FILE *file;
 664     category_t *category;
 665
 666     for (i = 0; i < mnemon->num_categories; i++) {
 667         category = &mnemon->categories[i];
 668
 669         xasprintf (&filename, "%s/%s",
 670                    mnemon->dir_name, category->name);
 671         xasprintf (&lock_filename, "%s/.#%s",
 672                    mnemon->dir_name, category->name);
 673
 674         file = fopen (lock_filename, "w");
 675         if (file == NULL) {
 676             fprintf (stderr, "Error: Failed to open %s for writing: %s\n",
 677                      lock_filename, strerror (errno));
 678             continue;
 679         }
 680
 681         category_print (category, file);
 682
 683         fsync (fileno (file));
 684         fclose (file);
 685
 686         err = rename (lock_filename, filename);
 687         if (err < 0) {
 688             fprintf (stderr, "Error: Failed to rename %s to %s: %s\n",
 689                      lock_filename, filename, strerror (errno));
 690             continue;
 691         }
 692
 693         free (filename);
 694         free (lock_filename);
 695     }
 696 }
 697
 698 /* Return a uniformly-distributed pseudo-random integer within the
 699  * range:
 700  *
 701  *      0 <= result < num_values
 702  */
 703 static int
 704 rand_within (int num_values)
 705 {
 706     return (int) (num_values * (rand() / (RAND_MAX + 1.0)));
 707 }
 708
 709 /* Return an exponentially-distributed pseudo-random integer within
 710  * the range:
 711  *
 712  *      0 <= result < num_values
 713  *
 714  * The distribution is such that each successively larger value will
 715  * occur with a probability of half of the previous value.
 716  */
 717 static int
 718 rand_within_exponential (int num_values)
 719 {
 720     static int r;
 721     static uint32_t mask = 0;
 722     int ones;
 723     int bit;
 724
 725     /* Optimize the constant case. */
 726     if (num_values == 1)
 727         return 0;
 728
 729     ones = 0;
 730
 731     do {
 732         if (mask == 0) {
 733             r = rand ();
 734             mask = 1 << 31;
 735             while (mask > RAND_MAX)
 736                 mask >>= 1;
 737         }
 738         bit = r & mask;
 739         mask >>= 1;
 740         if (bit) {
 741             ones++;
 742             if (ones == num_values)
 743                 ones = 0;
 744         }
 745     } while (bit);
 746
 747     return ones;
 748 }
 749
 750 category_t *
 751 mnemon_item_category (mnemon_t  *mnemon,
 752                       item_t    *item)
 753 {
 754     category_t *category;
 755     int i, item_index;
 756
 757     for (i = 0; i < mnemon->num_categories; i++) {
 758         category = &mnemon->categories[i];
 759         item_index = item - category->items;
 760         if (item_index >= 0 && item_index < category->num_items)
 761             return category;
 762     }
 763
 764     assert (0);
 765 }
 766
 767 void
 768 mnemon_select_item (mnemon_t     *mnemon,
 769                     bin_t       **bin_ret,
 770                     int          *item_index_ret,
 771                     category_t  **category_ret,
 772                     int          *introduced_ret)
 773 {
 774     int bin_index, item_index;
 775     bin_t *bin;
 776     item_t *item;
 777     category_t *category;
 778
 779     bin_index = rand_within_exponential (mnemon->num_bins);
 780     bin = &mnemon->bins[bin_index];
 781
 782     /* The most intuitive understanding of the introduced flag that
 783      * it's tracking never-before-learned items as they are pulled
 784      * from the bin with score 0. But that bin can become empty. So
 785      * the refined rule is that we also set introduced whenever we
 786      * pull from the lowest-indexed bin with a non-negative score. */
 787     if (bin->score >=0 &&
 788         (bin_index == 0 || mnemon->bins[bin_index-1].score < 0))
 789     {
 790         *introduced_ret = 1;
 791     }
 792     else
 793     {
 794         *introduced_ret = 0;
 795     }
 796
 797     item_index = rand_within (bin->num_items);
 798
 799     item = bin->items[item_index];
 800     category = mnemon_item_category (mnemon, item);
 801
 802     if (bin->score == 0) {
 803         if (category->order == CATEGORY_ORDER_SEQUENTIAL) {
 804             item = category_next_bin_zero_item (category);
 805             if (item)
 806                 item_index = bin_item_index (bin, item);
 807         }
 808     }
 809
 810     *bin_ret = bin;
 811     *item_index_ret = item_index;
 812     *category_ret = category;
 813 }
 814
 815 void
 816 mnemon_score_item (mnemon_t *mnemon,
 817                    bin_t *bin,
 818                    unsigned int item_index,
 819                    bool_t correct)
 820 {
 821     item_t *item;
 822
 823     if (item_index >= bin->num_items)
 824         return;
 825
 826     item = bin->items[item_index];
 827     bin_remove_item (bin, item_index);
 828
 829     /* If the bin is now empty, we must remove it. */
 830     if (bin->num_items == 0)
 831     {
 832         mnemon_remove_bin (mnemon, bin->score);
 833     }
 834
 835     if (correct)
 836     {
 837         item->score++;
 838         /* We reserve an item score of 0 for an item that has
 839          * never been asked. */
 840         if (item->score == 0)
 841             item->score = 1;
 842     }
 843     else
 844     {
 845         /* Penalize an incorrect response by forcing the score
 846          * negative. */
 847         if (item->score >= 0) {
 848             /* We go to -2 to force a little extra reinforcement
 849              * when re-learning an item, (otherwise, it will often
 850              * get asked again immediately where it is easy to get
 851              * a correct response without any learning). */
 852             item->score = -2;
 853         } else {
 854             item->score--;
 855         }
 856     }
 857
 858     bin = mnemon_get_bin (mnemon, item->score);
 859
 860     bin_add_item (bin, item);
 861 }