| 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. |
| |
| 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); |
| } |
| ----------------------------------------- |