/src/ruby/prism/line_offset_list.c
Line | Count | Source |
1 | | #include "prism/compiler/align.h" |
2 | | #include "prism/internal/line_offset_list.h" |
3 | | #include "prism/internal/arena.h" |
4 | | |
5 | | #include <assert.h> |
6 | | #include <string.h> |
7 | | |
8 | | /** |
9 | | * Initialize a new line offset list with the given capacity. |
10 | | */ |
11 | | void |
12 | 0 | pm_line_offset_list_init(pm_arena_t *arena, pm_line_offset_list_t *list, size_t capacity) { |
13 | 0 | list->offsets = (uint32_t *) pm_arena_alloc(arena, capacity * sizeof(uint32_t), PRISM_ALIGNOF(uint32_t)); |
14 | | |
15 | | // The first line always has offset 0. |
16 | 0 | list->offsets[0] = 0; |
17 | 0 | list->size = 1; |
18 | 0 | list->capacity = capacity; |
19 | 0 | } |
20 | | |
21 | | /** |
22 | | * Clear out the newlines that have been appended to the list. |
23 | | */ |
24 | | void |
25 | 0 | pm_line_offset_list_clear(pm_line_offset_list_t *list) { |
26 | 0 | list->size = 1; |
27 | 0 | } |
28 | | |
29 | | /** |
30 | | * Append a new offset to the newline list (slow path: resize and store). |
31 | | */ |
32 | | void |
33 | 0 | pm_line_offset_list_append_slow(pm_arena_t *arena, pm_line_offset_list_t *list, uint32_t cursor) { |
34 | 0 | size_t new_capacity = (list->capacity * 3) / 2; |
35 | 0 | uint32_t *new_offsets = (uint32_t *) pm_arena_alloc(arena, new_capacity * sizeof(uint32_t), PRISM_ALIGNOF(uint32_t)); |
36 | |
|
37 | 0 | memcpy(new_offsets, list->offsets, list->size * sizeof(uint32_t)); |
38 | |
|
39 | 0 | list->offsets = new_offsets; |
40 | 0 | list->capacity = new_capacity; |
41 | |
|
42 | 0 | assert(list->size == 0 || cursor > list->offsets[list->size - 1]); |
43 | 0 | list->offsets[list->size++] = cursor; |
44 | 0 | } |
45 | | |
46 | | /** |
47 | | * Returns the line of the given offset. If the offset is not in the list, the |
48 | | * line of the closest offset less than the given offset is returned. |
49 | | */ |
50 | | int32_t |
51 | 0 | pm_line_offset_list_line(const pm_line_offset_list_t *list, uint32_t cursor, int32_t start_line) { |
52 | 0 | size_t left = 0; |
53 | 0 | size_t right = list->size - 1; |
54 | |
|
55 | 0 | while (left <= right) { |
56 | 0 | size_t mid = left + (right - left) / 2; |
57 | |
|
58 | 0 | if (list->offsets[mid] == cursor) { |
59 | 0 | return ((int32_t) mid) + start_line; |
60 | 0 | } |
61 | | |
62 | 0 | if (list->offsets[mid] < cursor) { |
63 | 0 | left = mid + 1; |
64 | 0 | } else { |
65 | 0 | right = mid - 1; |
66 | 0 | } |
67 | 0 | } |
68 | | |
69 | 0 | return ((int32_t) left) + start_line - 1; |
70 | 0 | } |
71 | | |
72 | | /** |
73 | | * Returns the line and column of the given offset. If the offset is not in the |
74 | | * list, the line and column of the closest offset less than the given offset |
75 | | * are returned. |
76 | | */ |
77 | | pm_line_column_t |
78 | 0 | pm_line_offset_list_line_column(const pm_line_offset_list_t *list, uint32_t cursor, int32_t start_line) { |
79 | 0 | size_t left = 0; |
80 | 0 | size_t right = list->size - 1; |
81 | |
|
82 | 0 | while (left <= right) { |
83 | 0 | size_t mid = left + (right - left) / 2; |
84 | |
|
85 | 0 | if (list->offsets[mid] == cursor) { |
86 | 0 | return ((pm_line_column_t) { ((int32_t) mid) + start_line, 0 }); |
87 | 0 | } |
88 | | |
89 | 0 | if (list->offsets[mid] < cursor) { |
90 | 0 | left = mid + 1; |
91 | 0 | } else { |
92 | 0 | right = mid - 1; |
93 | 0 | } |
94 | 0 | } |
95 | | |
96 | 0 | return ((pm_line_column_t) { |
97 | 0 | .line = ((int32_t) left) + start_line - 1, |
98 | 0 | .column = cursor - list->offsets[left - 1] |
99 | 0 | }); |
100 | 0 | } |