1 /*
2  * Copyright 2018 Jonathan Dieter <jdieter@gmail.com>
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions are met:
6  *
7  *  1. Redistributions of source code must retain the above copyright notice,
8  *     this list of conditions and the following disclaimer.
9  *
10  *  2. Redistributions in binary form must reproduce the above copyright notice,
11  *     this list of conditions and the following disclaimer in the documentation
12  *     and/or other materials provided with the distribution.
13  *
14  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
15  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
16  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
17  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
18  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
19  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
20  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
21  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
22  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
23  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
24  * POSSIBILITY OF SUCH DAMAGE.
25  */
26 
27 #include <stdlib.h>
28 #include <stdio.h>
29 #include <stdint.h>
30 #include <stdbool.h>
31 #include <string.h>
32 #include <math.h>
33 #include <errno.h>
34 #include <zck.h>
35 
36 #include "zck_private.h"
37 
range_insert_new(zckCtx * zck,zckRangeItem * prev,zckRangeItem * next,uint64_t start,uint64_t end,zckRange * info,zckChunk * idx,int add_index)38 static zckRangeItem *range_insert_new(zckCtx *zck, zckRangeItem *prev,
39                                       zckRangeItem *next, uint64_t start,
40                                       uint64_t end, zckRange *info,
41                                       zckChunk *idx, int add_index) {
42     VALIDATE_PTR(zck);
43 
44     zckRangeItem *new = zmalloc(sizeof(zckRangeItem));
45     new->start = start;
46     new->end = end;
47     if(prev) {
48         new->prev = prev;
49         prev->next = new;
50     }
51     if(next) {
52         new->next = next;
53         next->prev = new;
54     }
55     if(add_index)
56         if(!index_new_chunk(zck, &(info->index), idx->digest, idx->digest_size,
57                             end-start+1, end-start+1, idx, false)) {
58             free(new);
59             return NULL;
60         }
61     return new;
62 }
63 
range_remove(zckCtx * zck,zckRangeItem * range)64 static zckRangeItem *range_remove(zckCtx *zck, zckRangeItem *range) {
65     zckRangeItem *next = range->next;
66     if(range->next)
67         range->next->prev = range->prev;
68     free(range);
69     return next;
70 }
71 
range_merge_combined(zckCtx * zck,zckRange * info)72 static void range_merge_combined(zckCtx *zck, zckRange *info) {
73     if(!info) {
74         set_error(zck, "zckRange not allocated");
75         return;
76     }
77     for(zckRangeItem *ptr=info->first; ptr;) {
78         if(ptr->next && ptr->end >= ptr->next->start-1) {
79             if(ptr->end < ptr->next->end)
80                 ptr->end = ptr->next->end;
81             ptr->next = range_remove(zck, ptr->next);
82             info->count -= 1;
83         } else {
84             ptr = ptr->next;
85         }
86     }
87 }
88 
range_add(zckRange * info,zckChunk * chk,zckCtx * zck)89 static bool range_add(zckRange *info, zckChunk *chk, zckCtx *zck) {
90     if(info == NULL || chk == NULL) {
91         set_error(zck, "zckRange or zckChunk not allocated");
92         return false;
93     }
94     size_t header_len = 0;
95     bool add_index = false;
96     if(zck) {
97         header_len = zck_get_header_length(zck);
98         add_index = true;
99     }
100 
101     size_t start = chk->start + header_len;
102     size_t end = chk->start + header_len + chk->comp_length - 1;
103     zckRangeItem *prev = info->first;
104     for(zckRangeItem *ptr=info->first; ptr;) {
105         prev = ptr;
106         if(start > ptr->start) {
107             ptr = ptr->next;
108             continue;
109         } else if(start < ptr->start) {
110             if(range_insert_new(zck, ptr->prev, ptr, start, end, info, chk,
111                                 add_index) == NULL)
112                 return false;
113             if(info->first == ptr) {
114                 info->first = ptr->prev;
115             }
116             info->count += 1;
117             range_merge_combined(zck, info);
118             return true;
119         } else { // start == ptr->start
120             if(end > ptr->end)
121                 ptr->end = end;
122             info->count += 1;
123             range_merge_combined(zck, info);
124             return true;
125         }
126     }
127     /* We've only reached here if we should be last item */
128     zckRangeItem *new = range_insert_new(zck, prev, NULL, start, end, info, chk,
129                                          add_index);
130     if(new == NULL)
131         return false;
132     if(info->first == NULL)
133         info->first = new;
134     info->count += 1;
135     range_merge_combined(zck, info);
136     return true;
137 }
138 
zck_range_free(zckRange ** info)139 void PUBLIC zck_range_free(zckRange **info) {
140     zckRangeItem *next = (*info)->first;
141     while(next) {
142         zckRangeItem *tmp = next;
143         next = next->next;
144         free(tmp);
145     }
146     index_clean(&((*info)->index));
147     free(*info);
148     *info = NULL;
149 }
150 
zck_get_range_char(zckCtx * zck,zckRange * range)151 char PUBLIC *zck_get_range_char(zckCtx *zck, zckRange *range) {
152     int buf_size = BUF_SIZE;
153     char *output = zmalloc(buf_size);
154     int loc = 0;
155     int count = 0;
156     zckRangeItem *ri = range->first;
157     while(ri) {
158         int length = snprintf(output+loc, buf_size-loc, "%lu-%lu,",
159                               (long unsigned)ri->start,
160                               (long unsigned)ri->end);
161         if(length < 0) {
162             set_fatal_error(zck, "Unable to get range: %s", strerror(errno));
163             free(output);
164             return NULL;
165         }
166         if(length > buf_size-loc) {
167             buf_size = (int)(buf_size * 1.5);
168             output = zrealloc(output, buf_size);
169             continue;
170         }
171         loc += length;
172         count++;
173         ri = ri->next;
174     }
175     output[loc-1]='\0'; // Remove final comma
176     output = zrealloc(output, loc);
177     return output;
178 }
179 
zck_get_missing_range(zckCtx * zck,int max_ranges)180 zckRange PUBLIC *zck_get_missing_range(zckCtx *zck, int max_ranges) {
181     VALIDATE_PTR(zck);
182 
183     zckRange *range = zmalloc(sizeof(zckRange));
184     for(zckChunk *chk = zck->index.first; chk; chk = chk->next) {
185         if(chk->valid)
186             continue;
187 
188         if(!range_add(range, chk, zck)) {
189             zck_range_free(&range);
190             return NULL;
191         }
192         if(max_ranges >= 0 && range->count >= max_ranges)
193             break;
194     }
195     return range;
196 }
197 
zck_get_range(size_t start,size_t end)198 char PUBLIC *zck_get_range(size_t start, size_t end) {
199     zckRange range = {0};
200     zckRangeItem ri = {0};
201     zckCtx *zck = zck_create();
202     range.first = &ri;
203     ri.start = start;
204     ri.end = end;
205     char *ret = zck_get_range_char(zck, &range);
206     zck_free(&zck);
207     return ret;
208 }
209 
zck_get_range_count(zckRange * range)210 int PUBLIC zck_get_range_count(zckRange *range) {
211     ALLOCD_INT(NULL, range);
212 
213     return range->count;
214 }
215