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