oid-array.h

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