1 /*
2  * sparse/token_store.c
3  *
4  * Copyright (C) 2012 Oracle.
5  *
6  * Permission is hereby granted, free of charge, to any person obtaining a copy
7  * of this software and associated documentation files (the "Software"), to deal
8  * in the Software without restriction, including without limitation the rights
9  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
10  * copies of the Software, and to permit persons to whom the Software is
11  * furnished to do so, subject to the following conditions:
12  *
13  * The above copyright notice and this permission notice shall be included in
14  * all copies or substantial portions of the Software.
15  *
16  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
19  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
21  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
22  * THE SOFTWARE.
23  */
24 
25 #include <stdlib.h>
26 #include <stdio.h>
27 #include <string.h>
28 #include "lib.h"
29 #include "parse.h"
30 #include "allocate.h"
31 
32 struct line {
33 	struct position pos;
34 	struct line *prev;
35 	struct token *token;
36 	struct line *next;
37 };
38 
39 __ALLOCATOR(struct token, "token store", perm_token);
40 ALLOCATOR(line, "line of tokens");
41 
copy_token(struct token * token)42 static struct token *copy_token(struct token *token)
43 {
44 	struct token *new;
45 
46 	new = __alloc_perm_token(0);
47 	memcpy(new, token, sizeof(*token));
48 	new->next = NULL;
49 	return new;
50 }
51 
52 static struct line *cursor;
53 
find_line(struct position pos)54 static void find_line(struct position pos)
55 {
56 	if (!cursor)
57 		return;
58 	if (pos.line == cursor->pos.line)
59 		return;
60 	if (pos.line < cursor->pos.line) {
61 		if (!cursor->prev)
62 			return;
63 		cursor = cursor->prev;
64 		find_line(pos);
65 		return;
66 	}
67 	if (!cursor->next)
68 		return;
69 	if (pos.line < cursor->next->pos.line)
70 		return;
71 	cursor = cursor->next;
72 	find_line(pos);
73 }
74 
insert_into_line(struct token ** current,struct token * new)75 static void insert_into_line(struct token **current, struct token *new)
76 {
77 	if (!*current) {
78 		*current = new;
79 		return;
80 	}
81 
82 	if (new->pos.pos < (*current)->pos.pos) {
83 		new->next = *current;
84 		*current = new;
85 		return;
86 	}
87 
88 	if (new->pos.pos == (*current)->pos.pos)
89 		return;
90 
91 	insert_into_line(&(*current)->next, new);
92 }
93 
store_token(struct token * token)94 static void store_token(struct token *token)
95 {
96 	token = copy_token(token);
97 
98 	find_line(token->pos);
99 
100 	if (!cursor) {
101 		cursor = __alloc_line(0);
102 		cursor->pos = token->pos;
103 		cursor->token = token;
104 		return;
105 	}
106 
107 	if (token->pos.line < cursor->pos.line) {
108 		cursor->prev = __alloc_line(0);
109 		cursor->prev->next = cursor;
110 		cursor = cursor->prev;
111 		cursor->pos = token->pos;
112 		cursor->token = token;
113 		return;
114 	}
115 
116 	if (token->pos.line == cursor->pos.line) {
117 		insert_into_line(&cursor->token, token);
118 		return;
119 	}
120 
121 	cursor->next = __alloc_line(0);
122 	cursor->next->prev = cursor;
123 	cursor = cursor->next;
124 	cursor->pos = token->pos;
125 	cursor->token = token;
126 }
127 
store_all_tokens(struct token * token)128 void store_all_tokens(struct token *token)
129 {
130 	while (token_type(token) != TOKEN_STREAMEND) {
131 		store_token(token);
132 		token = token->next;
133 	}
134 }
135 
first_token_from_line(struct position pos)136 struct token *first_token_from_line(struct position pos)
137 {
138 	find_line(pos);
139 
140 	if (!cursor)
141 		return NULL;
142 
143 	if (cursor->pos.stream != pos.stream)
144 		return NULL;
145 	if (cursor->pos.line != pos.line)
146 		return NULL;
147 
148 	return cursor->token;
149 }
150 
pos_get_token(struct position pos)151 struct token *pos_get_token(struct position pos)
152 {
153 	struct token *token;
154 
155 	token = first_token_from_line(pos);
156 	while (token) {
157 		if (pos.pos == token->pos.pos)
158 			return token;
159 		if (pos.pos < token->pos.pos)
160 			return NULL;
161 		token = token->next;
162 	}
163 	return NULL;
164 }
165 
pos_ident(struct position pos)166 char *pos_ident(struct position pos)
167 {
168 	struct token *token;
169 
170 	token = pos_get_token(pos);
171 	if (!token)
172 		return NULL;
173 	if (token_type(token) != TOKEN_IDENT)
174 		return NULL;
175 	return token->ident->name;
176 }
177 
178