/src/git/oid-array.h

Source (jump to first uncovered line)
#ifndef OID_ARRAY_H
#define OID_ARRAY_H

#include "hash.h"

/**
 * The 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.
 *
 * 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 oid_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);
 *     }
 */

/**
 * 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.
 */
struct oid_array {
  struct object_id *oid;
  size_t nr;
  size_t alloc;
  int sorted;
};

#define OID_ARRAY_INIT { 0 }

/**
 * 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).
 */
void oid_array_append(struct oid_array *array, const struct object_id *oid);

/**
 * 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.
 */
int oid_array_lookup(struct oid_array *array, const struct object_id *oid);

/**
 * Free all memory associated with the array and return it to the initial,
 * empty state.
 */
void oid_array_clear(struct oid_array *array);

typedef int (*for_each_oid_fn)(const struct object_id *oid,
             void *data);
/**
 * 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.
 */
int oid_array_for_each(struct oid_array *array,
           for_each_oid_fn fn,
           void *data);

/**
 * 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.
 */
int oid_array_for_each_unique(struct oid_array *array,
            for_each_oid_fn fn,
            void *data);

/**
 * Apply the callback function `want` to each entry in the array, retaining
 * only the entries for which the function returns true. Preserve the order
 * of the entries that are retained.
 */
void oid_array_filter(struct oid_array *array,
          for_each_oid_fn want,
          void *cbdata);

/**
 * Sort the array in order of ascending object id.
 */
void oid_array_sort(struct oid_array *array);

/**
 * Find the next unique oid in the array after position "cur".
 * The array must be sorted for this to work. You can iterate
 * over unique elements like this:
 *
 *   size_t i;
 *   oid_array_sort(array);
 *   for (i = 0; i < array->nr; i = oid_array_next_unique(array, i))
 *  printf("%s", oid_to_hex(array->oids[i]);
 *
 * Non-unique iteration can just increment with "i++" to visit each element.
 */
static inline size_t oid_array_next_unique(struct oid_array *array, size_t cur)
{
  do {
    cur++;
  } while (cur < array->nr &&
     oideq(array->oid + cur, array->oid + cur - 1));
  return cur;
}

#endif /* OID_ARRAY_H */

Line	Count	Source (jump to first uncovered line)
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	0	#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	0	{
130	0	do {
131	0	cur++;
132	0	} while (cur < array->nr &&
133	0	oideq(array->oid + cur, array->oid + cur - 1));
134	0	return cur;
135	0	} Unexecuted instantiation: bisect.c:oid_array_next_unique Unexecuted instantiation: branch.c:oid_array_next_unique Unexecuted instantiation: cat-file.c:oid_array_next_unique Unexecuted instantiation: diff.c:oid_array_next_unique Unexecuted instantiation: fetch-pack.c:oid_array_next_unique Unexecuted instantiation: fetch.c:oid_array_next_unique Unexecuted instantiation: for-each-ref.c:oid_array_next_unique Unexecuted instantiation: index-pack.c:oid_array_next_unique Unexecuted instantiation: log.c:oid_array_next_unique Unexecuted instantiation: ls-remote.c:oid_array_next_unique Unexecuted instantiation: pack-objects.c:oid_array_next_unique Unexecuted instantiation: pull.c:oid_array_next_unique Unexecuted instantiation: receive-pack.c:oid_array_next_unique Unexecuted instantiation: send-pack.c:oid_array_next_unique Unexecuted instantiation: tag.c:oid_array_next_unique Unexecuted instantiation: verify-tag.c:oid_array_next_unique Unexecuted instantiation: combine-diff.c:oid_array_next_unique Unexecuted instantiation: commit-graph.c:oid_array_next_unique Unexecuted instantiation: commit-reach.c:oid_array_next_unique Unexecuted instantiation: connect.c:oid_array_next_unique Unexecuted instantiation: delta-islands.c:oid_array_next_unique Unexecuted instantiation: diffcore-rename.c:oid_array_next_unique Unexecuted instantiation: merge-ort.c:oid_array_next_unique Unexecuted instantiation: object-name.c:oid_array_next_unique Unexecuted instantiation: oid-array.c:oid_array_next_unique Unexecuted instantiation: pack-bitmap-write.c:oid_array_next_unique Unexecuted instantiation: parse-options-cb.c:oid_array_next_unique Unexecuted instantiation: pseudo-merge.c:oid_array_next_unique Unexecuted instantiation: read-cache.c:oid_array_next_unique Unexecuted instantiation: ref-filter.c:oid_array_next_unique Unexecuted instantiation: shallow.c:oid_array_next_unique Unexecuted instantiation: submodule.c:oid_array_next_unique Unexecuted instantiation: transport.c:oid_array_next_unique Unexecuted instantiation: upload-pack.c:oid_array_next_unique
136
137		#endif /* OID_ARRAY_H */

Coverage Report

Created: 2024-09-16 06:11