oid-array.h

   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 { NULL, 0, 0, 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 */