« back to all changes in this revision
Viewing changes to src/segcol_list.c
- browse files at revision 1
- compare with another revision
- download diff
- download tarball
- view history from revision 1
- Committer: Alexandros Frantzis
- Date: 2011-10-01 10:10:46 UTC
- Revision ID: alf82@freemail.gr-20111001101046-etz52jurwzwc007x
Tags: upstream-0.3.2
Import upstream version 0.3.2
- files added:
- benchmarks
- bindings
- doc
- doc/devel
- doc/user
- src
- test
added
removed
src/segcol_list.c
1
/*
2
* Copyright 2008, 2009 Alexandros Frantzis, Michael Iatrou
3
*
4
* This file is part of libbls.
5
*
6
* libbls is free software: you can redistribute it and/or modify it under the
7
* terms of the GNU Lesser General Public License as published by the Free Software
8
* Foundation, either version 3 of the License, or (at your option) any later
9
* version.
10
*
11
* libbls is distributed in the hope that it will be useful, but WITHOUT ANY
12
* WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
13
* FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
14
* details.
15
*
16
* You should have received a copy of the GNU General Public License along with
17
* libbls. If not, see <http://www.gnu.org/licenses/>.
18
*/
19
20
/**
21
* @file segcol_list.c
22
*
23
* List implementation of segcol_t
24
*/
25
#include <stdlib.h>
26
#include <errno.h>
27
28
#include "segcol.h"
29
#include "segcol_internal.h"
30
#include "segcol_list.h"
31
#include "type_limits.h"
32
#include "list.h"
33
#include "debug.h"
34
35
struct segment_entry {
36
struct list_node ln;
37
segment_t *segment;
38
};
39
40
struct segcol_list_iter_impl {
41
struct list_node *node;
42
off_t mapping;
43
};
44
45
struct segcol_list_impl {
46
list_t *list;
47
struct list_node *cached_node;
48
off_t cached_mapping;
49
};
50
51
/* Forward declarations */
52
53
/* internal convenience functions */
54
static int find_seg_entry(segcol_t *segcol,
55
struct segment_entry **snode, off_t *mapping, off_t offset);
56
static int segcol_list_clear_cache(struct segcol_list_impl *impl);
57
static int segcol_list_set_cache(struct segcol_list_impl *impl,
58
struct list_node *node, off_t mapping);
59
60
/* segcol API implementation functions */
61
int segcol_list_new(segcol_t **segcol);
62
static int segcol_list_free(segcol_t *segcol);
63
static int segcol_list_append(segcol_t *segcol, segment_t *seg);
64
static int segcol_list_insert(segcol_t *segcol, off_t offset, segment_t *seg);
65
static int segcol_list_delete(segcol_t *segcol, segcol_t **deleted, off_t offset, off_t length);
66
static int segcol_list_find(segcol_t *segcol, segcol_iter_t **iter, off_t offset);
67
static int segcol_list_iter_new(segcol_t *segcol, void **iter);
68
static int segcol_list_iter_next(segcol_iter_t *iter);
69
static int segcol_list_iter_is_valid(segcol_iter_t *iter, int *valid);
70
static int segcol_list_iter_get_segment(segcol_iter_t *iter, segment_t **seg);
71
static int segcol_list_iter_get_mapping(segcol_iter_t *iter, off_t *mapping);
72
static int segcol_list_iter_free(segcol_iter_t *iter);
73
74
/* Function pointers for the list implementation of segcol_t */
75
static struct segcol_funcs segcol_list_funcs = {
76
.free = segcol_list_free,
77
.append = segcol_list_append,
78
.insert = segcol_list_insert,
79
.delete = segcol_list_delete,
80
.find = segcol_list_find,
81
.iter_new = segcol_list_iter_new,
82
.iter_next = segcol_list_iter_next,
83
.iter_is_valid = segcol_list_iter_is_valid,
84
.iter_get_segment = segcol_list_iter_get_segment,
85
.iter_get_mapping = segcol_list_iter_get_mapping,
86
.iter_free = segcol_list_iter_free
87
};
88
89
/**
90
* Finds the segment entry in the segcol_list that contains a logical offset.
91
*
92
* @param segcol the segcol_t to search
93
* @param[out] entry the found entry (or NULL if not found)
94
* @param[out] mapping the mapping of the found node
95
* @param offset the offset to look for
96
*
97
* @return the operation error code
98
*/
99
static int find_seg_entry(segcol_t *segcol,
100
struct segment_entry **entry, off_t *mapping, off_t offset)
101
{
102
segcol_iter_t *iter = NULL;
103
int err = segcol_find(segcol, &iter, offset);
104
105
if (err)
106
return_error(err);
107
108
int valid = 0;
109
if (segcol_iter_is_valid(iter, &valid) || !valid) {
110
*entry = NULL;
111
} else {
112
struct segcol_list_iter_impl *iter_impl = segcol_iter_get_impl(iter);
113
*entry = list_entry(iter_impl->node, struct segment_entry, ln);
114
*mapping = iter_impl->mapping;
115
}
116
117
segcol_iter_free(iter);
118
119
return 0;
120
}
121
122
/**
123
* Clears the search cache of a segcol_list_impl.
124
*
125
* @param impl the segcol_list_impl
126
*
127
* @return the operation error code
128
*/
129
static int segcol_list_clear_cache(struct segcol_list_impl *impl)
130
{
131
if (impl == NULL)
132
return_error(EINVAL);
133
134
impl->cached_node = NULL;
135
impl->cached_mapping = 0;
136
137
return 0;
138
}
139
140
/**
141
* Sets the search cache of a segcol_list_impl.
142
*
143
* @param impl the segcol_list_impl
144
* @param node the cached list node
145
* @param mapping the logical mapping of the cached node in the segcol_list
146
*
147
* @return the operation error code
148
*/
149
static int segcol_list_set_cache(struct segcol_list_impl *impl,
150
struct list_node *node, off_t mapping)
151
{
152
if (impl == NULL || node == NULL)
153
return_error(EINVAL);
154
155
impl->cached_node = node;
156
impl->cached_mapping = mapping;
157
158
return 0;
159
}
160
161
/*
162
* Gets the closest known node/mapping pair to an offset.
163
*
164
* @param impl the segcol_list_impl
165
* @param node the closest known list node
166
* @param mapping the mapping of the closest known node in the segcol_list
167
* @param offset the offset to look for
168
*
169
* @return the operation error code
170
*/
171
static int segcol_list_get_closest_node(segcol_t *segcol,
172
struct list_node **node, off_t *mapping, off_t offset)
173
{
174
off_t segcol_size;
175
segcol_get_size(segcol, &segcol_size);
176
177
struct segcol_list_impl *impl =
178
(struct segcol_list_impl *) segcol_get_impl(segcol);
179
180
/*
181
* Calculate the distance of the head, tail and cached nodes to the offset.
182
* The distance metric is the byte distance of the offset to the
183
* afforementioned nodes' mappings. However, our search algorithm is
184
* O(#segments) not O(#byte_diff), so this metric may not lead to good
185
* results in some cases.
186
*
187
* Eg if the distance metric from the head is 10000 with 1000 intervening
188
* segment nodes and the metric from the tail is 100000 with 1 intervening
189
* segment node we will incorrectly choose head as the closest node.
190
*/
191
off_t dist_from_cache = __MAX(off_t);
192
if (impl->cached_node != NULL) {
193
*node = impl->cached_node;
194
*mapping = impl->cached_mapping;
195
if (offset > *mapping)
196
dist_from_cache = offset - *mapping;
197
else
198
dist_from_cache = *mapping - offset;
199
}
200
201
off_t dist_from_head = offset;
202
off_t dist_from_tail = segcol_size - offset;
203
204
/*
205
* Decide which is the closest node to the offset:
206
* head, cached or tail.
207
*/
208
off_t cur_min = dist_from_cache;
209
210
if (dist_from_head < cur_min) {
211
*node = list_head(impl->list)->next;
212
*mapping = 0;
213
cur_min = dist_from_head;
214
}
215
216
if (dist_from_tail < cur_min) {
217
*node = list_tail(impl->list)->prev;
218
219
struct segment_entry *snode =
220
list_entry(*node, struct segment_entry, ln);
221
off_t seg_size;
222
segment_get_size(snode->segment, &seg_size);
223
224
*mapping = segcol_size - seg_size;
225
}
226
227
return 0;
228
}
229
230
/*****************
231
* API functions *
232
*****************/
233
234
/**
235
* Creates a new segcol_t using a linked list implementation.
236
*
237
* @param[out] segcol the created segcol_t
238
*
239
* @return the operation error code
240
*/
241
int segcol_list_new(segcol_t **segcol)
242
{
243
if (segcol == NULL)
244
return_error(EINVAL);
245
246
/* Allocate memory for implementation */
247
struct segcol_list_impl *impl = malloc(sizeof(struct segcol_list_impl));
248
249
if (impl == NULL)
250
return_error(EINVAL);
251
252
/* Create head and tail nodes */
253
int err = list_new(&impl->list, struct segment_entry, ln);
254
if (err)
255
return_error(err);
256
257
segcol_list_clear_cache(impl);
258
259
/* Create segcol_t */
260
err = segcol_create_impl(segcol, impl, &segcol_list_funcs);
261
262
if (err) {
263
list_free(impl->list);
264
free(impl);
265
return_error(err);
266
}
267
268
return 0;
269
}
270
271
static int segcol_list_free(segcol_t *segcol)
272
{
273
if (segcol == NULL)
274
return_error(EINVAL);
275
276
struct segcol_list_impl *impl =
277
(struct segcol_list_impl *) segcol_get_impl(segcol);
278
279
struct list_node *node;
280
struct list_node *tmp;
281
282
/* free segments */
283
list_for_each_safe(list_head(impl->list)->next, node, tmp) {
284
struct segment_entry *snode = list_entry(node, struct segment_entry, ln);
285
if (snode->segment != NULL)
286
segment_free(snode->segment);
287
free(snode);
288
}
289
290
list_free(impl->list);
291
292
free(impl);
293
294
return 0;
295
}
296
297
static int segcol_list_append(segcol_t *segcol, segment_t *seg)
298
{
299
if (segcol == NULL || seg == NULL)
300
return_error(EINVAL);
301
302
/*
303
* If the segment size is 0, return successfully without adding
304
* anything. Free the segment as we will not be using it.
305
*/
306
off_t seg_size;
307
segment_get_size(seg, &seg_size);
308
if (seg_size == 0) {
309
segment_free(seg);
310
return 0;
311
}
312
313
struct segcol_list_impl *impl =
314
(struct segcol_list_impl *) segcol_get_impl(segcol);
315
316
struct segment_entry *new_entry;
317
new_entry = malloc(sizeof(struct segment_entry));
318
if (new_entry == NULL)
319
return_error(ENOMEM);
320
321
new_entry->segment = seg;
322
323
/* Append at the end */
324
list_insert_before(list_tail(impl->list), &new_entry->ln);
325
326
/* Set the cache at the appended node */
327
off_t segcol_size;
328
segcol_get_size(segcol, &segcol_size);
329
segcol_list_set_cache(impl, &new_entry->ln, segcol_size);
330
331
return 0;
332
}
333
334
static int segcol_list_insert(segcol_t *segcol, off_t offset, segment_t *seg)
335
{
336
if (segcol == NULL || seg == NULL || offset < 0)
337
return_error(EINVAL);
338
339
struct segcol_list_impl *impl =
340
(struct segcol_list_impl *) segcol_get_impl(segcol);
341
342
/* find the segment that 'offset' is mapped to */
343
segcol_iter_t *iter;
344
int err = segcol_list_find(segcol, &iter, offset);
345
if (err)
346
return_error(err);
347
348
/*
349
* If the segment size is 0, return successfully without adding
350
* anything. Free the segment as we will not be using it.
351
* This check is placed after the first find_seg_entry() so that the
352
* validity of offset (if it is in range) is checked first.
353
*/
354
off_t seg_size;
355
segment_get_size(seg, &seg_size);
356
if (seg_size == 0) {
357
segment_free(seg);
358
segcol_iter_free(iter);
359
return 0;
360
}
361
362
segcol_list_clear_cache(impl);
363
364
segment_t *pseg;
365
segcol_list_iter_get_segment(iter, &pseg);
366
367
off_t mapping;
368
segcol_list_iter_get_mapping(iter, &mapping);
369
370
struct segcol_list_iter_impl *iter_impl =
371
(struct segcol_list_iter_impl *) segcol_iter_get_impl(iter);
372
373
struct segment_entry *pentry =
374
list_entry(iter_impl->node, struct segment_entry, ln);
375
376
segcol_iter_free(iter);
377
378
/* create a list node containing the new segment */
379
struct segment_entry *qentry;
380
qentry = malloc(sizeof(struct segment_entry));
381
if (qentry == NULL)
382
return_error(ENOMEM);
383
384
qentry->segment = seg;
385
386
/*
387
* split the existing segment and insert the new segment
388
*/
389
390
/* where to split the existing segment */
391
off_t split_index = offset - mapping;
392
393
/* check if a split is actually needed or we just have to prepend
394
* the new segment */
395
if (split_index == 0)
396
list_insert_before(&pentry->ln, &qentry->ln);
397
else {
398
segment_t *rseg;
399
err = segment_split(pseg, &rseg, split_index);
400
if (err)
401
return_error(err);
402
403
struct segment_entry *rentry;
404
rentry = malloc(sizeof(struct segment_entry));
405
if (rentry == NULL) {
406
segment_merge(pseg, rseg);
407
segment_free(rseg);
408
return_error(ENOMEM);
409
}
410
rentry->segment = rseg;
411
412
list_insert_after(&pentry->ln, &qentry->ln);
413
list_insert_after(&qentry->ln, &rentry->ln);
414
}
415
416
/* Set the cache at the inserted node */
417
segcol_list_set_cache(impl, &qentry->ln, offset);
418
419
return 0;
420
}
421
422
/*
423
* The algorithm first deletes from the segcol list the entry chain that is
424
* defined by first_entry and last_entry (the nodes that contain the start and
425
* end of the range, respectively). This possibly deletes more than it should
426
* because we completely delete the first and last segment, when perhaps only a
427
* part of them should be deleted (F, L). We fix this later on by reinserting
428
* a and b. Some of the comments below will refer to the following diagram:
429
*
430
* P: first_entry_prev a: entry_a F: first_entry
431
* N: last_entry_next b: entry_b L: last_entry
432
*
433
* -[P]-[a|F]-[]-[]-[L|b]-[N]- => -[]-[P]-[N]-[]- => -[P]-[a]-[b]-[N]-
434
* ^ ^
435
* offset offset + length
436
*/
437
static int segcol_list_delete(segcol_t *segcol, segcol_t **deleted, off_t
438
offset, off_t length)
439
{
440
if (segcol == NULL || offset < 0 || length < 0)
441
return_error(EINVAL);
442
443
/* Check range for overflow */
444
if (__MAX(off_t) - offset < length - 1 * (length != 0))
445
return_error(EOVERFLOW);
446
447
struct segcol_list_impl *impl =
448
(struct segcol_list_impl *) segcol_get_impl(segcol);
449
450
struct segment_entry *first_entry = NULL;
451
struct segment_entry *last_entry = NULL;
452
off_t first_mapping = -1;
453
off_t last_mapping = -1;
454
455
/* Find the first and last list nodes that contain the range */
456
int err = find_seg_entry(segcol, &first_entry, &first_mapping, offset);
457
if (err)
458
return_error(err);
459
460
/*
461
* If the length is 0 return successfully without doing anything.
462
* This check is placed after the first find_seg_entry() so that the
463
* validity of offset (if it is in range) is checked first.
464
*/
465
if (length == 0) {
466
/* Return an empty deleted segcol if the caller wants one */
467
if (deleted != NULL) {
468
err = segcol_list_new(deleted);
469
if (err)
470
return_error(err);
471
}
472
return 0;
473
}
474
475
err = find_seg_entry(segcol, &last_entry, &last_mapping,
476
offset + length - 1 * (length != 0));
477
478
if (err)
479
return_error(err);
480
481
if (first_entry == NULL || last_entry == NULL
482
|| first_entry->segment == NULL || last_entry->segment == NULL)
483
return_error(EINVAL);
484
485
segcol_list_clear_cache(impl);
486
487
/*
488
* entry_a will hold the part of the first segment that we must
489
* put back into the segcol.
490
* entry_b will hold the part of the last segment that we must
491
* put back into the segcol.
492
*/
493
struct segment_entry *entry_a;
494
struct segment_entry *entry_b;
495
496
entry_a = malloc(sizeof(struct segment_entry));
497
if (entry_a == NULL) {
498
err = ENOMEM;
499
goto_error(err, on_error_mem_entry_a);
500
}
501
entry_b = malloc(sizeof(struct segment_entry));
502
if (entry_b == NULL) {
503
err = ENOMEM;
504
goto_error(err, on_error_mem_entry_b);
505
}
506
507
/*
508
* The nodes that should go before and after entry_a and entry_b, respectively
509
* when and if we should insert them back in.
510
*/
511
struct segment_entry *entry_a_prev =
512
list_entry(first_entry->ln.prev, struct segment_entry, ln);
513
514
struct segment_entry *entry_b_next =
515
list_entry(last_entry->ln.next, struct segment_entry, ln);
516
517
/* Delete the chain */
518
list_delete_chain(&first_entry->ln, &last_entry->ln);
519
520
/* Calculate new size, after having deleted the chain */
521
off_t new_size;
522
segcol_get_size(segcol, &new_size);
523
524
off_t last_seg_size;
525
segment_get_size(last_entry->segment, &last_seg_size);
526
527
new_size -= last_mapping + last_seg_size - first_mapping;
528
529
/*
530
* Handle first node: Split first segment so that the first node contains
531
* only segment F (and store the remaining in entry_a). We only have to do
532
* something if the range to delete starts after the beginning of the first
533
* segment. Otherwise the whole segment should be deleted which has
534
* already been done by list_delete_chain.
535
*/
536
if (first_mapping < offset) {
537
segment_t *tmp_seg;
538
err = segment_split(first_entry->segment, &tmp_seg, offset - first_mapping);
539
if (err)
540
goto_error(err, on_error_first_entry);
541
542
entry_a->segment = first_entry->segment;
543
first_entry->segment = tmp_seg;
544
} else {
545
free(entry_a);
546
entry_a = NULL;
547
}
548
549
/*
550
* Handle last node: Split last segment so that the last node contains only
551
* segment L (and store the remaining in entry_b). We only have to do
552
* something if the range to delete ends after the end of the last segment.
553
* Otherwise the whole segment should be deleted which has already been
554
* done by list_delete_chain.
555
*/
556
if (last_mapping + last_seg_size > offset + length) {
557
/*
558
* If the first and last nodes are the same the segment that is
559
* contained in them may have been decreased by 'offset - mapping' due
560
* to the split in the handling of the first node. Take this into
561
* account to correctly calculate the index for the second split.
562
*/
563
int last_seg_dec = 0;
564
565
if (first_entry == last_entry)
566
last_seg_dec = offset - first_mapping;
567
568
segment_t *tmp_seg;
569
err = segment_split(last_entry->segment, &tmp_seg,
570
offset + length - last_mapping - last_seg_dec);
571
if (err)
572
goto_error(err, on_error_last_entry);
573
574
entry_b->segment = tmp_seg;
575
} else {
576
free(entry_b);
577
entry_b = NULL;
578
}
579
580
/*
581
* Insert incorrectly deleted parts of the segments back into segcol
582
*/
583
584
if (entry_a != NULL)
585
list_insert_after(&entry_a_prev->ln, &entry_a->ln);
586
587
if (entry_b != NULL)
588
list_insert_before(&entry_b_next->ln, &entry_b->ln);
589
590
/* Create a new segcol_t and put in the deleted segments */
591
segcol_t *deleted_tmp;
592
err = segcol_list_new(&deleted_tmp);
593
if (err)
594
goto_error(err, on_error_segcol_new);
595
596
struct segcol_list_impl *deleted_impl =
597
(struct segcol_list_impl *) segcol_get_impl(deleted_tmp);
598
599
list_insert_chain_after(list_head(deleted_impl->list), &first_entry->ln,
600
&last_entry->ln);
601
602
/* Either return the deleted segments or free them */
603
if (deleted != NULL)
604
*deleted = deleted_tmp;
605
else
606
segcol_free(deleted_tmp);
607
608
/* Set the cache at the node after the deleted range */
609
if (entry_b != NULL)
610
segcol_list_set_cache(impl, &entry_b->ln, offset);
611
else if (entry_b_next->ln.next != &entry_b_next->ln)
612
segcol_list_set_cache(impl, &entry_b_next->ln, offset);
613
614
return 0;
615
/*
616
* Handle failures so that the segcol is in its expected state
617
* after a failure and there are no memory leaks.
618
*/
619
on_error_segcol_new:
620
if (entry_b != NULL)
621
list_delete_chain(&entry_b->ln, &entry_b->ln);
622
623
if (entry_a != NULL)
624
list_delete_chain(&entry_a->ln, &entry_a->ln);
625
626
if (entry_b != NULL) {
627
segment_merge(last_entry->segment, entry_b->segment);
628
free(entry_b->segment);
629
}
630
on_error_last_entry:
631
if (entry_a != NULL) {
632
segment_merge(entry_a->segment, first_entry->segment);
633
free(first_entry->segment);
634
first_entry->segment = entry_a->segment;
635
}
636
on_error_first_entry:
637
list_insert_before(&entry_b_next->ln, &last_entry->ln);
638
list_insert_after(&entry_a_prev->ln, &first_entry->ln);
639
if (entry_b != NULL) free(entry_b);
640
on_error_mem_entry_b:
641
if (entry_a != NULL) free(entry_a);
642
on_error_mem_entry_a:
643
return err;
644
}
645
646
static int segcol_list_find(segcol_t *segcol, segcol_iter_t **iter, off_t offset)
647
{
648
if (segcol == NULL || iter == NULL || offset < 0)
649
return_error(EINVAL);
650
651
int err;
652
653
/* Make sure offset is in range */
654
off_t segcol_size;
655
segcol_get_size(segcol, &segcol_size);
656
657
if (offset >= segcol_size)
658
return_error(EINVAL);
659
660
struct segcol_list_impl *impl =
661
(struct segcol_list_impl *) segcol_get_impl(segcol);
662
663
/*
664
* Find the closest known node/mapping pair to the offset
665
* and start the search from there.
666
*/
667
struct list_node *cur_node = NULL;
668
off_t cur_mapping = -1;
669
670
segcol_list_get_closest_node(segcol, &cur_node, &cur_mapping, offset);
671
672
int fix_mapping = 0;
673
674
/* linear search of list nodes */
675
while (cur_node != cur_node->next && cur_node != cur_node->prev) {
676
struct segment_entry *snode =
677
list_entry(cur_node, struct segment_entry, ln);
678
679
segment_t *seg = snode->segment;
680
off_t seg_size;
681
err = segment_get_size(seg, &seg_size);
682
683
/*
684
* When we move backwards in the list the new mapping is the
685
* cur_mapping - prev_seg->size. In order to avoid getting the
686
* size twice we just set a flag to indicate that we should fix
687
* the mapping.
688
*/
689
if (fix_mapping)
690
cur_mapping -= seg_size;
691
692
/* We have found the node! */
693
if (offset >= cur_mapping && offset < cur_mapping + seg_size) {
694
segcol_list_set_cache(impl, cur_node, cur_mapping);
695
break;
696
}
697
698
/*
699
* Move forwards or backwards in the list depending on where
700
* is the offset relative to the current node.
701
*/
702
if (offset < cur_mapping) {
703
cur_node = cur_node->prev;
704
/*
705
* Fix the mapping in the next iteration. Otherwise we would have
706
* to get the size here, which is a waste since we are doing
707
* that at the start of the loop.
708
*/
709
fix_mapping = 1;
710
}
711
else if (offset >= cur_mapping + seg_size) {
712
cur_node = cur_node->next;
713
fix_mapping = 0;
714
cur_mapping += seg_size;
715
}
716
}
717
718
/* Create iterator to return search results */
719
err = segcol_iter_new(segcol, iter);
720
if (err)
721
return_error(err);
722
723
struct segcol_list_iter_impl *iter_impl =
724
(struct segcol_list_iter_impl *) segcol_iter_get_impl(*iter);
725
726
iter_impl->node = cur_node;
727
iter_impl->mapping = cur_mapping;
728
729
return 0;
730
}
731
732
static int segcol_list_iter_new(segcol_t *segcol, void **iter_impl)
733
{
734
if (segcol == NULL || iter_impl == NULL)
735
return_error(EINVAL);
736
737
struct segcol_list_impl *impl =
738
(struct segcol_list_impl *) segcol_get_impl(segcol);
739
struct segcol_list_iter_impl **iter_impl1 =
740
(struct segcol_list_iter_impl **)iter_impl;
741
742
*iter_impl1 = malloc(sizeof(struct segcol_list_iter_impl));
743
744
(*iter_impl1)->node = list_head(impl->list)->next;
745
(*iter_impl1)->mapping = 0;
746
747
return 0;
748
}
749
750
751
static int segcol_list_iter_next(segcol_iter_t *iter)
752
{
753
if (iter == NULL)
754
return_error(EINVAL);
755
756
struct segcol_list_iter_impl *iter_impl = segcol_iter_get_impl(iter);
757
758
if (iter_impl->node != iter_impl->node->next) {
759
off_t node_size;
760
761
struct segment_entry *snode =
762
list_entry(iter_impl->node, struct segment_entry, ln);
763
764
segment_get_size(snode->segment, &node_size);
765
iter_impl->node = iter_impl->node->next;
766
iter_impl->mapping = iter_impl->mapping + node_size;
767
}
768
769
return 0;
770
}
771
772
static int segcol_list_iter_get_segment(segcol_iter_t *iter, segment_t **seg)
773
{
774
if (iter == NULL || seg == NULL)
775
return_error(EINVAL);
776
777
struct segcol_list_iter_impl *iter_impl = segcol_iter_get_impl(iter);
778
779
*seg = list_entry(iter_impl->node, struct segment_entry, ln)->segment;
780
781
return 0;
782
}
783
784
static int segcol_list_iter_get_mapping(segcol_iter_t *iter, off_t *mapping)
785
{
786
if (iter == NULL || mapping == NULL)
787
return_error(EINVAL);
788
789
struct segcol_list_iter_impl *iter_impl = segcol_iter_get_impl(iter);
790
791
*mapping = iter_impl->mapping;
792
793
return 0;
794
}
795
796
static int segcol_list_iter_is_valid(segcol_iter_t *iter, int *valid)
797
{
798
if (iter == NULL || valid == NULL)
799
return_error(EINVAL);
800
801
struct segcol_list_iter_impl *iter_impl = segcol_iter_get_impl(iter);
802
803
/* Iterator is valid if it is not NULL and its node its not the head
804
* or tail */
805
*valid = (iter_impl != NULL) && (iter_impl->node != iter_impl->node->next)
806
&& (iter_impl->node != iter_impl->node->prev);
807
808
return 0;
809
}
810
811
static int segcol_list_iter_free(segcol_iter_t *iter)
812
{
813
if (iter == NULL)
814
return_error(EINVAL);
815
816
free(segcol_iter_get_impl(iter));
817
818
return 0;
819
}
Loggerhead is a web-based interface for Breezy
Version: 2.0.1