• Skip to content
  • Skip to link menu
Trinity API Reference
  • Trinity API Reference
  • kjs
 

kjs

  • kjs
identifier.cpp
1 /*
2  * This file is part of the KDE libraries
3  * Copyright (C) 2003 Apple Computer, Inc
4  *
5  * This library is free software; you can redistribute it and/or
6  * modify it under the terms of the GNU Library General Public
7  * License as published by the Free Software Foundation; either
8  * version 2 of the License, or (at your option) any later version.
9  *
10  * This library is distributed in the hope that it will be useful,
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13  * Library General Public License for more details.
14  *
15  * You should have received a copy of the GNU Library General Public License
16  * along with this library; see the file COPYING.LIB. If not, write to
17  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
18  * Boston, MA 02110-1301, USA.
19  *
20  */
21 
22 #include "identifier.h"
23 
24 #include <stdio.h>
25 #include <stdlib.h>
26 #include <string.h>
27 
28 #define DUMP_STATISTICS 0
29 
30 namespace KJS {
31 
32 #if DUMP_STATISTICS
33 
34 static int numProbes;
35 static int numCollisions;
36 
37 struct IdentifierStatisticsExitLogger { ~IdentifierStatisticsExitLogger(); };
38 
39 static IdentifierStatisticsExitLogger logger;
40 
41 IdentifierStatisticsExitLogger::~IdentifierStatisticsExitLogger()
42 {
43  printf("\nKJS::Identifier statistics\n\n");
44  printf("%d probes\n", numProbes);
45  printf("%d collisions (%.1f%%)\n", numCollisions, 100.0 * numCollisions / numProbes);
46 }
47 
48 #endif
49 
50 extern const Identifier argumentsPropertyName("arguments");
51 extern const Identifier calleePropertyName("callee");
52 extern const Identifier callerPropertyName("caller");
53 extern const Identifier constructorPropertyName("constructor");
54 extern const Identifier lengthPropertyName("length");
55 extern const Identifier messagePropertyName("message");
56 extern const Identifier namePropertyName("name");
57 extern const Identifier prototypePropertyName("prototype");
58 extern const Identifier specialPrototypePropertyName("__proto__");
59 extern const Identifier toLocaleStringPropertyName("toLocaleString");
60 extern const Identifier toStringPropertyName("toString");
61 extern const Identifier valueOfPropertyName("valueOf");
62 
63 static const int _minTableSize = 64;
64 
65 UString::Rep **Identifier::_table;
66 int Identifier::_tableSize;
67 int Identifier::_tableSizeMask;
68 int Identifier::_keyCount;
69 
70 bool Identifier::equal(UString::Rep *r, const char *s)
71 {
72  int length = r->len;
73  const UChar *d = r->data();
74  for (int i = 0; i != length; ++i)
75  if (d[i].uc != (unsigned char)s[i])
76  return false;
77  return s[length] == 0;
78 }
79 
80 bool Identifier::equal(UString::Rep *r, const UChar *s, int length)
81 {
82  if (r->len != length)
83  return false;
84  const UChar *d = r->data();
85  for (int i = 0; i != length; ++i)
86  if (d[i].uc != s[i].uc)
87  return false;
88  return true;
89 }
90 
91 bool Identifier::equal(UString::Rep *r, UString::Rep *b)
92 {
93  int length = r->len;
94  if (length != b->len)
95  return false;
96  const UChar *d = r->data();
97  const UChar *s = b->data();
98  for (int i = 0; i != length; ++i)
99  if (d[i].uc != s[i].uc)
100  return false;
101  return true;
102 }
103 
104 UString::Rep *Identifier::add(const char *c)
105 {
106  if (!c)
107  return &UString::Rep::null;
108  int length = strlen(c);
109  if (length == 0)
110  return &UString::Rep::empty;
111 
112  if (!_table)
113  expand();
114 
115  unsigned hash = UString::Rep::computeHash(c);
116 
117  int i = hash & _tableSizeMask;
118 #if DUMP_STATISTICS
119  ++numProbes;
120  numCollisions += _table[i] && !equal(_table[i], c);
121 #endif
122  while (UString::Rep *key = _table[i]) {
123  if (equal(key, c))
124  return key;
125  i = (i + 1) & _tableSizeMask;
126  }
127 
128  UChar *d = new UChar[length];
129  for (int j = 0; j != length; j++)
130  d[j] = c[j];
131 
132  UString::Rep *r = new UString::Rep;
133  r->dat = d;
134  r->len = length;
135  r->capacity = UString::Rep::capacityForIdentifier;
136  r->rc = 0;
137  r->_hash = hash;
138 
139  _table[i] = r;
140  ++_keyCount;
141 
142  if (_keyCount * 2 >= _tableSize)
143  expand();
144 
145  return r;
146 }
147 
148 UString::Rep *Identifier::add(const UChar *s, int length)
149 {
150  if (length == 0)
151  return &UString::Rep::empty;
152 
153  if (!_table)
154  expand();
155 
156  unsigned hash = UString::Rep::computeHash(s, length);
157 
158  int i = hash & _tableSizeMask;
159 #if DUMP_STATISTICS
160  ++numProbes;
161  numCollisions += _table[i] && !equal(_table[i], s, length);
162 #endif
163  while (UString::Rep *key = _table[i]) {
164  if (equal(key, s, length))
165  return key;
166  i = (i + 1) & _tableSizeMask;
167  }
168 
169  UChar *d = new UChar[length];
170  for (int j = 0; j != length; j++)
171  d[j] = s[j];
172 
173  UString::Rep *r = new UString::Rep;
174  r->dat = d;
175  r->len = length;
176  r->capacity = UString::Rep::capacityForIdentifier;
177  r->rc = 0;
178  r->_hash = hash;
179 
180  _table[i] = r;
181  ++_keyCount;
182 
183  if (_keyCount * 2 >= _tableSize)
184  expand();
185 
186  return r;
187 }
188 
189 UString::Rep *Identifier::add(UString::Rep *r)
190 {
191  if (r->capacity == UString::Rep::capacityForIdentifier)
192  return r;
193  if (r->len == 0)
194  return &UString::Rep::empty;
195 
196  if (!_table)
197  expand();
198 
199  unsigned hash = r->hash();
200 
201  int i = hash & _tableSizeMask;
202 #if DUMP_STATISTICS
203  ++numProbes;
204  numCollisions += _table[i] && !equal(_table[i], r);
205 #endif
206  while (UString::Rep *key = _table[i]) {
207  if (equal(key, r))
208  return key;
209  i = (i + 1) & _tableSizeMask;
210  }
211 
212  r->capacity = UString::Rep::capacityForIdentifier;
213 
214  _table[i] = r;
215  ++_keyCount;
216 
217  if (_keyCount * 2 >= _tableSize)
218  expand();
219 
220  return r;
221 }
222 
223 inline void Identifier::insert(UString::Rep *key)
224 {
225  unsigned hash = key->hash();
226 
227  int i = hash & _tableSizeMask;
228 #if DUMP_STATISTICS
229  ++numProbes;
230  numCollisions += _table[i] != 0;
231 #endif
232  while (_table[i])
233  i = (i + 1) & _tableSizeMask;
234 
235  _table[i] = key;
236 }
237 
238 void Identifier::remove(UString::Rep *r)
239 {
240  unsigned hash = r->hash();
241 
242  UString::Rep *key;
243 
244  int i = hash & _tableSizeMask;
245 #if DUMP_STATISTICS
246  ++numProbes;
247  numCollisions += _table[i] && equal(_table[i], r);
248 #endif
249  while ((key = _table[i])) {
250  if (equal(key, r))
251  break;
252  i = (i + 1) & _tableSizeMask;
253  }
254  if (!key)
255  return;
256 
257  _table[i] = 0;
258  --_keyCount;
259 
260  if (_keyCount * 6 < _tableSize && _tableSize > _minTableSize) {
261  shrink();
262  return;
263  }
264 
265  // Reinsert all the items to the right in the same cluster.
266  while (1) {
267  i = (i + 1) & _tableSizeMask;
268  key = _table[i];
269  if (!key)
270  break;
271  _table[i] = 0;
272  insert(key);
273  }
274 }
275 
276 void Identifier::expand()
277 {
278  rehash(_tableSize == 0 ? _minTableSize : _tableSize * 2);
279 }
280 
281 void Identifier::shrink()
282 {
283  rehash(_tableSize / 2);
284 }
285 
286 void Identifier::rehash(int newTableSize)
287 {
288  int oldTableSize = _tableSize;
289  UString::Rep **oldTable = _table;
290 
291  _tableSize = newTableSize;
292  _tableSizeMask = newTableSize - 1;
293  _table = (UString::Rep **)calloc(newTableSize, sizeof(UString::Rep *));
294 
295  for (int i = 0; i != oldTableSize; ++i)
296  if (UString::Rep *key = oldTable[i])
297  insert(key);
298 
299  free(oldTable);
300 }
301 
302 const Identifier &Identifier::null()
303 {
304  static Identifier null;
305  return null;
306 }
307 
308 } // namespace KJS
TDEStdAccel::key
int key(StdAccel) KDE_DEPRECATED
KJS
Definition: array_instance.h:27
KJS::Identifier::null
static const Identifier & null()
Creates an empty Identifier.
Definition: identifier.cpp:302
KJS::Identifier
Represents an Identifier for a Javascript object.
Definition: identifier.h:32

kjs

Skip menu "kjs"
  • Main Page
  • Class Hierarchy
  • Alphabetical List
  • Class List
  • File List
  • Class Members
  • Related Pages

kjs

Skip menu "kjs"
  • arts
  • dcop
  • dnssd
  • interfaces
  •   kspeech
  •     interface
  •     library
  •   tdetexteditor
  • kate
  • kded
  • kdoctools
  • kimgio
  • kjs
  • libtdemid
  • libtdescreensaver
  •     tdecore
  • tdeabc
  • tdecmshell
  • tdecore
  • tdefx
  • tdehtml
  • tdeinit
  • tdeio
  •   bookmarks
  •   httpfilter
  •   kpasswdserver
  •   kssl
  • tdeioslave
  •   http
  •   tdefile
  •   tdeio
  •   tdeioexec
  • tdemdi
  •   tdemdi
  • tdenewstuff
  • tdeparts
  • tdeprint
  • tderandr
  • tderesources
  • tdespell2
  • tdesu
  • tdeui
  • tdeunittest
  • tdeutils
  • tdewallet
Generated for kjs by doxygen 1.8.8
This website is maintained by Timothy Pearson.