prism/util/pm_newline_list.c

   1 #include "prism/util/pm_newline_list.h"
   2
   3 /**
   4  * Initialize a new newline list with the given capacity. Returns true if the
   5  * allocation of the offsets succeeds, otherwise returns false.
   6  */
   7 bool
   8 pm_newline_list_init(pm_newline_list_t *list, const uint8_t *start, size_t capacity) {
   9     list->offsets = (size_t *) xcalloc(capacity, sizeof(size_t));
  10     if (list->offsets == NULL) return false;
  11
  12     list->start = start;
  13
  14     // This is 1 instead of 0 because we want to include the first line of the
  15     // file as having offset 0, which is set because of calloc.
  16     list->size = 1;
  17     list->capacity = capacity;
  18
  19     return true;
  20 }
  21
  22 /**
  23  * Clear out the newlines that have been appended to the list.
  24  */
  25 void
  26 pm_newline_list_clear(pm_newline_list_t *list) {
  27     list->size = 1;
  28 }
  29
  30 /**
  31  * Append a new offset to the newline list. Returns true if the reallocation of
  32  * the offsets succeeds (if one was necessary), otherwise returns false.
  33  */
  34 bool
  35 pm_newline_list_append(pm_newline_list_t *list, const uint8_t *cursor) {
  36     if (list->size == list->capacity) {
  37         size_t *original_offsets = list->offsets;
  38
  39         list->capacity = (list->capacity * 3) / 2;
  40         list->offsets = (size_t *) xcalloc(list->capacity, sizeof(size_t));
  41         if (list->offsets == NULL) return false;
  42
  43         memcpy(list->offsets, original_offsets, list->size * sizeof(size_t));
  44         xfree(original_offsets);
  45     }
  46
  47     assert(*cursor == '\n');
  48     assert(cursor >= list->start);
  49     size_t newline_offset = (size_t) (cursor - list->start + 1);
  50
  51     assert(list->size == 0 || newline_offset > list->offsets[list->size - 1]);
  52     list->offsets[list->size++] = newline_offset;
  53
  54     return true;
  55 }
  56
  57 /**
  58  * Returns the line of the given offset. If the offset is not in the list, the
  59  * line of the closest offset less than the given offset is returned.
  60  */
  61 int32_t
  62 pm_newline_list_line(const pm_newline_list_t *list, const uint8_t *cursor, int32_t start_line) {
  63     assert(cursor >= list->start);
  64     size_t offset = (size_t) (cursor - list->start);
  65
  66     size_t left = 0;
  67     size_t right = list->size - 1;
  68
  69     while (left <= right) {
  70         size_t mid = left + (right - left) / 2;
  71
  72         if (list->offsets[mid] == offset) {
  73             return ((int32_t) mid) + start_line;
  74         }
  75
  76         if (list->offsets[mid] < offset) {
  77             left = mid + 1;
  78         } else {
  79             right = mid - 1;
  80         }
  81     }
  82
  83     return ((int32_t) left) + start_line - 1;
  84 }
  85
  86 /**
  87  * Returns the line and column of the given offset. If the offset is not in the
  88  * list, the line and column of the closest offset less than the given offset
  89  * are returned.
  90  */
  91 pm_line_column_t
  92 pm_newline_list_line_column(const pm_newline_list_t *list, const uint8_t *cursor, int32_t start_line) {
  93     assert(cursor >= list->start);
  94     size_t offset = (size_t) (cursor - list->start);
  95
  96     size_t left = 0;
  97     size_t right = list->size - 1;
  98
  99     while (left <= right) {
 100         size_t mid = left + (right - left) / 2;
 101
 102         if (list->offsets[mid] == offset) {
 103             return ((pm_line_column_t) { ((int32_t) mid) + start_line, 0 });
 104         }
 105
 106         if (list->offsets[mid] < offset) {
 107             left = mid + 1;
 108         } else {
 109             right = mid - 1;
 110         }
 111     }
 112
 113     return ((pm_line_column_t) {
 114         .line = ((int32_t) left) + start_line - 1,
 115         .column = (uint32_t) (offset - list->offsets[left - 1])
 116     });
 117 }
 118
 119 /**
 120  * Free the internal memory allocated for the newline list.
 121  */
 122 void
 123 pm_newline_list_free(pm_newline_list_t *list) {
 124     xfree(list->offsets);
 125 }