KJS

property_map.cpp
1 /*
2  * This file is part of the KDE libraries
3  * Copyright (C) 2004, 2005, 2006 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 "property_map.h"
23 
24 #include "object.h"
25 #include "protect.h"
26 #include "PropertyNameArray.h"
27 #include <algorithm>
28 #include <wtf/FastMalloc.h>
29 #include <wtf/Vector.h>
30 
31 using std::max;
32 
33 #define DEBUG_PROPERTIES 0
34 #define DO_CONSISTENCY_CHECK 0
35 #define DUMP_STATISTICS 0
36 #define USE_SINGLE_ENTRY 1
37 
38 // 2/28/2006 ggaren: super accurate JS iBench says that USE_SINGLE_ENTRY is a
39 // 3.2% performance boost.
40 
41 #if !DO_CONSISTENCY_CHECK
42 #define checkConsistency() ((void)0)
43 #endif
44 
45 namespace KJS
46 {
47 
48 // Choose a number for the following so that most property maps are smaller,
49 // but it's not going to blow out the stack to allocate this number of pointers.
50 const int smallMapThreshold = 1024;
51 
52 #if DUMP_STATISTICS
53 
54 static int numProbes;
55 static int numCollisions;
56 static int numRehashes;
57 static int numRemoves;
58 
59 struct PropertyMapStatisticsExitLogger {
60  ~PropertyMapStatisticsExitLogger();
61 };
62 
63 static PropertyMapStatisticsExitLogger logger;
64 
65 PropertyMapStatisticsExitLogger::~PropertyMapStatisticsExitLogger()
66 {
67  printf("\nKJS::PropertyMap statistics\n\n");
68  printf("%d probes\n", numProbes);
69  printf("%d collisions (%.1f%%)\n", numCollisions, 100.0 * numCollisions / numProbes);
70  printf("%d rehashes\n", numRehashes);
71  printf("%d removes\n", numRemoves);
72 }
73 
74 #endif
75 
76 // lastIndexUsed is an ever-increasing index used to identify the order items
77 // were inserted into the property map. It's vital that getEnumerablePropertyNames
78 // return the properties in the order they were added for compatibility with other
79 // browsers' JavaScript implementations.
80 struct PropertyMapHashTable {
81  int sizeMask;
82  int size;
83  int keyCount;
84  int sentinelCount;
85  int lastIndexUsed;
86  PropertyMapHashTableEntry entries[1];
87 };
88 
89 class SavedProperty
90 {
91 public:
92  Identifier key;
93  ProtectedPtr<JSValue> value;
94  int attributes;
95 };
96 
97 SavedProperties::SavedProperties() : _count(0) { }
98 SavedProperties::~SavedProperties() { }
99 
100 // Algorithm concepts from Algorithms in C++, Sedgewick.
101 
102 // This is a method rather than a variable to work around <rdar://problem/4462053>
103 static inline UString::Rep *deletedSentinel()
104 {
105  return reinterpret_cast<UString::Rep *>(0x1);
106 }
107 
108 // Returns true if the key is not null or the deleted sentinel, false otherwise
109 static inline bool isValid(UString::Rep *key)
110 {
111  return !!(reinterpret_cast<uintptr_t>(key) & ~0x1);
112 }
113 
114 PropertyMap::~PropertyMap()
115 {
116  if (!m_usingTable) {
117 #if USE_SINGLE_ENTRY
118  UString::Rep *key = m_singleEntryKey;
119  if (key) {
120  key->deref();
121  }
122 #endif
123  return;
124  }
125 
126  int minimumKeysToProcess = m_u.table->keyCount + m_u.table->sentinelCount;
127  Entry *entries = m_u.table->entries;
128  for (int i = 0; i < minimumKeysToProcess; i++) {
129  UString::Rep *key = entries[i].key;
130  if (key) {
131  if (key != deletedSentinel()) {
132  key->deref();
133  }
134  } else {
135  ++minimumKeysToProcess;
136  }
137  }
138  fastFree(m_u.table);
139 }
140 
141 void PropertyMap::clear()
142 {
143  if (!m_usingTable) {
144 #if USE_SINGLE_ENTRY
145  UString::Rep *key = m_singleEntryKey;
146  if (key) {
147  key->deref();
148  m_singleEntryKey = nullptr;
149  }
150 #endif
151  return;
152  }
153 
154  int size = m_u.table->size;
155  Entry *entries = m_u.table->entries;
156  for (int i = 0; i < size; i++) {
157  UString::Rep *key = entries[i].key;
158  if (isValid(key)) {
159  key->deref();
160  entries[i].key = nullptr;
161  entries[i].value = nullptr;
162  }
163  }
164  m_u.table->keyCount = 0;
165  m_u.table->sentinelCount = 0;
166 }
167 
168 bool PropertyMap::isEmpty() const
169 {
170  if (!m_usingTable) {
171  return !m_singleEntryKey;
172  } else {
173  return !m_u.table->keyCount;
174  }
175 }
176 
177 JSValue *PropertyMap::get(const Identifier &name, unsigned &attributes) const
178 {
179  assert(!name.isNull());
180 
181  UString::Rep *rep = name._ustring.rep();
182 
183  if (!m_usingTable) {
184 #if USE_SINGLE_ENTRY
185  UString::Rep *key = m_singleEntryKey;
186  if (rep == key) {
187  attributes = m_singleEntryAttributes;
188  return m_u.singleEntryValue;
189  }
190 #endif
191  return nullptr;
192  }
193 
194  unsigned h = rep->hash();
195  int sizeMask = m_u.table->sizeMask;
196  Entry *entries = m_u.table->entries;
197  int i = h & sizeMask;
198  int k = 0;
199 #if DUMP_STATISTICS
200  ++numProbes;
201  numCollisions += entries[i].key && entries[i].key != rep;
202 #endif
203  while (UString::Rep *key = entries[i].key) {
204  if (rep == key) {
205  attributes = entries[i].attributes;
206  return entries[i].value;
207  }
208  if (k == 0) {
209  k = 1 | (h % sizeMask);
210  }
211  i = (i + k) & sizeMask;
212 #if DUMP_STATISTICS
213  ++numRehashes;
214 #endif
215  }
216  return nullptr;
217 }
218 
219 JSValue *PropertyMap::get(const Identifier &name) const
220 {
221  assert(!name.isNull());
222 
223  UString::Rep *rep = name._ustring.rep();
224 
225  if (!m_usingTable) {
226 #if USE_SINGLE_ENTRY
227  UString::Rep *key = m_singleEntryKey;
228  if (rep == key) {
229  return m_u.singleEntryValue;
230  }
231 #endif
232  return nullptr;
233  }
234 
235  unsigned h = rep->hash();
236  int sizeMask = m_u.table->sizeMask;
237  Entry *entries = m_u.table->entries;
238  int i = h & sizeMask;
239  int k = 0;
240 #if DUMP_STATISTICS
241  ++numProbes;
242  numCollisions += entries[i].key && entries[i].key != rep;
243 #endif
244  while (UString::Rep *key = entries[i].key) {
245  if (rep == key) {
246  return entries[i].value;
247  }
248  if (k == 0) {
249  k = 1 | (h % sizeMask);
250  }
251  i = (i + k) & sizeMask;
252 #if DUMP_STATISTICS
253  ++numRehashes;
254 #endif
255  }
256  return nullptr;
257 }
258 
259 JSValue **PropertyMap::getLocation(const Identifier &name)
260 {
261  assert(!name.isNull());
262 
263  UString::Rep *rep = name._ustring.rep();
264 
265  if (!m_usingTable) {
266 #if USE_SINGLE_ENTRY
267  UString::Rep *key = m_singleEntryKey;
268  if (rep == key) {
269  return &m_u.singleEntryValue;
270  }
271 #endif
272  return nullptr;
273  }
274 
275  unsigned h = rep->hash();
276  int sizeMask = m_u.table->sizeMask;
277  Entry *entries = m_u.table->entries;
278  int i = h & sizeMask;
279  int k = 0;
280 #if DUMP_STATISTICS
281  ++numProbes;
282  numCollisions += entries[i].key && entries[i].key != rep;
283 #endif
284  while (UString::Rep *key = entries[i].key) {
285  if (rep == key) {
286  return &entries[i].value;
287  }
288  if (k == 0) {
289  k = 1 | (h % sizeMask);
290  }
291  i = (i + k) & sizeMask;
292 #if DUMP_STATISTICS
293  ++numRehashes;
294 #endif
295  }
296  return nullptr;
297 }
298 
299 JSValue **PropertyMap::getWriteLocation(const Identifier &name)
300 {
301  assert(!name.isNull());
302 
303  UString::Rep *rep = name._ustring.rep();
304 
305  if (!m_usingTable) {
306  UString::Rep *key = m_singleEntryKey;
307  if (rep == key && !(m_singleEntryAttributes & (ReadOnly | GetterSetter))) {
308  return &m_u.singleEntryValue;
309  }
310  return nullptr;
311  }
312 
313  unsigned h = rep->hash();
314  int sizeMask = m_u.table->sizeMask;
315  Entry *entries = m_u.table->entries;
316  int i = h & sizeMask;
317  int k = 0;
318 #if DUMP_STATISTICS
319  ++numProbes;
320  numCollisions += entries[i].key && entries[i].key != rep;
321 #endif
322  while (UString::Rep *key = entries[i].key) {
323  if (rep == key) {
324  if (entries[i].attributes & (ReadOnly | GetterSetter)) {
325  return nullptr;
326  } else {
327  return &entries[i].value;
328  }
329  }
330  if (k == 0) {
331  k = 1 | (h % sizeMask);
332  }
333  i = (i + k) & sizeMask;
334 #if DUMP_STATISTICS
335  ++numRehashes;
336 #endif
337  }
338  return nullptr;
339 }
340 
341 #if DEBUG_PROPERTIES
342 static void printAttributes(int attributes)
343 {
344  if (attributes == 0) {
345  printf("None");
346  } else {
347  if (attributes & ReadOnly) {
348  printf("ReadOnly ");
349  }
350  if (attributes & DontEnum) {
351  printf("DontEnum ");
352  }
353  if (attributes & DontDelete) {
354  printf("DontDelete ");
355  }
356  if (attributes & Internal) {
357  printf("Internal ");
358  }
359  if (attributes & Function) {
360  printf("Function ");
361  }
362  }
363 }
364 #endif
365 
366 void PropertyMap::put(const Identifier &name, JSValue *value, int attributes, bool roCheck)
367 {
368  assert(!name.isNull());
369  assert(value != nullptr);
370 
371  checkConsistency();
372 
373  UString::Rep *rep = name._ustring.rep();
374 
375 #if DEBUG_PROPERTIES
376  printf("adding property %s, attributes = 0x%08x (", name.ascii(), attributes);
377  printAttributes(attributes);
378  printf(")\n");
379 #endif
380 
381 #if USE_SINGLE_ENTRY
382  if (!m_usingTable) {
383  UString::Rep *key = m_singleEntryKey;
384  if (key) {
385  if (rep == key && !(roCheck && (m_singleEntryAttributes & ReadOnly))) {
386  m_u.singleEntryValue = value;
387  return;
388  }
389  } else {
390  rep->ref();
391  m_singleEntryKey = rep;
392  m_u.singleEntryValue = value;
393  m_singleEntryAttributes = static_cast<short>(attributes);
394  checkConsistency();
395  return;
396  }
397  }
398 #endif
399 
400  if (!m_usingTable || m_u.table->keyCount * 2 >= m_u.table->size) {
401  expand();
402  }
403 
404  unsigned h = rep->hash();
405  int sizeMask = m_u.table->sizeMask;
406  Entry *entries = m_u.table->entries;
407  int i = h & sizeMask;
408  int k = 0;
409  bool foundDeletedElement = false;
410  int deletedElementIndex = 0; /* initialize to make the compiler happy */
411 #if DUMP_STATISTICS
412  ++numProbes;
413  numCollisions += entries[i].key && entries[i].key != rep;
414 #endif
415  while (UString::Rep *key = entries[i].key) {
416  if (rep == key) {
417  if (roCheck && (entries[i].attributes & ReadOnly)) {
418  return;
419  }
420  // Put a new value in an existing hash table entry.
421  entries[i].value = value;
422  // Attributes are intentionally not updated.
423  return;
424  }
425  // If we find the deleted-element sentinel, remember it for use later.
426  if (key == deletedSentinel() && !foundDeletedElement) {
427  foundDeletedElement = true;
428  deletedElementIndex = i;
429  }
430  if (k == 0) {
431  k = 1 | (h % sizeMask);
432  }
433  i = (i + k) & sizeMask;
434 #if DUMP_STATISTICS
435  ++numRehashes;
436 #endif
437  }
438 
439  // Use either the deleted element or the 0 at the end of the chain.
440  if (foundDeletedElement) {
441  i = deletedElementIndex;
442  --m_u.table->sentinelCount;
443  }
444 
445  // Create a new hash table entry.
446  rep->ref();
447  entries[i].key = rep;
448  entries[i].value = value;
449  entries[i].attributes = attributes;
450  entries[i].index = ++m_u.table->lastIndexUsed;
451  ++m_u.table->keyCount;
452 
453  checkConsistency();
454 }
455 
456 void PropertyMap::insert(UString::Rep *key, JSValue *value, int attributes, int index)
457 {
458  assert(m_u.table);
459 
460  unsigned h = key->hash();
461  int sizeMask = m_u.table->sizeMask;
462  Entry *entries = m_u.table->entries;
463  int i = h & sizeMask;
464  int k = 0;
465 #if DUMP_STATISTICS
466  ++numProbes;
467  numCollisions += entries[i].key && entries[i].key != key;
468 #endif
469  while (entries[i].key) {
470  assert(entries[i].key != deletedSentinel());
471  if (k == 0) {
472  k = 1 | (h % sizeMask);
473  }
474  i = (i + k) & sizeMask;
475 #if DUMP_STATISTICS
476  ++numRehashes;
477 #endif
478  }
479 
480  entries[i].key = key;
481  entries[i].value = value;
482  entries[i].attributes = attributes;
483  entries[i].index = index;
484 }
485 
486 void PropertyMap::expand()
487 {
488  if (!m_usingTable) {
489  createTable();
490  } else {
491  rehash(m_u.table->size * 2);
492  }
493 }
494 
495 void PropertyMap::rehash()
496 {
497  ASSERT(m_usingTable);
498  ASSERT(m_u.table);
499  ASSERT(m_u.table->size);
500  rehash(m_u.table->size);
501 }
502 
503 void PropertyMap::createTable()
504 {
505  const int newTableSize = 16;
506 
507  ASSERT(!m_usingTable);
508 
509  checkConsistency();
510 
511 #if USE_SINGLE_ENTRY
512  JSValue *oldSingleEntryValue = m_u.singleEntryValue;
513 #endif
514 
515  m_u.table = (Table *)fastCalloc(1, sizeof(Table) + (newTableSize - 1) * sizeof(Entry));
516  m_u.table->size = newTableSize;
517  m_u.table->sizeMask = newTableSize - 1;
518  m_usingTable = true;
519 
520 #if USE_SINGLE_ENTRY
521  UString::Rep *key = m_singleEntryKey;
522  if (key) {
523  insert(key, oldSingleEntryValue, m_singleEntryAttributes, 0);
524  m_singleEntryKey = nullptr;
525  m_u.table->keyCount = 1;
526  }
527 #endif
528 
529  checkConsistency();
530 }
531 
532 void PropertyMap::rehash(int newTableSize)
533 {
534  ASSERT(!m_singleEntryKey);
535  ASSERT(m_u.table);
536  ASSERT(m_usingTable);
537 
538  checkConsistency();
539 
540  Table *oldTable = m_u.table;
541  int oldTableSize = oldTable->size;
542  int oldTableKeyCount = oldTable->keyCount;
543 
544  m_u.table = (Table *)fastCalloc(1, sizeof(Table) + (newTableSize - 1) * sizeof(Entry));
545  m_u.table->size = newTableSize;
546  m_u.table->sizeMask = newTableSize - 1;
547  m_u.table->keyCount = oldTableKeyCount;
548 
549  int lastIndexUsed = 0;
550  for (int i = 0; i != oldTableSize; ++i) {
551  Entry &entry = oldTable->entries[i];
552  UString::Rep *key = entry.key;
553  if (isValid(key)) {
554  int index = entry.index;
555  lastIndexUsed = max(index, lastIndexUsed);
556  insert(key, entry.value, entry.attributes, index);
557  }
558  }
559  m_u.table->lastIndexUsed = lastIndexUsed;
560 
561  fastFree(oldTable);
562 
563  checkConsistency();
564 }
565 
566 void PropertyMap::remove(const Identifier &name)
567 {
568  assert(!name.isNull());
569 
570  checkConsistency();
571 
572  UString::Rep *rep = name._ustring.rep();
573 
574  UString::Rep *key;
575 
576  if (!m_usingTable) {
577 #if USE_SINGLE_ENTRY
578  key = m_singleEntryKey;
579  if (rep == key) {
580  key->deref();
581  m_singleEntryKey = nullptr;
582  checkConsistency();
583  }
584 #endif
585  return;
586  }
587 
588  // Find the thing to remove.
589  unsigned h = rep->hash();
590  int sizeMask = m_u.table->sizeMask;
591  Entry *entries = m_u.table->entries;
592  int i = h & sizeMask;
593  int k = 0;
594 #if DUMP_STATISTICS
595  ++numProbes;
596  ++numRemoves;
597  numCollisions += entries[i].key && entries[i].key != rep;
598 #endif
599  while ((key = entries[i].key)) {
600  if (rep == key) {
601  break;
602  }
603  if (k == 0) {
604  k = 1 | (h % sizeMask);
605  }
606  i = (i + k) & sizeMask;
607 #if DUMP_STATISTICS
608  ++numRehashes;
609 #endif
610  }
611  if (!key) {
612  return;
613  }
614 
615  // Replace this one element with the deleted sentinel. Also set value to 0 and attributes to DontEnum
616  // to help callers that iterate all keys not have to check for the sentinel.
617  key->deref();
618  key = deletedSentinel();
619  entries[i].key = key;
620  entries[i].value = nullptr;
621  entries[i].attributes = DontEnum;
622  assert(m_u.table->keyCount >= 1);
623  --m_u.table->keyCount;
624  ++m_u.table->sentinelCount;
625 
626  if (m_u.table->sentinelCount * 4 >= m_u.table->size) {
627  rehash();
628  }
629 
630  checkConsistency();
631 }
632 
633 void PropertyMap::mark() const
634 {
635  if (!m_usingTable) {
636 #if USE_SINGLE_ENTRY
637  if (m_singleEntryKey) {
638  JSValue *v = m_u.singleEntryValue;
639  if (!v->marked()) {
640  v->mark();
641  }
642  }
643 #endif
644  return;
645  }
646 
647  int minimumKeysToProcess = m_u.table->keyCount;
648  Entry *entries = m_u.table->entries;
649  for (int i = 0; i < minimumKeysToProcess; i++) {
650  JSValue *v = entries[i].value;
651  if (v) {
652  if (!v->marked()) {
653  v->mark();
654  }
655  } else {
656  ++minimumKeysToProcess;
657  }
658  }
659 }
660 
661 static int comparePropertyMapEntryIndices(const void *a, const void *b)
662 {
663  int ia = static_cast<PropertyMapHashTableEntry *const *>(a)[0]->index;
664  int ib = static_cast<PropertyMapHashTableEntry *const *>(b)[0]->index;
665  if (ia < ib) {
666  return -1;
667  }
668  if (ia > ib) {
669  return +1;
670  }
671  return 0;
672 }
673 
674 bool PropertyMap::containsGettersOrSetters() const
675 {
676  if (!m_usingTable) {
677 #if USE_SINGLE_ENTRY
678  return !!(m_singleEntryAttributes & GetterSetter);
679 #else
680  return false;
681 #endif
682  }
683 
684  for (int i = 0; i != m_u.table->size; ++i) {
685  if (m_u.table->entries[i].attributes & GetterSetter) {
686  return true;
687  }
688  }
689 
690  return false;
691 }
692 
693 void PropertyMap::getPropertyNames(PropertyNameArray &propertyNames, PropertyMode mode) const
694 {
695  if (!m_usingTable) {
696 #if USE_SINGLE_ENTRY
697  UString::Rep *key = m_singleEntryKey;
698  if (key && checkEnumerable(m_singleEntryAttributes, mode)) {
699  propertyNames.add(Identifier(key));
700  }
701 #endif
702  return;
703  }
704 
705  // Allocate a buffer to use to sort the keys.
706  Vector<Entry *, smallMapThreshold> sortedEnumerables(m_u.table->keyCount);
707 
708  // Get pointers to the enumerable entries in the buffer.
709  Entry **p = sortedEnumerables.data();
710  int size = m_u.table->size;
711  Entry *entries = m_u.table->entries;
712  for (int i = 0; i != size; ++i) {
713  Entry *e = &entries[i];
714  if (e->key && checkEnumerable(e->attributes, mode)) {
715  *p++ = e;
716  }
717  }
718 
719  // Sort the entries by index.
720  qsort(sortedEnumerables.data(), p - sortedEnumerables.data(), sizeof(Entry *), comparePropertyMapEntryIndices);
721 
722  // Put the keys of the sorted entries into the list.
723  for (Entry **q = sortedEnumerables.data(); q != p; ++q) {
724  propertyNames.add(Identifier(q[0]->key));
725  }
726 }
727 
728 void PropertyMap::save(SavedProperties &p) const
729 {
730  int count = 0;
731 
732  if (!m_usingTable) {
733 #if USE_SINGLE_ENTRY
734  if (m_singleEntryKey && !(m_singleEntryAttributes & (ReadOnly | Function))) {
735  ++count;
736  }
737 #endif
738  } else {
739  int size = m_u.table->size;
740  Entry *entries = m_u.table->entries;
741  for (int i = 0; i != size; ++i)
742  if (isValid(entries[i].key) && !(entries[i].attributes & (ReadOnly | Function))) {
743  ++count;
744  }
745  }
746 
747  p._properties.clear();
748  p._count = count;
749 
750  if (count == 0) {
751  return;
752  }
753 
754  p._properties.set(new SavedProperty [count]);
755 
756  SavedProperty *prop = p._properties.get();
757 
758  if (!m_usingTable) {
759 #if USE_SINGLE_ENTRY
760  if (m_singleEntryKey && !(m_singleEntryAttributes & (ReadOnly | Function))) {
761  prop->key = Identifier(m_singleEntryKey);
762  prop->value = m_u.singleEntryValue;
763  prop->attributes = m_singleEntryAttributes;
764  ++prop;
765  }
766 #endif
767  } else {
768  // Save in the right order so we don't lose the order.
769  // Another possibility would be to save the indices.
770 
771  // Allocate a buffer to use to sort the keys.
772  Vector<Entry *, smallMapThreshold> sortedEntries(count);
773 
774  // Get pointers to the entries in the buffer.
775  Entry **p = sortedEntries.data();
776  int size = m_u.table->size;
777  Entry *entries = m_u.table->entries;
778  for (int i = 0; i != size; ++i) {
779  Entry *e = &entries[i];
780  if (isValid(e->key) && !(e->attributes & (ReadOnly | Function))) {
781  *p++ = e;
782  }
783  }
784  assert(p - sortedEntries.data() == count);
785 
786  // Sort the entries by index.
787  qsort(sortedEntries.data(), p - sortedEntries.data(), sizeof(Entry *), comparePropertyMapEntryIndices);
788 
789  // Put the sorted entries into the saved properties list.
790  for (Entry **q = sortedEntries.data(); q != p; ++q, ++prop) {
791  Entry *e = *q;
792  prop->key = Identifier(e->key);
793  prop->value = e->value;
794  prop->attributes = e->attributes;
795  }
796  }
797 }
798 
799 void PropertyMap::restore(const SavedProperties &p)
800 {
801  for (int i = 0; i != p._count; ++i) {
802  put(p._properties[i].key, p._properties[i].value, p._properties[i].attributes);
803  }
804 }
805 
806 #if DO_CONSISTENCY_CHECK
807 
808 void PropertyMap::checkConsistency()
809 {
810  if (!m_usingTable) {
811  return;
812  }
813 
814  int count = 0;
815  int sentinelCount = 0;
816  for (int j = 0; j != m_u.table->size; ++j) {
817  UString::Rep *rep = m_u.table->entries[j].key;
818  if (!rep) {
819  continue;
820  }
821  if (rep == deletedSentinel()) {
822  ++sentinelCount;
823  continue;
824  }
825  unsigned h = rep->hash();
826  int i = h & m_u.table->sizeMask;
827  int k = 0;
828  while (UString::Rep *key = m_u.table->entries[i].key) {
829  if (rep == key) {
830  break;
831  }
832  if (k == 0) {
833  k = 1 | (h % m_u.table->sizeMask);
834  }
835  i = (i + k) & m_u.table->sizeMask;
836  }
837  assert(i == j);
838  ++count;
839  }
840  assert(count == m_u.table->keyCount);
841  assert(sentinelCount == m_u.table->sentinelCount);
842  assert(m_u.table->size >= 16);
843  assert(m_u.table->sizeMask);
844  assert(m_u.table->size == m_u.table->sizeMask + 1);
845 }
846 
847 #endif // DO_CONSISTENCY_CHECK
848 
849 } // namespace KJS
QCA_EXPORT Logger * logger()
bool insert(Part *part, qint64 *insertId=nullptr)
KIOCORE_EXPORT TransferJob * put(const QUrl &url, int permissions, JobFlags flags=DefaultFlags)
This file is part of the KDE documentation.
Documentation copyright © 1996-2020 The KDE developers.
Generated on Sat Sep 19 2020 22:59:46 by doxygen 1.8.11 written by Dimitri van Heesch, © 1997-2006

KDE's Doxygen guidelines are available online.