git.oblomov.eu Git - git/blob - pack-objects.h

   1 #ifndef PACK_OBJECTS_H
   2 #define PACK_OBJECTS_H
   3
   4 #include "object-store.h"
   5
   6 #define OE_DFS_STATE_BITS       2
   7 #define OE_DEPTH_BITS           12
   8 #define OE_IN_PACK_BITS         10
   9
  10 /*
  11  * State flags for depth-first search used for analyzing delta cycles.
  12  *
  13  * The depth is measured in delta-links to the base (so if A is a delta
  14  * against B, then A has a depth of 1, and B a depth of 0).
  15  */
  16 enum dfs_state {
  17         DFS_NONE = 0,
  18         DFS_ACTIVE,
  19         DFS_DONE,
  20         DFS_NUM_STATES
  21 };
  22
  23 /*
  24  * basic object info
  25  * -----------------
  26  * idx.oid is filled up before delta searching starts. idx.crc32 is
  27  * only valid after the object is written out and will be used for
  28  * generating the index. idx.offset will be both gradually set and
  29  * used in writing phase (base objects get offset first, then deltas
  30  * refer to them)
  31  *
  32  * "size" is the uncompressed object size. Compressed size of the raw
  33  * data for an object in a pack is not stored anywhere but is computed
  34  * and made available when reverse .idx is made.
  35  *
  36  * "hash" contains a path name hash which is used for sorting the
  37  * delta list and also during delta searching. Once prepare_pack()
  38  * returns it's no longer needed.
  39  *
  40  * source pack info
  41  * ----------------
  42  * The (in_pack, in_pack_offset) tuple contains the location of the
  43  * object in the source pack. in_pack_header_size allows quickly
  44  * skipping the header and going straight to the zlib stream.
  45  *
  46  * "type" and "in_pack_type" both describe object type. in_pack_type
  47  * may contain a delta type, while type is always the canonical type.
  48  *
  49  * deltas
  50  * ------
  51  * Delta links (delta, delta_child and delta_sibling) are created to
  52  * reflect that delta graph from the source pack then updated or added
  53  * during delta searching phase when we find better deltas.
  54  *
  55  * delta_child and delta_sibling are last needed in
  56  * compute_write_order(). "delta" and "delta_size" must remain valid
  57  * at object writing phase in case the delta is not cached.
  58  *
  59  * If a delta is cached in memory and is compressed, delta_data points
  60  * to the data and z_delta_size contains the compressed size. If it's
  61  * uncompressed [1], z_delta_size must be zero. delta_size is always
  62  * the uncompressed size and must be valid even if the delta is not
  63  * cached.
  64  *
  65  * [1] during try_delta phase we don't bother with compressing because
  66  * the delta could be quickly replaced with a better one.
  67  */
  68 struct object_entry {
  69         struct pack_idx_entry idx;
  70         unsigned long size;     /* uncompressed size */
  71         unsigned in_pack_idx:OE_IN_PACK_BITS;   /* already in pack */
  72         off_t in_pack_offset;
  73         struct object_entry *delta;     /* delta base object */
  74         struct object_entry *delta_child; /* deltified objects who bases me */
  75         struct object_entry *delta_sibling; /* other deltified objects who
  76                                              * uses the same base as me
  77                                              */
  78         void *delta_data;       /* cached delta (uncompressed) */
  79         unsigned long delta_size;       /* delta data size (uncompressed) */
  80         unsigned long z_delta_size;     /* delta data size (compressed) */
  81         unsigned type_:TYPE_BITS;
  82         unsigned in_pack_type:TYPE_BITS; /* could be delta */
  83         unsigned type_valid:1;
  84         uint32_t hash;                  /* name hint hash */
  85         unsigned char in_pack_header_size;
  86         unsigned preferred_base:1; /*
  87                                     * we do not pack this, but is available
  88                                     * to be used as the base object to delta
  89                                     * objects against.
  90                                     */
  91         unsigned no_try_delta:1;
  92         unsigned tagged:1; /* near the very tip of refs */
  93         unsigned filled:1; /* assigned write-order */
  94         unsigned dfs_state:OE_DFS_STATE_BITS;
  95         unsigned depth:OE_DEPTH_BITS;
  96 };
  97
  98 struct packing_data {
  99         struct object_entry *objects;
 100         uint32_t nr_objects, nr_alloc;
 101
 102         int32_t *index;
 103         uint32_t index_size;
 104
 105         unsigned int *in_pack_pos;
 106
 107         /*
 108          * Only one of these can be non-NULL and they have different
 109          * sizes. if in_pack_by_idx is allocated, oe_in_pack() returns
 110          * the pack of an object using in_pack_idx field. If not,
 111          * in_pack[] array is used the same way as in_pack_pos[]
 112          */
 113         struct packed_git **in_pack_by_idx;
 114         struct packed_git **in_pack;
 115 };
 116
 117 void prepare_packing_data(struct packing_data *pdata);
 118 struct object_entry *packlist_alloc(struct packing_data *pdata,
 119                                     const unsigned char *sha1,
 120                                     uint32_t index_pos);
 121
 122 struct object_entry *packlist_find(struct packing_data *pdata,
 123                                    const unsigned char *sha1,
 124                                    uint32_t *index_pos);
 125
 126 static inline uint32_t pack_name_hash(const char *name)
 127 {
 128         uint32_t c, hash = 0;
 129
 130         if (!name)
 131                 return 0;
 132
 133         /*
 134          * This effectively just creates a sortable number from the
 135          * last sixteen non-whitespace characters. Last characters
 136          * count "most", so things that end in ".c" sort together.
 137          */
 138         while ((c = *name++) != 0) {
 139                 if (isspace(c))
 140                         continue;
 141                 hash = (hash >> 2) + (c << 24);
 142         }
 143         return hash;
 144 }
 145
 146 static inline enum object_type oe_type(const struct object_entry *e)
 147 {
 148         return e->type_valid ? e->type_ : OBJ_BAD;
 149 }
 150
 151 static inline void oe_set_type(struct object_entry *e,
 152                                enum object_type type)
 153 {
 154         if (type >= OBJ_ANY)
 155                 BUG("OBJ_ANY cannot be set in pack-objects code");
 156
 157         e->type_valid = type >= OBJ_NONE;
 158         e->type_ = (unsigned)type;
 159 }
 160
 161 static inline unsigned int oe_in_pack_pos(const struct packing_data *pack,
 162                                           const struct object_entry *e)
 163 {
 164         return pack->in_pack_pos[e - pack->objects];
 165 }
 166
 167 static inline void oe_set_in_pack_pos(const struct packing_data *pack,
 168                                       const struct object_entry *e,
 169                                       unsigned int pos)
 170 {
 171         pack->in_pack_pos[e - pack->objects] = pos;
 172 }
 173
 174 static inline struct packed_git *oe_in_pack(const struct packing_data *pack,
 175                                             const struct object_entry *e)
 176 {
 177         if (pack->in_pack_by_idx)
 178                 return pack->in_pack_by_idx[e->in_pack_idx];
 179         else
 180                 return pack->in_pack[e - pack->objects];
 181 }
 182
 183 void oe_map_new_pack(struct packing_data *pack,
 184                      struct packed_git *p);
 185 static inline void oe_set_in_pack(struct packing_data *pack,
 186                                   struct object_entry *e,
 187                                   struct packed_git *p)
 188 {
 189         if (!p->index)
 190                 oe_map_new_pack(pack, p);
 191         if (pack->in_pack_by_idx)
 192                 e->in_pack_idx = p->index;
 193         else
 194                 pack->in_pack[e - pack->objects] = p;
 195 }
 196
 197 #endif