boehm-gc/cord/cordxtra.c

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