Subversion Repositories openrisc

/*

 * Copyright (c) 1993-1994 by Xerox Corporation.  All rights reserved.

 *

 * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED

 * OR IMPLIED.  ANY USE IS AT YOUR OWN RISK.

 *

 * Permission is hereby granted to use or copy this program

 * for any purpose,  provided the above notices are retained on all copies.

 * Permission to modify the code and to distribute modified code is granted,

 * provided the above notices are retained, and a notice that the code was

 * modified is included with the above copyright notice.

 *

 * Author: Hans-J. Boehm (boehm@parc.xerox.com)

 */

/*

 * These are functions on cords that do not need to understand their

 * implementation.  They serve also serve as example client code for

 * cord_basics.

 */

/* Boehm, December 8, 1995 1:53 pm PST */

# include <stdio.h>

# include <string.h>

# include <stdlib.h>

# include <stdarg.h>

# include "cord.h"

# include "ec.h"

# define I_HIDE_POINTERS        /* So we get access to allocation lock. */

                                /* We use this for lazy file reading,   */

                                /* so that we remain independent        */

                                /* of the threads primitives.           */

# include "gc.h"

/* For now we assume that pointer reads and writes are atomic,  */

/* i.e. another thread always sees the state before or after    */

/* a write.  This might be false on a Motorola M68K with        */

/* pointers that are not 32-bit aligned.  But there probably    */

/* aren't too many threads packages running on those.           */

# define ATOMIC_WRITE(x,y) (x) = (y)

# define ATOMIC_READ(x) (*(x))

/* The standard says these are in stdio.h, but they aren't always: */

# ifndef SEEK_SET

#   define SEEK_SET 0

# endif

# ifndef SEEK_END

#   define SEEK_END 2

# endif

# define BUFSZ 2048     /* Size of stack allocated buffers when         */

                        /* we want large buffers.                       */

typedef void (* oom_fn)(void);

# define OUT_OF_MEMORY {  if (CORD_oom_fn != (oom_fn) 0) (*CORD_oom_fn)(); \

                          ABORT("Out of memory\n"); }

# define ABORT(msg) { fprintf(stderr, "%s\n", msg); abort(); }

CORD CORD_cat_char(CORD x, char c)

{

    register char * string;

    if (c == '\0') return(CORD_cat(x, CORD_nul(1)));

    string = GC_MALLOC_ATOMIC(2);

    if (string == 0) OUT_OF_MEMORY;

    string[0] = c;

    string[1] = '\0';

    return(CORD_cat_char_star(x, string, 1));

}

CORD CORD_catn(int nargs, ...)

{

    register CORD result = CORD_EMPTY;

    va_list args;

    register int i;

    va_start(args, nargs);

    for (i = 0; i < nargs; i++) {

        register CORD next = va_arg(args, CORD);

        result = CORD_cat(result, next);

    }

    va_end(args);

    return(result);

}

typedef struct {

        size_t len;

        size_t count;

        char * buf;

} CORD_fill_data;

int CORD_fill_proc(char c, void * client_data)

{

    register CORD_fill_data * d = (CORD_fill_data *)client_data;

    register size_t count = d -> count;

    (d -> buf)[count] = c;

    d -> count = ++count;

    if (count >= d -> len) {

        return(1);

    } else {

        return(0);

    }

}

int CORD_batched_fill_proc(const char * s, void * client_data)

{

    register CORD_fill_data * d = (CORD_fill_data *)client_data;

    register size_t count = d -> count;

    register size_t max = d -> len;

    register char * buf = d -> buf;

    register const char * t = s;

    while((buf[count] = *t++) != '\0') {

        count++;

        if (count >= max) {

            d -> count = count;

            return(1);

        }

    }

    d -> count = count;

    return(0);

}

/* Fill buf with len characters starting at i.                          */

/* Assumes len characters are available.                                */

void CORD_fill_buf(CORD x, size_t i, size_t len, char * buf)

{

    CORD_fill_data fd;

    fd.len = len;

    fd.buf = buf;

    fd.count = 0;

    (void)CORD_iter5(x, i, CORD_fill_proc, CORD_batched_fill_proc, &fd);

}

int CORD_cmp(CORD x, CORD y)

{

    CORD_pos xpos;

    CORD_pos ypos;

    register size_t avail, yavail;

    if (y == CORD_EMPTY) return(x != CORD_EMPTY);

    if (x == CORD_EMPTY) return(-1);

    if (CORD_IS_STRING(y) && CORD_IS_STRING(x)) return(strcmp(x,y));

    CORD_set_pos(xpos, x, 0);

    CORD_set_pos(ypos, y, 0);

    for(;;) {

        if (!CORD_pos_valid(xpos)) {

            if (CORD_pos_valid(ypos)) {

                return(-1);

            } else {

                return(0);

            }

        }

        if (!CORD_pos_valid(ypos)) {

            return(1);

        }

        if ((avail = CORD_pos_chars_left(xpos)) <= 0

            || (yavail = CORD_pos_chars_left(ypos)) <= 0) {

            register char xcurrent = CORD_pos_fetch(xpos);

            register char ycurrent = CORD_pos_fetch(ypos);

            if (xcurrent != ycurrent) return(xcurrent - ycurrent);

            CORD_next(xpos);

            CORD_next(ypos);

        } else {

            /* process as many characters as we can     */

            register int result;

            if (avail > yavail) avail = yavail;

            result = strncmp(CORD_pos_cur_char_addr(xpos),

                             CORD_pos_cur_char_addr(ypos), avail);

            if (result != 0) return(result);

            CORD_pos_advance(xpos, avail);

            CORD_pos_advance(ypos, avail);

        }

    }

}

int CORD_ncmp(CORD x, size_t x_start, CORD y, size_t y_start, size_t len)

{

    CORD_pos xpos;

    CORD_pos ypos;

    register size_t count;

    register long avail, yavail;

    CORD_set_pos(xpos, x, x_start);

    CORD_set_pos(ypos, y, y_start);

    for(count = 0; count < len;) {

        if (!CORD_pos_valid(xpos)) {

            if (CORD_pos_valid(ypos)) {

                return(-1);

            } else {

                return(0);

            }

        }

        if (!CORD_pos_valid(ypos)) {

            return(1);

        }

        if ((avail = CORD_pos_chars_left(xpos)) <= 0

            || (yavail = CORD_pos_chars_left(ypos)) <= 0) {

            register char xcurrent = CORD_pos_fetch(xpos);

            register char ycurrent = CORD_pos_fetch(ypos);

            if (xcurrent != ycurrent) return(xcurrent - ycurrent);

            CORD_next(xpos);

            CORD_next(ypos);

            count++;

        } else {

            /* process as many characters as we can     */

            register int result;

            if (avail > yavail) avail = yavail;

            count += avail;

            if (count > len) avail -= (count - len);

            result = strncmp(CORD_pos_cur_char_addr(xpos),

                             CORD_pos_cur_char_addr(ypos), (size_t)avail);

            if (result != 0) return(result);

            CORD_pos_advance(xpos, (size_t)avail);

            CORD_pos_advance(ypos, (size_t)avail);

        }

    }

    return(0);

}

char * CORD_to_char_star(CORD x)

{

    register size_t len = CORD_len(x);

    char * result = GC_MALLOC_ATOMIC(len + 1);

    if (result == 0) OUT_OF_MEMORY;

    CORD_fill_buf(x, 0, len, result);

    result[len] = '\0';

    return(result);

}

CORD CORD_from_char_star(const char *s)

{

    char * result;

    size_t len = strlen(s);

    if (0 == len) return(CORD_EMPTY);

    result = GC_MALLOC_ATOMIC(len + 1);

    if (result == 0) OUT_OF_MEMORY;

    memcpy(result, s, len+1);

    return(result);

}

const char * CORD_to_const_char_star(CORD x)

{

    if (x == 0) return("");

    if (CORD_IS_STRING(x)) return((const char *)x);

    return(CORD_to_char_star(x));

}

char CORD_fetch(CORD x, size_t i)

{

    CORD_pos xpos;

    CORD_set_pos(xpos, x, i);

    if (!CORD_pos_valid(xpos)) ABORT("bad index?");

    return(CORD_pos_fetch(xpos));

}

int CORD_put_proc(char c, void * client_data)

{

    register FILE * f = (FILE *)client_data;

    return(putc(c, f) == EOF);

}

int CORD_batched_put_proc(const char * s, void * client_data)

{

    register FILE * f = (FILE *)client_data;

    return(fputs(s, f) == EOF);

}

int CORD_put(CORD x, FILE * f)

{

    if (CORD_iter5(x, 0, CORD_put_proc, CORD_batched_put_proc, f)) {

        return(EOF);

    } else {

        return(1);

    }

}

typedef struct {

    size_t pos;         /* Current position in the cord */

    char target;        /* Character we're looking for  */

} chr_data;

int CORD_chr_proc(char c, void * client_data)

{

    register chr_data * d = (chr_data *)client_data;

    if (c == d -> target) return(1);

    (d -> pos) ++;

    return(0);

}

int CORD_rchr_proc(char c, void * client_data)

{

    register chr_data * d = (chr_data *)client_data;

    if (c == d -> target) return(1);

    (d -> pos) --;

    return(0);

}

int CORD_batched_chr_proc(const char *s, void * client_data)

{

    register chr_data * d = (chr_data *)client_data;

    register char * occ = strchr(s, d -> target);

    if (occ == 0) {

        d -> pos += strlen(s);

        return(0);

    } else {

        d -> pos += occ - s;

        return(1);

    }

}

size_t CORD_chr(CORD x, size_t i, int c)

{

    chr_data d;

    d.pos = i;

    d.target = c;

    if (CORD_iter5(x, i, CORD_chr_proc, CORD_batched_chr_proc, &d)) {

        return(d.pos);

    } else {

        return(CORD_NOT_FOUND);

    }

}

size_t CORD_rchr(CORD x, size_t i, int c)

{

    chr_data d;

    d.pos = i;

    d.target = c;

    if (CORD_riter4(x, i, CORD_rchr_proc, &d)) {

        return(d.pos);

    } else {

        return(CORD_NOT_FOUND);

    }

}

/* Find the first occurrence of s in x at position start or later.      */

/* This uses an asymptotically poor algorithm, which should typically   */

/* perform acceptably.  We compare the first few characters directly,   */

/* and call CORD_ncmp whenever there is a partial match.                */

/* This has the advantage that we allocate very little, or not at all.  */

/* It's very fast if there are few close misses.                        */

size_t CORD_str(CORD x, size_t start, CORD s)

{

    CORD_pos xpos;

    size_t xlen = CORD_len(x);

    size_t slen;

    register size_t start_len;

    const char * s_start;

    unsigned long s_buf = 0;     /* The first few characters of s        */

    unsigned long x_buf = 0;     /* Start of candidate substring.        */

                                /* Initialized only to make compilers   */

                                /* happy.                               */

    unsigned long mask = 0;

    register size_t i;

    register size_t match_pos;

    if (s == CORD_EMPTY) return(start);

    if (CORD_IS_STRING(s)) {

        s_start = s;

        slen = strlen(s);

    } else {

        s_start = CORD_to_char_star(CORD_substr(s, 0, sizeof(unsigned long)));

        slen = CORD_len(s);

    }

    if (xlen < start || xlen - start < slen) return(CORD_NOT_FOUND);

    start_len = slen;

    if (start_len > sizeof(unsigned long)) start_len = sizeof(unsigned long);

    CORD_set_pos(xpos, x, start);

    for (i = 0; i < start_len; i++) {

        mask <<= 8;

        mask |= 0xff;

        s_buf <<= 8;

        s_buf |= (unsigned char)s_start[i];

        x_buf <<= 8;

        x_buf |= (unsigned char)CORD_pos_fetch(xpos);

        CORD_next(xpos);

    }

    for (match_pos = start; ; match_pos++) {

        if ((x_buf & mask) == s_buf) {

            if (slen == start_len ||

                CORD_ncmp(x, match_pos + start_len,

                          s, start_len, slen - start_len) == 0) {

                return(match_pos);

            }

        }

        if ( match_pos == xlen - slen ) {

            return(CORD_NOT_FOUND);

        }

        x_buf <<= 8;

        x_buf |= (unsigned char)CORD_pos_fetch(xpos);

        CORD_next(xpos);

    }

}

void CORD_ec_flush_buf(CORD_ec x)

{

    register size_t len = x[0].ec_bufptr - x[0].ec_buf;

    char * s;

    if (len == 0) return;

    s = GC_MALLOC_ATOMIC(len+1);

    memcpy(s, x[0].ec_buf, len);

    s[len] = '\0';

    x[0].ec_cord = CORD_cat_char_star(x[0].ec_cord, s, len);

    x[0].ec_bufptr = x[0].ec_buf;

}

void CORD_ec_append_cord(CORD_ec x, CORD s)

{

    CORD_ec_flush_buf(x);

    x[0].ec_cord = CORD_cat(x[0].ec_cord, s);

}

/*ARGSUSED*/

char CORD_nul_func(size_t i, void * client_data)

{

    return((char)(unsigned long)client_data);

}

CORD CORD_chars(char c, size_t i)

{

    return(CORD_from_fn(CORD_nul_func, (void *)(unsigned long)c, i));

}

CORD CORD_from_file_eager(FILE * f)

{

    register int c;

    CORD_ec ecord;

    CORD_ec_init(ecord);

    for(;;) {

        c = getc(f);

        if (c == 0) {

          /* Append the right number of NULs    */

          /* Note that any string of NULs is rpresented in 4 words,     */

          /* independent of its length.                                 */

            register size_t count = 1;

            CORD_ec_flush_buf(ecord);

            while ((c = getc(f)) == 0) count++;

            ecord[0].ec_cord = CORD_cat(ecord[0].ec_cord, CORD_nul(count));

        }

        if (c == EOF) break;

        CORD_ec_append(ecord, c);

    }

    (void) fclose(f);

    return(CORD_balance(CORD_ec_to_cord(ecord)));

}

/* The state maintained for a lazily read file consists primarily       */

/* of a large direct-mapped cache of previously read values.            */

/* We could rely more on stdio buffering.  That would have 2            */

/* disadvantages:                                                       */

/*      1) Empirically, not all fseek implementations preserve the      */

/*         buffer whenever they could.                                  */

/*      2) It would fail if 2 different sections of a long cord         */

/*         were being read alternately.                                 */

/* We do use the stdio buffer for read ahead.                           */

/* To guarantee thread safety in the presence of atomic pointer         */

/* writes, cache lines are always replaced, and never modified in       */

/* place.                                                               */

# define LOG_CACHE_SZ 14

# define CACHE_SZ (1 << LOG_CACHE_SZ)

# define LOG_LINE_SZ 9

# define LINE_SZ (1 << LOG_LINE_SZ)

typedef struct {

    size_t tag;

    char data[LINE_SZ];

        /* data[i%LINE_SZ] = ith char in file if tag = i/LINE_SZ        */

} cache_line;

typedef struct {

    FILE * lf_file;

    size_t lf_current;  /* Current file pointer value */

    cache_line * volatile lf_cache[CACHE_SZ/LINE_SZ];

} lf_state;

# define MOD_CACHE_SZ(n) ((n) & (CACHE_SZ - 1))

# define DIV_CACHE_SZ(n) ((n) >> LOG_CACHE_SZ)

# define MOD_LINE_SZ(n) ((n) & (LINE_SZ - 1))

# define DIV_LINE_SZ(n) ((n) >> LOG_LINE_SZ)

# define LINE_START(n) ((n) & ~(LINE_SZ - 1))

typedef struct {

    lf_state * state;

    size_t file_pos;    /* Position of needed character. */

    cache_line * new_cache;

} refill_data;

/* Executed with allocation lock. */

static char refill_cache(client_data)

refill_data * client_data;

{

    register lf_state * state = client_data -> state;

    register size_t file_pos = client_data -> file_pos;

    FILE *f = state -> lf_file;

    size_t line_start = LINE_START(file_pos);

    size_t line_no = DIV_LINE_SZ(MOD_CACHE_SZ(file_pos));

    cache_line * new_cache = client_data -> new_cache;

    if (line_start != state -> lf_current

        && fseek(f, line_start, SEEK_SET) != 0) {

            ABORT("fseek failed");

    }

    if (fread(new_cache -> data, sizeof(char), LINE_SZ, f)

        <= file_pos - line_start) {

        ABORT("fread failed");

    }

    new_cache -> tag = DIV_LINE_SZ(file_pos);

    /* Store barrier goes here. */

    ATOMIC_WRITE(state -> lf_cache[line_no], new_cache);

    state -> lf_current = line_start + LINE_SZ;

    return(new_cache->data[MOD_LINE_SZ(file_pos)]);

}

char CORD_lf_func(size_t i, void * client_data)

{

    register lf_state * state = (lf_state *)client_data;

    register cache_line * volatile * cl_addr =

                &(state -> lf_cache[DIV_LINE_SZ(MOD_CACHE_SZ(i))]);

    register cache_line * cl = (cache_line *)ATOMIC_READ(cl_addr);

    if (cl == 0 || cl -> tag != DIV_LINE_SZ(i)) {

        /* Cache miss */

        refill_data rd;

        rd.state = state;

        rd.file_pos =  i;

        rd.new_cache = GC_NEW_ATOMIC(cache_line);

        if (rd.new_cache == 0) OUT_OF_MEMORY;

        return((char)(GC_word)

                  GC_call_with_alloc_lock((GC_fn_type) refill_cache, &rd));

    }

    return(cl -> data[MOD_LINE_SZ(i)]);

}

/*ARGSUSED*/

void CORD_lf_close_proc(void * obj, void * client_data)

{

    if (fclose(((lf_state *)obj) -> lf_file) != 0) {

        ABORT("CORD_lf_close_proc: fclose failed");

    }

}

CORD CORD_from_file_lazy_inner(FILE * f, size_t len)

{

    register lf_state * state = GC_NEW(lf_state);

    register int i;

    if (state == 0) OUT_OF_MEMORY;

    if (len != 0) {

        /* Dummy read to force buffer allocation.       */

        /* This greatly increases the probability       */

        /* of avoiding deadlock if buffer allocation    */

        /* is redirected to GC_malloc and the           */

        /* world is multithreaded.                      */

        char buf[1];

        (void) fread(buf, 1, 1, f);

        rewind(f);

    }

    state -> lf_file = f;

    for (i = 0; i < CACHE_SZ/LINE_SZ; i++) {

        state -> lf_cache[i] = 0;

    }

    state -> lf_current = 0;

    GC_REGISTER_FINALIZER(state, CORD_lf_close_proc, 0, 0, 0);

    return(CORD_from_fn(CORD_lf_func, state, len));

}

CORD CORD_from_file_lazy(FILE * f)

{

    register long len;

    if (fseek(f, 0l, SEEK_END) != 0) {

        ABORT("Bad fd argument - fseek failed");

    }

    if ((len = ftell(f)) < 0) {

        ABORT("Bad fd argument - ftell failed");

    }

    rewind(f);

    return(CORD_from_file_lazy_inner(f, (size_t)len));

}

# define LAZY_THRESHOLD (128*1024 + 1)

CORD CORD_from_file(FILE * f)

{

    register long len;

    if (fseek(f, 0l, SEEK_END) != 0) {

        ABORT("Bad fd argument - fseek failed");

    }

    if ((len = ftell(f)) < 0) {

        ABORT("Bad fd argument - ftell failed");

    }

    rewind(f);

    if (len < LAZY_THRESHOLD) {

        return(CORD_from_file_eager(f));

    } else {

        return(CORD_from_file_lazy_inner(f, (size_t)len));

    }

}