about summary refs log tree commit diff
path: root/third_party/git/Documentation/technical/api-oid-array.txt
diff options
context:
space:
mode:
authorVincent Ambo <tazjin@google.com>2020-05-25T23·06+0100
committerVincent Ambo <tazjin@google.com>2020-05-25T23·06+0100
commit93ba78d6f4632ef1c5228965e3edc8c0faf88c1e (patch)
tree85730c182a9f5f492ade8e8ccdb1c2356f9900bd /third_party/git/Documentation/technical/api-oid-array.txt
parent6f8fbf4aa4b1654ab27d4829e114538761817de0 (diff)
revert(3p/git): Revert merge of git upstream at v2.26.2 r/852
This causes cgit to serve error pages, which is undesirable.

This reverts commit 5229c9b232de5bfa959ad6ebbb4c8192ac513352, reversing
changes made to f2b211131f2347342dde63975b09cf603149f1a3.
Diffstat (limited to 'third_party/git/Documentation/technical/api-oid-array.txt')
-rw-r--r--third_party/git/Documentation/technical/api-oid-array.txt90
1 files changed, 90 insertions, 0 deletions
diff --git a/third_party/git/Documentation/technical/api-oid-array.txt b/third_party/git/Documentation/technical/api-oid-array.txt
new file mode 100644
index 000000000000..c97428c2c349
--- /dev/null
+++ b/third_party/git/Documentation/technical/api-oid-array.txt
@@ -0,0 +1,90 @@
+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.
+
+Functions
+---------
+
+`oid_array_append`::
+	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).
+
+`oid_array_lookup`::
+	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.
+
+`oid_array_clear`::
+	Free all memory associated with the array and return it to the
+	initial, empty state.
+
+`oid_array_for_each`::
+	Iterate over each element of the list, executing the callback
+	function for each one. Does not sort the list, so any custom
+	hash order is retained. If the callback returns a non-zero
+	value, the iteration ends immediately and the callback's
+	return is propagated; otherwise, 0 is returned.
+
+`oid_array_for_each_unique`::
+	Iterate over each unique element of the list in sorted order,
+	but otherwise behave like `oid_array_for_each`. If the array
+	is not sorted, this function has the side effect of sorting
+	it.
+
+`oid_array_filter`::
+	Apply the callback function `want` to each entry in the array,
+	retaining only the entries for which the function returns true.
+	Preserve the order of the entries that are retained.
+
+Examples
+--------
+
+-----------------------------------------
+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);
+}
+-----------------------------------------