oidset.h

   1 #ifndef OIDSET_H
   2 #define OIDSET_H
   3
   4 #include "oidmap.h"
   5
   6 /**
   7  * This API is similar to sha1-array, in that it maintains a set of object ids
   8  * in a memory-efficient way. The major differences are:
   9  *
  10  *   1. It uses a hash, so we can do online duplicate removal, rather than
  11  *      sort-and-uniq at the end. This can reduce memory footprint if you have
  12  *      a large list of oids with many duplicates.
  13  *
  14  *   2. The per-unique-oid memory footprint is slightly higher due to hash
  15  *      table overhead.
  16  */
  17
  18 /**
  19  * A single oidset; should be zero-initialized (or use OIDSET_INIT).
  20  */
  21 struct oidset {
  22         struct oidmap map;
  23 };
  24
  25 #define OIDSET_INIT { OIDMAP_INIT }
  26
  27
  28 static inline void oidset_init(struct oidset *set, size_t initial_size)
  29 {
  30         oidmap_init(&set->map, initial_size);
  31 }
  32
  33 /**
  34  * Returns true iff `set` contains `oid`.
  35  */
  36 int oidset_contains(const struct oidset *set, const struct object_id *oid);
  37
  38 /**
  39  * Insert the oid into the set; a copy is made, so "oid" does not need
  40  * to persist after this function is called.
  41  *
  42  * Returns 1 if the oid was already in the set, 0 otherwise. This can be used
  43  * to perform an efficient check-and-add.
  44  */
  45 int oidset_insert(struct oidset *set, const struct object_id *oid);
  46
  47 /**
  48  * Remove the oid from the set.
  49  *
  50  * Returns 1 if the oid was present in the set, 0 otherwise.
  51  */
  52 int oidset_remove(struct oidset *set, const struct object_id *oid);
  53
  54 /**
  55  * Remove all entries from the oidset, freeing any resources associated with
  56  * it.
  57  */
  58 void oidset_clear(struct oidset *set);
  59
  60 struct oidset_iter {
  61         struct oidmap_iter m_iter;
  62 };
  63
  64 static inline void oidset_iter_init(struct oidset *set,
  65                                     struct oidset_iter *iter)
  66 {
  67         oidmap_iter_init(&set->map, &iter->m_iter);
  68 }
  69
  70 static inline struct object_id *oidset_iter_next(struct oidset_iter *iter)
  71 {
  72         struct oidmap_entry *e = oidmap_iter_next(&iter->m_iter);
  73         return e ? &e->oid : NULL;
  74 }
  75
  76 static inline struct object_id *oidset_iter_first(struct oidset *set,
  77                                                   struct oidset_iter *iter)
  78 {
  79         oidset_iter_init(set, iter);
  80         return oidset_iter_next(iter);
  81 }
  82
  83 #endif /* OIDSET_H */