Debian Codegraph @

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