symbol.c

Go to the documentation of this file.

 
/***** Feature test switches ************************************************/
/***** System headers *******************************************************/
//@cond
#include "vm_config.h"
#include <stdint.h>
#include <string.h>
#include <limits.h>
#include <assert.h>
//@endcond
 
/***** Local headers ********************************************************/
#define MRBC_DEFINE_SYMBOL_TABLE
#include "_autogen_builtin_symbol.h"
#undef MRBC_DEFINE_SYMBOL_TABLE
#include "mrubyc.h"
 
/***** Constant values ******************************************************/
#if !defined(MRBC_SYMBOL_SEARCH_LINEAR) && !defined(MRBC_SYMBOL_SEARCH_BTREE)
#define MRBC_SYMBOL_SEARCH_BTREE
#endif
 
#define OFFSET_BUILTIN_SYMBOL 512
#if OFFSET_BUILTIN_SYMBOL <= MRBC_BUILTIN_SYMBOL_MAX
# error OFFSET_BUILTIN_SYMBOL overflow. Please increase the value.
#endif
 
 
/***** Macros ***************************************************************/
/***** Typedefs *************************************************************/
struct SYM_INDEX {
  uint16_t hash;        
#ifdef MRBC_SYMBOL_SEARCH_BTREE
#if MAX_SYMBOLS_COUNT <= UCHAR_MAX
  uint8_t  left, right;
#else
  uint16_t left, right;
#endif
#endif
  const char *cstr;     
};
 
 
/***** Function prototypes **************************************************/
/***** Local variables ******************************************************/
static struct SYM_INDEX sym_index[MAX_SYMBOLS_COUNT];
static int sym_index_pos;       // point to the last(free) sym_index array.
 
 
/***** Global variables *****************************************************/
/***** Signal catching functions ********************************************/
/***** Local functions ******************************************************/
 
//================================================================
static inline uint16_t calc_hash(const char *str)
{
  uint16_t h = 0;
 
  while( *str != '\0' ) {
    h = h * 17 + *str++;
  }
  return h;
}
 
 
//================================================================
static int search_builtin_symbol( const char *str )
{
  int left = 1;
  int right = sizeof(builtin_symbols) / sizeof(builtin_symbols[0]);
 
  while( left < right ) {
    int mid = (left + right) / 2;
    const unsigned char *p1 = (const unsigned char *)builtin_symbols[mid];
    const unsigned char *p2 = (const unsigned char *)str;
 
    while( 1 ) {        // string compare, same order as cruby.
      if( *p1 < *p2 ) {
        left = mid + 1;
        break;
      }
      if( *p1 > *p2 ) {
        right = mid;
        break;
      }
      if( *p1 == 0 ) {
        return mid;
      }
 
      p1++;
      p2++;
    }
  }
 
  return -1;
}
 
 
//================================================================
static int search_index( uint16_t hash, const char *str )
{
#ifdef MRBC_SYMBOL_SEARCH_LINEAR
  for( int i = 0; i < sym_index_pos; i++ ) {
    if( sym_index[i].hash == hash && strcmp(str, sym_index[i].cstr) == 0 ) {
      return i;
    }
  }
  return -1;
#endif
 
#ifdef MRBC_SYMBOL_SEARCH_BTREE
  int i = 0;
  do {
    if( sym_index[i].hash == hash && strcmp(str, sym_index[i].cstr) == 0 ) {
      return i;
    }
    if( hash < sym_index[i].hash ) {
      i = sym_index[i].left;
    } else {
      i = sym_index[i].right;
    }
  } while( i != 0 );
  return -1;
#endif
}
 
 
//================================================================
static int add_index( uint16_t hash, const char *str )
{
  if( sym_index_pos >= MAX_SYMBOLS_COUNT ) return -1;   // check overflow.
 
  int idx = sym_index_pos++;
 
  // append table.
  sym_index[idx].hash = hash;
  sym_index[idx].cstr = str;
 
#ifdef MRBC_SYMBOL_SEARCH_BTREE
  int i = 0;
 
  while( 1 ) {
    if( hash < sym_index[i].hash ) {
      // left side
      if( sym_index[i].left == 0 ) {    // left is empty?
        sym_index[i].left = idx;
        break;
      }
      i = sym_index[i].left;
    } else {
      // right side
      if( sym_index[i].right == 0 ) {   // right is empty?
        sym_index[i].right = idx;
        break;
      }
      i = sym_index[i].right;
    }
  }
#endif
 
  return idx;
}
 
 
/***** Global functions *****************************************************/
 
//================================================================
void mrbc_cleanup_symbol(void)
{
  memset(sym_index, 0, sizeof(sym_index));
  sym_index_pos = 0;
}
 
 
//================================================================
mrbc_sym mrbc_str_to_symid(const char *str)
{
  mrbc_sym sym_id = search_builtin_symbol(str);
  if( sym_id >= 0 ) return sym_id;
 
  uint16_t h = calc_hash(str);
  sym_id = search_index(h, str);
  if( sym_id < 0 ) sym_id = add_index( h, str );
  if( sym_id < 0 ) return sym_id;
 
  return sym_id + OFFSET_BUILTIN_SYMBOL;
}
 
 
//================================================================
const char * mrbc_symid_to_str(mrbc_sym sym_id)
{
  if( sym_id < OFFSET_BUILTIN_SYMBOL ) {
    return builtin_symbols[sym_id];
  }
 
  sym_id -= OFFSET_BUILTIN_SYMBOL;
  if( sym_id < 0 ) return "";
  if( sym_id >= sym_index_pos ) return "";
 
  return sym_index[sym_id].cstr;
}
 
 
//================================================================
mrbc_sym mrbc_search_symid( const char *str )
{
  mrbc_sym sym_id = search_builtin_symbol(str);
  if( sym_id >= 0 ) return sym_id;
 
  uint16_t h = calc_hash(str);
  sym_id = search_index(h, str);
  if( sym_id < 0 ) return sym_id;
 
  return sym_id + OFFSET_BUILTIN_SYMBOL;
}
 
 
//================================================================
void mrbc_make_nested_symbol_s( char *buf, mrbc_sym id1, mrbc_sym id2 )
{
  /*
    index:   0    1  2  3  4        5  6  7  8        9
    format: "\x01 id1(ascii 4bytes) id2(ascii 4bytes) \x00"
  */
  assert( sizeof(mrbc_sym) == 2 );
 
  uint8_t *p = (uint8_t*)buf + 9;
 
  *p-- = 0;
 
  for( int i = 0; i < 4; i++ ) {
    *p-- = '0' + (id2 & 0x0f);
    id2 >>= 4;
  }
  for( int i = 0; i < 4; i++ ) {
    *p-- = '0' + (id1 & 0x0f);
    id1 >>= 4;
  }
 
  *p = 0x01;
}
 
 
//================================================================
void mrbc_separate_nested_symid(mrbc_sym sym_id, mrbc_sym *id1, mrbc_sym *id2)
{
  assert( mrbc_is_nested_symid( sym_id ));
 
  const char *p = mrbc_symid_to_str(sym_id);
 
  *id1 = *id2 = 0;
  for( int i = 0; i < 4; i++ ) {
    *id1 = (*id1 << 4) + (*++p - '0');
  }
  for( int i = 0; i < 4; i++ ) {
    *id2 = (*id2 << 4) + (*++p - '0');
  }
}
 
 
//================================================================
mrbc_value mrbc_symbol_new(struct VM *vm, const char *str)
{
  mrbc_sym sym_id = mrbc_search_symid( str );
  if( sym_id >= 0 ) goto DONE;
 
  // create symbol object dynamically.
  int size = strlen(str) + 1;
  char *buf = mrbc_raw_alloc_no_free(size);
 
  memcpy(buf, str, size);
  sym_id = add_index( calc_hash(buf), buf );
  if( sym_id < 0 ) {
    mrbc_raisef(vm, MRBC_CLASS(Exception),
                "Overflow MAX_SYMBOLS_COUNT for '%s'", str );
    return mrbc_nil_value();
  }
 
  sym_id += OFFSET_BUILTIN_SYMBOL;
 
 DONE:
  return mrbc_symbol_value( sym_id );
}
 
 
/***** mruby/c methods ******************************************************/
 
//================================================================
static void c_symbol_all_symbols(struct VM *vm, mrbc_value v[], int argc)
{
  mrbc_value ret = mrbc_array_new(vm, sym_index_pos);
 
  for( int i = 0; i < sizeof(builtin_symbols) / sizeof(builtin_symbols[0]); i++ ) {
    mrbc_array_push(&ret, &mrbc_symbol_value(i));
  }
 
  for( int i = 0; i < sym_index_pos; i++ ) {
    mrbc_array_push(&ret, &mrbc_symbol_value(i + OFFSET_BUILTIN_SYMBOL));
  }
  SET_RETURN(ret);
}
 
 
#if MRBC_USE_STRING
//================================================================
static void c_symbol_inspect(struct VM *vm, mrbc_value v[], int argc)
{
  if( mrbc_type(v[0]) == MRBC_TT_CLASS ) {
    mrbc_object_inspect(vm, v, argc);
    return;
  }
 
  const char *s = mrbc_symid_to_str( mrbc_symbol(v[0]) );
 
  if( strchr(s, ':') ) {
    v[0] = mrbc_string_new_cstr(vm, ":\"");
    mrbc_string_append_cstr(&v[0], s);
    mrbc_string_append_cstr(&v[0], "\"");
  } else {
    v[0] = mrbc_string_new_cstr(vm, ":");
    mrbc_string_append_cstr(&v[0], s);
  }
}
 
 
//================================================================
static void c_symbol_to_s(struct VM *vm, mrbc_value v[], int argc)
{
  if( mrbc_type(v[0]) == MRBC_TT_CLASS ) {
    mrbc_object_inspect(vm, v, argc);
    return;
  }
 
  v[0] = mrbc_string_new_cstr(vm, mrbc_symid_to_str( mrbc_symbol(v[0]) ));
}
#endif
 
 
/* MRBC_AUTOGEN_METHOD_TABLE
 
  CLASS("Symbol")
  FILE("_autogen_class_symbol.h")
 
  METHOD( "all_symbols", c_symbol_all_symbols )
#if MRBC_USE_STRING
  METHOD( "inspect",     c_symbol_inspect )
  METHOD( "to_s",        c_symbol_to_s )
  METHOD( "id2name",     c_symbol_to_s )
#endif
  METHOD( "to_sym",      c_ineffect )
*/
#include "_autogen_class_symbol.h"
 
 
 
#if defined(MRBC_DEBUG)
//================================================================
void mrbc_debug_dump_symbol(void)
{
  mrbc_printf("<< Symbol table dump >>\n");
 
  for( int i = 0; i < sym_index_pos; i++ ) {
    mrbc_sym sym_id = i + OFFSET_BUILTIN_SYMBOL;
    mrbc_printf(" %04x: %s", sym_id, sym_index[i].cstr );
    if( mrbc_is_nested_symid(sym_id) ) {
      mrbc_printf(" as ");
      mrbc_print_symbol(sym_id);
    }
    mrbc_printf("\n");
  }
 
  mrbc_printf("\n");
}
 
 
//================================================================
void mrbc_symbol_statistics( int *total_used )
{
  *total_used = sym_index_pos;
}
#endif