← Back to branch summary

~ubuntu-branches/debian/sid/eclipse-cdt/sid

« back to all changes in this revision

Viewing changes to lrparser/org.eclipse.cdt.core.lrparser/old/org/eclipse/cdt/internal/core/dom/lrparser/symboltable/CImperativeSymbolTable.java

  • Committer: Package Import Robot
  • Author(s): Jakub Adam
  • Date: 2011-10-06 21:15:04 UTC
  • mfrom: (1.1.4)
  • Revision ID: package-import@ubuntu.com-20111006211504-8dutmljjih0zikfv
Tags: 8.0.1-1
* New upstream release.
* Split the JNI packages into a separate architecture dependent
  package and made eclipse-cdt architecture independent.
* Install JNI libraries into multiarch aware location
* Bumped Standards-Version to 3.9.2.

Show diffs side-by-side

added added

removed removed

Lines of Context:
lrparser/org.eclipse.cdt.core.lrparser/old/org/eclipse/cdt/internal/core/dom/lrparser/symboltable/CImperativeSymbolTable.java
 
1
/*******************************************************************************
 
2
 * Copyright (c) 2006, 2008 IBM Corporation and others.
 
3
 * All rights reserved. This program and the accompanying materials
 
4
 * are made available under the terms of the Eclipse Public License v1.0
 
5
 * which accompanies this distribution, and is available at
 
6
 * http://www.eclipse.org/legal/epl-v10.html
 
7
 *
 
8
 * Contributors:
 
9
 *     IBM Corporation - initial API and implementation
 
10
 *******************************************************************************/
 
11
package org.eclipse.cdt.internal.core.dom.lrparser.symboltable;
 
12
 
 
13
import java.util.ArrayList;
 
14
import java.util.LinkedList;
 
15
import java.util.List;
 
16
 
 
17
import org.eclipse.cdt.core.dom.ast.IBinding;
 
18
 
 
19
 
 
20
/**
 
21
 * Used to compute binding resolution during the parse.
 
22
 * 
 
23
 * Imperative style symbol table with destructive update.
 
24
 * 
 
25
 * Consists of two data structures, a hash table for fast lookup
 
26
 * of bindings given their names, and a stack used to keep track
 
27
 * of scopes.
 
28
 * 
 
29
 * 
 
30
 * @author Mike Kucera
 
31
 */
 
32
public class CImperativeSymbolTable {
 
33
        
 
34
        private static final int TABLE_SIZE = 256;
 
35
        
 
36
        private Bucket[] table = new Bucket[TABLE_SIZE];
 
37
        
 
38
        private LinkedList<SymbolScope> scopeStack = new LinkedList<SymbolScope>();
 
39
        
 
40
        
 
41
        
 
42
        /**
 
43
         * Represents a scope in the C language.
 
44
         */
 
45
        private static class SymbolScope {
 
46
                
 
47
                /** 
 
48
                 * List of buckets that have been modified in the current scope.
 
49
                 * When the scope is closed these buckets are popped, returning the 
 
50
                 * symbol table to the state it was in before the scope was opened.
 
51
                 */
 
52
                List<Integer> modifiedBuckets = new ArrayList<Integer>();
 
53
        }
 
54
        
 
55
        
 
56
        /**
 
57
         * A bucket object used to hold elements in the hash table.
 
58
         */
 
59
        private static class Bucket {
 
60
                String key;
 
61
                CNamespace namespace;
 
62
                IBinding binding;
 
63
                Bucket next;
 
64
                
 
65
                Bucket(Bucket next, CNamespace namespace, String key, IBinding binding) {
 
66
                        this.key = key;
 
67
                        this.namespace = namespace;
 
68
                        this.binding = binding;
 
69
                        this.next = next;
 
70
                }
 
71
        }
 
72
        
 
73
        
 
74
        public CImperativeSymbolTable() {
 
75
                openScope(); // open the global scope
 
76
                // TODO populate the global scope with built-ins
 
77
        }
 
78
        
 
79
        
 
80
        /**
 
81
         * Hashes a key into an index in the hash table.
 
82
         */
 
83
        private int index(String key) {
 
84
                return Math.abs(key.hashCode() % TABLE_SIZE);
 
85
        }
 
86
        
 
87
        
 
88
        /**
 
89
         * Adds a binding to the symbol table in the current scope.
 
90
         * 
 
91
         * @param mask A bit mask used to identify the namespace of the identifier.
 
92
         */
 
93
        public void put(CNamespace namespace, String ident, IBinding b) {               
 
94
                int index = index(ident);
 
95
                table[index] = new Bucket(table[index], namespace, ident, b);
 
96
                
 
97
                SymbolScope scope = scopeStack.getLast();
 
98
                scope.modifiedBuckets.add(index);
 
99
        }
 
100
        
 
101
 
 
102
        /**
 
103
         * Returns the binding associated with the given identifier, or
 
104
         * null if there is none.
 
105
         * 
 
106
         * @param mask A bit mask used to identify the namespace of the identifier.
 
107
         */
 
108
        public IBinding get(CNamespace namespace, String ident) {
 
109
                Bucket b = table[index(ident)];
 
110
                while(b != null) {
 
111
                        if(namespace == b.namespace && ident.equals(b.key))
 
112
                                return b.binding;
 
113
                        b = b.next;
 
114
                }
 
115
                return null;
 
116
        }
 
117
        
 
118
        
 
119
        /**
 
120
         * Opens a new inner scope for identifiers.
 
121
         * 
 
122
         * If an identifier is added that already exists in an outer scope 
 
123
         * then it will be shadowed.
 
124
         */
 
125
        public void openScope() {
 
126
                scopeStack.add(new SymbolScope());
 
127
        }
 
128
        
 
129
        
 
130
        /**
 
131
         * Remove all the symbols defined in the scope that is being closed.
 
132
         * 
 
133
         * @param scope An IScope object that will be used to represent this scope.
 
134
         * @throws SymbolTableException If the global scope has already been closed or if bindingScope is null.
 
135
         */
 
136
        public void closeScope() {              
 
137
                SymbolScope poppedScope = scopeStack.removeLast(); // pop the scopeStack
 
138
                        
 
139
                // pop each bucket that was modified in the scope
 
140
                for(int index : poppedScope.modifiedBuckets)
 
141
                        table[index] = table[index].next;
 
142
        }
 
143
        
 
144
        
 
145
        @SuppressWarnings("nls")
 
146
        @Override
 
147
        public String toString() {
 
148
                StringBuilder buff = new StringBuilder('[');
 
149
                for(Bucket b : table) {
 
150
                        while(b != null) {
 
151
                                buff.append('<').append(b.key).append(": ").append(b.binding).append(">, ");
 
152
                                b = b.next;
 
153
                        }
 
154
                }
 
155
                return buff.append(']').toString();
 
156
        }
 
157
}