[libvirt] [PATCH 3/4] memory: make it easier to avoid quadratic scaling of arrays
Eric Blake
eblake at redhat.com
Sat Aug 14 16:23:55 UTC 2010
* src/util/memory.h (VIR_RESIZE_N): New macro.
* src/util/memory.c (virResizeN): New function.
* docs/hacking.html.in: Document it.
---
docs/hacking.html.in | 51 ++++++++++++++++++++++++++++++++++++++++++-------
src/util/memory.c | 35 ++++++++++++++++++++++++++++++++++
src/util/memory.h | 26 +++++++++++++++++++++++++
3 files changed, 104 insertions(+), 8 deletions(-)
diff --git a/docs/hacking.html.in b/docs/hacking.html.in
index 4cc92f4..4967184 100644
--- a/docs/hacking.html.in
+++ b/docs/hacking.html.in
@@ -347,7 +347,7 @@
}
</pre></li>
- <li><p>To allocate an array of objects</p>
+ <li><p>To allocate an array of objects:</p>
<pre>
virDomainPtr domains;
@@ -359,11 +359,11 @@
}
</pre></li>
- <li><p>To allocate an array of object pointers</p>
+ <li><p>To allocate an array of object pointers:</p>
<pre>
virDomainPtr *domains;
- int ndomains = 10;
+ size_t ndomains = 10;
if (VIR_ALLOC_N(domains, ndomains) < 0) {
virReportOOMError();
@@ -371,25 +371,60 @@
}
</pre></li>
- <li><p>To re-allocate the array of domains to be 10 elements longer</p>
+ <li><p>To re-allocate the array of domains to be 1 element
+ longer (however, note that repeatedly expanding an array by 1
+ scales quadratically, so this is recommended only for smaller
+ arrays):</p>
<pre>
- if (VIR_EXPAND_N(domains, ndomains, 10) < 0) {
+ virDomainPtr domains;
+ size_t ndomains = 0;
+
+ if (VIR_EXPAND_N(domains, ndomains, 1) < 0) {
virReportOOMError();
return NULL;
}
+ domains[ndomains - 1] = domain;
</pre></li>
- <li><p>To trim an array of domains to have one less element</p>
+ <li><p>To ensure an array has room to hold at least one more
+ element (this approach scales better, but requires tracking
+ allocation separately from usage)</p>
<pre>
+ virDomainPtr domains;
+ size_t ndomains = 0;
+ size_t ndomains_max = 0;
+
+ if (VIR_RESIZE_N(domains, ndomains_max, ndomains, 1) < 0) {
+ virReportOOMError();
+ return NULL;
+ }
+ domains[ndomains++] = domain;
+</pre></li>
+
+ <li><p>To trim an array of domains to have one less element:</p>
+
+<pre>
+ virDomainPtr domains;
+ size_t ndomains = 0;
+ size_t ndomains_max = 0;
+
VIR_SHRINK_N(domains, ndomains, 1);
</pre></li>
- <li><p>To free the domain</p>
+ <li><p>To free an array of domains:</p>
<pre>
- VIR_FREE(domain);
+ virDomainPtr domains;
+ size_t ndomains = x;
+ size_t ndomains_max = y;
+ size_t i;
+
+ for (i = 0; i < ndomains; i++)
+ VIR_FREE(domains[i]);
+ VIR_FREE(domains)
+ ndomains_max = ndomains = 0;
</pre></li>
</ul>
diff --git a/src/util/memory.c b/src/util/memory.c
index e95aa47..7485bcb 100644
--- a/src/util/memory.c
+++ b/src/util/memory.c
@@ -198,6 +198,41 @@ int virExpandN(void *ptrptr, size_t size, size_t *countptr, size_t add)
}
/**
+ * virResizeN:
+ * @ptrptr: pointer to pointer for address of allocated memory
+ * @size: number of bytes per element
+ * @allocptr: pointer to number of elements allocated in array
+ * @count: number of elements currently used in array
+ * @add: minimum number of additional elements to support in array
+ *
+ * If 'count' + 'add' is larger than '*allocptr', then Resize the
+ * block of memory in 'ptrptr' to be an array of at least 'count' +
+ * 'add' elements, each 'size' bytes in length. Update 'ptrptr' and
+ * 'allocptr' with the details of the newly allocated memory. On
+ * failure, 'ptrptr' and 'allocptr' are not changed. Any newly
+ * allocated memory in 'ptrptr' is zero-filled.
+ *
+ * Returns -1 on failure to allocate, zero on success
+ */
+int virResizeN(void *ptrptr, size_t size, size_t *allocptr, size_t count,
+ size_t add)
+{
+ size_t delta;
+
+ if (count + add < count) {
+ errno = ENOMEM;
+ return -1;
+ }
+ if (count + add <= *allocptr)
+ return 0;
+
+ delta = count + add - *allocptr;
+ if (delta < *allocptr / 2)
+ delta = *allocptr / 2;
+ return virExpandN(ptrptr, size, allocptr, delta);
+}
+
+/**
* virShrinkN:
* @ptrptr: pointer to pointer for address of allocated memory
* @size: number of bytes per element
diff --git a/src/util/memory.h b/src/util/memory.h
index 98ac2b3..2b39393 100644
--- a/src/util/memory.h
+++ b/src/util/memory.h
@@ -54,6 +54,9 @@ int virReallocN(void *ptrptr, size_t size, size_t count) ATTRIBUTE_RETURN_CHECK
ATTRIBUTE_NONNULL(1);
int virExpandN(void *ptrptr, size_t size, size_t *count, size_t add)
ATTRIBUTE_RETURN_CHECK ATTRIBUTE_NONNULL(1) ATTRIBUTE_NONNULL(3);
+int virResizeN(void *ptrptr, size_t size, size_t *alloc, size_t count,
+ size_t desired)
+ ATTRIBUTE_RETURN_CHECK ATTRIBUTE_NONNULL(1) ATTRIBUTE_NONNULL(3);
void virShrinkN(void *ptrptr, size_t size, size_t *count, size_t remove)
ATTRIBUTE_NONNULL(1) ATTRIBUTE_NONNULL(3);
int virAllocVar(void *ptrptr,
@@ -117,6 +120,29 @@ void virFree(void *ptrptr) ATTRIBUTE_NONNULL(1);
virExpandN(&(ptr), sizeof(*(ptr)), &(count), add)
/**
+ * VIR_RESIZE_N:
+ * @ptr: pointer to hold address of allocated memory
+ * @alloc: variable tracking number of elements currently allocated
+ * @count: number of elements currently in use
+ * @add: minimum number of elements to additionally support
+ *
+ * Blindly using VIR_EXPAND_N(array, alloc, 1) in a loop scales
+ * quadratically, because every iteration must copy contents from
+ * all prior iterations. But amortized linear scaling can be achieved
+ * by tracking allocation size separately from the number of used
+ * elements, and growing geometrically only as needed.
+ *
+ * If 'count' + 'add' is larger than 'count', then geometrically reallocate
+ * the array of 'alloc' elements, each sizeof(*ptr) bytes long, and store
+ * the address of allocated memory in 'ptr' and the new size in 'alloc'.
+ * The new elements are filled with zero.
+ *
+ * Returns -1 on failure, 0 on success
+ */
+# define VIR_RESIZE_N(ptr, alloc, count, add) \
+ virResizeN(&(ptr), sizeof(*(ptr)), &(alloc), count, add)
+
+/**
* VIR_SHRINK_N:
* @ptr: pointer to hold address of allocated memory
* @count: variable tracking number of elements currently allocated
--
1.7.2.1
More information about the libvir-list
mailing list