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

   1 /*
   2  * Copyright © 2006 Carl Worth
   3  *
   4  * This program is free software; you can redistribute it and/or modify
   5  * it under the terms of the GNU General Public License as published by
   6  * the Free Software Foundation; either version 2, or (at your option)
   7  * any later version.
   8  *
   9  * This program is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  * GNU General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program; if not, write to the Free Software Foundation,
  16  * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA."
  17  */
  18
  19 /* for asprintf */
  20 #define _GNU_SOURCE
  21 #include <stdio.h>
  22 #include <stdlib.h>
  23 #include <stdarg.h>
  24 #include <stdint.h>
  25
  26 #include <sys/types.h>
  27 #include <dirent.h>
  28 #include <errno.h>
  29 #include <string.h>
  30 #include <assert.h>
  31
  32 #include <readline/readline.h>
  33 #include <readline/history.h>
  34
  35 typedef int bool_t;
  36
  37 typedef struct _item {
  38     int count;
  39     char *challenge;
  40     char *response;
  41 } item_t;
  42
  43 typedef struct _bin {
  44     int count;
  45     int items_size;
  46     int num_items;
  47     item_t **items;
  48 } bin_t;
  49
  50 typedef struct _category {
  51     char *name;
  52     int items_size;
  53     int num_items;
  54     item_t *items;
  55 } category_t;
  56
  57 typedef struct _mnemon {
  58     char *dir_name;
  59
  60     int categories_size;
  61     int num_categories;
  62     category_t *categories;
  63
  64     int bins_size;
  65     int num_bins;
  66     bin_t *bins;
  67 } mnemon_t;
  68
  69 static void *
  70 xmalloc (size_t size)
  71 {
  72     void *ret;
  73
  74     ret = malloc (size);
  75     if (ret == NULL) {
  76         fprintf (stderr, "Error: out of memory\n");
  77         exit (1);
  78     }
  79
  80     return ret;
  81 }
  82
  83 static void *
  84 xrealloc (void *ptr, size_t size)
  85 {
  86     void *ret;
  87
  88     ret = realloc (ptr, size);
  89     if (ret == NULL) {
  90         fprintf (stderr, "Error: out of memory\n");
  91         exit (1);
  92     }
  93
  94     return ret;
  95 }
  96
  97 static char *
  98 xstrdup (const char *s)
  99 {
 100     char *ret;
 101
 102     ret = strdup (s);
 103     if (s == NULL) {
 104         fprintf (stderr, "Error: out of memory\n");
 105         exit (1);
 106     }
 107
 108     return ret;
 109 }
 110
 111 static void
 112 xasprintf (char **strp, const char *fmt, ...)
 113 {
 114     va_list ap;
 115     int ret;
 116
 117     va_start (ap, fmt);
 118     ret = vasprintf (strp, fmt, ap);
 119     va_end (ap);
 120
 121     if (ret < 0) {
 122         fprintf (stderr, "Error: out of memory\n");
 123         exit (1);
 124     }
 125 }
 126
 127 static void
 128 item_init (item_t       *item,
 129            int           count,
 130            const char   *challenge,
 131            const char   *response)
 132 {
 133     item->count = count;
 134
 135     item->challenge = xmalloc (strlen (challenge) + 1 +
 136                                strlen (response) + 1);
 137     item->response = item->challenge + strlen (challenge) + 1;
 138
 139     strcpy (item->challenge, challenge);
 140     strcpy (item->response, response);
 141 }
 142
 143 static void
 144 item_fini (item_t *item)
 145 {
 146     /* item->response shares allocation with item->challenge, so
 147      * doesn't require a separate call to free */
 148     free (item->challenge);
 149 }
 150
 151 static void
 152 category_init (category_t *category,
 153                const char *name)
 154 {
 155     category->name = xstrdup (name);
 156
 157     category->items_size = 0;
 158     category->num_items = 0;
 159     category->items = NULL;
 160 }
 161
 162 static void
 163 category_fini (category_t *category)
 164 {
 165     int i;
 166
 167     for (i = 0; i < category->num_items; i++)
 168         item_fini (&category->items[i]);
 169
 170     free (category->items);
 171
 172     free (category->name);
 173 }
 174
 175 static void
 176 category_grow (category_t *category)
 177 {
 178     if (category->items_size)
 179         category->items_size *= 2;
 180     else
 181         category->items_size = 1;
 182
 183     category->items = xrealloc (category->items,
 184                                 category->items_size * sizeof (item_t));
 185 }
 186
 187 static item_t *
 188 category_add_item (category_t   *category,
 189                    int           count,
 190                    const char   *challenge,
 191                    const char   *response)
 192 {
 193     item_t *item;
 194
 195     if (category->num_items == category->items_size)
 196         category_grow (category);
 197
 198     item = &category->items[category->num_items++];
 199
 200     item_init (item, count, challenge, response);
 201
 202     return item;
 203 }
 204
 205 static void
 206 category_print (category_t      *category,
 207                 FILE            *file)
 208 {
 209     int i;
 210     item_t *item;
 211
 212     for (i = 0; i < category->num_items; i++) {
 213         item = &category->items[i];
 214         if (i != 0)
 215             fprintf (file, "\n");
 216         fprintf (file, "%d\n%s\n%s\n",
 217                  item->count,
 218                  item->challenge,
 219                  item->response);
 220     }
 221 }
 222
 223 static void
 224 bin_init (bin_t *bin,
 225           int    count)
 226 {
 227     bin->count = count;
 228
 229     bin->items_size = 0;
 230     bin->num_items = 0;
 231     bin->items = NULL;
 232 }
 233
 234 static void
 235 bin_fini (bin_t *bin)
 236 {
 237     free (bin->items);
 238 }
 239
 240 static void
 241 bin_grow (bin_t *bin)
 242 {
 243     if (bin->items_size)
 244         bin->items_size *= 2;
 245     else
 246         bin->items_size = 1;
 247
 248     bin->items = xrealloc (bin->items,
 249                            bin->items_size * sizeof (item_t*));
 250 }
 251
 252 static void
 253 bin_add_item (bin_t     *bin,
 254               item_t    *item)
 255 {
 256     assert (item->count == bin->count);
 257
 258     if (bin->num_items == bin->items_size)
 259         bin_grow (bin);
 260
 261     bin->items[bin->num_items++] = item;
 262 }
 263
 264 static void
 265 bin_remove_item (bin_t  *bin,
 266                  int     item_index)
 267 {
 268     /* Replace the current item with the last item, (no need to shift
 269      * any more than that since we don't care about the order of the
 270      * items within a bin). */
 271     bin->num_items--;
 272     if (bin->num_items)
 273         bin->items[item_index] = bin->items[bin->num_items];
 274 }
 275
 276 static void
 277 mnemon_init (mnemon_t *mnemon)
 278 {
 279     char *home;
 280
 281     home = getenv ("HOME");
 282     if (home == NULL)
 283         home = "";
 284
 285     xasprintf (&mnemon->dir_name, "%s/.mnemon", getenv ("HOME"));
 286
 287     mnemon->categories_size = 0;
 288     mnemon->num_categories = 0;
 289     mnemon->categories = NULL;
 290
 291     mnemon->bins_size = 0;
 292     mnemon->num_bins = 0;
 293     mnemon->bins = NULL;
 294 }
 295
 296 static void
 297 mnemon_fini (mnemon_t *mnemon)
 298 {
 299     int i;
 300
 301     for (i = 0; i < mnemon->num_bins; i++)
 302         bin_fini (&mnemon->bins[i]);
 303     free (mnemon->bins);
 304
 305     for (i = 0; i < mnemon->num_categories; i++)
 306         category_fini (&mnemon->categories[i]);
 307     free (mnemon->categories);
 308
 309     free (mnemon->dir_name);
 310 }
 311
 312 static void
 313 mnemon_categories_grow (mnemon_t *mnemon)
 314 {
 315     if (mnemon->categories_size)
 316         mnemon->categories_size *= 2;
 317     else
 318         mnemon->categories_size = 1;
 319
 320     mnemon->categories = xrealloc (mnemon->categories,
 321                                    mnemon->categories_size * sizeof (category_t));
 322 }
 323
 324 static category_t *
 325 mnemon_get_category (mnemon_t   *mnemon,
 326                      const char *name)
 327 {
 328     int i;
 329     category_t *category;
 330
 331     for (i = 0; i < mnemon->num_categories; i++)
 332         if (strcmp (mnemon->categories[i].name, name) == 0)
 333             return &mnemon->categories[i];
 334
 335     mnemon_categories_grow (mnemon);
 336
 337     category = &mnemon->categories[mnemon->num_categories++];
 338
 339     category_init (category, name);
 340
 341     return category;
 342 }
 343
 344 static void
 345 mnemon_bins_grow (mnemon_t *mnemon)
 346 {
 347     if (mnemon->bins_size)
 348         mnemon->bins_size *= 2;
 349     else
 350         mnemon->bins_size = 1;
 351
 352     mnemon->bins = xrealloc (mnemon->bins,
 353                              mnemon->bins_size * sizeof (bin_t));
 354 }
 355
 356 static bin_t *
 357 mnemon_get_bin (mnemon_t        *mnemon,
 358                 int              count)
 359 {
 360     int i;
 361     bin_t *bin;
 362
 363     for (i = 0; i < mnemon->num_bins; i++)
 364         if (mnemon->bins[i].count == count)
 365             return &mnemon->bins[i];
 366         else if (mnemon->bins[i].count > count)
 367             break;
 368
 369     if (mnemon->num_bins == mnemon->bins_size)
 370         mnemon_bins_grow (mnemon);
 371
 372     bin = &mnemon->bins[i];
 373
 374     /* Make room to insert new bin at its sorted location. */
 375     memmove (bin + 1, bin, (mnemon->num_bins - i) * sizeof (bin_t));
 376     mnemon->num_bins++;
 377
 378     bin_init (bin, count);
 379
 380     return bin;
 381 }
 382
 383 static void
 384 mnemon_remove_bin (mnemon_t     *mnemon,
 385                    bin_t        *bin)
 386 {
 387     int i = bin - mnemon->bins;
 388
 389     bin_fini (bin);
 390
 391     memmove (bin, bin + 1, (mnemon->num_bins - i) * sizeof (bin_t));
 392     mnemon->num_bins--;
 393 }
 394
 395 static void
 396 chomp (char *s)
 397 {
 398     int len = strlen (s);
 399     if (len == 0)
 400         return;
 401     if (s[len - 1] == '\n')
 402         s[len - 1] = '\0';
 403 }
 404
 405 static void
 406 mnemon_load_category (mnemon_t          *mnemon,
 407                       const char        *name)
 408 {
 409     FILE *file;
 410     char *line = NULL, *end;
 411     size_t line_size = 0;
 412     ssize_t bytes_read;
 413     int line_count = 0;
 414     char *path;
 415     category_t *category;
 416     int i;
 417
 418     path = xmalloc (strlen (mnemon->dir_name) + 1 + strlen (name) + 1);
 419     sprintf (path, "%s/%s", mnemon->dir_name, name);
 420
 421     file = fopen (path, "r");
 422     if (file == NULL) {
 423         fprintf (stderr, "Error: Failed to open %s: %s\n",
 424                  path, strerror (errno));
 425         exit (1);
 426     }
 427
 428     category = mnemon_get_category (mnemon, name);
 429
 430     while (1) {
 431         int count;
 432         char *challenge, *response;
 433
 434         /* Read bin number (ignoring blank separator lines) */
 435         do {
 436             bytes_read = getline (&line, &line_size, file);
 437             if (bytes_read == -1)
 438                 goto END_OF_FILE;
 439             line_count++;
 440             chomp (line);
 441         } while (*line == '\0');
 442
 443         count = strtol (line, &end, 10);
 444         if (*end != '\0') {
 445             fprintf (stderr, "Failed to parse bin number from \"%s\" at %s:%d\n",
 446                      line, path, line_count);
 447             exit (1);
 448         }
 449
 450         /* Read challenge */
 451         bytes_read = getline (&line, &line_size, file);
 452         if (bytes_read == -1)
 453             break;
 454         line_count++;
 455         chomp (line);
 456         challenge = strdup (line);
 457
 458         /* Read response */
 459         bytes_read = getline (&line, &line_size, file);
 460         if (bytes_read == -1)
 461             break;
 462         line_count++;
 463         chomp (line);
 464         response = line;
 465
 466         category_add_item (category, count, challenge, response);
 467
 468         free (challenge);
 469     }
 470   END_OF_FILE:
 471
 472     free (line);
 473     fclose (file);
 474     free (path);
 475
 476     /* Resize category items to fit exactly. */
 477     category->items_size = category->num_items;
 478     category->items = xrealloc (category->items, category->items_size * sizeof (item_t));
 479
 480     /* Now that the category is completely loaded, with stable
 481      * pointers to every item, we can add each item to its appropriate
 482      * bin. */
 483     for (i = 0; i < category->num_items; i++) {
 484         item_t *item = &category->items[i];
 485         bin_t *bin = mnemon_get_bin (mnemon, item->count);
 486
 487         bin_add_item (bin, item);
 488     }
 489 }
 490
 491 static void
 492 mnemon_load (mnemon_t *mnemon)
 493 {
 494     DIR *dir;
 495     struct dirent *dirent;
 496
 497     dir = opendir (mnemon->dir_name);
 498     if (dir == NULL) {
 499         fprintf (stderr, "Error: Failed to open directory %s: %s\n",
 500                  mnemon->dir_name, strerror (errno));
 501         exit (1);
 502     }
 503
 504     while (1) {
 505         dirent = readdir (dir);
 506         if (dirent == NULL)
 507             break;
 508
 509         if (dirent->d_type == DT_REG) {
 510             /* Ignore files matching *~, (yes, this shouldn't be
 511              * hard-coded in such an ad-hoc way, but there you go. */
 512             if (dirent->d_name[strlen(dirent->d_name)-1] != '~')
 513                 mnemon_load_category (mnemon, dirent->d_name);
 514         }
 515     }
 516
 517     closedir (dir);
 518 }
 519
 520 static void
 521 mnemon_save (mnemon_t *mnemon)
 522 {
 523     int i, err;
 524     char *filename, *lock_filename;
 525     FILE *file;
 526     category_t *category;
 527
 528     for (i = 0; i < mnemon->num_categories; i++) {
 529         category = &mnemon->categories[i];
 530
 531         xasprintf (&filename, "%s/%s",
 532                    mnemon->dir_name, category->name);
 533         xasprintf (&lock_filename, "%s/.#%s",
 534                    mnemon->dir_name, category->name);
 535
 536         file = fopen (lock_filename, "w");
 537         if (file == NULL) {
 538             fprintf (stderr, "Error: Failed to open %s for writing: %s\n",
 539                      lock_filename, strerror (errno));
 540             continue;
 541         }
 542
 543         category_print (category, file);
 544
 545         fclose (file);
 546
 547         err = rename (lock_filename, filename);
 548         if (err < 0) {
 549             fprintf (stderr, "Error: Failed to rename %s to %s: %s\n",
 550                      lock_filename, filename, strerror (errno));
 551             continue;
 552         }
 553
 554         free (filename);
 555         free (lock_filename);
 556     }
 557 }
 558
 559 /* Return a uniformly-distributed pseudo-random integer within the
 560  * range:
 561  *
 562  *      0 <= result < num_values
 563  */
 564 static int
 565 rand_within (int num_values)
 566 {
 567     return (int) (num_values * (rand() / (RAND_MAX + 1.0)));
 568 }
 569
 570 /* Return an exponentially-distributed pseudo-random integer within
 571  * the range:
 572  *
 573  *      0 <= result < num_values
 574  *
 575  * The distribution is such that each successively larger value will
 576  * occur with a probability of half of the previous value.
 577  */
 578 static int
 579 rand_within_exponential (int num_values)
 580 {
 581     static int r;
 582     static uint32_t mask = 0;
 583     int ones;
 584     int bit;
 585
 586     /* Optimize the constant case. */
 587     if (num_values == 1)
 588         return 0;
 589
 590     ones = 0;
 591
 592     do {
 593         if (mask == 0) {
 594             r = rand ();
 595             mask = 1 << 31;
 596             while (mask > RAND_MAX)
 597                 mask >>= 1;
 598         }
 599         bit = r & mask;
 600         mask >>= 1;
 601         if (bit) {
 602             ones++;
 603             if (ones == num_values)
 604                 ones = 0;
 605         }
 606     } while (bit);
 607
 608     return ones;
 609 }
 610
 611 static void
 612 mnemon_select_item (mnemon_t     *mnemon,
 613                     bin_t       **bin_ret,
 614                     int          *item_index_ret)
 615 {
 616     int bin_index;
 617     bin_t *bin;
 618
 619     bin_index = rand_within_exponential (mnemon->num_bins);
 620
 621     bin = &mnemon->bins[bin_index];
 622
 623     *bin_ret = bin;
 624     *item_index_ret = rand_within (bin->num_items);
 625 }
 626
 627 static void
 628 mnemon_do_challenges (mnemon_t *mnemon,
 629                       int       to_introduce)
 630 {
 631     bin_t *bin;
 632     int item_index;
 633     item_t *item;
 634     char *response;
 635     bool_t correct;
 636     int unlearned;
 637     int i;
 638
 639     /* Count the number of items with negative counts. */
 640     unlearned = 0;
 641     for (i = 0; i < mnemon->num_bins; i++) {
 642         bin = &mnemon->bins[i];
 643         if (bin->count >= 0)
 644             break;
 645         unlearned += bin->num_items;
 646     }
 647
 648     to_introduce -= unlearned;
 649     if (to_introduce < 0)
 650         to_introduce = 0;
 651
 652     if (unlearned) {
 653         printf ("You've got %d items to learn already. ", unlearned);
 654         if (to_introduce)
 655             printf ("I'll introduce %d more as we go.", to_introduce);
 656         printf ("\n");
 657     } else {
 658         printf ("Introducing %d new items.\n", to_introduce);
 659     }
 660     printf ("\n");
 661
 662     do {
 663         mnemon_select_item (mnemon, &bin, &item_index);
 664
 665         if (bin->count == 0)
 666             to_introduce--;
 667
 668         item = bin->items[item_index];
 669
 670         printf ("%s\n", item->challenge);
 671
 672         response = readline ("> ");
 673         if (response == NULL) {
 674             printf ("\n");
 675             break;
 676         }
 677
 678         correct = (strcmp (response, item->response) == 0);
 679
 680         bin_remove_item (bin, item_index);
 681
 682         /* If the bin is now empty, we must remove it. Also if we just
 683          * picked the last word we'll ever pick from the bin with
 684          * count 0, then we can remove that as well. */
 685         if (bin->num_items == 0 ||
 686             (bin->count == 0 && to_introduce == 0))
 687         {
 688             mnemon_remove_bin (mnemon, bin);
 689         }
 690
 691         if (correct) {
 692             item->count++;
 693             /* We reserve an item count of 0 for an item that has
 694              * never been asked. */
 695             if (item->count == 0) {
 696                 item->count = 1;
 697                 unlearned--;
 698                 printf ("You got it!");
 699             } else if (item->count < 0) {
 700                 printf ("Yes---just give me %d more.",
 701                         - item->count);
 702             } else if (item->count == 1) {
 703                 printf ("On your first try, no less!");
 704             } else {
 705                 printf ("Masterful.");
 706             }
 707         } else {
 708             printf ("  %s is the correct answer.",
 709                     item->response);
 710             if (item->count >= 0)
 711                 unlearned++;
 712             item->count--;
 713             /* Penalize an incorrect response by forcing the count
 714              * negative. */
 715             if (item->count >= 0) {
 716                 item->count = -1;
 717                 printf ( " Oops, you knew that, right?\n ");
 718             }
 719         }
 720
 721         printf (" (");
 722         if (to_introduce)
 723             printf ("%d to come.", to_introduce);
 724         if (to_introduce && unlearned)
 725             printf (" ");
 726         if (unlearned)
 727             printf ("%d still unlearned.", unlearned);
 728         if (to_introduce == 0 && unlearned == 0)
 729             printf ("Great job!");
 730         printf (")\n\n");
 731
 732         bin = mnemon_get_bin (mnemon, item->count);
 733
 734         bin_add_item (bin, item);
 735     } while (unlearned || to_introduce);
 736 }
 737
 738 int
 739 main (int argc, char *argv[])
 740 {
 741     mnemon_t mnemon;
 742
 743     srand (time (NULL));
 744
 745     mnemon_init (&mnemon);
 746
 747     mnemon_load (&mnemon);
 748
 749     mnemon_do_challenges (&mnemon, 10);
 750
 751     mnemon_save (&mnemon);
 752
 753     mnemon_fini (&mnemon);
 754
 755     return 0;
 756 }