Changeset 439 for EcnlProtoTool/trunk/mruby-2.1.1/src/symbol.c

Timestamp:

Jul 9, 2020, 8:51:43 AM (4 years ago)

Author:

coas-nagasima

Message:

mrubyを2.1.1に更新

Location:

EcnlProtoTool/trunk/mruby-2.1.1

Files:

• . (moved) (moved from EcnlProtoTool/trunk/mruby-1.3.0 )
• src/symbol.c (modified) (18 diffs)

EcnlProtoTool/trunk/mruby-2.1.1/src/symbol.c

@@ -16 +16 @@
 typedef struct symbol_name {
   mrb_bool lit : 1;
+  uint8_t prev;
   uint16_t len;
   const char *name;
 } symbol_name;
 
-static inline khint_t
-sym_hash_func(mrb_state *mrb, mrb_sym s)
-{
-  khint_t h = 0;
-  size_t i, len = mrb->symtbl[s].len;
-  const char *p = mrb->symtbl[s].name;
-
-  for (i=0; i<len; i++) {
-    h = (h << 5) - h + *p++;
-  }
-  return h;
-}
-#define sym_hash_equal(mrb,a, b) (mrb->symtbl[a].len == mrb->symtbl[b].len && memcmp(mrb->symtbl[a].name, mrb->symtbl[b].name, mrb->symtbl[a].len) == 0)
-
-KHASH_DECLARE(n2s, mrb_sym, mrb_sym, FALSE)
-KHASH_DEFINE (n2s, mrb_sym, mrb_sym, FALSE, sym_hash_func, sym_hash_equal)
-/* ------------------------------------------------------ */
+#define SYMBOL_INLINE_BIT_POS       1
+#define SYMBOL_INLINE_LOWER_BIT_POS 2
+#define SYMBOL_INLINE               (1 << (SYMBOL_INLINE_BIT_POS - 1))
+#define SYMBOL_INLINE_LOWER         (1 << (SYMBOL_INLINE_LOWER_BIT_POS - 1))
+#define SYMBOL_NORMAL_SHIFT         SYMBOL_INLINE_BIT_POS
+#define SYMBOL_INLINE_SHIFT         SYMBOL_INLINE_LOWER_BIT_POS
+#ifdef MRB_ENABLE_ALL_SYMBOLS
+# define SYMBOL_INLINE_P(sym) FALSE
+# define SYMBOL_INLINE_LOWER_P(sym) FALSE
+# define sym_inline_pack(name, len) 0
+# define sym_inline_unpack(sym, buf, lenp) NULL
+#else
+# define SYMBOL_INLINE_P(sym) ((sym) & SYMBOL_INLINE)
+# define SYMBOL_INLINE_LOWER_P(sym) ((sym) & SYMBOL_INLINE_LOWER)
+#endif
 
 static void
@@ -46 +45 @@
 }
 
+#ifndef MRB_ENABLE_ALL_SYMBOLS
+static const char pack_table[] = "_abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
+
+static mrb_sym
+sym_inline_pack(const char *name, size_t len)
+{
+  const size_t lower_length_max = (MRB_SYMBOL_BIT - 2) / 5;
+  const size_t mix_length_max   = (MRB_SYMBOL_BIT - 2) / 6;
+
+  char c;
+  const char *p;
+  size_t i;
+  mrb_sym sym = 0;
+  mrb_bool lower = TRUE;
+
+  if (len > lower_length_max) return 0; /* too long */
+  for (i=0; i<len; i++) {
+    uint32_t bits;
+
+    c = name[i];
+    if (c == 0) return 0;       /* NUL in name */
+    p = strchr(pack_table, (int)c);
+    if (p == 0) return 0;       /* non alnum char */
+    bits = (uint32_t)(p - pack_table)+1;
+    if (bits > 27) lower = FALSE;
+    if (i >= mix_length_max) break;
+    sym |= bits<<(i*6+SYMBOL_INLINE_SHIFT);
+  }
+  if (lower) {
+    sym = 0;
+    for (i=0; i<len; i++) {
+      uint32_t bits;
+
+      c = name[i];
+      p = strchr(pack_table, (int)c);
+      bits = (uint32_t)(p - pack_table)+1;
+      sym |= bits<<(i*5+SYMBOL_INLINE_SHIFT);
+    }
+    return sym | SYMBOL_INLINE | SYMBOL_INLINE_LOWER;
+  }
+  if (len > mix_length_max) return 0;
+  return sym | SYMBOL_INLINE;
+}
+
+static const char*
+sym_inline_unpack(mrb_sym sym, char *buf, mrb_int *lenp)
+{
+  int bit_per_char = SYMBOL_INLINE_LOWER_P(sym) ? 5 : 6;
+  int i;
+
+  mrb_assert(SYMBOL_INLINE_P(sym));
+
+  for (i=0; i<30/bit_per_char; i++) {
+    uint32_t bits = sym>>(i*bit_per_char+SYMBOL_INLINE_SHIFT) & ((1<<bit_per_char)-1);
+    if (bits == 0) break;
+    buf[i] = pack_table[bits-1];;
+  }
+  buf[i] = '\0';
+  if (lenp) *lenp = i;
+  return buf;
+}
+#endif
+
+static uint8_t
+symhash(const char *key, size_t len)
+{
+    uint32_t hash, i;
+
+    for(hash = i = 0; i < len; ++i) {
+        hash += key[i];
+        hash += (hash << 10);
+        hash ^= (hash >> 6);
+    }
+    hash += (hash << 3);
+    hash ^= (hash >> 11);
+    hash += (hash << 15);
+    return hash & 0xff;
+}
+
+static mrb_sym
+find_symbol(mrb_state *mrb, const char *name, size_t len, uint8_t *hashp)
+{
+  mrb_sym i;
+  symbol_name *sname;
+  uint8_t hash;
+
+  /* inline symbol */
+  i = sym_inline_pack(name, len);
+  if (i > 0) return i;
+
+  hash = symhash(name, len);
+  if (hashp) *hashp = hash;
+
+  i = mrb->symhash[hash];
+  if (i == 0) return 0;
+  do {
+    sname = &mrb->symtbl[i];
+    if (sname->len == len && memcmp(sname->name, name, len) == 0) {
+      return i<<SYMBOL_NORMAL_SHIFT;
+    }
+    if (sname->prev == 0xff) {
+      i -= 0xff;
+      sname = &mrb->symtbl[i];
+      while (mrb->symtbl < sname) {
+        if (sname->len == len && memcmp(sname->name, name, len) == 0) {
+          return (mrb_sym)(sname - mrb->symtbl)<<SYMBOL_NORMAL_SHIFT;
+        }
+        sname--;
+      }
+      return 0;
+    }
+    i -= sname->prev;
+  } while (sname->prev > 0);
+  return 0;
+}
+
 static mrb_sym
 sym_intern(mrb_state *mrb, const char *name, size_t len, mrb_bool lit)
 {
-  khash_t(n2s) *h = mrb->name2sym;
-  symbol_name *sname = mrb->symtbl; /* symtbl[0] for working memory */
-  khiter_t k;
   mrb_sym sym;
-  char *p;
+  symbol_name *sname;
+  uint8_t hash;
 
   sym_validate_len(mrb, len);
-  if (sname) {
-    sname->lit = lit;
-    sname->len = (uint16_t)len;
-    sname->name = name;
-    k = kh_get(n2s, mrb, h, 0);
-    if (k != kh_end(h))
-      return kh_key(h, k);
-  }
+  sym = find_symbol(mrb, name, len, &hash);
+  if (sym > 0) return sym;
 
   /* registering a new symbol */
@@ -69 +176 @@
   if (mrb->symcapa < sym) {
     if (mrb->symcapa == 0) mrb->symcapa = 100;
-    else mrb->symcapa = (size_t)(mrb->symcapa * 1.2);
+    else mrb->symcapa = (size_t)(mrb->symcapa * 6 / 5);
     mrb->symtbl = (symbol_name*)mrb_realloc(mrb, mrb->symtbl, sizeof(symbol_name)*(mrb->symcapa+1));
   }
@@ -79 +186 @@
   }
   else {
-    p = (char *)mrb_malloc(mrb, len+1);
+    char *p = (char *)mrb_malloc(mrb, len+1);
     memcpy(p, name, len);
     p[len] = 0;
@@ -85 +192 @@
     sname->lit = FALSE;
   }
-  kh_put(n2s, mrb, h, sym);
-
-  return sym;
+  if (mrb->symhash[hash]) {
+    mrb_sym i = sym - mrb->symhash[hash];
+    if (i > 0xff)
+      sname->prev = 0xff;
+    else
+      sname->prev = i;
+  }
+  else {
+    sname->prev = 0;
+  }
+  mrb->symhash[hash] = sym;
+
+  return sym<<SYMBOL_NORMAL_SHIFT;
 }
 
@@ -117 +234 @@
 mrb_check_intern(mrb_state *mrb, const char *name, size_t len)
 {
-  khash_t(n2s) *h = mrb->name2sym;
-  symbol_name *sname = mrb->symtbl;
-  khiter_t k;
+  mrb_sym sym;
 
   sym_validate_len(mrb, len);
-  sname->len = (uint16_t)len;
-  sname->name = name;
-
-  k = kh_get(n2s, mrb, h, 0);
-  if (k != kh_end(h)) {
-    return mrb_symbol_value(kh_key(h, k));
-  }
+  sym = find_symbol(mrb, name, len, NULL);
+  if (sym > 0) return mrb_symbol_value(sym);
   return mrb_nil_value();
 }
@@ -135 +245 @@
 mrb_check_intern_cstr(mrb_state *mrb, const char *name)
 {
-  return mrb_check_intern(mrb, name, (mrb_int)strlen(name));
+  return mrb_check_intern(mrb, name, strlen(name));
 }
 
@@ -144 +254 @@
 }
 
-/* lenp must be a pointer to a size_t variable */
-MRB_API const char*
-mrb_sym2name_len(mrb_state *mrb, mrb_sym sym, mrb_int *lenp)
-{
+static const char*
+sym2name_len(mrb_state *mrb, mrb_sym sym, char *buf, mrb_int *lenp)
+{
+  if (SYMBOL_INLINE_P(sym)) return sym_inline_unpack(sym, buf, lenp);
+
+  sym >>= SYMBOL_NORMAL_SHIFT;
   if (sym == 0 || mrb->symidx < sym) {
     if (lenp) *lenp = 0;
@@ -155 +267 @@
   if (lenp) *lenp = mrb->symtbl[sym].len;
   return mrb->symtbl[sym].name;
+}
+
+MRB_API const char*
+mrb_sym_name_len(mrb_state *mrb, mrb_sym sym, mrb_int *lenp)
+{
+  return sym2name_len(mrb, sym, mrb->symbuf, lenp);
 }
 
@@ -168 +286 @@
   }
   mrb_free(mrb, mrb->symtbl);
-  kh_destroy(n2s, mrb, mrb->name2sym);
 }
 
@@ -174 +291 @@
 mrb_init_symtbl(mrb_state *mrb)
 {
-  mrb->name2sym = kh_init(n2s, mrb);
 }
 
@@ -210 +326 @@
  */
 
-
-/* 15.2.11.3.1  */
-/*
- *  call-seq:
- *     sym == obj   -> true or false
- *
- *  Equality---If <i>sym</i> and <i>obj</i> are exactly the same
- *  symbol, returns <code>true</code>.
- */
-
-static mrb_value
-sym_equal(mrb_state *mrb, mrb_value sym1)
-{
-  mrb_value sym2;
-
-  mrb_get_args(mrb, "o", &sym2);
-
-  return mrb_bool_value(mrb_obj_equal(mrb, sym1, sym2));
-}
-
 /* 15.2.11.3.2  */
 /* 15.2.11.3.3  */
@@ -242 +338 @@
  */
 static mrb_value
-mrb_sym_to_s(mrb_state *mrb, mrb_value sym)
-{
-  mrb_sym id = mrb_symbol(sym);
-  const char *p;
-  mrb_int len;
-
-  p = mrb_sym2name_len(mrb, id, &len);
-  return mrb_str_new_static(mrb, p, len);
+sym_to_s(mrb_state *mrb, mrb_value sym)
+{
+  return mrb_sym_str(mrb, mrb_symbol(sym));
 }
 
@@ -388 +479 @@
           case '!': case '?': case '=': ++m;
           default: break;
-            }
         }
+      }
       break;
   }
@@ -404 +495 @@
   char *sp;
 
-  name = mrb_sym2name_len(mrb, id, &len);
+  name = mrb_sym_name_len(mrb, id, &len);
   str = mrb_str_new(mrb, 0, len+1);
   sp = RSTRING_PTR(str);
-  RSTRING_PTR(str)[0] = ':';
+  sp[0] = ':';
   memcpy(sp+1, name, len);
   mrb_assert_int_fit(mrb_int, len, size_t, SIZE_MAX);
   if (!symname_p(name) || strlen(name) != (size_t)len) {
-    str = mrb_str_dump(mrb, str);
+    str = mrb_str_inspect(mrb, str);
     sp = RSTRING_PTR(str);
     sp[0] = ':';
     sp[1] = '"';
   }
+#ifdef MRB_UTF8_STRING
+  if (SYMBOL_INLINE_P(id)) RSTR_SET_ASCII_FLAG(mrb_str_ptr(str));
+#endif
   return str;
 }
 
 MRB_API mrb_value
-mrb_sym2str(mrb_state *mrb, mrb_sym sym)
+mrb_sym_str(mrb_state *mrb, mrb_sym sym)
 {
   mrb_int len;
-  const char *name = mrb_sym2name_len(mrb, sym, &len);
+  const char *name = mrb_sym_name_len(mrb, sym, &len);
 
   if (!name) return mrb_undef_value(); /* can't happen */
+  if (SYMBOL_INLINE_P(sym)) {
+    mrb_value str = mrb_str_new(mrb, name, len);
+    RSTR_SET_ASCII_FLAG(mrb_str_ptr(str));
+    return str;
+  }
   return mrb_str_new_static(mrb, name, len);
 }
 
+static const char*
+sym_name(mrb_state *mrb, mrb_sym sym, mrb_bool dump)
+{
+  mrb_int len;
+  const char *name = mrb_sym_name_len(mrb, sym, &len);
+
+  if (!name) return NULL;
+  if (strlen(name) == (size_t)len && (!dump || symname_p(name))) {
+    return name;
+  }
+  else {
+    mrb_value str = SYMBOL_INLINE_P(sym) ?
+      mrb_str_new(mrb, name, len) : mrb_str_new_static(mrb, name, len);
+    str = mrb_str_dump(mrb, str);
+    return RSTRING_PTR(str);
+  }
+}
+
 MRB_API const char*
-mrb_sym2name(mrb_state *mrb, mrb_sym sym)
-{
-  mrb_int len;
-  const char *name = mrb_sym2name_len(mrb, sym, &len);
-
-  if (!name) return NULL;
-  if (symname_p(name) && strlen(name) == (size_t)len) {
-    return name;
-  }
-  else {
-    mrb_value str = mrb_str_dump(mrb, mrb_str_new_static(mrb, name, len));
-    return RSTRING_PTR(str);
-  }
+mrb_sym_name(mrb_state *mrb, mrb_sym sym)
+{
+  return sym_name(mrb, sym, FALSE);
+}
+
+MRB_API const char*
+mrb_sym_dump(mrb_state *mrb, mrb_sym sym)
+{
+  return sym_name(mrb, sym, TRUE);
 }
 
@@ -454 +567 @@
 
   mrb_get_args(mrb, "o", &s2);
-  if (mrb_type(s2) != MRB_TT_SYMBOL) return mrb_nil_value();
+  if (!mrb_symbol_p(s2)) return mrb_nil_value();
   sym1 = mrb_symbol(s1);
   sym2 = mrb_symbol(s2);
@@ -462 +575 @@
     int retval;
     mrb_int len, len1, len2;
-
-    p1 = mrb_sym2name_len(mrb, sym1, &len1);
-    p2 = mrb_sym2name_len(mrb, sym2, &len2);
+    char buf1[8], buf2[8];
+
+    p1 = sym2name_len(mrb, sym1, buf1, &len1);
+    p2 = sym2name_len(mrb, sym2, buf2, &len2);
     len = lesser(len1, len2);
     retval = memcmp(p1, p2, len);
@@ -482 +596 @@
   struct RClass *sym;
 
-  mrb->symbol_class = sym = mrb_define_class(mrb, "Symbol", mrb->object_class);                 /* 15.2.11 */
+  mrb->symbol_class = sym = mrb_define_class(mrb, "Symbol", mrb->object_class);  /* 15.2.11 */
   MRB_SET_INSTANCE_TT(sym, MRB_TT_SYMBOL);
   mrb_undef_class_method(mrb,  sym, "new");
 
-  mrb_define_method(mrb, sym, "===",             sym_equal,      MRB_ARGS_REQ(1));              /* 15.2.11.3.1  */
-  mrb_define_method(mrb, sym, "id2name",         mrb_sym_to_s,   MRB_ARGS_NONE());              /* 15.2.11.3.2  */
-  mrb_define_method(mrb, sym, "to_s",            mrb_sym_to_s,   MRB_ARGS_NONE());              /* 15.2.11.3.3  */
-  mrb_define_method(mrb, sym, "to_sym",          sym_to_sym,     MRB_ARGS_NONE());              /* 15.2.11.3.4  */
-  mrb_define_method(mrb, sym, "inspect",         sym_inspect,    MRB_ARGS_NONE());              /* 15.2.11.3.5(x)  */
-  mrb_define_method(mrb, sym, "<=>",             sym_cmp,        MRB_ARGS_REQ(1));
-}
+  mrb_define_method(mrb, sym, "id2name", sym_to_s,    MRB_ARGS_NONE());          /* 15.2.11.3.2 */
+  mrb_define_method(mrb, sym, "to_s",    sym_to_s,    MRB_ARGS_NONE());          /* 15.2.11.3.3 */
+  mrb_define_method(mrb, sym, "to_sym",  sym_to_sym,  MRB_ARGS_NONE());          /* 15.2.11.3.4 */
+  mrb_define_method(mrb, sym, "inspect", sym_inspect, MRB_ARGS_NONE());          /* 15.2.11.3.5(x) */
+  mrb_define_method(mrb, sym, "<=>",     sym_cmp,     MRB_ARGS_REQ(1));
+}