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 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 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 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 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 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 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 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 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