andy_shev

occurence.c

May 28th, 2018
172
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /* SPDX-License-Identifier: GPL-2.0 */
  2.  
  3. /*
  4.  * Find the duplication words in different sentenses.
  5.  *
  6.  * Possible ways to extend:
  7.  *   - support of input from file
  8.  *   - track and collect current sentense number
  9.  *   - better exit handling (perhaps atexit() implementation)
  10.  *   - support locales (call setlocale() and other stuff)
  11.  *   - support Unicode (characters should be multi-byte sequences)
  12.  *   - use hash instead of dumb list with O(n^2) time of execution
  13.  *   - hash will allow to digest huge files using sliding window approach
  14.  *   - alternative is word grep algorithm
  15.  *   - morphem based search (for example, it, its — can be considered same)
  16.  */
  17.  
  18. #include <ctype.h>
  19. #include <err.h>
  20. #include <stdio.h>
  21. #include <stdlib.h>
  22. #include <stdint.h>
  23. #include <stdbool.h>
  24. #include <string.h>
  25.  
  26. /* Double linked list implementation */
  27.  
  28. struct list_head {
  29.         struct list_head *prev;
  30.         struct list_head *next;
  31. };
  32.  
  33. #define LIST_HEAD(name) \
  34.         struct list_head name = { &(name), &(name) }
  35.  
  36. static inline void INIT_LIST_HEAD(struct list_head *list)
  37. {
  38.         list->next = list;
  39.         list->prev = list;
  40. }
  41.  
  42. static void list_del(struct list_head *entry)
  43. {
  44.         struct list_head *prev = entry->prev;
  45.         struct list_head *next = entry->next;
  46.  
  47.         next->prev = prev;
  48.         prev->next = next;
  49. }
  50.  
  51. static void list_add(struct list_head *new, struct list_head *head)
  52. {
  53.         struct list_head *prev = head->prev;
  54.         struct list_head *next = head;
  55.  
  56.         next->prev = new;
  57.         new->next = next;
  58.         new->prev = prev;
  59.         prev->next = new;
  60. }
  61.  
  62. static int list_empty(const struct list_head *head)
  63. {
  64.         return head->next == head;
  65. }
  66.  
  67. static inline int list_is_singular(const struct list_head *head)
  68. {
  69.         return !list_empty(head) && (head->next == head->prev);
  70. }
  71.  
  72. /* The member type of list_head MUST be first in a structure */
  73. #define list_entry(ptr, type, member)           ((type *)(ptr))
  74.  
  75. #define list_first_entry(ptr, type, member)     list_entry((ptr)->next, type, member)
  76.  
  77. #define list_next_entry(pos, member)            list_entry((pos)->member.next, typeof(*(pos)), member)
  78.  
  79. #define list_last_entry(ptr, type, member)      list_entry((ptr)->prev, type, member)
  80.  
  81. #define list_for_each_entry_safe(pos, n, head, member)                  \
  82.         for (pos = list_first_entry(head, typeof(*pos), member),        \
  83.                n = list_next_entry(pos, member);                        \
  84.              &pos->member != (head);                                    \
  85.              pos = n, n = list_next_entry(n, member))
  86.  
  87. /*************************************/
  88.  
  89. struct off {
  90.         struct list_head node;  /* MUST be first member */
  91.         int offset;
  92. };
  93.  
  94. struct word {
  95.         struct list_head node;  /* MUST be first member */
  96.         struct list_head off;
  97.         const char *w;
  98. };
  99.  
  100. static void offset_free(struct list_head *head)
  101. {
  102.         struct off *o, *_o;
  103.  
  104.         list_for_each_entry_safe(o, _o, head, node) {
  105.                 list_del(&o->node);
  106.                 free(o);
  107.         }
  108. }
  109.  
  110. static int offset_add(struct list_head *head, int offset)
  111. {
  112.         struct off *o;
  113.  
  114.         o = malloc(sizeof(*o));
  115.         if (!o)
  116.                 return -1;
  117.  
  118.         o->offset = offset;
  119.  
  120.         list_add(&o->node, head);
  121.         return 0;
  122. }
  123.  
  124. static void word_free(struct list_head *head)
  125. {
  126.         struct word *w, *_w;
  127.  
  128.         list_for_each_entry_safe(w, _w, head, node) {
  129.                 offset_free(&w->off);
  130.                 list_del(&w->node);
  131.                 free(w);
  132.         }
  133. }
  134.  
  135. static int word_add(struct list_head *head, const char *word, int offset)
  136. {
  137.         struct word *w;
  138.         int ret;
  139.  
  140.         w = malloc(sizeof(*w));
  141.         if (!w)
  142.                 return -1;
  143.  
  144.         INIT_LIST_HEAD(&w->off);
  145.         ret = offset_add(&w->off, offset);
  146.         if (ret) {
  147.                 free(w);
  148.                 return ret;
  149.         }
  150.  
  151.         w->w = word;
  152.  
  153.         list_add(&w->node, head);
  154.         return 0;
  155. }
  156.  
  157. static struct word *word_find(struct list_head *head, const char *word)
  158. {
  159.         struct word *w, *_w;
  160.  
  161.         list_for_each_entry_safe(w, _w, head, node) {
  162.                 if (!strcasecmp(w->w, word))
  163.                         return w;
  164.         }
  165.         return NULL;
  166. }
  167.  
  168. static void word_dump(struct list_head *head, bool dups)
  169. {
  170.         struct word *w, *_w;
  171.  
  172.         printf("Dump %s:\n", dups ? "dups only" : "entire list");
  173.         list_for_each_entry_safe(w, _w, head, node) {
  174.                 struct off *o, *_o;
  175.  
  176.                 if (dups && list_is_singular(&w->off))
  177.                         continue;
  178.  
  179.                 printf("%s:", w->w);
  180.                 list_for_each_entry_safe(o, _o, &w->off, node) {
  181.                         printf(" %d", o->offset);
  182.                 }
  183.                 printf("\n");
  184.         }
  185.         printf("\n");
  186. }
  187.  
  188. int tokenize(struct list_head *head, char *data)
  189. {
  190.         char *p = data, *q;
  191.         int current = 0;
  192.         struct word *w;
  193.         int ret;
  194.  
  195.         while ((q = strsep(&p, " \t\n"))) {
  196.                 int offset = (uintptr_t)q - (uintptr_t)data;
  197.                 char *r = q + strlen(q) - 1;
  198.                 bool end;
  199.  
  200.                 /* Skip whitespaces */
  201.                 if (*q == '\0')
  202.                         continue;
  203.  
  204.                 /* End of sentense? */
  205.                 end = strchr(".!?", *r) != NULL;
  206.                 while (r >= q && !isalnum(*r))
  207.                         *r-- = '\0';
  208.  
  209.                 /* Skip malformed sentenses */
  210.                 if (*q == '\0')
  211.                         continue;
  212.  
  213.                 w = word_find(head, q);
  214.                 if (w) {
  215.                         /* We have it in our list */
  216.                         struct off *last = list_last_entry(&w->off, struct off, node);
  217.  
  218.                         if (last->offset < current) {
  219.                                 ret = offset_add(&w->off, offset);
  220.                                 if (ret) {
  221.                                         word_free(head);
  222.                                         return ret;
  223.                                 }
  224.                         }
  225.                 } else {
  226.                         /* New word */
  227.                         ret = word_add(head, q, offset);
  228.                         if (ret) {
  229.                                 word_free(head);
  230.                                 return ret;
  231.                         }
  232.                 }
  233.  
  234.                 /* Track current sentense by word offset */
  235.                 current = end ? (uintptr_t)r - (uintptr_t)data : current;
  236.         }
  237.         return 0;
  238. }
  239.  
  240. static const char *input =
  241.         "\n"
  242.         "What the heck? It's easy to count 33 cows. Easy to\n"
  243.         "implement. A computer is dumb, user is slave!\n";
  244.  
  245. int main(int argc, char *argv[])
  246. {
  247.         char *data = strdup(input);
  248.         LIST_HEAD(words);
  249.         int ret;
  250.  
  251.         ret = tokenize(&words, data);
  252.         if (ret) {
  253.                 free(data);
  254.                 err(1, "tokenize()");
  255.         }
  256.  
  257.         word_dump(&words, false);
  258.         word_dump(&words, true);
  259.  
  260.         word_free(&words);
  261.         free(data);
  262.         return 0;
  263. }
RAW Paste Data