← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/delta.h

  • Committer: Martin Pool
  • Date: 2011-07-04 21:15:24 UTC
  • mto: (6034.1.1 filter-tree)
  • mto: This revision was merged to the branch mainline in revision 6035.
  • Revision ID: mbp@canonical.com-20110704211524-ilb7l6g4i3iizke7
Test exporting filtered tree to a zip (already works)

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/delta.h
 
1
/*
 
2
 * delta.h: headers for delta functionality
 
3
 *
 
4
 * Adapted from GIT for Bazaar by
 
5
 *   John Arbash Meinel <john@arbash-meinel.com> (C) 2009
 
6
 *
 
7
 * This code is free software; you can redistribute it and/or modify
 
8
 * it under the terms of the GNU General Public License version 2 as
 
9
 * published by the Free Software Foundation.
 
10
 */
 
11
#ifndef DELTA_H
 
12
#define DELTA_H
 
13
 
 
14
/* opaque object for delta index */
 
15
struct delta_index;
 
16
 
 
17
struct source_info {
 
18
    const void *buf; /* Pointer to the beginning of source data */
 
19
    unsigned long size; /* Total length of source data */
 
20
    unsigned long agg_offset; /* Start of source data as part of the
 
21
                                 aggregate source */
 
22
};
 
23
 
 
24
/* result type for functions that have multiple failure modes */
 
25
typedef enum {
 
26
    DELTA_OK,             /* Success */
 
27
    DELTA_OUT_OF_MEMORY,  /* Could not allocate required memory */
 
28
    DELTA_INDEX_NEEDED,   /* A delta_index must be passed */
 
29
    DELTA_SOURCE_EMPTY,   /* A source_info had no content */
 
30
    DELTA_SOURCE_BAD,     /* A source_info had invalid or corrupt content */
 
31
    DELTA_BUFFER_EMPTY,   /* A buffer pointer and size */
 
32
    DELTA_SIZE_TOO_BIG,   /* Delta data is larger than the max requested */
 
33
} delta_result;
 
34
 
 
35
 
 
36
/*
 
37
 * create_delta_index: compute index data from given buffer
 
38
 *
 
39
 * Returns a delta_result status, when DELTA_OK then *fresh is set to a struct
 
40
 * delta_index that should be passed to subsequent create_delta() calls, or to
 
41
 * free_delta_index().  Other values are a failure, and *fresh is unset.
 
42
 * The given buffer must not be freed nor altered before free_delta_index() is
 
43
 * called. The resultant struct must be freed using free_delta_index().
 
44
 *
 
45
 * :param max_bytes_to_index: Limit the number of regions to sample to this
 
46
 *      amount of text. We will store at most max_bytes_to_index / RABIN_WINDOW
 
47
 *      pointers into the source text.  Useful if src can be unbounded in size,
 
48
 *      and you are willing to trade match accuracy for peak memory.
 
49
 */
 
50
extern delta_result
 
51
create_delta_index(const struct source_info *src,
 
52
                   struct delta_index *old,
 
53
                   struct delta_index **fresh,
 
54
                   int max_bytes_to_index);
 
55
 
 
56
 
 
57
/*
 
58
 * create_delta_index_from_delta: compute index data from given buffer
 
59
 *
 
60
 * Returns a delta_result status, when DELTA_OK then *fresh is set to a struct
 
61
 * delta_index that should be passed to subsequent create_delta() calls, or to
 
62
 * free_delta_index().  Other values are a failure, and *fresh is unset.
 
63
 * The bytes must be in the form of a delta structure, as generated by
 
64
 * create_delta(). The generated index will only index the insert bytes, and
 
65
 * not any of the control structures.
 
66
 */
 
67
extern delta_result
 
68
create_delta_index_from_delta(const struct source_info *delta,
 
69
                              struct delta_index *old,
 
70
                              struct delta_index **fresh);
 
71
/*
 
72
 * free_delta_index: free the index created by create_delta_index()
 
73
 *
 
74
 * Given pointer must be what create_delta_index() returned, or NULL.
 
75
 */
 
76
extern void free_delta_index(struct delta_index *index);
 
77
 
 
78
/*
 
79
 * sizeof_delta_index: returns memory usage of delta index
 
80
 *
 
81
 * Given pointer must be what create_delta_index() returned, or NULL.
 
82
 */
 
83
extern unsigned long sizeof_delta_index(struct delta_index *index);
 
84
 
 
85
/*
 
86
 * create_delta: create a delta from given index for the given buffer
 
87
 *
 
88
 * This function may be called multiple times with different buffers using
 
89
 * the same delta_index pointer.  If max_delta_size is non-zero and the
 
90
 * resulting delta is to be larger than max_delta_size then DELTA_SIZE_TOO_BIG
 
91
 * is returned.  Otherwise on success, DELTA_OK is returned and *delta_data is
 
92
 * set to a new buffer with the delta data and *delta_size is updated with its
 
93
 * size.  That buffer must be freed by the caller.
 
94
 */
 
95
extern delta_result
 
96
create_delta(const struct delta_index *index,
 
97
             const void *buf, unsigned long bufsize,
 
98
             unsigned long *delta_size, unsigned long max_delta_size,
 
99
             void **delta_data);
 
100
 
 
101
/* the smallest possible delta size is 3 bytes
 
102
 * Target size, Copy command, Copy length
 
103
 */
 
104
#define DELTA_SIZE_MIN  3
 
105
 
 
106
/*
 
107
 * This must be called twice on the delta data buffer, first to get the
 
108
 * expected source buffer size, and again to get the target buffer size.
 
109
 */
 
110
static unsigned long
 
111
get_delta_hdr_size(unsigned char **datap, const unsigned char *top)
 
112
{
 
113
    unsigned char *data = *datap;
 
114
    unsigned char cmd;
 
115
    unsigned long size = 0;
 
116
    int i = 0;
 
117
    do {
 
118
        cmd = *data++;
 
119
        size |= (cmd & ~0x80) << i;
 
120
        i += 7;
 
121
    } while (cmd & 0x80 && data < top);
 
122
    *datap = data;
 
123
    return size;
 
124
}
 
125
 
 
126
/*
 
127
 * Return the basic information about a given delta index.
 
128
 * :param index: The delta_index object
 
129
 * :param pos: The offset in the entry list. Start at 0, and walk until you get
 
130
 *      0 as a return code.
 
131
 * :param global_offset: return value, distance to the beginning of all sources
 
132
 * :param hash_val: return value, the RABIN hash associated with this pointer
 
133
 * :param hash_offset: Location for this entry in the hash array.
 
134
 * :return: 1 if pos != -1 (there was data produced)
 
135
 */
 
136
extern int
 
137
get_entry_summary(const struct delta_index *index, int pos,
 
138
                  unsigned int *text_offset, unsigned int *hash_val);
 
139
 
 
140
/*
 
141
 * Determine what entry index->hash[X] points to.
 
142
 */
 
143
extern int
 
144
get_hash_offset(const struct delta_index *index, int pos,
 
145
                unsigned int *entry_offset);
 
146
 
 
147
/*
 
148
 * Compute the rabin_hash of the given data, it is assumed the data is at least
 
149
 * RABIN_WINDOW wide (16 bytes).
 
150
 */
 
151
extern unsigned int
 
152
rabin_hash(const unsigned char *data);
 
153
 
 
154
#endif