home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / sa104os2.zip / SATHR104.ZIP / SATHER / SYSTEM / GC / CORD / CORDXTRA.C < prev    next >
C/C++ Source or Header  |  1994-10-03  |  17KB  |  600 lines
  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, October 3, 1994 5:10 pm PDT */
  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;
  227.     char * result;
  228.     
  229.     if (x == 0) return("");
  230.     len = CORD_len(x);
  231.     result = (char *)GC_MALLOC_ATOMIC(len + 1);
  232.     if (result == 0) OUT_OF_MEMORY;
  233.     CORD_fill_buf(x, 0, len, result);
  234.     result[len] = '\0';
  235.     return(result);
  236. }
  237.  
  238. const char * CORD_to_const_char_star(CORD x)
  239. {
  240.     if (x == 0) return("");
  241.     if (CORD_IS_STRING(x)) return((const char *)x);
  242.     return(CORD_to_char_star(x));
  243. }
  244.  
  245. char CORD_fetch(CORD x, size_t i)
  246. {
  247.     CORD_pos xpos;
  248.     
  249.     CORD_set_pos(xpos, x, i);
  250.     if (!CORD_pos_valid(xpos)) ABORT("bad index?");
  251.     return(CORD_pos_fetch(xpos));
  252. }
  253.  
  254.  
  255. int CORD_put_proc(char c, void * client_data)
  256. {
  257.     register FILE * f = (FILE *)client_data;
  258.     
  259.     return(putc(c, f) == EOF);
  260. }
  261.  
  262. int CORD_batched_put_proc(const char * s, void * client_data)
  263. {
  264.     register FILE * f = (FILE *)client_data;
  265.     
  266.     return(fputs(s, f) == EOF);
  267. }
  268.     
  269.  
  270. int CORD_put(CORD x, FILE * f)
  271. {
  272.     if (CORD_iter5(x, 0, CORD_put_proc, CORD_batched_put_proc, f)) {
  273.         return(EOF);
  274.     } else {
  275.         return(1);
  276.     }
  277. }
  278.  
  279. typedef struct {
  280.     size_t pos;        /* Current position in the cord */
  281.     char target;    /* Character we're looking for    */
  282. } chr_data;
  283.  
  284. int CORD_chr_proc(char c, void * client_data)
  285. {
  286.     register chr_data * d = (chr_data *)client_data;
  287.     
  288.     if (c == d -> target) return(1);
  289.     (d -> pos) ++;
  290.     return(0);
  291. }
  292.  
  293. int CORD_rchr_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_batched_chr_proc(const char *s, void * client_data)
  303. {
  304.     register chr_data * d = (chr_data *)client_data;
  305.     register char * occ = strchr(s, d -> target);
  306.     
  307.     if (occ == 0) {
  308.           d -> pos += strlen(s);
  309.           return(0);
  310.     } else {
  311.         d -> pos += occ - s;
  312.         return(1);
  313.     }
  314. }
  315.  
  316. size_t CORD_chr(CORD x, size_t i, int c)
  317. {
  318.     chr_data d;
  319.     
  320.     d.pos = i;
  321.     d.target = c;
  322.     if (CORD_iter5(x, i, CORD_chr_proc, CORD_batched_chr_proc, &d)) {
  323.         return(d.pos);
  324.     } else {
  325.         return(CORD_NOT_FOUND);
  326.     }
  327. }
  328.  
  329. size_t CORD_rchr(CORD x, size_t i, int c)
  330. {
  331.     chr_data d;
  332.     
  333.     d.pos = i;
  334.     d.target = c;
  335.     if (CORD_riter4(x, i, CORD_rchr_proc, &d)) {
  336.         return(d.pos);
  337.     } else {
  338.         return(CORD_NOT_FOUND);
  339.     }
  340. }
  341.  
  342. /* Find the first occurrence of s in x at position start or later.    */
  343. /* This uses an asymptotically poor algorithm, which should typically     */
  344. /* perform acceptably.  We compare the first few characters directly,    */
  345. /* and call CORD_ncmp whenever there is a partial match.        */
  346. /* This has the advantage that we allocate very little, or not at all.    */
  347. /* It's very fast if there are few close misses.            */
  348. size_t CORD_str(CORD x, size_t start, CORD s)
  349. {
  350.     CORD_pos xpos;
  351.     size_t xlen = CORD_len(x);
  352.     size_t slen;
  353.     register size_t start_len;
  354.     const char * s_start;
  355.     unsigned long s_buf = 0;    /* The first few characters of s    */
  356.     unsigned long x_buf = 0;    /* Start of candidate substring.    */
  357.                     /* Initialized only to make compilers    */
  358.                     /* happy.                */
  359.     unsigned long mask = 0;
  360.     register size_t i;
  361.     register size_t match_pos;
  362.     
  363.     if (s == CORD_EMPTY) return(start);
  364.     if (CORD_IS_STRING(s)) {
  365.         s_start = s;
  366.         slen = strlen(s);
  367.     } else {
  368.         s_start = CORD_to_char_star(CORD_substr(s, 0, sizeof(unsigned long)));
  369.         slen = CORD_len(s);
  370.     }
  371.     if (xlen < start || xlen - start < slen) return(CORD_NOT_FOUND);
  372.     start_len = slen;
  373.     if (start_len > sizeof(unsigned long)) start_len = sizeof(unsigned long);
  374.     CORD_set_pos(xpos, x, start);
  375.     for (i = 0; i < start_len; i++) {
  376.         mask <<= 8;
  377.         mask |= 0xff;
  378.         s_buf <<= 8;
  379.         s_buf |= s_start[i];
  380.         x_buf <<= 8;
  381.         x_buf |= CORD_pos_fetch(xpos);
  382.         CORD_next(xpos);
  383.     }
  384.     for (match_pos = start; match_pos < xlen - slen; match_pos++) {
  385.         if ((x_buf & mask) == s_buf) {
  386.             if (slen == start_len ||
  387.                  CORD_ncmp(x, match_pos + start_len,
  388.                         s, start_len, slen - start_len) == 0) {
  389.                 return(match_pos);
  390.             }
  391.         }
  392.         x_buf <<= 8;
  393.         x_buf |= CORD_pos_fetch(xpos);
  394.         CORD_next(xpos);
  395.     }
  396.     return(CORD_NOT_FOUND);
  397. }
  398.  
  399. void CORD_ec_flush_buf(CORD_ec x)
  400. {
  401.     register size_t len = x[0].ec_bufptr - x[0].ec_buf;
  402.     char * s;
  403.  
  404.     if (len == 0) return;
  405.     s = GC_MALLOC_ATOMIC(len+1);
  406.     memcpy(s, x[0].ec_buf, len);
  407.     s[len] = '\0';
  408.     x[0].ec_cord = CORD_cat_char_star(x[0].ec_cord, s, len);
  409.     x[0].ec_bufptr = x[0].ec_buf;
  410. }
  411.  
  412. void CORD_ec_append_cord(CORD_ec x, CORD s)
  413. {
  414.     CORD_ec_flush_buf(x);
  415.     x[0].ec_cord = CORD_cat(x[0].ec_cord, s);
  416. }
  417.  
  418. /*ARGSUSED*/
  419. char CORD_nul_func(size_t i, void * client_data)
  420. {
  421.     return((char)(unsigned long)client_data);
  422. }
  423.  
  424.  
  425. CORD CORD_chars(char c, size_t i)
  426. {
  427.     return(CORD_from_fn(CORD_nul_func, (void *)(unsigned long)c, i));
  428. }
  429.  
  430. CORD CORD_from_file_eager(FILE * f)
  431. {
  432.     register int c;
  433.     CORD_ec ecord;
  434.     
  435.     CORD_ec_init(ecord);
  436.     for(;;) {
  437.         c = getc(f);
  438.         if (c == 0) {
  439.           /* Append the right number of NULs    */
  440.           /* Note that any string of NULs is rpresented in 4 words,    */
  441.           /* independent of its length.                    */
  442.             register size_t count = 1;
  443.             
  444.             CORD_ec_flush_buf(ecord);
  445.             while ((c = getc(f)) == 0) count++;
  446.             ecord[0].ec_cord = CORD_cat(ecord[0].ec_cord, CORD_nul(count));
  447.         }
  448.         if (c == EOF) break;
  449.         CORD_ec_append(ecord, c);
  450.     }
  451.     (void) fclose(f);
  452.     return(CORD_balance(CORD_ec_to_cord(ecord)));
  453. }
  454.  
  455. /* The state maintained for a lazily read file consists primarily    */
  456. /* of a large direct-mapped cache of previously read values.        */
  457. /* We could rely more on stdio buffering.  That would have 2        */
  458. /* disadvantages:                            */
  459. /*      1) Empirically, not all fseek implementations preserve the    */
  460. /*       buffer whenever they could.                    */
  461. /*    2) It would fail if 2 different sections of a long cord        */
  462. /*       were being read alternately.                    */
  463. /* We do use the stdio buffer for read ahead.                */
  464. /* To guarantee thread safety in the presence of atomic pointer        */
  465. /* writes, cache lines are always replaced, and never modified in    */
  466. /* place.                                */
  467.  
  468. # define LOG_CACHE_SZ 14
  469. # define CACHE_SZ (1 << LOG_CACHE_SZ)
  470. # define LOG_LINE_SZ 9
  471. # define LINE_SZ (1 << LOG_LINE_SZ)
  472.  
  473. typedef struct {
  474.     size_t tag;
  475.     char data[LINE_SZ];
  476.         /* data[i%LINE_SZ] = ith char in file if tag = i/LINE_SZ    */
  477. } cache_line;
  478.  
  479. typedef struct {
  480.     FILE * lf_file;
  481.     size_t lf_current;    /* Current file pointer value */
  482.     cache_line * volatile lf_cache[CACHE_SZ/LINE_SZ];
  483. } lf_state;
  484.  
  485. # define MOD_CACHE_SZ(n) ((n) & (CACHE_SZ - 1))
  486. # define DIV_CACHE_SZ(n) ((n) >> LOG_CACHE_SZ)
  487. # define MOD_LINE_SZ(n) ((n) & (LINE_SZ - 1))
  488. # define DIV_LINE_SZ(n) ((n) >> LOG_LINE_SZ)
  489. # define LINE_START(n) ((n) & ~(LINE_SZ - 1))
  490.  
  491. typedef struct {
  492.     lf_state * state;
  493.     size_t file_pos;    /* Position of needed character. */
  494.     cache_line * new_cache;
  495. } refill_data;
  496.  
  497. /* Executed with allocation lock. */
  498. static char refill_cache(client_data)
  499. refill_data * client_data;
  500. {
  501.     register lf_state * state = client_data -> state;
  502.     register size_t file_pos = client_data -> file_pos;
  503.     FILE *f = state -> lf_file;
  504.     size_t line_start = LINE_START(file_pos);
  505.     size_t line_no = DIV_LINE_SZ(MOD_CACHE_SZ(file_pos));
  506.     cache_line * new_cache = client_data -> new_cache;
  507.     
  508.     if (line_start != state -> lf_current
  509.         && fseek(f, line_start, SEEK_SET) != 0) {
  510.             ABORT("fseek failed");
  511.     }
  512.     if (fread(new_cache -> data, sizeof(char), LINE_SZ, f)
  513.         <= file_pos - line_start) {
  514.         ABORT("fread failed");
  515.     }
  516.     new_cache -> tag = DIV_LINE_SZ(file_pos);
  517.     /* Store barrier goes here. */
  518.     ATOMIC_WRITE(state -> lf_cache[line_no], new_cache);
  519.     state -> lf_current = line_start + LINE_SZ;
  520.     return(new_cache->data[MOD_LINE_SZ(file_pos)]);
  521. }
  522.  
  523. char CORD_lf_func(size_t i, void * client_data)
  524. {
  525.     register lf_state * state = (lf_state *)client_data;
  526.     register cache_line * volatile * cl_addr =
  527.         &(state -> lf_cache[DIV_LINE_SZ(MOD_CACHE_SZ(i))]);
  528.     register cache_line * cl = (cache_line *)ATOMIC_READ(cl_addr);
  529.     
  530.     if (cl == 0 || cl -> tag != DIV_LINE_SZ(i)) {
  531.         /* Cache miss */
  532.         refill_data rd;
  533.         
  534.         rd.state = state;
  535.         rd.file_pos =  i;
  536.         rd.new_cache = GC_NEW_ATOMIC(cache_line);
  537.         if (rd.new_cache == 0) OUT_OF_MEMORY;
  538.         return((char)(GC_word)
  539.               GC_call_with_alloc_lock((GC_fn_type) refill_cache, &rd));
  540.     }
  541.     return(cl -> data[MOD_LINE_SZ(i)]);
  542. }    
  543.  
  544. /*ARGSUSED*/
  545. void CORD_lf_close_proc(void * obj, void * client_data)  
  546. {
  547.     if (fclose(((lf_state *)obj) -> lf_file) != 0) {
  548.         ABORT("CORD_lf_close_proc: fclose failed");
  549.     }
  550. }            
  551.  
  552. CORD CORD_from_file_lazy_inner(FILE * f, size_t len)
  553. {
  554.     register lf_state * state = GC_NEW(lf_state);
  555.     register int i;
  556.     
  557.     if (state == 0) OUT_OF_MEMORY;
  558.     state -> lf_file = f;
  559.     for (i = 0; i < CACHE_SZ/LINE_SZ; i++) {
  560.         state -> lf_cache[i] = 0;
  561.     }
  562.     state -> lf_current = 0;
  563.     GC_register_finalizer(state, CORD_lf_close_proc, 0, 0, 0);
  564.     return(CORD_from_fn(CORD_lf_func, state, len));
  565. }
  566.  
  567. CORD CORD_from_file_lazy(FILE * f)
  568. {
  569.     register long len;
  570.     
  571.     if (fseek(f, 0l, SEEK_END) != 0) {
  572.         ABORT("Bad fd argument - fseek failed");
  573.     }
  574.     if ((len = ftell(f)) < 0) {
  575.         ABORT("Bad fd argument - ftell failed");
  576.     }
  577.     rewind(f);
  578.     return(CORD_from_file_lazy_inner(f, (size_t)len));
  579. }
  580.  
  581. # define LAZY_THRESHOLD (128*1024 + 1)
  582.  
  583. CORD CORD_from_file(FILE * f)
  584. {
  585.     register long len;
  586.     
  587.     if (fseek(f, 0l, SEEK_END) != 0) {
  588.         ABORT("Bad fd argument - fseek failed");
  589.     }
  590.     if ((len = ftell(f)) < 0) {
  591.         ABORT("Bad fd argument - ftell failed");
  592.     }
  593.     rewind(f);
  594.     if (len < LAZY_THRESHOLD) {
  595.         return(CORD_from_file_eager(f));
  596.     } else {
  597.         return(CORD_from_file_lazy_inner(f, (size_t)len));
  598.     }
  599. }
  600.