#include "builtin.h"

#include "cache.h"

#include "attr.h"

#include "object.h"

#include "blob.h"

#include "commit.h"

#include "tag.h"

#include "tree.h"

#include "delta.h"

#include "pack.h"

#include "pack-revindex.h"

#include "csum-file.h"

#include "tree-walk.h"

#include "diff.h"

#include "revision.h"

#include "list-objects.h"

#include "progress.h"

#include "refs.h"

#ifdef THREADED_DELTA_SEARCH

#include "thread-utils.h"

#include <pthread.h>

#endif

static const char pack_usage[] = "\

git pack-objects [{ -q | --progress | --all-progress }] \n\

[--max-pack-size=N] [--local] [--incremental] \n\

[--window=N] [--window-memory=N] [--depth=N] \n\

[--no-reuse-delta] [--no-reuse-object] [--delta-base-offset] \n\

[--threads=N] [--non-empty] [--revs [--unpacked | --all]*] [--reflog] \n\

[--stdout | base-name] [--include-tag] \n\

[--keep-unreachable | --unpack-unreachable] \n\

[<ref-list | <object-list]";

struct object_entry {

};

/*

* Objects we are going to pack are collected in objects array (dynamically

* expanded). nr_objects & nr_alloc controls this array. They are stored

* in the order we see -- typically rev-list --objects order that gives us

* nice "minimum seek" order.

*/

static struct object_entry *objects;

static struct pack_idx_entry **written_list;

static uint32_t nr_objects, nr_alloc, nr_result, nr_written;

static int non_empty;

static int reuse_delta = 1, reuse_object = 1;

static int keep_unreachable, unpack_unreachable, include_tag;

static int local;

static int incremental;

static int ignore_packed_keep;

static int allow_ofs_delta;

static const char *base_name;

static int progress = 1;

static int window = 10;

static uint32_t pack_size_limit, pack_size_limit_cfg;

static int depth = 50;

static int delta_search_threads = 1;

static int pack_to_stdout;

static int num_preferred_base;

static struct progress *progress_state;

static int pack_compression_level = Z_DEFAULT_COMPRESSION;

static int pack_compression_seen;

static unsigned long delta_cache_size = 0;

static unsigned long max_delta_cache_size = 0;

static unsigned long cache_max_small_delta_size = 1000;

static unsigned long window_memory_limit = 0;

/*

* The object names in objects array are hashed with this hashtable,

* to help looking up the entry by object name.

* This hashtable is built after all the objects are seen.

*/

static int *object_ix;

static int object_ix_hashsz;

/*

* stats

*/

static uint32_t written, written_delta;

static uint32_t reused, reused_delta;

static void *get_delta(struct object_entry *entry)

{

unsigned long size, base_size, delta_size;

void *buf, *base_buf, *delta_buf;

enum object_type type;

buf = read_sha1_file(entry->idx.sha1, &type, &size);

if (!buf)

die("unable to read %s", sha1_to_hex(entry->idx.sha1));

base_buf = read_sha1_file(entry->delta->idx.sha1, &type, &base_size);

if (!base_buf)

die("unable to read %s", sha1_to_hex(entry->delta->idx.sha1));

delta_buf = diff_delta(base_buf, base_size,

buf, size, &delta_size, 0);

if (!delta_buf || delta_size != entry->delta_size)

die("delta size changed");

free(buf);

free(base_buf);

return delta_buf;

}

static unsigned long do_compress(void **pptr, unsigned long size)

{

z_stream stream;

void *in, *out;

unsigned long maxsize;

memset(&stream, 0, sizeof(stream));

deflateInit(&stream, pack_compression_level);

maxsize = deflateBound(&stream, size);

in = *pptr;

out = xmalloc(maxsize);

*pptr = out;

stream.next_in = in;

stream.avail_in = size;

stream.next_out = out;

stream.avail_out = maxsize;

while (deflate(&stream, Z_FINISH) == Z_OK)

; /* nothing */

deflateEnd(&stream);

free(in);

return stream.total_out;

}

/*

* The per-object header is a pretty dense thing, which is

* - first byte: low four bits are "size", then three bits of "type",

* and the high bit is "size continues".

* - each byte afterwards: low seven bits are size continuation,

* with the high bit being "size continues"

*/

static int encode_header(enum object_type type, unsigned long size, unsigned char *hdr)

{

int n = 1;

unsigned char c;

if (type < OBJ_COMMIT || type > OBJ_REF_DELTA)

die("bad type %d", type);

c = (type << 4) | (size & 15);

size >>= 4;

while (size) {

*hdr++ = c | 0x80;

c = size & 0x7f;

size >>= 7;

n++;

}

*hdr = c;

return n;

}

/*

* we are going to reuse the existing object data as is. make

* sure it is not corrupt.

*/

static int check_pack_inflate(struct packed_git *p,

unsigned long expect)

{

z_stream stream;

unsigned char fakebuf[4096], *in;

int st;

memset(&stream, 0, sizeof(stream));

git_inflate_init(&stream);

do {

in = use_pack(p, w_curs, offset, &stream.avail_in);

stream.next_in = in;

stream.next_out = fakebuf;

stream.avail_out = sizeof(fakebuf);

st = git_inflate(&stream, Z_FINISH);

offset += stream.next_in - in;

} while (st == Z_OK || st == Z_BUF_ERROR);

git_inflate_end(&stream);

return (st == Z_STREAM_END &&

stream.total_out == expect &&

stream.total_in == len) ? 0 : -1;

}

static void copy_pack_data(struct sha1file *f,

off_t len)

{

unsigned char *in;

unsigned int avail;

while (len) {

in = use_pack(p, w_curs, offset, &avail);

if (avail > len)

avail = (unsigned int)len;

sha1write(f, in, avail);

offset += avail;

len -= avail;

}

}

static unsigned long write_object(struct sha1file *f,

struct object_entry *entry,

off_t write_offset)

{

unsigned long size, limit, datalen;

void *buf;

unsigned char header[10], dheader[10];

unsigned hdrlen;

enum object_type type;

int usable_delta, to_reuse;

if (!pack_to_stdout)

crc32_begin(f);

type = entry->type;

/* write limit if limited packsize and not first object */

if (!pack_size_limit || !nr_written)

limit = 0;

else if (pack_size_limit <= write_offset)

/*

* the earlier object did not fit the limit; avoid

* mistaking this with unlimited (i.e. limit = 0).

*/

limit = 1;

else

limit = pack_size_limit - write_offset;

if (!entry->delta)

usable_delta = 0; /* no delta */

else if (!pack_size_limit)

usable_delta = 1; /* unlimited packfile */

else if (entry->delta->idx.offset == (off_t)-1)

usable_delta = 0; /* base was written to another pack */

else if (entry->delta->idx.offset)

usable_delta = 1; /* base already exists in this pack */

else

usable_delta = 0; /* base could end up in another pack */

if (!reuse_object)

to_reuse = 0; /* explicit */

else if (!entry->in_pack)

to_reuse = 0; /* can't reuse what we don't have */

else if (type == OBJ_REF_DELTA || type == OBJ_OFS_DELTA)

/* check_object() decided it for us ... */

to_reuse = usable_delta;

/* ... but pack split may override that */

else if (type != entry->in_pack_type)

to_reuse = 0; /* pack has delta which is unusable */

else if (entry->delta)

to_reuse = 0; /* we want to pack afresh */

else

to_reuse = 1; /* we have it in-pack undeltified,

* and we do not need to deltify it.

*/

if (!to_reuse) {

no_reuse:

if (!usable_delta) {

buf = read_sha1_file(entry->idx.sha1, &type, &size);

if (!buf)

die("unable to read %s", sha1_to_hex(entry->idx.sha1));

/*

* make sure no cached delta data remains from a

* previous attempt before a pack split occured.

*/

free(entry->delta_data);

entry->delta_data = NULL;

entry->z_delta_size = 0;

} else if (entry->delta_data) {

size = entry->delta_size;

buf = entry->delta_data;

entry->delta_data = NULL;

type = (allow_ofs_delta && entry->delta->idx.offset) ?

OBJ_OFS_DELTA : OBJ_REF_DELTA;

} else {

buf = get_delta(entry);

size = entry->delta_size;

type = (allow_ofs_delta && entry->delta->idx.offset) ?

OBJ_OFS_DELTA : OBJ_REF_DELTA;

}

if (entry->z_delta_size)

datalen = entry->z_delta_size;

else

datalen = do_compress(&buf, size);

/*

* The object header is a byte of 'type' followed by zero or

* more bytes of length.

*/

hdrlen = encode_header(type, size, header);

if (type == OBJ_OFS_DELTA) {

/*

* Deltas with relative base contain an additional

* encoding of the relative offset for the delta

* base from this object's position in the pack.

*/

off_t ofs = entry->idx.offset - entry->delta->idx.offset;

unsigned pos = sizeof(dheader) - 1;

dheader[pos] = ofs & 127;

while (ofs >>= 7)

dheader[--pos] = 128 | (--ofs & 127);

if (limit && hdrlen + sizeof(dheader) - pos + datalen + 20 >= limit) {

free(buf);

return 0;

}

sha1write(f, header, hdrlen);

sha1write(f, dheader + pos, sizeof(dheader) - pos);

hdrlen += sizeof(dheader) - pos;

} else if (type == OBJ_REF_DELTA) {

/*

* Deltas with a base reference contain

* an additional 20 bytes for the base sha1.

*/

if (limit && hdrlen + 20 + datalen + 20 >= limit) {

free(buf);

return 0;

}

sha1write(f, header, hdrlen);

sha1write(f, entry->delta->idx.sha1, 20);

hdrlen += 20;

} else {

if (limit && hdrlen + datalen + 20 >= limit) {

free(buf);

return 0;

}

sha1write(f, header, hdrlen);

}

sha1write(f, buf, datalen);

free(buf);

}

else {

struct packed_git *p = entry->in_pack;

struct pack_window *w_curs = NULL;

struct revindex_entry *revidx;

off_t offset;

if (entry->delta)

type = (allow_ofs_delta && entry->delta->idx.offset) ?

OBJ_OFS_DELTA : OBJ_REF_DELTA;

hdrlen = encode_header(type, entry->size, header);

offset = entry->in_pack_offset;

revidx = find_pack_revindex(p, offset);

datalen = revidx[1].offset - offset;

if (!pack_to_stdout && p->index_version > 1 &&

check_pack_crc(p, &w_curs, offset, datalen, revidx->nr)) {

error("bad packed object CRC for %s", sha1_to_hex(entry->idx.sha1));

unuse_pack(&w_curs);

goto no_reuse;

}

offset += entry->in_pack_header_size;

datalen -= entry->in_pack_header_size;

if (!pack_to_stdout && p->index_version == 1 &&

check_pack_inflate(p, &w_curs, offset, datalen, entry->size)) {

error("corrupt packed object for %s", sha1_to_hex(entry->idx.sha1));

unuse_pack(&w_curs);

goto no_reuse;

}

if (type == OBJ_OFS_DELTA) {

off_t ofs = entry->idx.offset - entry->delta->idx.offset;

unsigned pos = sizeof(dheader) - 1;

dheader[pos] = ofs & 127;

while (ofs >>= 7)

dheader[--pos] = 128 | (--ofs & 127);

if (limit && hdrlen + sizeof(dheader) - pos + datalen + 20 >= limit) {

unuse_pack(&w_curs);

return 0;

}

sha1write(f, header, hdrlen);

sha1write(f, dheader + pos, sizeof(dheader) - pos);

hdrlen += sizeof(dheader) - pos;

reused_delta++;

} else if (type == OBJ_REF_DELTA) {

if (limit && hdrlen + 20 + datalen + 20 >= limit) {

unuse_pack(&w_curs);

return 0;

}

sha1write(f, header, hdrlen);

sha1write(f, entry->delta->idx.sha1, 20);

hdrlen += 20;

reused_delta++;

} else {

if (limit && hdrlen + datalen + 20 >= limit) {

unuse_pack(&w_curs);

return 0;

}

sha1write(f, header, hdrlen);

}

copy_pack_data(f, p, &w_curs, offset, datalen);

unuse_pack(&w_curs);

reused++;

}

if (usable_delta)

written_delta++;

written++;

if (!pack_to_stdout)

entry->idx.crc32 = crc32_end(f);

return hdrlen + datalen;

}

static int write_one(struct sha1file *f,

struct object_entry *e,

off_t *offset)

{

unsigned long size;

/* offset is non zero if object is written already. */

if (e->idx.offset || e->preferred_base)

return 1;

/* if we are deltified, write out base object first. */

if (e->delta && !write_one(f, e->delta, offset))

return 0;

e->idx.offset = *offset;

size = write_object(f, e, *offset);

if (!size) {

e->idx.offset = 0;

return 0;

}

written_list[nr_written++] = &e->idx;

/* make sure off_t is sufficiently large not to wrap */

if (*offset > *offset + size)

die("pack too large for current definition of off_t");

*offset += size;

return 1;

}

/* forward declaration for write_pack_file */

static int adjust_perm(const char *path, mode_t mode);

static void write_pack_file(void)

{

uint32_t i = 0, j;

struct sha1file *f;

off_t offset;

struct pack_header hdr;

uint32_t nr_remaining = nr_result;

time_t last_mtime = 0;

if (progress > pack_to_stdout)

progress_state = start_progress("Writing objects", nr_result);

written_list = xmalloc(nr_objects * sizeof(*written_list));

do {

unsigned char sha1[20];

char *pack_tmp_name = NULL;

if (pack_to_stdout) {

f = sha1fd_throughput(1, "<stdout>", progress_state);

} else {

char tmpname[PATH_MAX];

int fd;

fd = odb_mkstemp(tmpname, sizeof(tmpname),

"pack/tmp_pack_XXXXXX");

pack_tmp_name = xstrdup(tmpname);

f = sha1fd(fd, pack_tmp_name);

}

hdr.hdr_signature = htonl(PACK_SIGNATURE);

hdr.hdr_version = htonl(PACK_VERSION);

hdr.hdr_entries = htonl(nr_remaining);

sha1write(f, &hdr, sizeof(hdr));

offset = sizeof(hdr);

nr_written = 0;

for (; i < nr_objects; i++) {

if (!write_one(f, objects + i, &offset))

break;

display_progress(progress_state, written);

}

/*

* Did we write the wrong # entries in the header?

* If so, rewrite it like in fast-import

*/

if (pack_to_stdout) {

sha1close(f, sha1, CSUM_CLOSE);

} else if (nr_written == nr_remaining) {

sha1close(f, sha1, CSUM_FSYNC);

} else {

int fd = sha1close(f, sha1, 0);

fixup_pack_header_footer(fd, sha1, pack_tmp_name,

nr_written, sha1, offset);

close(fd);

}

if (!pack_to_stdout) {

mode_t mode = umask(0);

struct stat st;

char *idx_tmp_name, tmpname[PATH_MAX];

umask(mode);

mode = 0444 & ~mode;

idx_tmp_name = write_idx_file(NULL, written_list,

nr_written, sha1);

snprintf(tmpname, sizeof(tmpname), "%s-%s.pack",

base_name, sha1_to_hex(sha1));

free_pack_by_name(tmpname);

if (adjust_perm(pack_tmp_name, mode))

die("unable to make temporary pack file readable: %s",

strerror(errno));

if (rename(pack_tmp_name, tmpname))

die("unable to rename temporary pack file: %s",

strerror(errno));

/*

* Packs are runtime accessed in their mtime

* order since newer packs are more likely to contain

* younger objects. So if we are creating multiple

* packs then we should modify the mtime of later ones

* to preserve this property.

*/

if (stat(tmpname, &st) < 0) {

warning("failed to stat %s: %s",

tmpname, strerror(errno));

} else if (!last_mtime) {

last_mtime = st.st_mtime;

} else {

struct utimbuf utb;

utb.actime = st.st_atime;

utb.modtime = --last_mtime;

if (utime(tmpname, &utb) < 0)

warning("failed utime() on %s: %s",

tmpname, strerror(errno));

}

snprintf(tmpname, sizeof(tmpname), "%s-%s.idx",

base_name, sha1_to_hex(sha1));

if (adjust_perm(idx_tmp_name, mode))

die("unable to make temporary index file readable: %s",

strerror(errno));

if (rename(idx_tmp_name, tmpname))

die("unable to rename temporary index file: %s",

strerror(errno));

free(idx_tmp_name);

free(pack_tmp_name);

puts(sha1_to_hex(sha1));

}

/* mark written objects as written to previous pack */

for (j = 0; j < nr_written; j++) {

written_list[j]->offset = (off_t)-1;

}

nr_remaining -= nr_written;

} while (nr_remaining && i < nr_objects);

free(written_list);

stop_progress(&progress_state);

if (written != nr_result)

die("wrote %"PRIu32" objects while expecting %"PRIu32,

written, nr_result);

/*

* We have scanned through [0 ... i). Since we have written

* the correct number of objects, the remaining [i ... nr_objects)

* items must be either already written (due to out-of-order delta base)

* or a preferred base. Count those which are neither and complain if any.

*/

for (j = 0; i < nr_objects; i++) {

struct object_entry *e = objects + i;

j += !e->idx.offset && !e->preferred_base;

}

if (j)

die("wrote %"PRIu32" objects as expected but %"PRIu32

" unwritten", written, j);

}

static int locate_object_entry_hash(const unsigned char *sha1)

{

int i;

unsigned int ui;

memcpy(&ui, sha1, sizeof(unsigned int));

i = ui % object_ix_hashsz;

while (0 < object_ix[i]) {

if (!hashcmp(sha1, objects[object_ix[i] - 1].idx.sha1))

return i;

if (++i == object_ix_hashsz)

i = 0;

}

return -1 - i;

}

static struct object_entry *locate_object_entry(const unsigned char *sha1)

{

int i;

if (!object_ix_hashsz)

return NULL;

i = locate_object_entry_hash(sha1);

if (0 <= i)

return &objects[object_ix[i]-1];

return NULL;

}

static void rehash_objects(void)

{

uint32_t i;

struct object_entry *oe;

object_ix_hashsz = nr_objects * 3;

if (object_ix_hashsz < 1024)

object_ix_hashsz = 1024;

object_ix = xrealloc(object_ix, sizeof(int) * object_ix_hashsz);

memset(object_ix, 0, sizeof(int) * object_ix_hashsz);

for (i = 0, oe = objects; i < nr_objects; i++, oe++) {

int ix = locate_object_entry_hash(oe->idx.sha1);

if (0 <= ix)

continue;

ix = -1 - ix;

object_ix[ix] = i + 1;

}

}

static unsigned name_hash(const char *name)

{

unsigned char c;

unsigned hash = 0;

if (!name)

return 0;

/*

* This effectively just creates a sortable number from the

* last sixteen non-whitespace characters. Last characters

* count "most", so things that end in ".c" sort together.

*/

while ((c = *name++) != 0) {

if (isspace(c))

continue;

hash = (hash >> 2) + (c << 24);

}

return hash;

}

static void setup_delta_attr_check(struct git_attr_check *check)

{

static struct git_attr *attr_delta;

if (!attr_delta)

attr_delta = git_attr("delta", 5);

check[0].attr = attr_delta;

}

static int no_try_delta(const char *path)

{

struct git_attr_check check[1];

setup_delta_attr_check(check);

if (git_checkattr(path, ARRAY_SIZE(check), check))

return 0;

if (ATTR_FALSE(check->value))

return 1;

return 0;

}

static int add_object_entry(const unsigned char *sha1, enum object_type type,

const char *name, int exclude)

{

struct object_entry *entry;

struct packed_git *p, *found_pack = NULL;

off_t found_offset = 0;

int ix;

unsigned hash = name_hash(name);

ix = nr_objects ? locate_object_entry_hash(sha1) : -1;

if (ix >= 0) {

if (exclude) {

entry = objects + object_ix[ix] - 1;

if (!entry->preferred_base)

nr_result--;

entry->preferred_base = 1;

}

return 0;

}

if (!exclude && local && has_loose_object_nonlocal(sha1))

return 0;

for (p = packed_git; p; p = p->next) {

off_t offset = find_pack_entry_one(sha1, p);

if (offset) {

if (!found_pack) {

found_offset = offset;

found_pack = p;

}

if (exclude)

break;

if (incremental)

return 0;

if (local && !p->pack_local)

return 0;

if (ignore_packed_keep && p->pack_local && p->pack_keep)

return 0;

}

}

if (nr_objects >= nr_alloc) {

nr_alloc = (nr_alloc + 1024) * 3 / 2;

objects = xrealloc(objects, nr_alloc * sizeof(*entry));

}

entry = objects + nr_objects++;

memset(entry, 0, sizeof(*entry));

hashcpy(entry->idx.sha1, sha1);

entry->hash = hash;

if (type)

entry->type = type;

if (exclude)

entry->preferred_base = 1;

else

nr_result++;

if (found_pack) {

entry->in_pack = found_pack;

entry->in_pack_offset = found_offset;

}

if (object_ix_hashsz * 3 <= nr_objects * 4)

rehash_objects();

else

object_ix[-1 - ix] = nr_objects;

display_progress(progress_state, nr_objects);

if (name && no_try_delta(name))

entry->no_try_delta = 1;

return 1;

}

struct pbase_tree_cache {

};

static struct pbase_tree_cache *(pbase_tree_cache[256]);

static int pbase_tree_cache_ix(const unsigned char *sha1)

{

return sha1[0] % ARRAY_SIZE(pbase_tree_cache);

}

static int pbase_tree_cache_ix_incr(int ix)

{

return (ix+1) % ARRAY_SIZE(pbase_tree_cache);

}

static struct pbase_tree {

} *pbase_tree;

static struct pbase_tree_cache *pbase_tree_get(const unsigned char *sha1)

{

struct pbase_tree_cache *ent, *nent;

void *data;

unsigned long size;

enum object_type type;

int neigh;

int my_ix = pbase_tree_cache_ix(sha1);

int available_ix = -1;

/* pbase-tree-cache acts as a limited hashtable.

* your object will be found at your index or within a few

* slots after that slot if it is cached.

*/

for (neigh = 0; neigh < 8; neigh++) {

ent = pbase_tree_cache[my_ix];

if (ent && !hashcmp(ent->sha1, sha1)) {

ent->ref++;

return ent;

}

else if (((available_ix < 0) && (!ent || !ent->ref)) ||

((0 <= available_ix) &&

(!ent && pbase_tree_cache[available_ix])))

available_ix = my_ix;

if (!ent)

break;

my_ix = pbase_tree_cache_ix_incr(my_ix);

}

/* Did not find one. Either we got a bogus request or

* we need to read and perhaps cache.

*/

data = read_sha1_file(sha1, &type, &size);

if (!data)

return NULL;

if (type != OBJ_TREE) {

free(data);

return NULL;

}

/* We need to either cache or return a throwaway copy */

if (available_ix < 0)

ent = NULL;

else {

ent = pbase_tree_cache[available_ix];

my_ix = available_ix;

}

if (!ent) {

nent = xmalloc(sizeof(*nent));

nent->temporary = (available_ix < 0);

}

else {

/* evict and reuse */

free(ent->tree_data);

nent = ent;

}

hashcpy(nent->sha1, sha1);

nent->tree_data = data;

nent->tree_size = size;

nent->ref = 1;

if (!nent->temporary)

pbase_tree_cache[my_ix] = nent;

return nent;

}

static void pbase_tree_put(struct pbase_tree_cache *cache)

{

if (!cache->temporary) {

cache->ref--;

return;

}

free(cache->tree_data);

free(cache);

}

static int name_cmp_len(const char *name)

{

int i;

for (i = 0; name[i] && name[i] != '\n' && name[i] != '/'; i++)

;

return i;

}

static void add_pbase_object(struct tree_desc *tree,

const char *name,

int cmplen,

const char *fullname)

{

struct name_entry entry;

int cmp;

while (tree_entry(tree,&entry)) {

if (S_ISGITLINK(entry.mode))

continue;

cmp = tree_entry_len(entry.path, entry.sha1) != cmplen ? 1 :

memcmp(name, entry.path, cmplen);

if (cmp > 0)

continue;

if (cmp < 0)

return;

if (name[cmplen] != '/') {

add_object_entry(entry.sha1,

object_type(entry.mode),

fullname, 1);

return;

}

if (S_ISDIR(entry.mode)) {

struct tree_desc sub;

struct pbase_tree_cache *tree;

const char *down = name+cmplen+1;

int downlen = name_cmp_len(down);

tree = pbase_tree_get(entry.sha1);

if (!tree)

return;

init_tree_desc(&sub, tree->tree_data, tree->tree_size);

add_pbase_object(&sub, down, downlen, fullname);

pbase_tree_put(tree);

}

}

}

static unsigned *done_pbase_paths;

static int done_pbase_paths_num;

static int done_pbase_paths_alloc;

static int done_pbase_path_pos(unsigned hash)

{

int lo = 0;

int hi = done_pbase_paths_num;

while (lo < hi) {

int mi = (hi + lo) / 2;

if (done_pbase_paths[mi] == hash)

return mi;

if (done_pbase_paths[mi] < hash)

hi = mi;

else

lo = mi + 1;

}

return -lo-1;

}

static int check_pbase_path(unsigned hash)

{

int pos = (!done_pbase_paths) ? -1 : done_pbase_path_pos(hash);

if (0 <= pos)

return 1;

pos = -pos - 1;

if (done_pbase_paths_alloc <= done_pbase_paths_num) {

done_pbase_paths_alloc = alloc_nr(done_pbase_paths_alloc);

done_pbase_paths = xrealloc(done_pbase_paths,

done_pbase_paths_alloc *

sizeof(unsigned));

}

done_pbase_paths_num++;

if (pos < done_pbase_paths_num)

memmove(done_pbase_paths + pos + 1,

done_pbase_paths + pos,

(done_pbase_paths_num - pos - 1) * sizeof(unsigned));

done_pbase_paths[pos] = hash;

return 0;

}

static void add_preferred_base_object(const char *name)

{

struct pbase_tree *it;

int cmplen;

unsigned hash = name_hash(name);

if (!num_preferred_base || check_pbase_path(hash))

return;

cmplen = name_cmp_len(name);

for (it = pbase_tree; it; it = it->next) {

if (cmplen == 0) {

add_object_entry(it->pcache.sha1, OBJ_TREE, NULL, 1);

}

else {

struct tree_desc tree;

init_tree_desc(&tree, it->pcache.tree_data, it->pcache.tree_size);

add_pbase_object(&tree, name, cmplen, name);

}

}

}

static void add_preferred_base(unsigned char *sha1)

{

struct pbase_tree *it;

void *data;

unsigned long size;

unsigned char tree_sha1[20];

if (window <= num_preferred_base++)

return;

data = read_object_with_reference(sha1, tree_type, &size, tree_sha1);

if (!data)

return;

for (it = pbase_tree; it; it = it->next) {