<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN"
"http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head><meta http-equiv="content-type" content="text/html; charset=utf-8" />
<title>[205842] trunk</title>
</head>
<body>
<style type="text/css"><!--
#msg dl.meta { border: 1px #006 solid; background: #369; padding: 6px; color: #fff; }
#msg dl.meta dt { float: left; width: 6em; font-weight: bold; }
#msg dt:after { content:':';}
#msg dl, #msg dt, #msg ul, #msg li, #header, #footer, #logmsg { font-family: verdana,arial,helvetica,sans-serif; font-size: 10pt; }
#msg dl a { font-weight: bold}
#msg dl a:link { color:#fc3; }
#msg dl a:active { color:#ff0; }
#msg dl a:visited { color:#cc6; }
h3 { font-family: verdana,arial,helvetica,sans-serif; font-size: 10pt; font-weight: bold; }
#msg pre { overflow: auto; background: #ffc; border: 1px #fa0 solid; padding: 6px; }
#logmsg { background: #ffc; border: 1px #fa0 solid; padding: 1em 1em 0 1em; }
#logmsg p, #logmsg pre, #logmsg blockquote { margin: 0 0 1em 0; }
#logmsg p, #logmsg li, #logmsg dt, #logmsg dd { line-height: 14pt; }
#logmsg h1, #logmsg h2, #logmsg h3, #logmsg h4, #logmsg h5, #logmsg h6 { margin: .5em 0; }
#logmsg h1:first-child, #logmsg h2:first-child, #logmsg h3:first-child, #logmsg h4:first-child, #logmsg h5:first-child, #logmsg h6:first-child { margin-top: 0; }
#logmsg ul, #logmsg ol { padding: 0; list-style-position: inside; margin: 0 0 0 1em; }
#logmsg ul { text-indent: -1em; padding-left: 1em; }#logmsg ol { text-indent: -1.5em; padding-left: 1.5em; }
#logmsg > ul, #logmsg > ol { margin: 0 0 1em 0; }
#logmsg pre { background: #eee; padding: 1em; }
#logmsg blockquote { border: 1px solid #fa0; border-left-width: 10px; padding: 1em 1em 0 1em; background: white;}
#logmsg dl { margin: 0; }
#logmsg dt { font-weight: bold; }
#logmsg dd { margin: 0; padding: 0 0 0.5em 0; }
#logmsg dd:before { content:'\00bb';}
#logmsg table { border-spacing: 0px; border-collapse: collapse; border-top: 4px solid #fa0; border-bottom: 1px solid #fa0; background: #fff; }
#logmsg table th { text-align: left; font-weight: normal; padding: 0.2em 0.5em; border-top: 1px dotted #fa0; }
#logmsg table td { text-align: right; border-top: 1px dotted #fa0; padding: 0.2em 0.5em; }
#logmsg table thead th { text-align: center; border-bottom: 1px solid #fa0; }
#logmsg table th.Corner { text-align: left; }
#logmsg hr { border: none 0; border-top: 2px dashed #fa0; height: 1px; }
#header, #footer { color: #fff; background: #636; border: 1px #300 solid; padding: 6px; }
#patch { width: 100%; }
#patch h4 {font-family: verdana,arial,helvetica,sans-serif;font-size:10pt;padding:8px;background:#369;color:#fff;margin:0;}
#patch .propset h4, #patch .binary h4 {margin:0;}
#patch pre {padding:0;line-height:1.2em;margin:0;}
#patch .diff {width:100%;background:#eee;padding: 0 0 10px 0;overflow:auto;}
#patch .propset .diff, #patch .binary .diff {padding:10px 0;}
#patch span {display:block;padding:0 10px;}
#patch .modfile, #patch .addfile, #patch .delfile, #patch .propset, #patch .binary, #patch .copfile {border:1px solid #ccc;margin:10px 0;}
#patch ins {background:#dfd;text-decoration:none;display:block;padding:0 10px;}
#patch del {background:#fdd;text-decoration:none;display:block;padding:0 10px;}
#patch .lines, .info {color:#888;background:#fff;}
--></style>
<div id="msg">
<dl class="meta">
<dt>Revision</dt> <dd><a href="http://trac.webkit.org/projects/webkit/changeset/205842">205842</a></dd>
<dt>Author</dt> <dd>sbarati@apple.com</dd>
<dt>Date</dt> <dd>2016-09-12 17:14:59 -0700 (Mon, 12 Sep 2016)</dd>
</dl>
<h3>Log Message</h3>
<pre>HashMapImpl should take into account m_deleteCount in its load factor and it should be able to rehash the table to be smaller
https://bugs.webkit.org/show_bug.cgi?id=161640
Reviewed by Geoffrey Garen.
JSTests:
* microbenchmarks/map-rehash.js: Added.
* stress/map-delete.js: Added.
(assert):
* stress/map-rehash-2.js: Added.
(assert):
* stress/map-rehash.js: Added.
(assert):
Source/JavaScriptCore:
HashMapImpl now takes into account m_deleteCount in its load factor.
It now knows how to rehash to either decrease its capacity, stay at
the same capacity, or increase its capacity. The reason we can sometimes
stay at the same capacity is that we can reduce the load factor enough
by rehashing that growing isn't warranted. The reason for this is that
anytime we rehash, we remove all deleted sentinels from the buffer.
Therefore, staying at the same same capacity, when there are deleted entries,
can still reduce the load factor because it removes all deleted sentinels.
* runtime/HashMapImpl.h:
(JSC::HashMapBuffer::create):
(JSC::HashMapBuffer::reset):
(JSC::HashMapImpl::HashMapImpl):
(JSC::HashMapImpl::add):
(JSC::HashMapImpl::remove):
(JSC::HashMapImpl::size):
(JSC::HashMapImpl::clear):
(JSC::HashMapImpl::approximateSize):
(JSC::HashMapImpl::shouldRehashAfterAdd):
(JSC::HashMapImpl::shouldShrink):
(JSC::HashMapImpl::rehash):
(JSC::HashMapImpl::checkConsistency):
(JSC::HashMapImpl::makeAndSetNewBuffer):
(JSC::HashMapImpl::assertBufferIsEmpty):</pre>
<h3>Modified Paths</h3>
<ul>
<li><a href="#trunkJSTestsChangeLog">trunk/JSTests/ChangeLog</a></li>
<li><a href="#trunkSourceJavaScriptCoreChangeLog">trunk/Source/JavaScriptCore/ChangeLog</a></li>
<li><a href="#trunkSourceJavaScriptCoreruntimeHashMapImplh">trunk/Source/JavaScriptCore/runtime/HashMapImpl.h</a></li>
</ul>
<h3>Added Paths</h3>
<ul>
<li><a href="#trunkJSTestsmicrobenchmarksmaprehashjs">trunk/JSTests/microbenchmarks/map-rehash.js</a></li>
<li><a href="#trunkJSTestsstressmapdeletejs">trunk/JSTests/stress/map-delete.js</a></li>
<li><a href="#trunkJSTestsstressmaprehash2js">trunk/JSTests/stress/map-rehash-2.js</a></li>
<li><a href="#trunkJSTestsstressmaprehashjs">trunk/JSTests/stress/map-rehash.js</a></li>
</ul>
</div>
<div id="patch">
<h3>Diff</h3>
<a id="trunkJSTestsChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/JSTests/ChangeLog (205841 => 205842)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/JSTests/ChangeLog 2016-09-12 23:51:57 UTC (rev 205841)
+++ trunk/JSTests/ChangeLog 2016-09-13 00:14:59 UTC (rev 205842)
</span><span class="lines">@@ -1,3 +1,18 @@
</span><ins>+2016-09-12 Saam Barati <sbarati@apple.com>
+
+ HashMapImpl should take into account m_deleteCount in its load factor and it should be able to rehash the table to be smaller
+ https://bugs.webkit.org/show_bug.cgi?id=161640
+
+ Reviewed by Geoffrey Garen.
+
+ * microbenchmarks/map-rehash.js: Added.
+ * stress/map-delete.js: Added.
+ (assert):
+ * stress/map-rehash-2.js: Added.
+ (assert):
+ * stress/map-rehash.js: Added.
+ (assert):
+
</ins><span class="cx"> 2016-09-12 Yusuke Suzuki <utatane.tea@gmail.com>
</span><span class="cx">
</span><span class="cx"> Unreviewed, fix tests for different libm environments
</span></span></pre></div>
<a id="trunkJSTestsmicrobenchmarksmaprehashjs"></a>
<div class="addfile"><h4>Added: trunk/JSTests/microbenchmarks/map-rehash.js (0 => 205842)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/JSTests/microbenchmarks/map-rehash.js (rev 0)
+++ trunk/JSTests/microbenchmarks/map-rehash.js 2016-09-13 00:14:59 UTC (rev 205842)
</span><span class="lines">@@ -0,0 +1,21 @@
</span><ins>+function test(bias) {
+ let set = new Set;
+ let counter = 0;
+ for (let i = 0; i < 50000; i++) {
+ ++counter;
+ if (!set.size || Math.random() > bias) {
+ let key = counter;
+ set.add(key);
+ } else {
+ let keyToRemove = set[Symbol.iterator]().next().value;
+ set.delete(keyToRemove);
+ }
+ }
+}
+
+let start = Date.now();
+test(0.45);
+test(0.60);
+const verbose = false;
+if (verbose)
+ print(Date.now() - start);
</ins></span></pre></div>
<a id="trunkJSTestsstressmapdeletejs"></a>
<div class="addfile"><h4>Added: trunk/JSTests/stress/map-delete.js (0 => 205842)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/JSTests/stress/map-delete.js (rev 0)
+++ trunk/JSTests/stress/map-delete.js 2016-09-13 00:14:59 UTC (rev 205842)
</span><span class="lines">@@ -0,0 +1,19 @@
</span><ins>+function assert(b) {
+ if (!b)
+ throw new Error("Bad!")
+}
+
+let set = new Set;
+for (let i = 0; i < 50000; i++) {
+ assert(set.size === i);
+ set.add(i);
+ assert(set.has(i));
+}
+
+for (let i = 0; i < 50000; i++) {
+ assert(set.size === 50000 - i);
+ set.delete(i);
+ assert(!set.has(i));
+}
+
+assert(!set.size);
</ins></span></pre></div>
<a id="trunkJSTestsstressmaprehash2js"></a>
<div class="addfile"><h4>Added: trunk/JSTests/stress/map-rehash-2.js (0 => 205842)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/JSTests/stress/map-rehash-2.js (rev 0)
+++ trunk/JSTests/stress/map-rehash-2.js 2016-09-13 00:14:59 UTC (rev 205842)
</span><span class="lines">@@ -0,0 +1,13 @@
</span><ins>+function assert(b) {
+ if (!b)
+ throw new Error("Bad!")
+}
+
+let set = new Set;
+for (let i = 0; i < 64 + ((128 - 64)/2); i++) {
+ set.add(i);
+}
+
+for (let i = 0; i < 64 + ((128 - 64)/2); i++) {
+ set.delete(i);
+}
</ins></span></pre></div>
<a id="trunkJSTestsstressmaprehashjs"></a>
<div class="addfile"><h4>Added: trunk/JSTests/stress/map-rehash.js (0 => 205842)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/JSTests/stress/map-rehash.js (rev 0)
+++ trunk/JSTests/stress/map-rehash.js 2016-09-13 00:14:59 UTC (rev 205842)
</span><span class="lines">@@ -0,0 +1,26 @@
</span><ins>+function assert(b) {
+ if (!b)
+ throw new Error("Bad!")
+}
+
+let set = new Set;
+let items = [];
+for (let i = 0; i < 3000; i++) {
+ items.push(i);
+ set.add(i);
+}
+
+let counter = 1000000;
+while (items.length) {
+ if (Math.random() < 0.85) {
+ let item = items.pop();
+ let removed = set.delete(item);
+ assert(removed);
+ assert(items.length === set.size);
+ } else {
+ let newItem = ++counter;
+ items.push(newItem);
+ set.add(newItem);
+ assert(items.length === set.size);
+ }
+}
</ins></span></pre></div>
<a id="trunkSourceJavaScriptCoreChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/ChangeLog (205841 => 205842)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/ChangeLog 2016-09-12 23:51:57 UTC (rev 205841)
+++ trunk/Source/JavaScriptCore/ChangeLog 2016-09-13 00:14:59 UTC (rev 205842)
</span><span class="lines">@@ -1,3 +1,35 @@
</span><ins>+2016-09-12 Saam Barati <sbarati@apple.com>
+
+ HashMapImpl should take into account m_deleteCount in its load factor and it should be able to rehash the table to be smaller
+ https://bugs.webkit.org/show_bug.cgi?id=161640
+
+ Reviewed by Geoffrey Garen.
+
+ HashMapImpl now takes into account m_deleteCount in its load factor.
+ It now knows how to rehash to either decrease its capacity, stay at
+ the same capacity, or increase its capacity. The reason we can sometimes
+ stay at the same capacity is that we can reduce the load factor enough
+ by rehashing that growing isn't warranted. The reason for this is that
+ anytime we rehash, we remove all deleted sentinels from the buffer.
+ Therefore, staying at the same same capacity, when there are deleted entries,
+ can still reduce the load factor because it removes all deleted sentinels.
+
+ * runtime/HashMapImpl.h:
+ (JSC::HashMapBuffer::create):
+ (JSC::HashMapBuffer::reset):
+ (JSC::HashMapImpl::HashMapImpl):
+ (JSC::HashMapImpl::add):
+ (JSC::HashMapImpl::remove):
+ (JSC::HashMapImpl::size):
+ (JSC::HashMapImpl::clear):
+ (JSC::HashMapImpl::approximateSize):
+ (JSC::HashMapImpl::shouldRehashAfterAdd):
+ (JSC::HashMapImpl::shouldShrink):
+ (JSC::HashMapImpl::rehash):
+ (JSC::HashMapImpl::checkConsistency):
+ (JSC::HashMapImpl::makeAndSetNewBuffer):
+ (JSC::HashMapImpl::assertBufferIsEmpty):
+
</ins><span class="cx"> 2016-09-12 Benjamin Poulain <bpoulain@apple.com>
</span><span class="cx">
</span><span class="cx"> [JSC] Use GetArrayLength for JSArray.length even when the array type is undecided
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreruntimeHashMapImplh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/runtime/HashMapImpl.h (205841 => 205842)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/runtime/HashMapImpl.h 2016-09-12 23:51:57 UTC (rev 205841)
+++ trunk/Source/JavaScriptCore/runtime/HashMapImpl.h 2016-09-13 00:14:59 UTC (rev 205842)
</span><span class="lines">@@ -158,9 +158,14 @@
</span><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> HashMapBuffer* buffer = static_cast<HashMapBuffer*>(data);
</span><del>- memset(buffer, -1, allocationSize);
</del><ins>+ buffer->reset(capacity);
</ins><span class="cx"> return buffer;
</span><span class="cx"> }
</span><ins>+
+ ALWAYS_INLINE void reset(uint32_t capacity)
+ {
+ memset(this, -1, allocationSize(capacity));
+ }
</ins><span class="cx"> };
</span><span class="cx">
</span><span class="cx"> ALWAYS_INLINE static bool areKeysEqual(ExecState* exec, JSValue a, JSValue b)
</span><span class="lines">@@ -280,7 +285,7 @@
</span><span class="cx">
</span><span class="cx"> HashMapImpl(VM& vm, Structure* structure)
</span><span class="cx"> : Base(vm, structure)
</span><del>- , m_size(0)
</del><ins>+ , m_keyCount(0)
</ins><span class="cx"> , m_deleteCount(0)
</span><span class="cx"> , m_capacity(4)
</span><span class="cx"> {
</span><span class="lines">@@ -391,8 +396,10 @@
</span><span class="cx"> newTail->setPrev(vm, newEntry);
</span><span class="cx"> newTail->setDeleted(true);
</span><span class="cx"> newEntry->setNext(vm, newTail);
</span><del>- uint32_t newSize = ++m_size;
- if (2*newSize > m_capacity)
</del><ins>+
+ ++m_keyCount;
+
+ if (shouldRehashAfterAdd())
</ins><span class="cx"> rehash(exec);
</span><span class="cx"> }
</span><span class="cx">
</span><span class="lines">@@ -410,21 +417,25 @@
</span><span class="cx">
</span><span class="cx"> *bucket = deletedValue();
</span><span class="cx">
</span><del>- m_deleteCount++;
</del><ins>+ ++m_deleteCount;
+ ASSERT(m_keyCount > 0);
+ --m_keyCount;
</ins><span class="cx">
</span><ins>+ if (shouldShrink())
+ rehash(exec);
+
</ins><span class="cx"> return true;
</span><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> ALWAYS_INLINE uint32_t size() const
</span><span class="cx"> {
</span><del>- RELEASE_ASSERT(m_size >= m_deleteCount);
- return m_size - m_deleteCount;
</del><ins>+ return m_keyCount;
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> ALWAYS_INLINE void clear(ExecState* exec)
</span><span class="cx"> {
</span><span class="cx"> VM& vm = exec->vm();
</span><del>- m_size = 0;
</del><ins>+ m_keyCount = 0;
</ins><span class="cx"> m_deleteCount = 0;
</span><span class="cx"> HashMapBucketType* head = m_head.get();
</span><span class="cx"> HashMapBucketType* bucket = m_head->next();
</span><span class="lines">@@ -433,6 +444,7 @@
</span><span class="cx"> HashMapBucketType* next = bucket->next();
</span><span class="cx"> // We restart each iterator by pointing it to the head of the list.
</span><span class="cx"> bucket->setNext(vm, head);
</span><ins>+ bucket->setDeleted(true);
</ins><span class="cx"> bucket = next;
</span><span class="cx"> }
</span><span class="cx"> m_head->setNext(vm, m_tail.get());
</span><span class="lines">@@ -439,6 +451,7 @@
</span><span class="cx"> m_tail->setPrev(vm, m_head.get());
</span><span class="cx"> m_capacity = 4;
</span><span class="cx"> makeAndSetNewBuffer(exec, vm);
</span><ins>+ checkConsistency();
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> ALWAYS_INLINE size_t bufferSizeInBytes() const
</span><span class="lines">@@ -464,11 +477,21 @@
</span><span class="cx"> size_t size = sizeof(HashMapImpl);
</span><span class="cx"> size += bufferSizeInBytes();
</span><span class="cx"> size += 2 * sizeof(HashMapBucketType); // Head and tail members.
</span><del>- size += (m_deleteCount + m_size) * sizeof(HashMapBucketType); // Number of members on the list.
</del><ins>+ size += m_keyCount * sizeof(HashMapBucketType); // Number of members that are on the list.
</ins><span class="cx"> return size;
</span><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> private:
</span><ins>+ ALWAYS_INLINE uint32_t shouldRehashAfterAdd() const
+ {
+ return 2 * (m_keyCount + m_deleteCount) >= m_capacity;
+ }
+
+ ALWAYS_INLINE uint32_t shouldShrink() const
+ {
+ return 8 * m_keyCount <= m_capacity && m_capacity > 4;
+ }
+
</ins><span class="cx"> ALWAYS_INLINE HashMapBucketType** findBucketAlreadyHashedAndNormalized(ExecState* exec, JSValue key, uint32_t hash)
</span><span class="cx"> {
</span><span class="cx"> const uint32_t mask = m_capacity - 1;
</span><span class="lines">@@ -490,11 +513,35 @@
</span><span class="cx"> VM& vm = exec->vm();
</span><span class="cx"> auto scope = DECLARE_THROW_SCOPE(vm);
</span><span class="cx">
</span><del>- m_capacity = m_capacity * 2;
- makeAndSetNewBuffer(exec, vm);
- if (UNLIKELY(scope.exception()))
- return;
</del><ins>+ uint32_t oldCapacity = m_capacity;
+ if (shouldShrink()) {
+ m_capacity = m_capacity / 2;
+ ASSERT(m_capacity >= 4);
+ } else if (3 * m_keyCount <= m_capacity && m_capacity > 64) {
+ // We stay at the same size if rehashing would cause us to be no more than
+ // 1/3rd full. This comes up for programs like this:
+ // Say the hash table grew to a key count of 64, causing it to grow to a capacity of 256.
+ // Then, the table added 63 items. The load is now 127. Then, 63 items are deleted.
+ // The load is still 127. Then, another item is added. The load is now 128, and we
+ // decide that we need to rehash. The key count is 65, almost exactly what it was
+ // when we grew to a capacity of 256. We don't really need to grow to a capacity
+ // of 512 in this situation. Instead, we choose to rehash at the same size. This
+ // will bring the load down to 65. We rehash into the same size when we determine
+ // that the new load ratio will be under 1/3rd. (We also pick a minumum capacity
+ // at which this rule kicks in because otherwise we will be too sensitive to rehashing
+ // at the same capacity).
+ } else
+ m_capacity = (Checked<uint32_t>(m_capacity) * 2).unsafeGet();
</ins><span class="cx">
</span><ins>+ if (m_capacity != oldCapacity) {
+ makeAndSetNewBuffer(exec, vm);
+ if (UNLIKELY(scope.exception()))
+ return;
+ } else {
+ m_buffer.get()->reset(m_capacity);
+ assertBufferIsEmpty();
+ }
+
</ins><span class="cx"> HashMapBucketType* iter = m_head->next();
</span><span class="cx"> HashMapBucketType* end = m_tail.get();
</span><span class="cx"> const uint32_t mask = m_capacity - 1;
</span><span class="lines">@@ -513,8 +560,26 @@
</span><span class="cx"> buffer[index] = iter;
</span><span class="cx"> iter = iter->next();
</span><span class="cx"> }
</span><ins>+
+ m_deleteCount = 0;
+
+ checkConsistency();
</ins><span class="cx"> }
</span><span class="cx">
</span><ins>+ ALWAYS_INLINE void checkConsistency() const
+ {
+ if (!ASSERT_DISABLED) {
+ HashMapBucketType* iter = m_head->next();
+ HashMapBucketType* end = m_tail.get();
+ uint32_t size = 0;
+ while (iter != end) {
+ ++size;
+ iter = iter->next();
+ }
+ ASSERT(size == m_keyCount);
+ }
+ }
+
</ins><span class="cx"> void makeAndSetNewBuffer(ExecState* exec, VM& vm)
</span><span class="cx"> {
</span><span class="cx"> ASSERT(!(m_capacity & (m_capacity - 1)));
</span><span class="lines">@@ -524,9 +589,14 @@
</span><span class="cx"> return;
</span><span class="cx">
</span><span class="cx"> m_buffer.set(vm, this, buffer);
</span><ins>+ assertBufferIsEmpty();
+ }
+
+ ALWAYS_INLINE void assertBufferIsEmpty() const
+ {
</ins><span class="cx"> if (!ASSERT_DISABLED) {
</span><span class="cx"> for (unsigned i = 0; i < m_capacity; i++)
</span><del>- ASSERT(isEmpty(this->buffer()[i]));
</del><ins>+ ASSERT(isEmpty(buffer()[i]));
</ins><span class="cx"> }
</span><span class="cx"> }
</span><span class="cx">
</span><span class="lines">@@ -533,7 +603,7 @@
</span><span class="cx"> WriteBarrier<HashMapBucketType> m_head;
</span><span class="cx"> WriteBarrier<HashMapBucketType> m_tail;
</span><span class="cx"> AuxiliaryBarrier<HashMapBufferType*> m_buffer;
</span><del>- uint32_t m_size;
</del><ins>+ uint32_t m_keyCount;
</ins><span class="cx"> uint32_t m_deleteCount;
</span><span class="cx"> uint32_t m_capacity;
</span><span class="cx"> };
</span></span></pre>
</div>
</div>
</body>
</html>