?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Use correct types for cursor absolute and relative offsets
[hed.git] / libhed / file.c
blobe8f7ec38dacec7ba1372fb3cdfc68b8f71a98292
1 /* $Id$ */
2
3 /*
4 * hed - Hexadecimal editor
5 * Copyright (C) 2004 Petr Baudis <pasky@ucw.cz>
6 *
7 * This program is free software; you can redistribute it and/or modify
8 * it under the terms of version 2 of the GNU General Public License as
9 * published by the Free Software Foundation.
10 *
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
15 *
16 * You should have received a copy of the GNU General Public License
17 * along with this program; if not, write to the Free Software
18 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
19 */
20
21 /*
22 * There hammer on the anvil smote,
23 * There chisel clove, and graver wrote;
24 * There forged was blade, and bound was hilt;
25 * The delver mined, the mason built.
26 * There beryl, pearl, and opal pale,
27 * And metal wrought like fishes' mail,
28 * Buckler and corslet, axe and sword,
29 * And shining spears were laid in hoard.
30 */
31
32 /* Feature macros needed for:
33 * - memrchr
34 * - pread, pwrite
35 * - stpcpy
36 */
37 #define _GNU_SOURCE
38
39 #include <config.h>
40
41 #include <errno.h>
42 #include <fcntl.h>
43 #include <limits.h>
44 #include <stdio.h>
45 #include <stdlib.h>
46 #include <string.h>
47 #include <sys/ioctl.h>
48 #include <unistd.h>
49 #include <linux/fs.h> /* BLKGETSIZE and BLKGETSIZE64 */
50
51 #include "file.h"
52 #include "file_priv.h"
53 #include "access.h"
54 #include "cache.h"
55 #include "swap.h"
56 #include "tree.h"
57 #include "expr.h"
58
59 /* memrchr() might not be available */
60 #ifndef HAVE_MEMRCHR
61 # include "memrchr.c"
62 #endif /* HAVE_MEMRCHR */
63
64 /*
65 * `Piles of jewels?' said Gandalf. `No. The Orcs have often plundered Moria;
66 * there is nothing left in the upper halls. And since the dwarves fled, no one
67 * dares to seek the shafts and treasuries down in the deep places: they are
68 * drowned in water--or in a shadow of fear.'
69 */
70
71 /* TODO: Currently the file blocks allocation is not very sophisticated and
72 * when the weather is bad it could probably have rather horrible results. */
73
74 #undef BLOCKS_DEBUG
75 #ifdef BLOCKS_DEBUG
76 #define BDEBUG(x...) fprintf(stderr, x)
77 #else
78 #define BDEBUG(x...)
79 #endif
80
81 /* Number of blocks in cache */
82 #define CACHE_LENGTH 64
83
84 /* Blocks for readahead */
85 #define FILE_READAHEAD (CACHE_LENGTH/2)
86
87 /* Searches for data object don't care about the EOF flag */
88 #define STATEMASK_SANS_EOF (HED_BLOCK_STATEMASK & ~HED_BLOCK_EOF)
89
90 #define first_block(f) next_block(last_block(f))
91 #define prev_block(b) (tree_entry(prev_in_tree(&(b)->t),struct hed_block,t))
92 #define next_block(b) (tree_entry(next_in_tree(&(b)->t),struct hed_block,t))
93 #define last_block(f) (&(f)->terminal_block)
94
95 #define block_offset(b) tree_block_offset(&(b)->t)
96
97 #define recalc_block_recursive(b) recalc_node_recursive(&(b)->t)
98
99 #define chain_block(tree,b,p) insert_into_tree((tree), &(b)->t, &(p)->t)
100 #define recalc_chain_block(tree,b,p) do { \
101 chain_block((tree), (b), (p)); \
102 recalc_block_recursive((b)); \
103 } while (0)
104
105 #define unchain_block(tree,b) del_from_tree((tree), &(b)->t)
106 #define recalc_unchain_block(tree,b) recalc_del_from_tree((tree), &(b)->t)
107
108 #define init_block_list(tree,b) init_tree(tree, &(b)->t)
109 #define init_block_link(b) init_node(&(b)->t)
110
111 #define find_block(tree,o) tree_entry(find_in_tree((tree),(o)),struct hed_block,t)
112
113 #define block_is_loadable(b) \
114 (((b)->flags & (HED_BLOCK_VIRTUAL | HED_BLOCK_EOF | HED_BLOCK_BAD)) \
115 == HED_BLOCK_VIRTUAL)
116
117 #ifdef HED_CONFIG_SWAP
118
119 /* Return the swp file object */
120 static inline struct swp_file *
121 file_swp(struct file_priv *file)
122 {
123 return file->swp;
124 }
125
126 #else
127
128 /* Provide a stub for the non-swap case */
129 static inline void *
130 file_swp(struct file_priv *file)
131 {
132 return NULL;
133 }
134
135 #endif
136
137 #ifdef HED_CONFIG_READAHEAD
138
139 #define file_ra_none(f) ((f)->readahead == HED_RA_NONE)
140 #define file_ra_forward(f) ((f)->readahead == HED_RA_FORWARD)
141 #define file_ra_backward(f) ((f)->readahead == HED_RA_BACKWARD)
142
143 static inline void
144 set_readahead(struct file_priv *file, int val)
145 {
146 file->readahead = val;
147 }
148
149 #else
150
151 #define file_ra_none(f) (1)
152 #define file_ra_forward(f) (0)
153 #define file_ra_backward(f) (0)
154 #define set_readahead(file,t) do {} while(0)
155
156 #endif /* HED_CONFIG_READAHEAD */
157
158 void
159 hed_file_set_readahead(struct hed_file *file, enum hed_readahead val)
160 {
161 set_readahead(file_private(file), val);
162 }
163
164 static void
165 shrink_block(struct hed_block *block, hed_uoff_t amount)
166 {
167 block->t.maxoff -= amount;
168 if (!hed_block_size(block))
169 hed_block_set_empty(block);
170 recalc_block_recursive(block);
171 }
172
173 /* Get the physical offset of the byte immediately following @block. */
174 static inline hed_uoff_t
175 phys_end(const struct hed_block *block)
176 {
177 return hed_block_is_inserted(block)
178 ? block->phys_pos
179 : block->phys_pos + hed_block_size(block);
180 }
181
182 static struct hed_block *
183 next_nonzero_block(struct hed_block *block)
184 {
185 while (!hed_block_is_terminal(block)) {
186 block = next_block(block);
187 if (!hed_block_is_empty(block))
188 return block;
189 }
190 return NULL;
191 }
192
193 static struct hed_block *
194 prev_nonzero_block(struct hed_block *block)
195 {
196 do {
197 block = prev_block(block);
198 if (hed_block_is_terminal(block))
199 return NULL;
200 } while (hed_block_is_empty(block));
201 return block;
202 }
203
204 bool
205 hed_block_is_after_erase(struct hed_block *block)
206 {
207 struct hed_block *prev = prev_nonzero_block(block);
208 return prev
209 ? block->phys_pos > phys_end(prev)
210 : !!block->phys_pos;
211 }
212
213 bool
214 hed_block_is_after_insert(struct hed_block *block)
215 {
216 struct hed_block *prev = prev_nonzero_block(block);
217 return prev && hed_block_is_inserted(prev);
218 }
219
220 /* Get the blocks tree */
221 static inline struct hed_tree *
222 hed_file_blocks(struct file_priv *file)
223 {
224 return &file->blocks;
225 }
226
227 #ifndef BLOCKS_DEBUG
228 # define dump_blocks(file) {}
229 #else
230
231 static hed_uoff_t
232 block_phys_size(struct hed_block *block)
233 {
234 struct hed_block *next;
235
236 if (hed_block_is_terminal(block))
237 return 0;
238 next = next_block(block);
239 return next->phys_pos - block->phys_pos;
240 }
241
242 static void
243 dump_block(int level, struct file_priv *file, struct hed_tree_node *node,
244 hed_uoff_t *cur_offset, hed_uoff_t *cur_poffset)
245 {
246 struct hed_block *block = tree_entry(node, struct hed_block, t);
247 unsigned char *p;
248 hed_cursor_t *cur;
249 char t[21] = " ";
250 char data[9], *dp;
251
252 if (node->left)
253 dump_block(level + 1, file, node->left, cur_offset, cur_poffset);
254 p = hed_block_data(block);
255 dp = data;
256 if (p && !hed_block_is_empty(block)) {
257 if (node->maxoff >= 0)
258 dp += snprintf(dp, 3, "%02x", p[0]);
259 if (node->maxoff >= 1)
260 dp += snprintf(dp, 3, "%02x", p[1]);
261 if (node->maxoff >= 2)
262 dp += snprintf(dp, 3, "%02x", p[2]);
263 if (node->maxoff >= 3)
264 dp += snprintf(dp, 3, "%02x", p[3]);
265 }
266 memset(dp, ' ', sizeof(data) - (dp - data));
267 data[8] = 0;
268
269 if (level < 20) t[level] = '>'; else t[19] = '.';
270 fprintf(stderr, "%s [%06llx] [%06llx] %c%c%c%c%c %05llx %05llx"
271 " {%s} -- %p ^%p [%06llx]\n",
272 t,
273 (unsigned long long) *cur_offset,
274 (unsigned long long) *cur_poffset,
275 hed_block_is_bad(block) ? 'b' : ' ',
276 hed_block_is_eof(block) ? 'e' : ' ',
277 hed_block_is_virtual(block) ? 'v' : ' ',
278 hed_block_is_inserted(block) ? 'i' : ' ',
279 hed_block_is_dirty(block) ? '*' : ' ',
280 (unsigned long long) node->maxoff + 1,
281 (unsigned long long) block_phys_size(block),
282 data,
283 node, node->up,
284 (unsigned long long) node->cover_size
285 );
286 list_for_each_entry (cur, &block->refs, list) {
287 fprintf(stderr, " <%p>: %llx->%p:%llx\n",
288 cur, (long long)cur->pos,
289 cur->block, (unsigned long long)cur->off);
290 }
291 assert(*cur_poffset == block->phys_pos);
292 *cur_offset += node->maxoff + 1;
293 *cur_poffset += block_phys_size(block);
294 if (node->right)
295 dump_block(level + 1, file, node->right, cur_offset, cur_poffset);
296 assert(node->cover_size == (node->left ? node->left->cover_size : 0)
297 + (node->right ? node->right->cover_size : 0)
298 + node->maxoff + 1);
299 }
300
301 /* Walk the tree manually here, because foreach_block() does not provide
302 * the tree structure.
303 * TODO: Change this if you plan to debug any other block containers.
304 */
305 static void
306 dump_blocks(struct file_priv *file)
307 {
308 struct hed_block *first = first_block(file);
309 hed_uoff_t cur_offset, cur_poffset;
310
311 fprintf(stderr, "-- blocks dump --\n");
312 cur_offset = 0;
313 cur_poffset = first->phys_pos;
314 dump_block(0, file, hed_file_blocks(file)->root,
315 &cur_offset, &cur_poffset);
316 fprintf(stderr, "-- blocks dump end --\n");
317 }
318 #endif
319
320 static void
321 get_cursor(struct file_priv *file, hed_uoff_t offset, hed_cursor_t *curs)
322 {
323 struct hed_block *block;
324
325 block = find_block(hed_file_blocks(file), offset);
326 assert(block != NULL);
327 curs->pos = offset;
328 curs->block = block;
329 curs->off = offset - block_offset(block);
330 list_add(&curs->list, &block->refs);
331
332 BDEBUG("Mapped %llx to %llx+%llx/%llx\n",
333 offset, offset - curs->off, curs->off, hed_block_size(block));
334 }
335
336 void
337 hed_get_cursor(struct hed_file *file, hed_uoff_t offset, hed_cursor_t *curs)
338 {
339 get_cursor(file_private(file), offset, curs);
340 }
341
342 static inline void
343 put_cursor(hed_cursor_t *curs)
344 {
345 list_del(&curs->list);
346 }
347
348 void
349 hed_put_cursor(hed_cursor_t *curs)
350 {
351 put_cursor(curs);
352 }
353
354 void
355 hed_update_cursor(struct hed_file *file, hed_uoff_t offset, hed_cursor_t *curs)
356 {
357 put_cursor(curs);
358 get_cursor(file_private(file), offset, curs);
359 }
360
361 void
362 hed_dup_cursor(const hed_cursor_t *src, hed_cursor_t *dst)
363 {
364 dst->pos = src->pos;
365 dst->block = src->block;
366 dst->off = src->off;
367 list_add_tail(&dst->list, &src->block->refs);
368 }
369
370 void
371 hed_dup2_cursor(const hed_cursor_t *src, hed_cursor_t *dst)
372 {
373 if (hed_is_a_cursor(dst))
374 put_cursor(dst);
375 hed_dup_cursor(src, dst);
376 }
377
378 /* Move cursors from @old to @new, adding @off to their block
379 * offsets to keep them at the same position. */
380 static void
381 update_cursors(const struct hed_block *old, struct hed_block *new,
382 hed_off_t off)
383 {
384 hed_cursor_t *curs;
385
386 BDEBUG("Updating cursors from <%p> to <%p>%c%llx\n",
387 old, new, off >= 0 ? '+' : '-', off >= 0 ? off : -off);
388
389 list_for_each_entry(curs, &old->refs, list) {
390 curs->block = new;
391 curs->off += off;
392 }
393 }
394
395 /* Move cursors in the range <@start;@end> from @old to @new,
396 * adding @off to their block offset, plus moving the reference list. */
397 static void
398 move_cursors(const struct hed_block *old, struct hed_block *new,
399 hed_uoff_t start, hed_uoff_t end, hed_off_t off)
400 {
401 hed_cursor_t *curs, *nextcurs;
402
403 BDEBUG("Moving cursors from <%p>:%llx:%llx to <%p>%c%llx\n",
404 old, start, end, new,
405 off >= 0 ? '+' : '-', off >= 0 ? off : -off);
406
407 list_for_each_entry_safe(curs, nextcurs, &old->refs, list)
408 if (curs->off >= start && curs->off <= end) {
409 curs->block = new;
410 curs->off += off;
411 list_move(&curs->list, &new->refs);
412 }
413 }
414
415 /* Move cursors in the range @block:<@start;@end> to @newpos */
416 static void
417 move_cursors_abs(const struct hed_block *block,
418 hed_uoff_t start, hed_uoff_t end,
419 const hed_cursor_t *newpos)
420 {
421 hed_cursor_t *curs, *nextcurs;
422
423 BDEBUG("Moving cursors from <%p>:%llx:%llx to <%p>:%llx\n",
424 block, start, end, newpos->block, newpos->off);
425
426 list_for_each_entry_safe(curs, nextcurs, &block->refs, list)
427 if (curs->off >= start && curs->off <= end) {
428 curs->pos = newpos->pos;
429 curs->block = newpos->block;
430 curs->off = newpos->off;
431 list_move(&curs->list, &newpos->block->refs);
432 }
433 }
434
435 /* Update the positions of cursors at and after @start for all
436 * blocks starting at @block */
437 static void
438 slide_cursors(const struct hed_block *block, hed_uoff_t start, hed_off_t off)
439 {
440 hed_cursor_t *curs;
441 const struct hed_block *nblock;
442
443 BDEBUG("Sliding cursors >= %llx by %c%llx, starting at <%p>\n",
444 start, off >= 0 ? '+' : '-', off >= 0 ? off : -off, block);
445 nblock = block;
446 do {
447 block = nblock;
448 list_for_each_entry(curs, &block->refs, list)
449 if (curs->pos >= start)
450 curs->pos += off;
451 nblock = next_block(block);
452 } while (!hed_block_is_terminal(block));
453 }
454
455 static struct hed_block *
456 new_block(struct file_priv *file, long flags)
457 {
458 struct hed_block *new;
459
460 if (! (new = swp_zalloc(file_swp(file), sizeof(struct hed_block))) )
461 return NULL;
462
463 new->flags = flags;
464 init_block_link(new);
465 INIT_LIST_HEAD(&new->refs);
466 if (flags & HED_BLOCK_EXCACHE)
467 INIT_LIST_HEAD(&new->lru);
468 else
469 list_add_tail(&new->lru, &file->lru);
470
471 return new;
472 }
473
474 static struct hed_block *
475 new_virt_block(struct file_priv *file, hed_uoff_t pos, hed_uoff_t size,
476 long extraflags)
477 {
478 struct hed_block *new = new_block(file, (HED_BLOCK_EXCACHE |
479 HED_BLOCK_VIRTUAL |
480 extraflags));
481 if (!new)
482 return NULL;
483
484 assert(size != 0);
485 new->t.maxoff = size - 1;
486 new->phys_pos = pos;
487 BDEBUG("Spawned new virtual block [%llx] at %llx\n", size, pos);
488 return new;
489 }
490
491 static struct hed_block *
492 new_data_block(struct file_priv *file, hed_uoff_t pos, hed_uoff_t size,
493 struct hed_block_data *dataobj)
494 {
495 struct hed_block *new = new_block(file, 0);
496 if (!new)
497 return NULL;
498
499 cache_get(dataobj);
500 new->dataobj = dataobj;
501 assert(size != 0);
502 new->t.maxoff = size - 1;
503 new->phys_pos = pos;
504 new->dataoff = FILE_BLOCK_OFF(pos);
505 BDEBUG("Spawned new data block [%llx] at %llx\n", size, pos);
506 return new;
507 }
508
509 static void
510 file_free_block(struct file_priv *file, struct hed_block *block)
511 {
512 if (block->dataobj)
513 cache_put(file->cache, block->dataobj);
514 list_del(&block->lru);
515
516 swp_free(file_swp(file), block);
517 }
518
519 static void
520 merge_and_free(struct file_priv *file, struct hed_block *block,
521 struct hed_block *merger, hed_off_t off)
522 {
523 /* A bit more efficient than move_cursors() */
524 update_cursors(block, merger, off);
525 list_splice(&block->refs, &merger->refs);
526
527 /* Messing with block sizes and unchaining is a bit tricky
528 * since unchain_block() can splay(). So we really need
529 * to recalc_block_recursive() right after we update the size.
530 * If this place turns out to be a hot-spot, we can optimize
531 * the tree operations here. */
532 merger->t.maxoff += hed_block_size(block);
533 recalc_block_recursive(merger);
534
535 /* Destroy the block */
536 recalc_unchain_block(hed_file_blocks(file), block);
537 file_free_block(file, block);
538 }
539
540 /* This may kill the previous block as well, if it can be merged
541 * with the next one. It will never kill anything which _follows_. */
542 static void
543 kill_block(struct file_priv *file, struct hed_block *block)
544 {
545 struct hed_block *prev, *next;
546
547 assert(!hed_block_is_dirty(block) || hed_block_is_empty(block));
548
549 if (!hed_block_is_virtual(block)) {
550 /* Convert physical to virtual */
551 assert(block->dataobj);
552 cache_put(file->cache, block->dataobj);
553 block->dataobj = NULL;
554
555 list_del_init(&block->lru); /* unlink the block from LRU */
556 block->flags = HED_BLOCK_EXCACHE | HED_BLOCK_VIRTUAL |
557 (block->flags & (HED_BLOCK_EOF | HED_BLOCK_EMPTY));
558 }
559
560 prev = prev_block(block);
561 if (prev->flags == block->flags &&
562 prev->phys_pos + hed_block_size(prev) == block->phys_pos) {
563 merge_and_free(file, block, prev, hed_block_size(prev));
564 block = prev;
565 }
566
567 next = next_block(block);
568 if (next->flags == block->flags &&
569 block->phys_pos + hed_block_size(block) == next->phys_pos) {
570 update_cursors(next, next, hed_block_size(block));
571 next->phys_pos -= hed_block_size(block);
572 merge_and_free(file, block, next, 0);
573 block = next;
574 }
575
576 if (hed_block_is_empty(block)) {
577 /* No recalculation needed, zero size. */
578 unchain_block(hed_file_blocks(file), block);
579 file_free_block(file, block);
580 }
581 }
582
583 static bool
584 kill_block_if_empty(struct file_priv *file, struct hed_block *block)
585 {
586 if (!hed_block_is_terminal(block) && hed_block_is_empty(block) &&
587 list_empty(&block->refs)) {
588 kill_block(file, block);
589 return true;
590 }
591 return false;
592 }
593
594 static struct hed_block *
595 split_block(struct file_priv *file, struct hed_block *block,
596 hed_uoff_t splitpoint)
597 {
598 struct hed_block *head;
599
600 assert(!hed_block_is_empty(block));
601
602 head = new_block(file, block->flags & ~HED_BLOCK_TERMINAL);
603 if (!head)
604 return NULL;
605
606 if ( (head->dataobj = block->dataobj) ) {
607 cache_get(head->dataobj);
608 head->dataoff = block->dataoff;
609 block->dataoff += splitpoint;
610 } else
611 assert(hed_block_is_virtual(block));
612
613 assert(splitpoint != 0);
614 head->t.maxoff = splitpoint - 1;
615 head->phys_pos = block->phys_pos;
616
617 if (!hed_block_is_inserted(block))
618 block->phys_pos += splitpoint;
619 shrink_block(block, splitpoint);
620
621 recalc_chain_block(hed_file_blocks(file), head, block);
622
623 move_cursors(block, head, 0, splitpoint - 1, 0);
624 update_cursors(block, block, -splitpoint);
625
626 return head;
627 }
628
629 /* Replace a chunk in @block with @newblock */
630 static int
631 replace_chunk(struct file_priv *file, struct hed_block *block,
632 hed_uoff_t offset, struct hed_block *newblock)
633 {
634 size_t len;
635
636 assert(offset <= block->t.maxoff);
637 assert(newblock->t.maxoff <= block->t.maxoff - offset);
638
639 /* Re-create the head block if necessary */
640 if (offset && !split_block(file, block, offset))
641 return -1;
642
643 /* Move pointers to the new block */
644 len = hed_block_size(newblock);
645 assert(len > 0);
646 move_cursors(block, newblock, 0, len - 1, 0);
647
648 /* Shorten the tail block */
649 len = hed_block_size(newblock);
650 block->dataoff += len;
651 assert(!hed_block_is_inserted(block));
652 block->phys_pos += len;
653 shrink_block(block, len);
654 update_cursors(block, block, -(hed_off_t)len);
655
656 /* Insert the new block */
657 recalc_chain_block(hed_file_blocks(file), newblock, block);
658
659 /* Kill the tail block if possible */
660 kill_block_if_empty(file, block);
661
662 return 0;
663 }
664
665 #ifdef HED_CONFIG_SWAP
666
667 static char *
668 swp_filename(const char *filename)
669 {
670 size_t fnlen = strlen(filename);
671 char *swp;
672 char *file;
673
674 if (!(swp = malloc(fnlen + 9)) )
675 return NULL;
676 strcpy(swp, filename);
677
678 file = strrchr(swp, '/');
679 file = file ? file + 1 : swp;
680 *file = '.';
681 strcpy(stpcpy(file + 1, filename + (file -swp)), ".hedswp");
682 return swp;
683 }
684
685 static char *
686 newswp_filename(char *swpname)
687 {
688 char *p = NULL; /* bogus assignment to silence a warning */
689 char *ret;
690
691 ret = swpname;
692 while (!access(ret, F_OK)) {
693 if (ret == swpname) {
694 if (! (ret = strdup(swpname)) )
695 return NULL;
696 p = ret + strlen(ret) - 1;
697 }
698
699 if (*p == 'a') {
700 free(ret);
701 return NULL;
702 }
703 --*p;
704 }
705 return ret;
706 }
707
708 int
709 hed_file_remove_swap(struct hed_file *f)
710 {
711 struct file_priv *file = file_private(f);
712 if (remove(file->swpname))
713 return -1;
714 if (rename(file->newswpname, file->swpname))
715 return -1;
716
717 free(file->newswpname);
718 file->newswpname = file->swpname;
719 return 0;
720 }
721
722 static inline struct file_priv *
723 file_swp_init(const char *name)
724 {
725 char *swpname, *newswpname;
726 struct swp_file *swp;
727 struct file_priv *file;
728
729 swpname = swp_filename(name);
730 if (!swpname)
731 goto fail;
732 newswpname = newswp_filename(swpname);
733 if (!newswpname)
734 goto fail_free_name;
735 swp = swp_init_write(newswpname);
736 if (!swp)
737 goto fail_free_newname;
738
739 assert(sizeof(struct swp_header) + sizeof(struct file_priv)
740 <= FILE_BLOCK_SIZE);
741 file = swp_private(swp);
742 memset(file, 0, sizeof *file);
743
744 file->swp = swp;
745 file->swpname = swpname;
746 file->newswpname = newswpname;
747
748 return file;
749
750 fail_free_newname:
751 free(newswpname);
752 fail_free_name:
753 if (swpname != newswpname)
754 free(swpname);
755 fail:
756 return NULL;
757 }
758
759 static inline void
760 file_swp_done(struct file_priv *file)
761 {
762 remove(file->newswpname);
763 if (file->newswpname != file->swpname)
764 free(file->newswpname);
765 free(file->swpname);
766 swp_done(file_swp(file));
767 /* file was de-allocated automatically with file->swp */
768 }
769
770 int
771 hed_file_has_swap(struct hed_file *f)
772 {
773 struct file_priv *file = file_private(f);
774 return file->swpname != file->newswpname;
775 }
776
777 char *
778 hed_file_swap_name(struct hed_file *f)
779 {
780 struct file_priv *file = file_private(f);
781 return file->swpname;
782 }
783
784 #else /* HED_CONFIG_SWAP */
785
786 static inline struct file_priv *
787 file_swp_init(const char *name)
788 {
789 return calloc(1, sizeof(struct file_priv));
790 }
791
792 static inline void
793 file_swp_done(struct file_priv *file)
794 {
795 free(file);
796 }
797
798 int
799 hed_file_has_swap(struct hed_file *file)
800 {
801 return 0;
802 }
803
804 int
805 hed_file_remove_swap(struct hed_file *file)
806 {
807 return 0;
808 }
809
810 char *
811 hed_file_swap_name(struct hed_file *file)
812 {
813 return NULL;
814 }
815
816 #endif /* HED_CONFIG_SWAP */
817
818 static inline struct stat *
819 file_stat(struct file_priv *file)
820 {
821 return &file->s;
822 }
823
824 int
825 hed_file_update_size(struct hed_file *f)
826 {
827 struct file_priv *file = file_private(f);
828 hed_uoff_t oldsize = file->f.phys_size;
829
830 if(fstat(file->fd, file_stat(file)) < 0)
831 return -1;
832
833 if (S_ISBLK(file_stat(file)->st_mode)) {
834 if (ioctl(file->fd, BLKGETSIZE64, &file->f.phys_size)) {
835 unsigned long size_in_blocks;
836 if (ioctl(file->fd, BLKGETSIZE, &size_in_blocks))
837 return -1;
838 file->f.phys_size = (hed_uoff_t)size_in_blocks << 9;
839 }
840 } else if (S_ISREG(file_stat(file)->st_mode)) {
841 file->f.phys_size = file_stat(file)->st_size;
842 } else if (S_ISCHR(file_stat(file)->st_mode)) {
843 if (lseek(file->fd, 0, SEEK_SET) < 0)
844 return -1;
845 file->f.phys_size = (hed_uoff_t)OFF_MAX + 1;
846 } else {
847 errno = EINVAL;
848 return -1;
849 }
850
851 file->f.size += file->f.phys_size - oldsize;
852 return 0;
853 }
854
855 static int
856 do_file_open(struct file_priv *file)
857 {
858 file->fd = open(file->f.name, O_RDONLY);
859 if (file->fd < 0) {
860 if (errno != ENOENT)
861 return errno;
862 fprintf(stderr, "Warning: File %s does not exist\n",
863 file->f.name);
864 memset(file_stat(file), 0, sizeof(struct stat));
865
866 } else if (hed_file_update_size(&file->f)) {
867 int errsv = errno;
868 close(file->fd);
869 return errsv;
870 }
871 return 0;
872 }
873
874 static int
875 file_setup_blocks(struct file_priv *file)
876 {
877 hed_uoff_t phys_size = file->f.phys_size;
878 struct hed_block *block;
879
880 block = &file->terminal_block;
881 block->flags = HED_BLOCK_EXCACHE | HED_BLOCK_VIRTUAL
882 | HED_BLOCK_EOF | HED_BLOCK_TERMINAL;
883 INIT_LIST_HEAD(&block->lru);
884 INIT_LIST_HEAD(&block->refs);
885 block->t.maxoff = OFF_MAX - phys_size;
886 block->phys_pos = phys_size;
887
888 init_block_list(hed_file_blocks(file), block);
889
890 if (phys_size) {
891 block = new_virt_block(file, 0, phys_size, 0);
892 if (!block)
893 return -1;
894 recalc_chain_block(hed_file_blocks(file), block,
895 &file->terminal_block);
896 }
897
898 return 0;
899 }
900
901 int
902 libhed_init(void)
903 {
904 return file_access_init();
905 }
906
907 struct hed_file *
908 hed_open(const char *name)
909 {
910 struct file_priv *file = file_swp_init(name);
911
912 if (!file)
913 goto fail;
914
915 file->f.name = name;
916 INIT_LIST_HEAD(&file->lru);
917
918 file->cache = cache_init(CACHE_LENGTH, file_swp(file));
919 if (!file->cache)
920 goto fail_file;
921
922 if (do_file_open(file))
923 goto fail_file;
924
925 if (file_setup_blocks(file))
926 goto fail_file;
927
928 fixup_register(file);
929
930 return &file->f;
931
932 fail_file:
933 hed_close(&file->f);
934 fail:
935 return NULL;
936 }
937
938 void
939 hed_close(struct hed_file *f)
940 {
941 struct file_priv *file = file_private(f);
942 assert(file);
943
944 /* Do not check for errors:
945 * 1. This FD is read-only => no data loss possbile
946 * 2. We're about to exit anyway => no resource leak
947 */
948 if (file->fd >= 0)
949 close(file->fd);
950
951 fixup_deregister(file);
952
953 /* No need to free file blocks here, because all data is
954 * allocated either from the cache or from the swap file
955 * and both is going to be destroyed now.
956 */
957
958 if (file->cache)
959 cache_done(file->cache);
960
961 file_swp_done(file);
962 }
963
964 /* Adjust a cursor after off gets outside its block */
965 static void
966 fixup_cursor_slow(hed_cursor_t *curs)
967 {
968 struct hed_block *block = curs->block;
969 hed_uoff_t off = curs->off;
970
971 do {
972 if ((hed_off_t)off < 0) {
973 block = prev_block(block);
974 off += hed_block_size(block);
975 } else {
976 off -= hed_block_size(block);
977 block = next_block(block);
978 }
979 } while (!hed_block_is_terminal(block) && off > block->t.maxoff);
980
981 curs->block = block;
982 curs->off = off;
983 list_move(&curs->list, &block->refs);
984 }
985
986 /* Adjust a cursor if off gets outside its block.
987 * This is separate from fixup_cursor_slow, because it is supposed
988 * to be small enough to be inlined (which is a win, because most of
989 * the time no fixup has to be done, so the fast inlined path is used).
990 */
991 static inline void
992 fixup_cursor(hed_cursor_t *curs)
993 {
994 if (curs->off > curs->block->t.maxoff)
995 fixup_cursor_slow(curs);
996 }
997
998 hed_off_t
999 hed_move_relative(hed_cursor_t *curs, hed_off_t num)
1000 {
1001 hed_uoff_t newpos = curs->pos + num;
1002 if (num < 0 && newpos > curs->pos)
1003 newpos = 0;
1004 else if (num > 0 && newpos < curs->pos)
1005 newpos = UOFF_MAX;
1006 num = newpos - curs->pos;
1007 curs->pos = newpos;
1008 curs->off += num;
1009 fixup_cursor(curs);
1010 return num;
1011 }
1012
1013 /* Relative move with no checking (and only by a small amount) */
1014 static inline void
1015 move_rel_fast(hed_cursor_t *curs, ssize_t num)
1016 {
1017 curs->off += num;
1018 curs->pos += num;
1019 fixup_cursor(curs);
1020 }
1021
1022 static void
1023 alloc_caches(struct file_priv *file, struct hed_block_data **caches, int n)
1024 {
1025 struct remap_control rc;
1026 int i;
1027
1028 BDEBUG("Allocate %d caches (%d free slots available)\n",
1029 n, file->cache->nfree);
1030
1031 assert(n <= CACHE_LENGTH);
1032 while (file->cache->nfree < n) {
1033 struct hed_block *block;
1034
1035 assert(!list_empty(&file->lru));
1036 block = list_entry(file->lru.next, struct hed_block, lru);
1037 BDEBUG("Killing block at physical %llx\n", block->phys_pos);
1038 kill_block(file, block);
1039 }
1040
1041 for (i = 0; i < n; ++i) {
1042 caches[i] = cache_alloc(file->cache);
1043 assert(caches[i]);
1044 }
1045
1046 remap_init(&rc);
1047 remap_compact(&rc, file->cache, caches, n);
1048 for (i = 0; i < n; ++i)
1049 remap_add(&rc, caches[i]->data);
1050 remap_finish(&rc);
1051 }
1052
1053 static inline void
1054 free_caches(struct file_priv *file, struct hed_block_data **preload, int n)
1055 {
1056 int i;
1057
1058 for (i = 0; i < n; ++i)
1059 if (preload[i])
1060 cache_put(file->cache, preload[i]);
1061 }
1062
1063 static int
1064 file_load_data(struct file_priv *file,
1065 struct hed_block_data **caches, int n,
1066 hed_uoff_t offset)
1067 {
1068 struct hed_block_data *dataobj = caches[0];
1069 void *data = dataobj->data;
1070 ssize_t rsize, total, segsize;
1071
1072 segsize = n << FILE_BLOCK_SHIFT;
1073 for (total = 0; total < segsize; total += rsize) {
1074 rsize = pread(file->fd, data + total,
1075 segsize - total, offset + total);
1076 if (!rsize) {
1077 memset(data + total, 0, segsize - total);
1078 break;
1079 }
1080 if (rsize < 0) {
1081 cache_put(file->cache,
1082 caches[total >> FILE_BLOCK_SHIFT]);
1083 caches[total >> FILE_BLOCK_SHIFT] = NULL;
1084 total = FILE_BLOCK_ROUND(total);
1085 rsize = FILE_BLOCK_SIZE;
1086 BDEBUG("Error reading block at phys %llx: %s\n",
1087 offset + total, strerror(errno));
1088 }
1089 }
1090
1091 BDEBUG("Loaded data at phys %llx up to %llx\n",
1092 offset, offset + segsize);
1093 return 0;
1094 }
1095
1096 #ifdef HED_CONFIG_MMAP
1097
1098 static int
1099 file_load_data_mmap(struct file_priv *file,
1100 struct hed_block_data **caches, int n,
1101 hed_uoff_t offset)
1102 {
1103 void *data;
1104 ssize_t segsize;
1105 int i;
1106
1107 segsize = n << FILE_BLOCK_SHIFT;
1108 data = mmap(NULL, segsize,
1109 PROT_READ | PROT_WRITE,
1110 MAP_PRIVATE | (file->fd < 0 ? MAP_ANONYMOUS : 0),
1111 file->fd, offset);
1112
1113 if (data == MAP_FAILED) {
1114 BDEBUG("mmap failed at %llx: fail over to traditional read\n",
1115 offset);
1116
1117 data = mmap(NULL, segsize,
1118 PROT_READ | PROT_WRITE,
1119 MAP_PRIVATE | MAP_ANONYMOUS,
1120 0, 0);
1121 if (data == MAP_FAILED)
1122 return -1;
1123
1124 for (i = 0; i < n; ++i)
1125 caches[i]->data = data + (i << FILE_BLOCK_SHIFT);
1126 return file_load_data(file, caches, n, offset);
1127 }
1128
1129 for (i = 0; i < n; ++i)
1130 caches[i]->data = data + (i << FILE_BLOCK_SHIFT);
1131
1132 BDEBUG("Loaded data at phys %llx up to %llx\n",
1133 offset, offset + segsize);
1134 return 0;
1135 }
1136 # define file_load_data file_load_data_mmap
1137
1138 #endif
1139
1140 /* Find the block with the lowest physical position that intersects
1141 * the loaded segment. The search starts at @block.
1142 */
1143 static struct hed_block *
1144 first_load_block(struct hed_block *block, hed_uoff_t segstart)
1145 {
1146 struct hed_block *prev = block;
1147 do {
1148 block = prev;
1149 prev = prev_block(prev);
1150 } while (!hed_block_is_terminal(prev) && phys_end(prev) > segstart);
1151 return block;
1152 }
1153
1154 static int
1155 load_blocks(struct file_priv *file, const hed_cursor_t *from)
1156 {
1157 hed_uoff_t physpos, segstart;
1158 struct hed_block_data *preload[FILE_READAHEAD];
1159 size_t ra_bkw, ra_fwd, ra_off;
1160 hed_cursor_t pos;
1161 int nblocks;
1162 int ret;
1163
1164 segstart = hed_cursor_phys_pos(from);
1165 ra_bkw = FILE_BLOCK_OFF(segstart);
1166 ra_fwd = FILE_BLOCK_SIZE - ra_bkw;
1167
1168 if (file_ra_forward(file))
1169 ra_fwd += (FILE_READAHEAD - 1) << FILE_BLOCK_SHIFT;
1170 else if (file_ra_backward(file))
1171 ra_bkw += (FILE_READAHEAD - 1) << FILE_BLOCK_SHIFT;
1172
1173 if (ra_bkw > segstart)
1174 ra_bkw = segstart;
1175 if (ra_fwd > file->f.phys_size - segstart)
1176 ra_fwd = file->f.phys_size - segstart;
1177
1178 segstart -= ra_bkw;
1179 ra_fwd += ra_bkw;
1180 pos.block = first_load_block(from->block, segstart);
1181 pos.off = segstart >= pos.block->phys_pos
1182 ? segstart - pos.block->phys_pos
1183 : 0;
1184
1185 list_add(&pos.list, &pos.block->refs);
1186 nblocks = ((ra_fwd - 1) >> FILE_BLOCK_SHIFT) + 1;
1187 alloc_caches(file, preload, nblocks);
1188 put_cursor(&pos);
1189
1190 ret = -1; /* be a pessimist */
1191 if (file_load_data(file, preload, nblocks, segstart))
1192 goto out;
1193
1194 while (physpos = hed_cursor_phys_pos(&pos),
1195 ra_off = physpos - segstart,
1196 ra_off < ra_fwd) {
1197 struct hed_block_data *dataobj;
1198 struct hed_block *newblock;
1199 size_t datalen;
1200
1201 if (!hed_block_is_virtual(pos.block)) {
1202 pos.block = next_block(pos.block);
1203 pos.off = 0;
1204 continue;
1205 }
1206
1207 datalen = FILE_BLOCK_SIZE - FILE_BLOCK_OFF(physpos);
1208 if (datalen > hed_block_size(pos.block) - pos.off)
1209 datalen = hed_block_size(pos.block) - pos.off;
1210
1211 dataobj = preload[ra_off >> FILE_BLOCK_SHIFT];
1212 newblock = dataobj
1213 ? new_data_block(file, physpos, datalen, dataobj)
1214 : new_virt_block(file, physpos, datalen,
1215 HED_BLOCK_BAD);
1216 if (!newblock)
1217 goto out;
1218
1219 /* Punch the new block */
1220 BDEBUG("Add %s block at %llx, length %llx\n",
1221 hed_block_is_virtual(newblock) ? "error" : "physical",
1222 newblock->phys_pos, hed_block_size(newblock));
1223 if (replace_chunk(file, pos.block, pos.off, newblock)) {
1224 file_free_block(file, newblock);
1225 goto out;
1226 }
1227
1228 pos.block = next_block(newblock);
1229 pos.off = 0;
1230 }
1231 ret = 0;
1232
1233 out:
1234 /* All cache objects now have an extra reference from the
1235 * allocation. Drop it. */
1236 free_caches(file, preload, nblocks);
1237
1238 dump_blocks(file);
1239 return ret;
1240 }
1241
1242 /* Shorten a block at beginning and enlarge the preceding block.
1243 *
1244 * Re-allocate at most @len bytes from the beginning of @block to the
1245 * end of the preceding block.
1246 * If @block is virtual, this will effectively devirtualize the range.
1247 * If @block is not virtual, this will change the backing store of
1248 * the bytes in the range.
1249 * Returns: the number of bytes actually moved.
1250 */
1251 static size_t
1252 shrink_at_begin(struct hed_block *block, size_t len, long state)
1253 {
1254 struct hed_block *prev;
1255 size_t maxgrow;
1256
1257 /* Basic assumptions */
1258 assert(!(state & HED_BLOCK_VIRTUAL));
1259
1260 /* The previous block must exist: */
1261 prev = prev_block(block);
1262 if (hed_block_is_terminal(prev))
1263 return 0;
1264
1265 /* The block flags must match the requested @state: */
1266 if ((prev->flags & HED_BLOCK_STATEMASK) != state)
1267 return 0;
1268
1269 /* No deletions at end, or similar: */
1270 if (prev->phys_pos + hed_block_size(prev) != block->phys_pos)
1271 return 0;
1272
1273 /* Append less bytes than requested if not all are available */
1274 assert(prev->t.maxoff < prev->dataobj->size - prev->dataoff);
1275 maxgrow = prev->dataobj->size - prev->dataoff - hed_block_size(prev);
1276 if (len > maxgrow)
1277 len = maxgrow;
1278 if (!len)
1279 return 0;
1280
1281 BDEBUG("Appending 0:%lx to the previous block\n", len);
1282
1283 /* Move cursors away from the to-be-chopped beginning */
1284 move_cursors(block, prev, 0, len - 1, hed_block_size(prev));
1285
1286 /* Enlarge the previous block */
1287 prev->t.maxoff += len;
1288 recalc_block_recursive(prev);
1289
1290 /* Shorten the original block */
1291 block->dataoff += len;
1292 block->phys_pos += len;
1293 shrink_block(block, len);
1294
1295 return len;
1296 }
1297
1298 /* Shorten a block at end and enlarge the following block.
1299 *
1300 * Re-allocate at most @len bytes from the end of @block to the
1301 * beginning of the following block.
1302 * If @block is virtual, this will effectively devirtualize the range.
1303 * If @block is not virtual, this will change the backing store of
1304 * the bytes in the range.
1305 * Returns: the number of bytes actually moved.
1306 */
1307 static size_t
1308 shrink_at_end(struct hed_block *block, size_t len, long state)
1309 {
1310 struct hed_block *next;
1311 hed_uoff_t off;
1312
1313 /* Basic assumptions */
1314 assert(!(state & HED_BLOCK_VIRTUAL));
1315
1316 /* The next block must exist: */
1317 if (hed_block_is_terminal(block))
1318 return 0;
1319 next = next_block(block);
1320
1321 /* The block flags must match the requested @state: */
1322 if ((next->flags & HED_BLOCK_STATEMASK) != state)
1323 return 0;
1324
1325 /* No deletions at end, or similar: */
1326 if (block->phys_pos + hed_block_size(block) != next->phys_pos)
1327 return 0;
1328
1329 /* Prepend less bytes than requested if not all are available */
1330 if (len > next->dataoff)
1331 len = next->dataoff;
1332 if (!len)
1333 return 0;
1334 off = hed_block_size(block) - len;
1335
1336 BDEBUG("Prepending %llx:%lx to the next block\n", off, len);
1337
1338 /* Shift cursors in the new physical block */
1339 update_cursors(next, next, len);
1340
1341 /* Move cursors away from the to-be-chopped end */
1342 move_cursors(block, next, off, UOFF_MAX, -off);
1343
1344 /* Enlarge the next block */
1345 next->dataoff -= len;
1346 next->phys_pos -= len;
1347 next->t.maxoff += len;
1348 recalc_block_recursive(next);
1349
1350 /* Shorten the original block */
1351 shrink_block(block, len);
1352
1353 return len;
1354 }
1355
1356 /* Search for an existing data object within the same physical block
1357 * as @curs, and having the given @state flags.
1358 */
1359 static struct hed_block_data *
1360 search_data(struct file_priv *file, const hed_cursor_t *curs, long state)
1361 {
1362 struct hed_block *block;
1363 hed_uoff_t physpos;
1364
1365 physpos = FILE_BLOCK_ROUND(curs->block->phys_pos + curs->off);
1366 BDEBUG("Search for already loaded data at %llx starting at %llx...",
1367 physpos, curs->block->phys_pos);
1368
1369 /* Search backwards */
1370 block = curs->block;
1371 while (!hed_block_is_terminal(block = prev_block(block))) {
1372 if (block->phys_pos < physpos)
1373 break;
1374 if ((block->flags & STATEMASK_SANS_EOF) == state) {
1375 BDEBUG(" found at %llx\n", block->phys_pos);
1376 assert(block->dataobj);
1377 return block->dataobj;
1378 }
1379 }
1380
1381 /* Search forwards */
1382 block = curs->block;
1383 while (!hed_block_is_terminal(block)) {
1384 block = next_block(block);
1385 if (block->phys_pos >= physpos + FILE_BLOCK_SIZE)
1386 break;
1387 if ((block->flags & STATEMASK_SANS_EOF) == state) {
1388 BDEBUG(" found at %llx\n", block->phys_pos);
1389 assert(block->dataobj);
1390 return block->dataobj;
1391 }
1392 }
1393
1394 BDEBUG(" not found\n");
1395 return NULL;
1396 }
1397
1398 static int
1399 reuse_loaded_data(struct file_priv *file, const hed_cursor_t *curs,
1400 struct hed_block_data *data)
1401 {
1402 struct hed_block *physblock;
1403 struct hed_block *block = curs->block;
1404 hed_uoff_t block_offset = curs->off;
1405 hed_uoff_t physpos = block->phys_pos + block_offset;
1406 size_t part = FILE_BLOCK_OFF(physpos);
1407 size_t len =
1408 FILE_BLOCK_SIZE - part <= hed_block_size(block) - block_offset
1409 ? FILE_BLOCK_SIZE - part
1410 : hed_block_size(block) - block_offset;
1411
1412 if (part > block_offset)
1413 part = block_offset;
1414 physpos -= part;
1415 len += part;
1416 block_offset -= part;
1417
1418 if (! (physblock = new_data_block(file, physpos, len, data)) )
1419 return -1;
1420
1421 BDEBUG("Add physical block at %llx, length %llx\n",
1422 physblock->phys_pos, hed_block_size(physblock));
1423 if (replace_chunk(file, block, block_offset, physblock)) {
1424 file_free_block(file, physblock);
1425 return -1;
1426 }
1427
1428 dump_blocks(file);
1429 return 0;
1430 }
1431
1432 /* Replace a part of a virtual block with content loaded
1433 * from disk. The amount of data loaded from the disk depends
1434 * on various factors with the goal to choose the most efficient
1435 * ratio. The only guarantee is that the byte at @curs will
1436 * be in a non-virtual block when this function returns 0.
1437 */
1438 static int
1439 devirtualize_clean(struct file_priv *file, const hed_cursor_t *curs)
1440 {
1441 struct hed_block *block = curs->block;
1442 hed_uoff_t block_offset = curs->off;
1443 hed_uoff_t remain = hed_block_size(block) - block_offset;
1444 struct hed_block_data *data;
1445
1446 BDEBUG("punch a clean hole at %llx into %llx:%llx\n", block_offset,
1447 block_offset(block), hed_block_size(block));
1448 assert(hed_block_is_virtual(block));
1449
1450 /* Check if we can combine with a neighbouring block */
1451 if (shrink_at_begin(block, hed_block_size(block), 0) > block_offset
1452 || shrink_at_end(block, hed_block_size(block), 0) >= remain) {
1453 kill_block_if_empty(file, block);
1454 dump_blocks(file);
1455 return 0;
1456 }
1457
1458 /* Check if the block is already loaded elsewhere */
1459 data = search_data(file, curs, 0);
1460 return data
1461 ? reuse_loaded_data(file, curs, data)
1462 : load_blocks(file, curs);
1463 }
1464
1465 /* Unles the block at @curs is already dirty, replace at most
1466 * @len bytes at @curs with a newly allocated out-of-cache block.
1467 * The block is marked dirty and its data is left uninitialized.
1468 * Note that this function may devirtualize less than @len bytes.
1469 * In the worst case only 1 byte at @curs will be available.
1470 */
1471 static int
1472 prepare_modify(struct file_priv *file, hed_cursor_t *curs, size_t len)
1473 {
1474 struct hed_block *block = curs->block;
1475 hed_uoff_t block_offset = curs->off;
1476 hed_uoff_t remain = hed_block_size(block) - block_offset;
1477 long newstate = HED_BLOCK_DIRTY | (block->flags & HED_BLOCK_EOF);
1478 struct hed_block *newblock;
1479
1480 if (hed_block_is_dirty(block))
1481 return 0;
1482
1483 if (len > remain)
1484 len = remain;
1485
1486 BDEBUG("punch a dirty hole at %llx:%lx into %llx:%llx\n",
1487 block_offset, len,
1488 block_offset(block), hed_block_size(block));
1489
1490 /* Check if we can combine with a neighbouring block */
1491 if ((block_offset == 0 &&
1492 shrink_at_begin(block, len, newstate)) ||
1493 (remain == len &&
1494 shrink_at_end(block, len, newstate) >= len)) {
1495 kill_block_if_empty(file, block);
1496 dump_blocks(file);
1497 return 0;
1498 }
1499
1500 /* Initialize a new block */
1501 newblock = new_block(file, HED_BLOCK_EXCACHE | newstate);
1502 if (!newblock)
1503 goto out_err;
1504
1505 /* Allocate data */
1506 if ( (newblock->dataobj = search_data(file, curs, HED_BLOCK_DIRTY)) )
1507 cache_get(newblock->dataobj);
1508 else if (! (newblock->dataobj = block_data_new(file->cache,
1509 FILE_BLOCK_SIZE)) )
1510 goto out_err_free;
1511
1512 newblock->phys_pos = block->phys_pos + block_offset;
1513 newblock->dataoff = FILE_BLOCK_OFF(newblock->phys_pos);
1514 if (len > FILE_BLOCK_SIZE - newblock->dataoff)
1515 len = FILE_BLOCK_SIZE - newblock->dataoff;
1516 assert(len != 0);
1517 newblock->t.maxoff = len - 1;
1518
1519 if (replace_chunk(file, block, block_offset, newblock))
1520 goto out_err_free;
1521
1522 dump_blocks(file);
1523 return 0;
1524
1525 out_err_free:
1526 file_free_block(file, newblock);
1527 out_err:
1528 return -1;
1529 }
1530
1531 /* Ensure that @curs points to an up-to-date non-virtual block.
1532 * Load the data from disk if necessary, return zero on failure. */
1533 size_t
1534 hed_prepare_read(struct hed_file *f, const hed_cursor_t *curs, size_t len)
1535 {
1536 struct file_priv *file = file_private(f);
1537 struct hed_block *block = curs->block;
1538 if (block_is_loadable(block) &&
1539 devirtualize_clean(file, curs) < 0)
1540 return 0;
1541
1542 return hed_cursor_chunk_len(curs, len);
1543 }
1544
1545 /* Move the block pointer to the next block */
1546 static struct hed_block *
1547 cursor_next_block(hed_cursor_t *curs)
1548 {
1549 struct hed_block *block = next_nonzero_block(curs->block);
1550
1551 if (block) {
1552 curs->block = block;
1553 curs->off = 0;
1554 list_move(&curs->list, &block->refs);
1555 }
1556 return block;
1557 }
1558
1559 /* Copy in @count bytes from @pos.
1560 * Returns the number of bytes that were not read (i.e. zero on success).
1561 * The @pos cursor is moved by the amount of data read.
1562 * CAUTION: If you read up to MAX_OFF, then @pos points one byte
1563 * beyond the EOF block upon return.
1564 */
1565 static size_t
1566 copy_in(struct file_priv *file, void *buf, size_t count, hed_cursor_t *pos)
1567 {
1568 size_t cpylen;
1569
1570 pos->pos += count;
1571 while (count && (cpylen = hed_prepare_read(&file->f, pos, count))) {
1572 if (hed_block_is_bad(pos->block))
1573 break;
1574 else if (hed_block_is_virtual(pos->block))
1575 memset(buf, 0, cpylen);
1576 else
1577 memcpy(buf, hed_cursor_data(pos), cpylen);
1578
1579 buf += cpylen;
1580 count -= cpylen;
1581 if ( (pos->off += cpylen) >= hed_block_size(pos->block) )
1582 if (!cursor_next_block(pos))
1583 break;
1584 }
1585 pos->pos -= count;
1586 return count;
1587 }
1588
1589 size_t
1590 hed_file_cpin(struct hed_file *file, void *buf, size_t count,
1591 const hed_cursor_t *pos)
1592 {
1593 hed_cursor_t mypos;
1594 size_t ret;
1595
1596 hed_dup_cursor(pos, &mypos);
1597 ret = copy_in(file_private(file), buf, count, &mypos);
1598 put_cursor(&mypos);
1599 return ret;
1600 }
1601
1602 /* Set the modified flag */
1603 static inline void
1604 set_modified(struct file_priv *file)
1605 {
1606 file->f.modified = true;
1607 }
1608
1609 /* Clear the modified flag */
1610 static inline void
1611 clear_modified(struct file_priv *file)
1612 {
1613 file->f.modified = false;
1614 }
1615
1616 int
1617 hed_file_set_byte(struct hed_file *f, hed_cursor_t *curs, unsigned char byte)
1618 {
1619 struct file_priv *file = file_private(f);
1620
1621 if (prepare_modify(file, curs, 1))
1622 return -1;
1623 set_modified(file);
1624
1625 hed_block_data(curs->block)[curs->off] = byte;
1626
1627 if (hed_block_is_terminal(next_block(curs->block)))
1628 file->f.size = curs->pos + 1;
1629
1630 return 0;
1631 }
1632
1633 size_t
1634 hed_file_set_block(struct hed_file *f, hed_cursor_t *curs,
1635 unsigned char *buf, size_t len)
1636 {
1637 struct file_priv *file = file_private(f);
1638 while (len) {
1639 size_t span;
1640
1641 if (prepare_modify(file, curs, len))
1642 break;
1643 set_modified(file);
1644
1645 span = hed_cursor_chunk_len(curs, len);
1646 memcpy(hed_cursor_data(curs), buf, span);
1647 buf += span;
1648 len -= span;
1649 move_rel_fast(curs, span);
1650 }
1651
1652 if (hed_block_is_terminal(curs->block))
1653 file->f.size = curs->pos;
1654
1655 return len;
1656 }
1657
1658 hed_uoff_t
1659 hed_file_set_bytes(struct hed_file *f, hed_cursor_t *curs,
1660 unsigned char byte, hed_uoff_t rep)
1661 {
1662 struct file_priv *file = file_private(f);
1663 while (rep) {
1664 size_t span;
1665
1666 if (prepare_modify(file, curs, rep))
1667 break;
1668 set_modified(file);
1669
1670 span = hed_cursor_chunk_len(curs, rep);
1671 memset(hed_cursor_data(curs), byte, span);
1672 rep -= span;
1673 move_rel_fast(curs, span);
1674 }
1675
1676 if (hed_block_is_terminal(curs->block))
1677 file->f.size = curs->pos;
1678
1679 return rep;
1680 }
1681
1682 static int
1683 file_erase_continuous(struct file_priv *file, hed_cursor_t *curs, size_t len)
1684 {
1685 struct hed_block *block = curs->block;
1686 hed_uoff_t block_offset = curs->off;
1687
1688 /* Find the new position */
1689 hed_move_relative(curs, len);
1690
1691 /* Move all other cursors in the erased range to the new position */
1692 assert(len > 0);
1693 move_cursors_abs(block, block_offset,
1694 block_offset + len - 1, curs);
1695
1696 if (!block_offset) {
1697 block->dataoff += len;
1698 if (!hed_block_is_inserted(block))
1699 block->phys_pos += len;
1700 } else if (block_offset + len <= block->t.maxoff) {
1701 block = split_block(file, block, block_offset + len);
1702 if (!block)
1703 return -1;
1704 }
1705
1706 move_cursors(block, block, block_offset, UOFF_MAX, -(hed_uoff_t)len);
1707
1708 shrink_block(block, len);
1709 kill_block_if_empty(file, block);
1710 return 0;
1711 }
1712
1713 size_t
1714 hed_file_erase_block(struct hed_file *f, hed_cursor_t *curs, hed_uoff_t len)
1715 {
1716 struct file_priv *file = file_private(f);
1717 hed_uoff_t todo;
1718
1719 todo = len;
1720 while (!hed_block_is_terminal(curs->block) && todo) {
1721 size_t span = hed_cursor_chunk_len(curs, todo);
1722
1723 if (file_erase_continuous(file, curs, span))
1724 break;
1725
1726 todo -= span;
1727 }
1728 len -= todo;
1729
1730 file->f.size -= len;
1731 set_modified(file);
1732
1733 file->terminal_block.t.maxoff += len;
1734 recalc_block_recursive(&file->terminal_block);
1735
1736 struct hed_block *slideblock = prev_block(curs->block);
1737 if (hed_block_is_terminal(slideblock))
1738 slideblock = curs->block;
1739 slide_cursors(slideblock, curs->pos, -len);
1740
1741 return hed_block_is_terminal(curs->block) ? 0 : todo;
1742 }
1743
1744 /* Note that @curs may be detached from the block reference list
1745 * with put_cursor(). Only the pos, block and off fields are used.
1746 * This is an implementation detail currently required by
1747 * hed_file_insert_block(), which sets @curs and @curs_ins to the
1748 * same value. Other users of the library must not rely on it.
1749 */
1750 int
1751 hed_file_insert_begin(struct hed_file *f, const hed_cursor_t *curs,
1752 hed_cursor_t *curs_ins)
1753 {
1754 struct file_priv *file = file_private(f);
1755 struct hed_block *newblock;
1756
1757 BDEBUG("Starting insert at %llx\n", curs->pos);
1758
1759 newblock = new_block(file, (HED_BLOCK_EXCACHE | HED_BLOCK_EMPTY |
1760 HED_BLOCK_INSERTED | HED_BLOCK_DIRTY |
1761 (curs->block->flags & HED_BLOCK_EOF)));
1762 if (!newblock)
1763 return -1;
1764
1765 newblock->t.maxoff = (hed_uoff_t)-1;
1766 newblock->phys_pos = hed_cursor_phys_pos(curs);
1767 newblock->dataobj = block_data_new(file->cache, FILE_BLOCK_SIZE);
1768 if (!newblock->dataobj) {
1769 file_free_block(file, newblock);
1770 return -1;
1771 }
1772
1773 if (curs->off && !split_block(file, curs->block, curs->off)) {
1774 file_free_block(file, newblock);
1775 return -1;
1776 }
1777
1778 chain_block(hed_file_blocks(file), newblock, curs->block);
1779
1780 curs_ins->pos = curs->pos;
1781 curs_ins->off = 0;
1782 curs_ins->block = newblock;
1783 list_add(&curs_ins->list, &newblock->refs);
1784
1785 dump_blocks(file);
1786 return 0;
1787 }
1788
1789 void
1790 hed_file_insert_end(struct hed_file *f, hed_cursor_t *curs_ins)
1791 {
1792 struct file_priv *file = file_private(f);
1793 struct hed_block *block = curs_ins->block;
1794
1795 BDEBUG("End insert at %llx\n", curs_ins->pos);
1796
1797 curs_ins->block = NULL;
1798 list_del(&curs_ins->list);
1799 if (!kill_block_if_empty(file, block))
1800 block_data_shrink(file->cache, block->dataobj,
1801 block->dataoff + hed_block_size(block));
1802
1803 dump_blocks(file);
1804 }
1805
1806 static void
1807 insert_block(struct file_priv *file, hed_cursor_t *curs,
1808 unsigned char *buf, size_t len)
1809 {
1810 struct hed_block *block = curs->block;
1811 hed_uoff_t offset = curs->pos;
1812
1813 assert(hed_block_is_excache(block));
1814 assert(hed_block_is_dirty(block));
1815 set_modified(file);
1816
1817 memcpy(hed_block_data(block) + curs->off, buf, len);
1818 block->t.maxoff += len;
1819 assert(len != 0);
1820 hed_block_clear_empty(block);
1821 recalc_block_recursive(block);
1822 curs->off += len;
1823 curs->pos += len;
1824
1825 slide_cursors(next_block(block), offset, len);
1826 }
1827
1828 size_t
1829 hed_file_insert_block(struct hed_file *f, hed_cursor_t *curs,
1830 unsigned char *buf, size_t len)
1831 {
1832 struct file_priv *file = file_private(f);
1833 size_t todo = len;
1834 while (todo) {
1835 struct hed_block *block = curs->block;
1836 size_t remain;
1837
1838 remain = block->dataobj->size - block->dataoff - curs->off;
1839 if (!remain) {
1840 put_cursor(curs);
1841 curs->block = next_block(block);
1842 curs->off = 0;
1843
1844 if (hed_file_insert_begin(&file->f, curs, curs))
1845 break;
1846
1847 continue;
1848 }
1849
1850 if (remain > todo)
1851 remain = todo;
1852
1853 BDEBUG("Append %ld bytes to the insert block\n",
1854 (long) remain);
1855 insert_block(file, curs, buf, remain);
1856 buf += remain;
1857 todo -= remain;
1858 }
1859 len -= todo;
1860
1861 if (curs->pos > file->f.size)
1862 file->f.size = curs->pos;
1863 else
1864 file->f.size += len;
1865
1866 file->terminal_block.t.maxoff -= len;
1867 recalc_block_recursive(&file->terminal_block);
1868
1869 return todo;
1870 }
1871
1872 int
1873 hed_file_insert_byte(struct hed_file *file, hed_cursor_t *curs,
1874 unsigned char byte)
1875 {
1876 return hed_file_insert_block(file, curs, &byte, 1);
1877 }
1878
1879 size_t
1880 hed_file_insert_once(struct hed_file *file, hed_cursor_t *curs,
1881 unsigned char *buf, size_t len)
1882 {
1883 hed_cursor_t insert;
1884
1885 if (!hed_file_insert_begin(file, curs, &insert)) {
1886 len = hed_file_insert_block(file, &insert, buf, len);
1887 hed_file_insert_end(file, &insert);
1888 }
1889 return len;
1890 }
1891
1892 struct commit_control {
1893 struct file_priv *file;
1894 int wfd; /* file descriptor for writing */
1895 hed_cursor_t begoff, endoff;
1896 void *buffer; /* write buffer (one block) */
1897 };
1898
1899 static ssize_t
1900 commit_write(struct commit_control *cc, hed_uoff_t pos, ssize_t len)
1901 {
1902 BDEBUG(" -> write %lx bytes at %llx\n",
1903 (unsigned long)len, pos);
1904 return pwrite(cc->wfd, cc->buffer, len, pos);
1905 }
1906
1907 /* Commit forwards. */
1908 static int
1909 commit_forwards(struct commit_control *cc)
1910 {
1911 int ret = 0;
1912
1913 BDEBUG("Writing forwards %llx-%llx\n",
1914 cc->begoff.pos, cc->endoff.pos);
1915
1916 while (cc->begoff.pos < cc->endoff.pos) {
1917 size_t left;
1918 ssize_t written;
1919
1920 left = copy_in(cc->file, cc->buffer,
1921 FILE_BLOCK_SIZE, &cc->begoff);
1922 if (left) {
1923 move_rel_fast(&cc->begoff, left);
1924 ret = -1;
1925 continue;
1926 }
1927
1928 written = commit_write(cc, cc->begoff.pos - FILE_BLOCK_SIZE,
1929 FILE_BLOCK_SIZE);
1930 if (written < FILE_BLOCK_SIZE)
1931 ret = -1;
1932 }
1933
1934 return ret;
1935 }
1936
1937 /* Commit backwards. */
1938 static int
1939 commit_backwards(struct commit_control *cc)
1940 {
1941 hed_cursor_t curs;
1942 int ret = 0;
1943
1944 BDEBUG("Writing backwards %llx-%llx\n",
1945 cc->begoff.pos, cc->endoff.pos);
1946
1947 hed_dup_cursor(&cc->endoff, &curs);
1948 while (curs.pos > cc->begoff.pos) {
1949 size_t left;
1950 ssize_t written;
1951
1952 move_rel_fast(&curs, -FILE_BLOCK_SIZE);
1953 left = hed_file_cpin(&cc->file->f, cc->buffer,
1954 FILE_BLOCK_SIZE, &curs);
1955 if (left) {
1956 ret = -1;
1957 continue;
1958 }
1959
1960 written = commit_write(cc, curs.pos, FILE_BLOCK_SIZE);
1961 if (written < FILE_BLOCK_SIZE)
1962 ret = -1;
1963 }
1964 hed_put_cursor(&curs);
1965
1966 return ret;
1967 }
1968
1969 /* Return the number of clean bytes following @curs.
1970 * Usage note: the caller must ensure that the starting position
1971 * is clean.
1972 */
1973 static hed_uoff_t
1974 clean_span(hed_cursor_t *curs)
1975 {
1976 hed_uoff_t next_pos;
1977 struct hed_block *block = curs->block;
1978 hed_uoff_t ret = -curs->off;
1979
1980 assert(!hed_block_is_dirty(block));
1981
1982 do {
1983 ret += hed_block_size(block);
1984 next_pos = block->phys_pos + hed_block_size(block);
1985 block = next_nonzero_block(block);
1986 } while (block->phys_pos == next_pos && /* no insertions, deletions */
1987 !hed_block_is_dirty(block) && /* no modifications */
1988 !hed_block_is_terminal(block));
1989 return ret;
1990 }
1991
1992 static void
1993 undirty_blocks(struct file_priv *file)
1994 {
1995 struct hed_block *block, *next;
1996
1997 BDEBUG("Undirtying blocks:\n");
1998 dump_blocks(file);
1999
2000 next = first_block(file);
2001 next->phys_pos = 0;
2002 while (!hed_block_is_terminal(next)) {
2003 block = next;
2004 next = next_block(block);
2005 next->phys_pos = block->phys_pos + hed_block_size(block);
2006
2007 hed_block_clear_dirty(block);
2008 hed_block_clear_eof(block);
2009 kill_block(file, block);
2010 }
2011
2012 BDEBUG("After undirtying\n");
2013 dump_blocks(file);
2014 }
2015
2016 static int
2017 commit_init(struct commit_control *cc, struct file_priv *file)
2018 {
2019 cc->file = file;
2020 cc->buffer = malloc(FILE_BLOCK_SIZE);
2021 if (!cc->buffer)
2022 goto err;
2023
2024 if (file->fd < 0) {
2025 file->fd = open(file->f.name, O_RDONLY | O_CREAT, 0666);
2026 if (file->fd < 0)
2027 goto err_free;
2028 }
2029
2030 cc->wfd = open(file->f.name, O_WRONLY);
2031 if (cc->wfd < 0)
2032 goto err_free;
2033
2034 return 0;
2035
2036 err_free:
2037 free(cc->buffer);
2038 err:
2039 return -1;
2040 }
2041
2042 int
2043 hed_file_commit(struct hed_file *f)
2044 {
2045 struct file_priv *file = file_private(f);
2046 struct commit_control cc;
2047 hed_off_t shift;
2048 int ret = 0;
2049
2050 if (commit_init(&cc, file))
2051 return -1;
2052
2053 dump_blocks(file);
2054
2055 get_cursor(file, 0,&cc.begoff);
2056 hed_dup_cursor(&cc.begoff, &cc.endoff);
2057 shift = -cc.begoff.block->phys_pos;
2058 while(!hed_block_is_terminal(cc.endoff.block)) {
2059 hed_uoff_t skip;
2060 hed_off_t newshift;
2061
2062 if (!shift && !hed_block_is_dirty(cc.endoff.block)) {
2063 skip = FILE_BLOCK_ROUND(clean_span(&cc.endoff));
2064 if (skip) {
2065 ret |= commit_forwards(&cc);
2066
2067 BDEBUG("Skipping %llx-%llx\n",
2068 cc.endoff.pos, cc.endoff.pos + skip);
2069 hed_move_relative(&cc.endoff, skip);
2070 hed_dup2_cursor(&cc.endoff, &cc.begoff);
2071 continue;
2072 }
2073 }
2074
2075 skip = FILE_BLOCK_ROUND(hed_cursor_span(&cc.endoff));
2076 hed_move_relative(&cc.endoff, skip ?: FILE_BLOCK_SIZE);
2077
2078 newshift = !hed_block_is_eof(cc.endoff.block)
2079 ? cc.endoff.pos - hed_cursor_phys_pos(&cc.endoff)
2080 : 0;
2081
2082 if (shift <= 0 && newshift > 0) {
2083 move_rel_fast(&cc.endoff, -FILE_BLOCK_SIZE);
2084 ret |= commit_forwards(&cc);
2085 hed_dup2_cursor(&cc.endoff, &cc.begoff);
2086 } else if (shift > 0 && newshift <= 0) {
2087 ret |= commit_backwards(&cc);
2088 hed_dup2_cursor(&cc.endoff, &cc.begoff);
2089 }
2090 shift = newshift;
2091 }
2092 assert(cc.endoff.pos >= hed_file_size(&file->f));
2093
2094 ret |= commit_forwards(&cc);
2095 put_cursor(&cc.begoff);
2096 put_cursor(&cc.endoff);
2097
2098 ftruncate(cc.wfd, hed_file_size(&file->f));
2099 file->f.phys_size = hed_file_size(&file->f);
2100
2101 ret |= close(cc.wfd);
2102 free(cc.buffer);
2103
2104 undirty_blocks(file);
2105
2106 if (!ret)
2107 clear_modified(file);
2108
2109 return ret;
2110 }
2111
2112 #ifdef HED_CONFIG_SWAP
2113 int
2114 hed_file_write_swap(struct hed_file *file)
2115 {
2116 return swp_write(file_swp(file_private(file)));
2117 }
2118
2119 static int
2120 do_read_swap(struct file_priv *file, struct swp_file *swp, hed_cursor_t *pos)
2121 {
2122 struct file_priv *swpfile = swp_private(swp);
2123 struct hed_block *cur, block;
2124 hed_uoff_t phys_pos;
2125
2126 if (file_stat(swpfile)->st_size != file_stat(file)->st_size ||
2127 file_stat(swpfile)->st_mtime != file_stat(file)->st_mtime) {
2128 fprintf(stderr, "stat info mismatch (you modified the file since hed ran on it; refusing to touch it)\n");
2129 return -1;
2130 }
2131
2132 BDEBUG("Swap header match\n");
2133
2134 phys_pos = 0;
2135 cur = first_block(swpfile);
2136 do {
2137 struct hed_block_data dataobj;
2138 size_t (*mergefn)(struct hed_file*, hed_cursor_t*,
2139 unsigned char*, size_t);
2140 void *data;
2141 size_t res;
2142
2143 if (swp_cpin(swp, &block, cur, sizeof(struct hed_block))) {
2144 perror("Cannot read block descriptor");
2145 return -1;
2146 }
2147 BDEBUG("BLOCK %p: flags %02lx phys 0x%02llx size 0x%llx\n",
2148 cur, block.flags, (long long)block.phys_pos,
2149 (long long)hed_block_size(&block));
2150
2151 if (block.phys_pos - phys_pos) {
2152 if (hed_file_erase_block(&file->f, pos,
2153 block.phys_pos - phys_pos)) {
2154 perror("Cannot erase");
2155 return -1;
2156 }
2157 phys_pos = block.phys_pos;
2158 }
2159
2160 if (!hed_block_is_inserted(&block))
2161 phys_pos += hed_block_size(&block);
2162
2163 if (!hed_block_is_dirty(&block)) {
2164 hed_move_relative(pos, hed_block_size(&block));
2165 continue;
2166 }
2167
2168 if (swp_cpin(swp, &dataobj, block.dataobj,
2169 sizeof(struct hed_block_data))) {
2170 perror("Cannot read data descriptor");
2171 return -1;
2172 }
2173 BDEBUG("DATA %p: size 0x%lx\n",
2174 block.dataobj, (long)dataobj.size);
2175
2176 if (! (data = malloc(hed_block_size(&block))) ) {
2177 perror("Cannot allocate data");
2178 return -1;
2179 }
2180
2181 if (swp_cpin(swp, data, dataobj.data + block.dataoff,
2182 hed_block_size(&block))) {
2183 perror("Cannot read data");
2184 return -1;
2185 }
2186
2187 mergefn = hed_block_is_inserted(&block)
2188 ? hed_file_insert_once
2189 : hed_file_set_block;
2190 res = mergefn(&file->f, pos, data, hed_block_size(&block));
2191 free(data);
2192 if (res) {
2193 perror("Cannot merge data");
2194 return -1;
2195 }
2196 } while (cur = next_block(&block), !hed_block_is_terminal(&block));
2197
2198 dump_blocks(file);
2199 return 0;
2200 }
2201
2202 int
2203 hed_file_read_swap(struct hed_file *f)
2204 {
2205 struct file_priv *file = file_private(f);
2206 struct swp_file *swp;
2207 hed_cursor_t pos;
2208 int ret;
2209
2210 if (! (swp = swp_init_read(file->swpname)) )
2211 return -1;
2212
2213 get_cursor(file, 0, &pos);
2214 ret = do_read_swap(file, swp, &pos);
2215 put_cursor(&pos);
2216
2217 swp_done(swp);
2218 return ret;
2219 }
2220
2221 #else
2222
2223 int
2224 hed_file_write_swap(struct hed_file *file)
2225 {
2226 return 0;
2227 }
2228
2229 int
2230 hed_file_read_swap(struct hed_file *file)
2231 {
2232 return -1;
2233 }
2234
2235 #endif /* HED_CONFIG_SWAP */
2236
2237 /* Check if the search string is all zero */
2238 static bool
2239 is_allzero(unsigned char *s, size_t len)
2240 {
2241 while (len--)
2242 if (*s++)
2243 return false;
2244 return true;
2245 }
2246
2247 static void
2248 reverse(unsigned char *p, size_t len)
2249 {
2250 unsigned char *q = p + len;
2251 while (p < q) {
2252 unsigned char x = *p;
2253 *p++ = *--q;
2254 *q = x;
2255 }
2256 }
2257
2258 static void
2259 compute_badchar(ssize_t *badchar, const unsigned char *s, ssize_t len)
2260 {
2261 size_t i = 1;
2262 while (i < len)
2263 badchar[*s++] = i++;
2264 }
2265
2266 static void
2267 compute_sfx(ssize_t *sfx, const unsigned char *s, ssize_t len)
2268 {
2269 ssize_t f, g, i;
2270
2271 sfx[len - 1] = len;
2272 f = 0; /* bogus assignment to silence a warning */
2273 g = len - 1;
2274 for (i = len - 2; i >= 0; --i) {
2275 if (i > g && sfx[i + len - 1 - f] < i - g)
2276 sfx[i] = sfx[i + len - 1 - f];
2277 else {
2278 if (i < g)
2279 g = i;
2280 f = i;
2281 while (g >= 0 && s[g] == s[g + len - 1 - f])
2282 --g;
2283 sfx[i] = f - g;
2284 }
2285 }
2286 }
2287
2288 static void
2289 compute_goodsfx(ssize_t *goodsfx, const unsigned char *s, ssize_t len)
2290 {
2291 ssize_t i, j, *sfx = goodsfx + len;
2292
2293 compute_sfx(sfx, s, len);
2294
2295 for (i = 0; i < len; ++i)
2296 goodsfx[i] = len;
2297 j = 0;
2298 for (i = len - 1; i >= 0; --i)
2299 if (sfx[i] == i + 1)
2300 for (; j < len - 1 - i; ++j)
2301 if (goodsfx[j] == len)
2302 goodsfx[j] = len - 1 - i;
2303 for (i = 0; i <= len - 2; ++i)
2304 goodsfx[len - 1 - sfx[i]] = len - 1 - i;
2305 }
2306
2307 /* Search for a constant byte string using the Boyer-Moore algorithm. */
2308 static inline unsigned char*
2309 search_buf(unsigned char *buf, size_t buflen, unsigned char *needle,
2310 size_t maxidx, ssize_t *badchar, ssize_t *goodsfx)
2311 {
2312 if (!maxidx)
2313 return memchr(buf, *needle, buflen);
2314
2315 while (buflen > maxidx) {
2316 unsigned char *p;
2317 size_t i;
2318 ssize_t shift;
2319
2320 for (p = buf + maxidx, i = maxidx; p >= buf; --p, --i)
2321 if (needle[i] != *p)
2322 break;
2323 if (p < buf)
2324 return buf;
2325
2326 shift = i + 1 - badchar[*p];
2327 if (shift < goodsfx[i])
2328 shift = goodsfx[i];
2329
2330 buf += shift;
2331 buflen -= shift;
2332 }
2333 return NULL;
2334 }
2335
2336 /* Search for a constant byte string backwards. */
2337 static inline unsigned char*
2338 search_buf_rev(unsigned char *buf, size_t buflen, unsigned char *needle,
2339 size_t maxidx, ssize_t *badchar, ssize_t *goodsfx)
2340 {
2341 if (!maxidx)
2342 return memrchr(buf, *needle, buflen);
2343
2344 buf += buflen - maxidx - 1;
2345 while (buflen > maxidx) {
2346 unsigned char *p;
2347 size_t i;
2348 ssize_t shift;
2349
2350 for (p = buf, i = maxidx; p <= buf + maxidx; ++p, --i)
2351 if (needle[i] != *p)
2352 break;
2353 if (p > buf + maxidx)
2354 return buf;
2355
2356 shift = i + 1 - badchar[*p];
2357 if (shift < goodsfx[i])
2358 shift = goodsfx[i];
2359
2360 buf -= shift;
2361 buflen -= shift;
2362 }
2363 return NULL;
2364 }
2365
2366 /* Search for a constant byte string using the Boyer-Moore algorithm. */
2367 static int
2368 find_bytestr(struct file_priv *file, hed_cursor_t *from, int dir,
2369 unsigned char *needle, size_t len)
2370 {
2371 void *dynalloc;
2372 ssize_t *badchar, *goodsfx;
2373 unsigned char *readbuf;
2374 unsigned char *p, *q;
2375 size_t remain;
2376 bool allzero;
2377 int ret;
2378
2379 if (len > 1) {
2380 dynalloc = calloc(sizeof(ssize_t) * (256 + 2*len)
2381 + 2*(len-1), 1);
2382 if (!dynalloc)
2383 return HED_FINDOFF_ERROR;
2384 badchar = dynalloc;
2385 goodsfx = badchar + 256;
2386 readbuf = dynalloc + sizeof(ssize_t) * (256 + 2*len);
2387
2388 if (dir < 0)
2389 reverse(needle, len);
2390 compute_badchar(badchar, needle, len);
2391 compute_goodsfx(goodsfx, needle, len);
2392 } else {
2393 dynalloc = NULL;
2394 badchar = goodsfx = NULL;
2395 readbuf = NULL;
2396 }
2397
2398 assert(!hed_block_is_terminal(from->block));
2399
2400 allzero = is_allzero(needle, len);
2401 --len; /* simplify offset computing */
2402
2403 ret = HED_FINDOFF_NO_MATCH;
2404 if (dir < 0) {
2405 remain = -len;
2406 while (move_rel_fast(from, -remain),
2407 ret && from->pos >= len) {
2408
2409 if (!hed_prepare_read(&file->f, from, SIZE_MAX)) {
2410 ret = HED_FINDOFF_ERROR;
2411 break;
2412 }
2413 remain = from->off;
2414
2415 if (remain < len) {
2416 remain += len;
2417 if (remain > from->pos)
2418 remain = from->pos;
2419 move_rel_fast(from, -remain);
2420 ++remain;
2421 if (hed_file_cpin(&file->f, readbuf,
2422 remain, from)) {
2423 remain = -len + 1;
2424 continue;
2425 }
2426 p = readbuf;
2427 } else if (!hed_block_is_virtual(from->block)) {
2428 p = from->block->dataobj->data +
2429 from->block->dataoff;
2430 from->off -= remain;
2431 from->pos -= remain;
2432 ++remain;
2433 } else if (!hed_block_is_bad(from->block) && allzero) {
2434 ret = 0;
2435 remain = len;
2436 continue;
2437 } else {
2438 ++remain;
2439 continue;
2440 }
2441
2442 q = search_buf_rev(p, remain, needle, len,
2443 badchar, goodsfx);
2444 if (q) {
2445 ret = 0;
2446 remain = p - q;
2447 } else
2448 remain = -len + 1;
2449 }
2450 } else {
2451 for ( ; ret && !hed_block_is_terminal(from->block);
2452 move_rel_fast(from, remain)) {
2453
2454 remain = hed_prepare_read(&file->f, from, SIZE_MAX);
2455 if (!remain) {
2456 ret = HED_FINDOFF_ERROR;
2457 break;
2458 }
2459
2460 if (remain <= len) {
2461 remain += len;
2462 remain = copy_in(file, readbuf, remain, from);
2463 if (remain) {
2464 remain -= len;
2465 continue;
2466 }
2467 p = readbuf;
2468 } else if (!hed_block_is_virtual(from->block)) {
2469 p = from->block->dataobj->data +
2470 from->block->dataoff + from->off;
2471 from->off += remain;
2472 from->pos += remain;
2473 } else if (!hed_block_is_bad(from->block) && allzero) {
2474 ret = 0;
2475 remain = 0;
2476 continue;
2477 } else {
2478 remain -= len;
2479 continue;
2480 }
2481
2482 q = search_buf(p, remain, needle, len,
2483 badchar, goodsfx);
2484 if (q) {
2485 ret = 0;
2486 remain = q - p - remain;
2487 } else
2488 remain = -len;
2489 }
2490 }
2491
2492 if (dynalloc)
2493 free(dynalloc);
2494 return ret;
2495 }
2496
2497 static int
2498 find_expr(struct file_priv *file, hed_cursor_t *from, int dir,
2499 struct hed_expr *expr)
2500 {
2501 size_t len = hed_expr_len(expr);
2502 unsigned char *buf;
2503
2504 if (!len)
2505 return HED_FINDOFF_NO_MATCH;
2506
2507 for (;;) {
2508 hed_cursor_t match;
2509 size_t remain;
2510 unsigned char *p;
2511 size_t pos;
2512
2513 if (hed_expr_eval(expr) & HED_AEF_ERROR)
2514 return HED_FINDOFF_ERROR;
2515 buf = hed_expr_buf(expr);
2516
2517 hed_dup_cursor(from, &match);
2518 p = NULL; /* bogus assignment to silence a warning */
2519 remain = 0;
2520 for (pos = 0; pos < len; pos++) {
2521 if (!remain) {
2522 remain = hed_prepare_read(&file->f, &match,
2523 SIZE_MAX);
2524 if (!remain ||
2525 hed_block_is_bad(match.block))
2526 break;
2527 p = hed_cursor_data(&match);
2528 cursor_next_block(&match);
2529 }
2530 if ((p ? *p++ : 0) != buf[pos])
2531 break;
2532 remain--;
2533 }
2534 put_cursor(&match);
2535
2536 if (pos == len)
2537 return 0;
2538 if (!remain)
2539 return HED_FINDOFF_ERROR;
2540
2541 if (dir < 0 && hed_block_is_terminal(from->block)) {
2542 from->pos -= from->off;
2543 from->off = 0;
2544 }
2545 move_rel_fast(from, dir);
2546 if (hed_block_is_terminal(from->block))
2547 break;
2548
2549 if (! (hed_expr_flags(expr) & HED_AEF_DYNAMIC) )
2550 return find_bytestr(file, from, dir, buf, len);
2551 }
2552
2553 return HED_FINDOFF_NO_MATCH;
2554 }
2555
2556 int
2557 hed_file_find_expr(struct hed_file *f, hed_cursor_t *pos, int dir,
2558 struct hed_expr *expr)
2559 {
2560 struct file_priv *file = file_private(f);
2561 int res;
2562
2563 assert(dir == 1 || dir == -1);
2564
2565 set_readahead(file, dir > 0 ? HED_RA_FORWARD : HED_RA_BACKWARD);
2566 res = find_expr(file, pos, dir, expr);
2567 set_readahead(file, HED_RA_NONE);
2568
2569 return res;
2570 }
Fast hexadecimal editor