C   37
angel
Guest on 20th September 2023 12:15:01 AM


  1. #include <ctype.h>
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <string.h>
  5.  
  6.  
  7.  
  8. /**
  9.  * Constant
  10.  */
  11.  
  12. enum
  13. {
  14.     IDENTIFIERS_MAX_COUNT = 100,
  15. };
  16.  
  17. enum
  18. {
  19.     IDENTIFIER_POS_MAX_ASIZE = 1000,
  20. };
  21.  
  22. enum
  23. {
  24.     IDENTIFIER_MAX_STRLEN = 100,
  25.     IDENTIFIER_MAX_ASIZE,
  26. };
  27.  
  28.  
  29.  
  30. /**
  31.  * Data Type
  32.  */
  33.  
  34. struct Record_
  35. {
  36.     char  *identifier;
  37.     short *positions;
  38.     short *positions_last_ptr;
  39. };
  40.  
  41. typedef struct Record_ Record;
  42.  
  43.  
  44.  
  45. /**
  46.  * Function Prototype
  47.  */
  48.  
  49. void    record_write(char const *identifier, int line_number);
  50. Record *record_bsearch(char const *identifier, Record **ptr_insert_entry);
  51.  
  52. int     is_reserved_word(char const *token);
  53. int     is_valid_identifier_char(int chr);
  54.  
  55.  
  56.  
  57. /**
  58.  * Global Variables
  59.  */
  60.  
  61. /* Allocation Pool */
  62. char  g_identifier_pool[IDENTIFIERS_MAX_COUNT][IDENTIFIER_MAX_ASIZE];
  63. short g_identifier_pos_pool[IDENTIFIERS_MAX_COUNT][IDENTIFIER_POS_MAX_ASIZE];
  64.  
  65. /* Allocator Pointer */
  66. char  (*g_identifier_alloc)[IDENTIFIER_MAX_ASIZE] = g_identifier_pool;
  67. short (*g_identifier_pos_alloc)[IDENTIFIER_POS_MAX_ASIZE] =
  68.                                                         g_identifier_pos_pool;
  69.  
  70. /* Record Array */
  71. Record g_identifier_records[IDENTIFIERS_MAX_COUNT];
  72. size_t g_identifier_records_count = 0;
  73.  
  74.  
  75.  
  76. /**
  77.  * Main Function
  78.  */
  79.  
  80. int
  81. main()
  82. {
  83.     int line_number = 1;
  84.     int chr;
  85.  
  86.     char  token[IDENTIFIER_MAX_ASIZE] = {'\0'};
  87.     char *token_ptr = token;
  88.  
  89.     do
  90.     {
  91.         chr = fgetc(stdin);
  92.  
  93.         if (is_valid_identifier_char(chr))
  94.         {
  95.             *token_ptr++ = (char)chr;
  96.         }
  97.         else
  98.         {
  99.             if (strlen(token) > 0 &&
  100.                 !isdigit(token[0]) &&
  101.                 !is_reserved_word(token))
  102.             {
  103.                 record_write(token, line_number);
  104.             }
  105.  
  106.             memset(token, '\0', sizeof(token));
  107.             token_ptr = token;
  108.         }
  109.  
  110.         if (chr == '\n')
  111.         {
  112.             ++line_number;
  113.         }
  114.     }
  115.     while (chr != EOF);
  116.  
  117.  
  118.     int i;
  119.     short *position_ptr;
  120.  
  121.     for (i = 0; i < g_identifier_records_count; ++i)
  122.     {
  123.         printf("%s:", g_identifier_records[i].identifier);
  124.  
  125.         position_ptr = g_identifier_records[i].positions;
  126.         while (position_ptr <= g_identifier_records[i].positions_last_ptr)
  127.         {
  128.             printf(" %d", *position_ptr++);
  129.         }
  130.  
  131.         printf("\n");
  132.     }
  133.  
  134.     return EXIT_SUCCESS;
  135. }
  136.  
  137.  
  138.  
  139. /**
  140.  * Function Implememnts
  141.  */
  142.  
  143. int
  144. is_valid_identifier_char(int chr)
  145. {
  146.     return (isdigit(chr) || isupper(chr) || islower(chr) || chr == '_');
  147. }
  148.  
  149.  
  150.  
  151. int
  152. is_reserved_word(char const *token)
  153. {
  154.     static char reserved_words[][9] =
  155.         {
  156.             "auto", "break", "case", "char", "const", "continue", "default",
  157.             "do", "double", "else", "enum", "extern", "float", "for", "goto",
  158.             "if", "int", "long", "register", "return", "short", "signed",
  159.             "sizeof", "static", "struct", "switch", "typedef", "union",
  160.             "unsigned", "void", "volatile", "while"
  161.         };
  162.  
  163.     static size_t reserved_words_count =
  164.         sizeof(reserved_words)/sizeof(char[9]);
  165.  
  166.     size_t i = 0;
  167.     for (i = 0; i < reserved_words_count; ++i)
  168.     {
  169.         if (strcmp(token, reserved_words[i]) == 0)
  170.         {
  171.             return 1;
  172.         }
  173.     }
  174.  
  175.     return 0;
  176. }
  177.  
  178.  
  179.  
  180. void
  181. record_write(char const *identifier, int line_number)
  182. {
  183.     Record *insert_entry = NULL;
  184.     Record *record_entry = record_bsearch(identifier, &insert_entry);
  185.  
  186.  
  187.     if (!record_entry)
  188.     {
  189.         size_t index = insert_entry - g_identifier_records;
  190.  
  191.         if (index < g_identifier_records_count)
  192.         {
  193.             memmove((insert_entry + 1),
  194.                     (insert_entry),
  195.                     (sizeof(Record) * (g_identifier_records_count - index)));
  196.         }
  197.  
  198.         g_identifier_records_count++;
  199.         record_entry = insert_entry;
  200.  
  201.         record_entry->identifier = *g_identifier_alloc++;
  202.         record_entry->positions = *g_identifier_pos_alloc++;
  203.         record_entry->positions_last_ptr = record_entry->positions;
  204.  
  205.         strcpy(record_entry->identifier, identifier);
  206.         *(record_entry->positions_last_ptr) = line_number;
  207.     }
  208.     else
  209.     {
  210.         if (*(record_entry->positions_last_ptr) != line_number)
  211.         {
  212.             *(++record_entry->positions_last_ptr) = line_number;
  213.         }
  214.     }
  215. }
  216.  
  217.  
  218.  
  219. Record *
  220. record_bsearch(char const *identifier, Record **ptr_insert_entry)
  221. {
  222.     int compare = 0;
  223.  
  224.  
  225.     /* -- Check No Record -------- */
  226.     if (g_identifier_records_count == 0)
  227.     {
  228.         *ptr_insert_entry = g_identifier_records;
  229.         return NULL;
  230.     }
  231.  
  232.  
  233.     /* -- Check Two (Less) Record -------- */
  234.     if (g_identifier_records_count <= 2)
  235.     {
  236.         Record *curr = NULL;
  237.  
  238.         for (curr = g_identifier_records;
  239.              curr < g_identifier_records + g_identifier_records_count;
  240.              curr++)
  241.         {
  242.             compare = strcmp(identifier, curr->identifier);
  243.  
  244.             if (compare == 0)
  245.             {
  246.                 *ptr_insert_entry = curr;
  247.                 return curr;
  248.             }
  249.             else if (compare < 0)
  250.             {
  251.                 *ptr_insert_entry = curr;
  252.                 return NULL;
  253.             }
  254.         }
  255.  
  256.         *ptr_insert_entry = curr;
  257.         return NULL;
  258.     }
  259.  
  260.  
  261.     /* -- More than Two -------- */
  262.     Record *begin = g_identifier_records;
  263.     Record *end   = g_identifier_records + (g_identifier_records_count - 1);
  264.  
  265.  
  266.     compare = strcmp(identifier, begin->identifier);
  267.     if (compare == 0)
  268.     {
  269.         *ptr_insert_entry = begin;
  270.         return begin;
  271.     }
  272.     else if (compare < 0)
  273.     {
  274.         *ptr_insert_entry = begin;
  275.         return NULL;
  276.     }
  277.  
  278.  
  279.     compare = strcmp(identifier, end->identifier);
  280.     if (compare == 0)
  281.     {
  282.         *ptr_insert_entry = end;
  283.         return end;
  284.     }
  285.     else if (compare > 0)
  286.     {
  287.         *ptr_insert_entry = end + 1;
  288.         return NULL;
  289.     }
  290.  
  291.  
  292.     while (end - begin > 1)
  293.     {
  294.         Record *mid = begin + (end - begin) / 2;
  295.  
  296.         compare = strcmp(identifier, mid->identifier);
  297.  
  298.         if (compare == 0)
  299.         {
  300.             *ptr_insert_entry = mid;
  301.             return mid;
  302.         }
  303.         else if (compare < 0)
  304.         {
  305.             end = mid;
  306.         }
  307.         else /* if (compare > 0) */
  308.         {
  309.             begin = mid;
  310.         }
  311.     }
  312.  
  313.     *ptr_insert_entry = end;
  314.     return NULL;
  315. }
  316.  
  317.  
  318.  
  319. /* -- eof -------- */
Raw Paste

Login or Register to edit or fork this paste. It's free.