Debian Codegraph @

gc/cord/cordxtra.c

raw
1 /*
2 * Copyright (c) 1993-1994 by Xerox Corporation. All rights reserved.
3 *
4 * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
5 * OR IMPLIED. ANY USE IS AT YOUR OWN RISK.
6 *
7 * Permission is hereby granted to use or copy this program
8 * for any purpose, provided the above notices are retained on all copies.
9 * Permission to modify the code and to distribute modified code is granted,
10 * provided the above notices are retained, and a notice that the code was
11 * modified is included with the above copyright notice.
12 */
13
14 /*
15 * These are functions on cords that do not need to understand their
16 * implementation. They serve also serve as example client code for
17 * cord_basics.
18 */
19
20 #ifdef HAVE_CONFIG_H
21 # include "config.h"
22 #endif
23 #ifndef CORD_BUILD
24 # define CORD_BUILD
25 #endif
26
27 # include <stdio.h>
28 # include <string.h>
29 # include <stdlib.h>
30 # include <stdarg.h>
31
32 # include "cord.h"
33 # include "ec.h"
34
35 # define I_HIDE_POINTERS /* So we get access to allocation lock. */
36 /* We use this for lazy file reading, */
37 /* so that we remain independent */
38 /* of the threads primitives. */
39 # include "gc.h"
40
41 /* If available, use GCC built-in atomic load-acquire and store-release */
42 /* primitives to access the cache lines safely. Otherwise, fall back */
43 /* to using the GC allocation lock even during the cache lines reading. */
44 /* Note: for simplicity of libcord building, do not rely on GC_THREADS */
45 /* macro, libatomic_ops package presence and private/gc_atomic_ops.h. */
46 #if !defined(AO_DISABLE_GCC_ATOMICS) \
47 && ((defined(__clang__) && __clang_major__ >= 8) /* clang 8.0+ */ \
48 || (defined(__GNUC__) /* gcc 5.4+ */ \
49 && (__GNUC__ > 5 || (__GNUC__ == 5 && __GNUC_MINOR__ >= 4))))
50 # define CORD_USE_GCC_ATOMIC
51 #endif
52
53 /* The standard says these are in stdio.h, but they aren't always: */
54 # ifndef SEEK_SET
55 # define SEEK_SET 0
56 # endif
57 # ifndef SEEK_END
58 # define SEEK_END 2
59 # endif
60
61 # define BUFSZ 2048 /* Size of stack allocated buffers when */
62 /* we want large buffers. */
63
64 typedef void (* oom_fn)(void);
65
66 # define OUT_OF_MEMORY { if (CORD_oom_fn != (oom_fn) 0) (*CORD_oom_fn)(); \
67 ABORT("Out of memory"); }
68 # define ABORT(msg) { fprintf(stderr, "%s\n", msg); abort(); }
69
70 #if GC_GNUC_PREREQ(3, 4) || defined(__clang__)
71 # define CORD_ATTR_UNUSED __attribute__((__unused__))
72 #else
73 # define CORD_ATTR_UNUSED /* empty */
74 #endif
75
76 CORD CORD_cat_char(CORD x, char c)
77 {
78 char * string;
79
80 if (c == '\0') return(CORD_cat(x, CORD_nul(1)));
81 string = (char *)GC_MALLOC_ATOMIC(2);
82 if (string == 0) OUT_OF_MEMORY;
83 string[0] = c;
84 string[1] = '\0';
85 return(CORD_cat_char_star(x, string, 1));
86 }
87
88 CORD CORD_catn(int nargs, ...)
89 {
90 CORD result = CORD_EMPTY;
91 va_list args;
92 int i;
93
94 va_start(args, nargs);
95 for (i = 0; i < nargs; i++) {
96 CORD next = va_arg(args, CORD);
97 result = CORD_cat(result, next);
98 }
99 va_end(args);
100 return(result);
101 }
102
103 typedef struct {
104 size_t len;
105 size_t count;
106 char * buf;
107 } CORD_fill_data;
108
109 int CORD_fill_proc(char c, void * client_data)
110 {
111 CORD_fill_data * d = (CORD_fill_data *)client_data;
112 size_t count = d -> count;
113
114 (d -> buf)[count] = c;
115 d -> count = ++count;
116 if (count >= d -> len) {
117 return(1);
118 } else {
119 return(0);
120 }
121 }
122
123 int CORD_batched_fill_proc(const char * s, void * client_data)
124 {
125 CORD_fill_data * d = (CORD_fill_data *)client_data;
126 size_t count = d -> count;
127 size_t max = d -> len;
128 char * buf = d -> buf;
129 const char * t = s;
130
131 while((buf[count] = *t++) != '\0') {
132 count++;
133 if (count >= max) {
134 d -> count = count;
135 return(1);
136 }
137 }
138 d -> count = count;
139 return(0);
140 }
141
142 /* Fill buf with len characters starting at i. */
143 /* Assumes len characters are available in buf. */
144 /* Return 1 if buf is filled fully (and len is */
145 /* non-zero), 0 otherwise. */
146 int CORD_fill_buf(CORD x, size_t i, size_t len, char * buf)
147 {
148 CORD_fill_data fd;
149
150 fd.len = len;
151 fd.buf = buf;
152 fd.count = 0;
153 return CORD_iter5(x, i, CORD_fill_proc, CORD_batched_fill_proc, &fd);
154 }
155
156 int CORD_cmp(CORD x, CORD y)
157 {
158 CORD_pos xpos;
159 CORD_pos ypos;
160
161 if (y == CORD_EMPTY) return(x != CORD_EMPTY);
162 if (x == CORD_EMPTY) return(-1);
163 if (CORD_IS_STRING(y) && CORD_IS_STRING(x)) return(strcmp(x,y));
164 CORD_set_pos(xpos, x, 0);
165 CORD_set_pos(ypos, y, 0);
166 for(;;) {
167 size_t avail, yavail;
168
169 if (!CORD_pos_valid(xpos)) {
170 if (CORD_pos_valid(ypos)) {
171 return(-1);
172 } else {
173 return(0);
174 }
175 }
176 if (!CORD_pos_valid(ypos)) {
177 return(1);
178 }
179 avail = CORD_pos_chars_left(xpos);
180 if (avail == 0
181 || (yavail = CORD_pos_chars_left(ypos)) == 0) {
182 char xcurrent = CORD_pos_fetch(xpos);
183 char ycurrent = CORD_pos_fetch(ypos);
184 if (xcurrent != ycurrent) return(xcurrent - ycurrent);
185 CORD_next(xpos);
186 CORD_next(ypos);
187 } else {
188 /* process as many characters as we can */
189 int result;
190
191 if (avail > yavail) avail = yavail;
192 result = strncmp(CORD_pos_cur_char_addr(xpos),
193 CORD_pos_cur_char_addr(ypos), avail);
194 if (result != 0) return(result);
195 CORD_pos_advance(xpos, avail);
196 CORD_pos_advance(ypos, avail);
197 }
198 }
199 }
200
201 int CORD_ncmp(CORD x, size_t x_start, CORD y, size_t y_start, size_t len)
202 {
203 CORD_pos xpos;
204 CORD_pos ypos;
205 size_t count;
206
207 CORD_set_pos(xpos, x, x_start);
208 CORD_set_pos(ypos, y, y_start);
209 for(count = 0; count < len;) {
210 long avail, yavail;
211
212 if (!CORD_pos_valid(xpos)) {
213 if (CORD_pos_valid(ypos)) {
214 return(-1);
215 } else {
216 return(0);
217 }
218 }
219 if (!CORD_pos_valid(ypos)) {
220 return(1);
221 }
222 if ((avail = CORD_pos_chars_left(xpos)) <= 0
223 || (yavail = CORD_pos_chars_left(ypos)) <= 0) {
224 char xcurrent = CORD_pos_fetch(xpos);
225 char ycurrent = CORD_pos_fetch(ypos);
226
227 if (xcurrent != ycurrent) return(xcurrent - ycurrent);
228 CORD_next(xpos);
229 CORD_next(ypos);
230 count++;
231 } else {
232 /* process as many characters as we can */
233 int result;
234
235 if (avail > yavail) avail = yavail;
236 count += avail;
237 if (count > len)
238 avail -= (long)(count - len);
239 result = strncmp(CORD_pos_cur_char_addr(xpos),
240 CORD_pos_cur_char_addr(ypos), (size_t)avail);
241 if (result != 0) return(result);
242 CORD_pos_advance(xpos, (size_t)avail);
243 CORD_pos_advance(ypos, (size_t)avail);
244 }
245 }
246 return(0);
247 }
248
249 char * CORD_to_char_star(CORD x)
250 {
251 size_t len = CORD_len(x);
252 char * result = (char *)GC_MALLOC_ATOMIC(len + 1);
253
254 if (result == 0) OUT_OF_MEMORY;
255 if (len > 0 && CORD_fill_buf(x, 0, len, result) != 1)
256 ABORT("CORD_fill_buf malfunction");
257 result[len] = '\0';
258 return(result);
259 }
260
261 CORD CORD_from_char_star(const char *s)
262 {
263 char * result;
264 size_t len = strlen(s);
265
266 if (0 == len) return(CORD_EMPTY);
267 result = (char *)GC_MALLOC_ATOMIC(len + 1);
268 if (result == 0) OUT_OF_MEMORY;
269 memcpy(result, s, len+1);
270 return(result);
271 }
272
273 const char * CORD_to_const_char_star(CORD x)
274 {
275 if (x == 0) return("");
276 if (CORD_IS_STRING(x)) return((const char *)x);
277 return(CORD_to_char_star(x));
278 }
279
280 char CORD_fetch(CORD x, size_t i)
281 {
282 CORD_pos xpos;
283
284 CORD_set_pos(xpos, x, i);
285 if (!CORD_pos_valid(xpos)) ABORT("bad index?");
286 return(CORD_pos_fetch(xpos));
287 }
288
289
290 int CORD_put_proc(char c, void * client_data)
291 {
292 FILE * f = (FILE *)client_data;
293
294 return(putc(c, f) == EOF);
295 }
296
297 int CORD_batched_put_proc(const char * s, void * client_data)
298 {
299 FILE * f = (FILE *)client_data;
300
301 return(fputs(s, f) == EOF);
302 }
303
304
305 int CORD_put(CORD x, FILE * f)
306 {
307 if (CORD_iter5(x, 0, CORD_put_proc, CORD_batched_put_proc, f)) {
308 return(EOF);
309 } else {
310 return(1);
311 }
312 }
313
314 typedef struct {
315 size_t pos; /* Current position in the cord */
316 char target; /* Character we're looking for */
317 } chr_data;
318
319 int CORD_chr_proc(char c, void * client_data)
320 {
321 chr_data * d = (chr_data *)client_data;
322
323 if (c == d -> target) return(1);
324 (d -> pos) ++;
325 return(0);
326 }
327
328 int CORD_rchr_proc(char c, void * client_data)
329 {
330 chr_data * d = (chr_data *)client_data;
331
332 if (c == d -> target) return(1);
333 (d -> pos) --;
334 return(0);
335 }
336
337 int CORD_batched_chr_proc(const char *s, void * client_data)
338 {
339 chr_data * d = (chr_data *)client_data;
340 const char * occ = strchr(s, d -> target);
341
342 if (NULL == occ) {
343 d -> pos += strlen(s);
344 return(0);
345 } else {
346 d -> pos += occ - s;
347 return(1);
348 }
349 }
350
351 size_t CORD_chr(CORD x, size_t i, int c)
352 {
353 chr_data d;
354
355 d.pos = i;
356 d.target = (char)c;
357 if (CORD_iter5(x, i, CORD_chr_proc, CORD_batched_chr_proc, &d)) {
358 return(d.pos);
359 } else {
360 return(CORD_NOT_FOUND);
361 }
362 }
363
364 size_t CORD_rchr(CORD x, size_t i, int c)
365 {
366 chr_data d;
367
368 d.pos = i;
369 d.target = (char)c;
370 if (CORD_riter4(x, i, CORD_rchr_proc, &d)) {
371 return(d.pos);
372 } else {
373 return(CORD_NOT_FOUND);
374 }
375 }
376
377 /* Find the first occurrence of s in x at position start or later. */
378 /* This uses an asymptotically poor algorithm, which should typically */
379 /* perform acceptably. We compare the first few characters directly, */
380 /* and call CORD_ncmp whenever there is a partial match. */
381 /* This has the advantage that we allocate very little, or not at all. */
382 /* It's very fast if there are few close misses. */
383 size_t CORD_str(CORD x, size_t start, CORD s)
384 {
385 CORD_pos xpos;
386 size_t xlen = CORD_len(x);
387 size_t slen;
388 size_t start_len;
389 const char * s_start;
390 unsigned long s_buf = 0; /* The first few characters of s */
391 unsigned long x_buf = 0; /* Start of candidate substring. */
392 /* Initialized only to make compilers */
393 /* happy. */
394 unsigned long mask = 0;
395 size_t i;
396 size_t match_pos;
397
398 if (s == CORD_EMPTY) return(start);
399 if (CORD_IS_STRING(s)) {
400 s_start = s;
401 slen = strlen(s);
402 } else {
403 s_start = CORD_to_char_star(CORD_substr(s, 0, sizeof(unsigned long)));
404 slen = CORD_len(s);
405 }
406 if (xlen < start || xlen - start < slen) return(CORD_NOT_FOUND);
407 start_len = slen;
408 if (start_len > sizeof(unsigned long)) start_len = sizeof(unsigned long);
409 CORD_set_pos(xpos, x, start);
410 for (i = 0; i < start_len; i++) {
411 mask <<= 8;
412 mask |= 0xff;
413 s_buf <<= 8;
414 s_buf |= (unsigned char)s_start[i];
415 x_buf <<= 8;
416 x_buf |= (unsigned char)CORD_pos_fetch(xpos);
417 CORD_next(xpos);
418 }
419 for (match_pos = start; ; match_pos++) {
420 if ((x_buf & mask) == s_buf) {
421 if (slen == start_len ||
422 CORD_ncmp(x, match_pos + start_len,
423 s, start_len, slen - start_len) == 0) {
424 return(match_pos);
425 }
426 }
427 if ( match_pos == xlen - slen ) {
428 return(CORD_NOT_FOUND);
429 }
430 x_buf <<= 8;
431 x_buf |= (unsigned char)CORD_pos_fetch(xpos);
432 CORD_next(xpos);
433 }
434 }
435
436 void CORD_ec_flush_buf(CORD_ec x)
437 {
438 size_t len = x[0].ec_bufptr - x[0].ec_buf;
439 char * s;
440
441 if (len == 0) return;
442 s = (char *)GC_MALLOC_ATOMIC(len + 1);
443 if (NULL == s) OUT_OF_MEMORY;
444 memcpy(s, x[0].ec_buf, len);
445 s[len] = '\0';
446 x[0].ec_cord = CORD_cat_char_star(x[0].ec_cord, s, len);
447 x[0].ec_bufptr = x[0].ec_buf;
448 }
449
450 void CORD_ec_append_cord(CORD_ec x, CORD s)
451 {
452 CORD_ec_flush_buf(x);
453 x[0].ec_cord = CORD_cat(x[0].ec_cord, s);
454 }
455
456 char CORD_nul_func(size_t i CORD_ATTR_UNUSED, void * client_data)
457 {
458 return (char)(GC_word)client_data;
459 }
460
461 CORD CORD_chars(char c, size_t i)
462 {
463 return CORD_from_fn(CORD_nul_func, (void *)(GC_word)(unsigned char)c, i);
464 }
465
466 CORD CORD_from_file_eager(FILE * f)
467 {
468 CORD_ec ecord;
469
470 CORD_ec_init(ecord);
471 for(;;) {
472 int c = getc(f);
473
474 if (c == 0) {
475 /* Append the right number of NULs */
476 /* Note that any string of NULs is represented in 4 words, */
477 /* independent of its length. */
478 size_t count = 1;
479
480 CORD_ec_flush_buf(ecord);
481 while ((c = getc(f)) == 0) count++;
482 ecord[0].ec_cord = CORD_cat(ecord[0].ec_cord, CORD_nul(count));
483 }
484 if (c == EOF) break;
485 CORD_ec_append(ecord, (char)c);
486 }
487 (void) fclose(f);
488 return(CORD_balance(CORD_ec_to_cord(ecord)));
489 }
490
491 /* The state maintained for a lazily read file consists primarily */
492 /* of a large direct-mapped cache of previously read values. */
493 /* We could rely more on stdio buffering. That would have 2 */
494 /* disadvantages: */
495 /* 1) Empirically, not all fseek implementations preserve the */
496 /* buffer whenever they could. */
497 /* 2) It would fail if 2 different sections of a long cord */
498 /* were being read alternately. */
499 /* We do use the stdio buffer for read ahead. */
500 /* To guarantee thread safety in the presence of atomic pointer */
501 /* writes, cache lines are always replaced, and never modified in */
502 /* place. */
503
504 # define LOG_CACHE_SZ 14
505 # define CACHE_SZ (1 << LOG_CACHE_SZ)
506 # define LOG_LINE_SZ 9
507 # define LINE_SZ (1 << LOG_LINE_SZ)
508
509 typedef struct {
510 size_t tag;
511 char data[LINE_SZ];
512 /* data[i%LINE_SZ] = ith char in file if tag = i/LINE_SZ */
513 } cache_line;
514
515 typedef struct {
516 FILE * lf_file;
517 size_t lf_current; /* Current file pointer value */
518 cache_line * volatile lf_cache[CACHE_SZ/LINE_SZ];
519 } lf_state;
520
521 # define MOD_CACHE_SZ(n) ((n) & (CACHE_SZ - 1))
522 # define DIV_CACHE_SZ(n) ((n) >> LOG_CACHE_SZ)
523 # define MOD_LINE_SZ(n) ((n) & (LINE_SZ - 1))
524 # define DIV_LINE_SZ(n) ((n) >> LOG_LINE_SZ)
525 # define LINE_START(n) ((n) & ~(size_t)(LINE_SZ - 1))
526
527 typedef struct {
528 lf_state * state;
529 size_t file_pos; /* Position of needed character. */
530 cache_line * new_cache;
531 } refill_data;
532
533 /* Executed with allocation lock. */
534 static void * GC_CALLBACK refill_cache(void * client_data)
535 {
536 lf_state * state = ((refill_data *)client_data) -> state;
537 size_t file_pos = ((refill_data *)client_data) -> file_pos;
538 FILE *f = state -> lf_file;
539 size_t line_start = LINE_START(file_pos);
540 size_t line_no = DIV_LINE_SZ(MOD_CACHE_SZ(file_pos));
541 cache_line * new_cache = ((refill_data *)client_data) -> new_cache;
542
543 if (line_start != state -> lf_current
544 && fseek(f, (long)line_start, SEEK_SET) != 0) {
545 ABORT("fseek failed");
546 }
547 if (fread(new_cache -> data, sizeof(char), LINE_SZ, f)
548 <= file_pos - line_start) {
549 ABORT("fread failed");
550 }
551 new_cache -> tag = DIV_LINE_SZ(file_pos);
552 # ifdef CORD_USE_GCC_ATOMIC
553 __atomic_store_n(&(state -> lf_cache[line_no]), new_cache,
554 __ATOMIC_RELEASE);
555 # else
556 state -> lf_cache[line_no] = new_cache;
557 # endif
558 GC_END_STUBBORN_CHANGE((/* no volatile */ void *)(state -> lf_cache
559 + line_no));
560 state -> lf_current = line_start + LINE_SZ;
561 return (void *)((GC_word)new_cache->data[MOD_LINE_SZ(file_pos)]);
562 }
563
564 #ifndef CORD_USE_GCC_ATOMIC
565 static void * GC_CALLBACK get_cache_line(void * client_data)
566 {
567 return (void *)(*(cache_line **)client_data);
568 }
569 #endif
570
571 char CORD_lf_func(size_t i, void * client_data)
572 {
573 lf_state * state = (lf_state *)client_data;
574 cache_line * volatile * cl_addr =
575 &(state -> lf_cache[DIV_LINE_SZ(MOD_CACHE_SZ(i))]);
576 # ifdef CORD_USE_GCC_ATOMIC
577 cache_line * cl = (cache_line *)__atomic_load_n(cl_addr,
578 __ATOMIC_ACQUIRE);
579 # else
580 cache_line * cl = (cache_line *)GC_call_with_alloc_lock(
581 get_cache_line, (void *)cl_addr);
582 # endif
583
584 if (cl == 0 || cl -> tag != DIV_LINE_SZ(i)) {
585 /* Cache miss */
586 refill_data rd;
587
588 rd.state = state;
589 rd.file_pos = i;
590 rd.new_cache = GC_NEW_ATOMIC(cache_line);
591 if (rd.new_cache == 0) OUT_OF_MEMORY;
592 return (char)((GC_word)GC_call_with_alloc_lock(refill_cache, &rd));
593 }
594 return(cl -> data[MOD_LINE_SZ(i)]);
595 }
596
597 #ifndef GC_NO_FINALIZATION
598 void CORD_lf_close_proc(void * obj, void * client_data CORD_ATTR_UNUSED)
599 {
600 if (fclose(((lf_state *)obj) -> lf_file) != 0) {
601 ABORT("CORD_lf_close_proc: fclose failed");
602 }
603 }
604 #endif
605
606 CORD CORD_from_file_lazy_inner(FILE * f, size_t len)
607 {
608 lf_state * state = GC_NEW(lf_state);
609 int i;
610
611 if (state == 0) OUT_OF_MEMORY;
612 if (len != 0) {
613 /* Dummy read to force buffer allocation. */
614 /* This greatly increases the probability */
615 /* of avoiding deadlock if buffer allocation */
616 /* is redirected to GC_malloc and the */
617 /* world is multi-threaded. */
618 char buf[1];
619
620 if (fread(buf, 1, 1, f) > 1
621 || fseek(f, 0l, SEEK_SET) != 0) {
622 ABORT("Bad f argument or I/O failure");
623 }
624 }
625 state -> lf_file = f;
626 for (i = 0; i < CACHE_SZ/LINE_SZ; i++) {
627 state -> lf_cache[i] = 0;
628 }
629 state -> lf_current = 0;
630 # ifndef GC_NO_FINALIZATION
631 GC_REGISTER_FINALIZER(state, CORD_lf_close_proc, 0, 0, 0);
632 # endif
633 return(CORD_from_fn(CORD_lf_func, state, len));
634 }
635
636 CORD CORD_from_file_lazy(FILE * f)
637 {
638 long len;
639
640 if (fseek(f, 0l, SEEK_END) != 0
641 || (len = ftell(f)) < 0
642 || fseek(f, 0l, SEEK_SET) != 0) {
643 ABORT("Bad f argument or I/O failure");
644 }
645 return(CORD_from_file_lazy_inner(f, (size_t)len));
646 }
647
648 # define LAZY_THRESHOLD (128*1024 + 1)
649
650 CORD CORD_from_file(FILE * f)
651 {
652 long len;
653
654 if (fseek(f, 0l, SEEK_END) != 0
655 || (len = ftell(f)) < 0
656 || fseek(f, 0l, SEEK_SET) != 0) {
657 ABORT("Bad f argument or I/O failure");
658 }
659 if (len < LAZY_THRESHOLD) {
660 return(CORD_from_file_eager(f));
661 } else {
662 return(CORD_from_file_lazy_inner(f, (size_t)len));
663 }
664 }