diff options
author | Junio C Hamano <gitster@pobox.com> | 2017-04-19 21:37:13 -0700 |
---|---|---|
committer | Junio C Hamano <gitster@pobox.com> | 2017-04-19 21:37:13 -0700 |
commit | b1081e4004091947b6c6a806625addd1cbba61b7 (patch) | |
tree | 2cf8dfc6a5e33499b5dbcc8b3e94dbe311e2acfa /Documentation/technical/api-oid-array.txt | |
parent | c703555cc89cf6aedf549a1233b242d8cb8e0f20 (diff) | |
parent | e239dabb1465d3ff927840b4fff15150a2170b4e (diff) | |
download | git-b1081e4004091947b6c6a806625addd1cbba61b7.tar.gz git-b1081e4004091947b6c6a806625addd1cbba61b7.tar.xz |
Merge branch 'bc/object-id'
Conversion from unsigned char [40] to struct object_id continues.
* bc/object-id:
Documentation: update and rename api-sha1-array.txt
Rename sha1_array to oid_array
Convert sha1_array_for_each_unique and for_each_abbrev to object_id
Convert sha1_array_lookup to take struct object_id
Convert remaining callers of sha1_array_lookup to object_id
Make sha1_array_append take a struct object_id *
sha1-array: convert internal storage for struct sha1_array to object_id
builtin/pull: convert to struct object_id
submodule: convert check_for_new_submodule_commits to object_id
sha1_name: convert disambiguate_hint_fn to take object_id
sha1_name: convert struct disambiguate_state to object_id
test-sha1-array: convert most code to struct object_id
parse-options-cb: convert sha1_array_append caller to struct object_id
fsck: convert init_skiplist to struct object_id
builtin/receive-pack: convert portions to struct object_id
builtin/pull: convert portions to struct object_id
builtin/diff: convert to struct object_id
Convert GIT_SHA1_RAWSZ used for allocation to GIT_MAX_RAWSZ
Convert GIT_SHA1_HEXSZ used for allocation to GIT_MAX_HEXSZ
Define new hash-size constants for allocating memory
Diffstat (limited to 'Documentation/technical/api-oid-array.txt')
-rw-r--r-- | Documentation/technical/api-oid-array.txt | 80 |
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 000000000..b0c11f868 --- /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. + +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_unique`:: + 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. + +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); +} +----------------------------------------- |