| 1 | #ifndef OID_ARRAY_H |
| 2 | #define OID_ARRAY_H |
| 3 | |
| 4 | #include "hash.h" |
| 5 | |
| 6 | /** |
| 7 | * The API provides storage and manipulation of sets of object identifiers. |
| 8 | * The emphasis is on storage and processing efficiency, making them suitable |
| 9 | * for large lists. Note that the ordering of items is not preserved over some |
| 10 | * operations. |
| 11 | * |
| 12 | * Examples |
| 13 | * -------- |
| 14 | * ----------------------------------------- |
| 15 | * int print_callback(const struct object_id *oid, |
| 16 | * void *data) |
| 17 | * { |
| 18 | * printf("%s\n", oid_to_hex(oid)); |
| 19 | * return 0; // always continue |
| 20 | * } |
| 21 | * |
| 22 | * void some_func(void) |
| 23 | * { |
| 24 | * struct oid_array hashes = OID_ARRAY_INIT; |
| 25 | * struct object_id oid; |
| 26 | * |
| 27 | * // Read objects into our set |
| 28 | * while (read_object_from_stdin(oid.hash)) |
| 29 | * oid_array_append(&hashes, &oid); |
| 30 | * |
| 31 | * // Check if some objects are in our set |
| 32 | * while (read_object_from_stdin(oid.hash)) { |
| 33 | * if (oid_array_lookup(&hashes, &oid) >= 0) |
| 34 | * printf("it's in there!\n"); |
| 35 | * |
| 36 | * // Print the unique set of objects. We could also have |
| 37 | * // avoided adding duplicate objects in the first place, |
| 38 | * // but we would end up re-sorting the array repeatedly. |
| 39 | * // Instead, this will sort once and then skip duplicates |
| 40 | * // in linear time. |
| 41 | * |
| 42 | * oid_array_for_each_unique(&hashes, print_callback, NULL); |
| 43 | * } |
| 44 | */ |
| 45 | |
| 46 | /** |
| 47 | * A single array of object IDs. This should be initialized by assignment from |
| 48 | * `OID_ARRAY_INIT`. The `oid` member contains the actual data. The `nr` member |
| 49 | * contains the number of items in the set. The `alloc` and `sorted` members |
| 50 | * are used internally, and should not be needed by API callers. |
| 51 | */ |
| 52 | struct oid_array { |
| 53 | struct object_id *oid; |
| 54 | size_t nr; |
| 55 | size_t alloc; |
| 56 | int sorted; |
| 57 | }; |
| 58 | |
| 59 | #define OID_ARRAY_INIT { 0 } |
| 60 | |
| 61 | /** |
| 62 | * Add an item to the set. The object ID will be placed at the end of the array |
| 63 | * (but note that some operations below may lose this ordering). |
| 64 | */ |
| 65 | void oid_array_append(struct oid_array *array, const struct object_id *oid); |
| 66 | |
| 67 | /** |
| 68 | * Perform a binary search of the array for a specific object ID. If found, |
| 69 | * returns the offset (in number of elements) of the object ID. If not found, |
| 70 | * returns a negative integer. If the array is not sorted, this function has |
| 71 | * the side effect of sorting it. |
| 72 | */ |
| 73 | int oid_array_lookup(struct oid_array *array, const struct object_id *oid); |
| 74 | |
| 75 | /** |
| 76 | * Free all memory associated with the array and return it to the initial, |
| 77 | * empty state. |
| 78 | */ |
| 79 | void oid_array_clear(struct oid_array *array); |
| 80 | |
| 81 | typedef int (*for_each_oid_fn)(const struct object_id *oid, |
| 82 | void *data); |
| 83 | /** |
| 84 | * Iterate over each element of the list, executing the callback function for |
| 85 | * each one. Does not sort the list, so any custom hash order is retained. |
| 86 | * If the callback returns a non-zero value, the iteration ends immediately |
| 87 | * and the callback's return is propagated; otherwise, 0 is returned. |
| 88 | */ |
| 89 | int oid_array_for_each(struct oid_array *array, |
| 90 | for_each_oid_fn fn, |
| 91 | void *data); |
| 92 | |
| 93 | /** |
| 94 | * Iterate over each unique element of the list in sorted order, but otherwise |
| 95 | * behave like `oid_array_for_each`. If the array is not sorted, this function |
| 96 | * has the side effect of sorting it. |
| 97 | */ |
| 98 | int oid_array_for_each_unique(struct oid_array *array, |
| 99 | for_each_oid_fn fn, |
| 100 | void *data); |
| 101 | |
| 102 | /** |
| 103 | * Apply the callback function `want` to each entry in the array, retaining |
| 104 | * only the entries for which the function returns true. Preserve the order |
| 105 | * of the entries that are retained. |
| 106 | */ |
| 107 | void oid_array_filter(struct oid_array *array, |
| 108 | for_each_oid_fn want, |
| 109 | void *cbdata); |
| 110 | |
| 111 | /** |
| 112 | * Sort the array in order of ascending object id. |
| 113 | */ |
| 114 | void oid_array_sort(struct oid_array *array); |
| 115 | |
| 116 | /** |
| 117 | * Find the next unique oid in the array after position "cur". |
| 118 | * The array must be sorted for this to work. You can iterate |
| 119 | * over unique elements like this: |
| 120 | * |
| 121 | * size_t i; |
| 122 | * oid_array_sort(array); |
| 123 | * for (i = 0; i < array->nr; i = oid_array_next_unique(array, i)) |
| 124 | * printf("%s", oid_to_hex(array->oids[i]); |
| 125 | * |
| 126 | * Non-unique iteration can just increment with "i++" to visit each element. |
| 127 | */ |
| 128 | static inline size_t oid_array_next_unique(struct oid_array *array, size_t cur) |
| 129 | { |
| 130 | do { |
| 131 | cur++; |
| 132 | } while (cur < array->nr && |
| 133 | oideq(array->oid + cur, array->oid + cur - 1)); |
| 134 | return cur; |
| 135 | } |
| 136 | |
| 137 | #endif /* OID_ARRAY_H */ |