Remove the bin with count 0 once we're done introducing new items
[mnemon] / 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     mnemon_bins_grow (mnemon);
370
371     bin = &mnemon->bins[i];
372
373     /* Make room to insert new bin at its sorted location. */
374     memmove (bin + 1, bin, (mnemon->num_bins - i) * sizeof (bin_t));
375     mnemon->num_bins++;
376
377     bin_init (bin, count);
378
379     return bin;
380 }
381
382 static void
383 mnemon_remove_bin (mnemon_t     *mnemon,
384                    bin_t        *bin)
385 {
386     int i = bin - mnemon->bins;
387
388     bin_fini (bin);
389
390     memmove (bin, bin + 1, (mnemon->num_bins - i) * sizeof (bin_t));
391     mnemon->num_bins--;
392 }
393
394 static void
395 chomp (char *s)
396 {
397     int len = strlen (s);
398     if (len == 0)
399         return;
400     if (s[len - 1] == '\n')
401         s[len - 1] = '\0';
402 }
403
404 static void
405 mnemon_load_category (mnemon_t          *mnemon,
406                       const char        *name)
407 {
408     FILE *file;
409     char *line = NULL, *end;
410     size_t line_size = 0;
411     ssize_t bytes_read;
412     int line_count = 0;
413     char *path;
414     category_t *category;
415     int i;
416
417     path = xmalloc (strlen (mnemon->dir_name) + 1 + strlen (name) + 1);
418     sprintf (path, "%s/%s", mnemon->dir_name, name);
419
420     file = fopen (path, "r");
421     if (file == NULL) {
422         fprintf (stderr, "Error: Failed to open %s: %s\n",
423                  path, strerror (errno));
424         exit (1);
425     }
426
427     category = mnemon_get_category (mnemon, name);
428
429     while (1) {
430         int count;
431         char *challenge, *response;
432
433         /* Read bin number (ignoring blank separator lines) */
434         do {
435             bytes_read = getline (&line, &line_size, file);
436             if (bytes_read == -1)
437                 goto END_OF_FILE;
438             line_count++;
439             chomp (line);
440         } while (*line == '\0');
441
442         count = strtol (line, &end, 10);
443         if (*end != '\0') {
444             fprintf (stderr, "Failed to parse bin number from \"%s\" at %s:%d\n",
445                      line, path, line_count);
446             exit (1);
447         }
448
449         /* Read challenge */
450         bytes_read = getline (&line, &line_size, file);
451         if (bytes_read == -1)
452             break;
453         line_count++;
454         chomp (line);
455         challenge = strdup (line);
456
457         /* Read response */
458         bytes_read = getline (&line, &line_size, file);
459         if (bytes_read == -1)
460             break;
461         line_count++;
462         chomp (line);
463         response = line;
464
465         category_add_item (category, count, challenge, response);
466
467         free (challenge);
468     }
469   END_OF_FILE:
470
471     free (line);
472     fclose (file);
473     free (path);
474
475     /* Resize category items to fit exactly. */
476     category->items_size = category->num_items;
477     category->items = xrealloc (category->items, category->items_size * sizeof (item_t));
478
479     /* Now that the category is completely loaded, with stable
480      * pointers to every item, we can add each item to its appropriate
481      * bin. */
482     for (i = 0; i < category->num_items; i++) {
483         item_t *item = &category->items[i];
484         bin_t *bin = mnemon_get_bin (mnemon, item->count);
485
486         bin_add_item (bin, item);
487     }
488 }
489
490 static void
491 mnemon_load (mnemon_t *mnemon)
492 {
493     DIR *dir;
494     struct dirent *dirent;
495
496     dir = opendir (mnemon->dir_name);
497     if (dir == NULL) {
498         fprintf (stderr, "Error: Failed to open directory %s: %s\n",
499                  mnemon->dir_name, strerror (errno));
500         exit (1);
501     }
502
503     while (1) {
504         dirent = readdir (dir);
505         if (dirent == NULL)
506             break;
507
508         if (dirent->d_type == DT_REG) {
509             /* Ignore files matching *~, (yes, this shouldn't be
510              * hard-coded in such an ad-hoc way, but there you go. */
511             if (dirent->d_name[strlen(dirent->d_name)-1] != '~')
512                 mnemon_load_category (mnemon, dirent->d_name);
513         }
514     }
515
516     closedir (dir);
517 }
518
519 static void
520 mnemon_save (mnemon_t *mnemon)
521 {
522     int i, err;
523     char *filename, *lock_filename;
524     FILE *file;
525     category_t *category;
526
527     for (i = 0; i < mnemon->num_categories; i++) {
528         category = &mnemon->categories[i];
529
530         xasprintf (&filename, "%s/%s",
531                    mnemon->dir_name, category->name);
532         xasprintf (&lock_filename, "%s/.#%s",
533                    mnemon->dir_name, category->name);
534
535         file = fopen (lock_filename, "w");
536         if (file == NULL) {
537             fprintf (stderr, "Error: Failed to open %s for writing: %s\n",
538                      lock_filename, strerror (errno));
539             continue;
540         }
541
542         category_print (category, file);
543
544         fclose (file);
545
546         err = rename (lock_filename, filename);
547         if (err < 0) {
548             fprintf (stderr, "Error: Failed to rename %s to %s: %s\n",
549                      lock_filename, filename, strerror (errno));
550             continue;
551         }
552
553         free (filename);
554         free (lock_filename);
555     }
556 }
557
558 /* Return a uniformly-distributed pseudo-random integer within the
559  * range:
560  *
561  *      0 <= result < num_values
562  */
563 static int
564 rand_within (int num_values)
565 {
566     return (int) (num_values * (rand() / (RAND_MAX + 1.0)));
567 }
568
569 /* Return an exponentially-distributed pseudo-random integer within
570  * the range:
571  *
572  *      0 <= result < num_values
573  *
574  * The distribution is such that each successively larger value will
575  * occur with a probability of half of the previous value.
576  */
577 static int
578 rand_within_exponential (int num_values)
579 {
580     static int r;
581     static uint32_t mask = 0;
582     int ones;
583     int bit;
584
585     /* Optimize the constant case. */
586     if (num_values == 1)
587         return 0;
588
589     ones = 0;
590
591     do {
592         if (mask == 0) {
593             r = rand ();
594             mask = 1 << 31;
595             while (mask > RAND_MAX)
596                 mask >>= 1;
597         }
598         bit = r & mask;
599         mask >>= 1;
600         if (bit) {
601             ones++;
602             if (ones == num_values)
603                 ones = 0;
604         }
605     } while (bit);
606
607     return ones;
608 }
609
610 static void
611 mnemon_select_item (mnemon_t     *mnemon,
612                     bin_t       **bin_ret,
613                     int          *item_index_ret)
614 {
615     int bin_index;
616     bin_t *bin;
617
618     bin_index = rand_within_exponential (mnemon->num_bins);
619
620     bin = &mnemon->bins[bin_index];
621
622     *bin_ret = bin;
623     *item_index_ret = rand_within (bin->num_items);
624 }
625
626 static void
627 mnemon_do_challenges (mnemon_t *mnemon,
628                       int       to_introduce)
629 {
630     bin_t *bin;
631     int item_index;
632     item_t *item;
633     char *response;
634     bool_t correct;
635     int unlearned;
636     int i;
637
638     /* Count the number of items with negative counts. */
639     unlearned = 0;
640     for (i = 0; i < mnemon->num_bins; i++) {
641         bin = &mnemon->bins[i];
642         if (bin->count >= 0)
643             break;
644         unlearned += bin->num_items;
645     }
646
647     to_introduce -= unlearned;
648     if (to_introduce < 0)
649         to_introduce = 0;
650
651     if (unlearned) {
652         printf ("You've got %d items to learn already. ", unlearned);
653         if (to_introduce)
654             printf ("I'll introduce %d more as we go.", to_introduce);
655         printf ("\n");
656     } else {
657         printf ("Introducing %d new items.\n", to_introduce);
658     }
659     printf ("\n");
660
661     do {
662         mnemon_select_item (mnemon, &bin, &item_index);
663
664         if (bin->count == 0)
665             to_introduce--;
666
667         item = bin->items[item_index];
668
669         printf ("%s\n", item->challenge);
670
671         response = readline ("> ");
672         if (response == NULL) {
673             printf ("\n");
674             break;
675         }
676
677         correct = (strcmp (response, item->response) == 0);
678
679         bin_remove_item (bin, item_index);
680
681         /* If the bin is now empty, we must remove it. Also if we just
682          * picked the last word we'll ever pick from the bin with
683          * count 0, then we can remove that as well. */
684         if (bin->num_items == 0 ||
685             (bin->count == 0 && to_introduce == 0))
686         {
687             mnemon_remove_bin (mnemon, bin);
688         }
689
690         if (correct) {
691             item->count++;
692             /* We reserve an item count of 0 for an item that has
693              * never been asked. */
694             if (item->count == 0) {
695                 item->count = 1;
696                 unlearned--;
697                 printf ("You got it!");
698             } else if (item->count < 0) {
699                 printf ("Yes---just give me %d more.",
700                         - item->count);
701             } else if (item->count == 1) {
702                 printf ("On your first try, no less!");
703             } else {
704                 printf ("Masterful.");
705             }
706         } else {
707             printf ("  %s is the correct answer.",
708                     item->response);
709             if (item->count >= 0)
710                 unlearned++;
711             item->count--;
712             /* Penalize an incorrect response by forcing the count
713              * negative. */
714             if (item->count >= 0) {
715                 item->count = -1;
716                 printf ( " Oops, you knew that, right?\n ");
717             }
718         }
719
720         printf (" (");
721         if (to_introduce)
722             printf ("%d to come.", to_introduce);
723         if (to_introduce && unlearned)
724             printf (" ");
725         if (unlearned)
726             printf ("%d still unlearned.", unlearned);
727         if (to_introduce == 0 && unlearned == 0)
728             printf ("Great job!");
729         printf (")\n\n");
730
731         bin = mnemon_get_bin (mnemon, item->count);
732
733         bin_add_item (bin, item);
734     } while (unlearned || to_introduce);
735 }
736
737 int
738 main (int argc, char *argv[])
739 {
740     mnemon_t mnemon;
741
742     srand (time (NULL));
743
744     mnemon_init (&mnemon);
745
746     mnemon_load (&mnemon);
747
748     mnemon_do_challenges (&mnemon, 10);
749
750     mnemon_save (&mnemon);
751
752     mnemon_fini (&mnemon);
753
754     return 0;
755 }