path: root/Documentation/technical/api-oid-array.txt
diff options
authorbrian m. carlson <>2017-03-31 01:40:01 (GMT)
committerJunio C Hamano <>2017-03-31 15:33:56 (GMT)
commite239dabb1465d3ff927840b4fff15150a2170b4e (patch)
tree570d3346ab209ca0859bea3bdf72e603fc5a9043 /Documentation/technical/api-oid-array.txt
parent910650d2f8755359ab7b1f0e2a2d576c06a68091 (diff)
Documentation: update and rename api-sha1-array.txt
Since the structure and functions have changed names, update the code examples and the documentation. Rename the file to match the new name of the API. Signed-off-by: brian m. carlson <> Signed-off-by: Junio C Hamano <>
Diffstat (limited to 'Documentation/technical/api-oid-array.txt')
1 files changed, 80 insertions, 0 deletions
diff --git a/Documentation/technical/api-oid-array.txt b/Documentation/technical/api-oid-array.txt
new file mode 100644
index 0000000..b0c11f8
--- /dev/null
+++ b/Documentation/technical/api-oid-array.txt
@@ -0,0 +1,80 @@
+oid-array API
+The oid-array API provides storage and manipulation of sets of object
+identifiers. The emphasis is on storage and processing efficiency,
+making them suitable for large lists. Note that the ordering of items is
+not preserved over some operations.
+Data Structures
+`struct oid_array`::
+ A single array of object IDs. This should be initialized by
+ assignment from `OID_ARRAY_INIT`. The `oid` member contains
+ the actual data. The `nr` member contains the number of items in
+ the set. The `alloc` and `sorted` members are used internally,
+ and should not be needed by API callers.
+ Add an item to the set. The object ID will be placed at the end of
+ the array (but note that some operations below may lose this
+ ordering).
+ Perform a binary search of the array for a specific object ID.
+ If found, returns the offset (in number of elements) of the
+ object ID. If not found, returns a negative integer. If the array
+ is not sorted, this function has the side effect of sorting it.
+ Free all memory associated with the array and return it to the
+ initial, empty state.
+ Efficiently iterate over each unique element of the list,
+ executing the callback function for each one. If the array is
+ not sorted, this function has the side effect of sorting it. If
+ the callback returns a non-zero value, the iteration ends
+ immediately and the callback's return is propagated; otherwise,
+ 0 is returned.
+int print_callback(const struct object_id *oid,
+ void *data)
+ printf("%s\n", oid_to_hex(oid));
+ return 0; /* always continue */
+void some_func(void)
+ struct sha1_array hashes = OID_ARRAY_INIT;
+ struct object_id oid;
+ /* Read objects into our set */
+ while (read_object_from_stdin(oid.hash))
+ oid_array_append(&hashes, &oid);
+ /* Check if some objects are in our set */
+ while (read_object_from_stdin(oid.hash)) {
+ if (oid_array_lookup(&hashes, &oid) >= 0)
+ printf("it's in there!\n");
+ /*
+ * Print the unique set of objects. We could also have
+ * avoided adding duplicate objects in the first place,
+ * but we would end up re-sorting the array repeatedly.
+ * Instead, this will sort once and then skip duplicates
+ * in linear time.
+ */
+ oid_array_for_each_unique(&hashes, print_callback, NULL);