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