diff options
Diffstat (limited to 'hash.c')
| -rw-r--r-- | hash.c | 470 |
1 files changed, 389 insertions, 81 deletions
@@ -6,12 +6,13 @@ $Date: 1996/12/25 10:42:26 $ created at: Mon Nov 22 18:51:18 JST 1993 - Copyright (C) 1993-1996 Yukihiro Matsumoto + Copyright (C) 1993-1997 Yukihiro Matsumoto ************************************************/ #include "ruby.h" #include "st.h" +#include "sig.h" #ifdef HAVE_STRING_H # include <string.h> @@ -19,31 +20,44 @@ char *strchr(); #endif +#define HASH_DELETED 0x1 +#define HASH_REHASHED 0x2 + +#ifndef NT char *getenv(); +#endif VALUE cHash; static VALUE envtbl; static ID hash; -VALUE f_getenv(), f_setenv(); + +VALUE +rb_hash(obj) + VALUE obj; +{ + return rb_funcall(obj, hash, 0); +} static int -rb_cmp(a, b) +any_cmp(a, b) VALUE a, b; { if (FIXNUM_P(a)) { if (FIXNUM_P(b)) return a != b; } - - if (TYPE(a) == T_STRING) { + else if (TYPE(a) == T_STRING) { if (TYPE(b) == T_STRING) return str_cmp(a, b); } - return !rb_eql(a, b); + DEFER_INTS; + a = !rb_eql(a, b); + ENABLE_INTS; + return a; } static int -rb_hash(a, mod) +any_hash(a, mod) VALUE a; int mod; { @@ -59,17 +73,85 @@ rb_hash(a, mod) break; default: + DEFER_INTS; hval = rb_funcall(a, hash, 0); + if (!FIXNUM_P(hval)) { + hval = rb_funcall(hval, '%', 1, INT2FIX(65439)); + } + ENABLE_INTS; hval = FIX2INT(hval); } return hval % mod; } static struct st_hash_type objhash = { - rb_cmp, - rb_hash, + any_cmp, + any_hash, +}; + +struct hash_foreach_arg { + struct RHash *hash; + enum st_retval (*func)(); + char *arg; }; +static int +hash_foreach_iter(key, value, arg) + VALUE key, value; + struct hash_foreach_arg *arg; +{ + int status; + + if (key == Qnil) return ST_CONTINUE; + status = (*arg->func)(key, value, arg->arg); + if (arg->hash->status & HASH_REHASHED) return ST_STOP; + return status; +} + +static int +hash_foreach_call(arg) + struct hash_foreach_arg *arg; +{ + return st_foreach(arg->hash->tbl, hash_foreach_iter, arg); +} + +static int +hash_delete_nil(key, value) + VALUE key, value; +{ + if (key == Qnil) return ST_DELETE; + return ST_CONTINUE; +} + +static void +hash_foreach_ensure(hash) + struct RHash *hash; +{ + hash->iter_lev--; + + if (hash->iter_lev == 0) { + if (hash->status & HASH_DELETED) { + st_foreach(hash->tbl, hash_delete_nil, 0); + } + hash->status = 0; + } +} + +static int +hash_foreach(hash, func, farg) + struct RHash *hash; + enum st_retval (*func)(); + char *farg; +{ + struct hash_foreach_arg arg; + + hash->iter_lev++; + arg.hash = hash; + arg.func = func; + arg.arg = farg; + return rb_ensure(hash_foreach_call, &arg, hash_foreach_ensure, hash); +} + static VALUE hash_s_new(argc, argv, class) int argc; @@ -86,13 +168,14 @@ hash_s_new(argc, argv, class) if (NIL_P(sz)) size = 0; else size = NUM2INT(sz); + hash->iter_lev = 0; + hash->status = 0; + hash->tbl = 0; /* avoid GC crashing */ hash->tbl = st_init_table_with_size(&objhash, size); return (VALUE)hash; } -static VALUE hash_clone(); - VALUE hash_new2(class) VALUE class; @@ -120,8 +203,11 @@ hash_s_create(argc, argv, class) else { NEWOBJ(hash, struct RHash); OBJSETUP(hash, class, T_HASH); + + hash->iter_lev = 0; + hash->status = 0; + hash->tbl = 0; /* avoid GC crashing */ hash->tbl = (st_table*)st_copy(RHASH(argv[0])->tbl); - return (VALUE)hash; } } @@ -145,11 +231,39 @@ hash_clone(hash) NEWOBJ(hash2, struct RHash); CLONESETUP(hash2, hash); + hash2->iter_lev = 0; + hash2->status = 0; + hash2->tbl = 0; /* avoid GC crashing */ hash2->tbl = (st_table*)st_copy(hash->tbl); return (VALUE)hash2; } +static int +hash_rehash_i(key, value, tbl) + VALUE key, value; + st_table *tbl; +{ + if (key != Qnil) { + st_insert(tbl, key, value); + } + return ST_CONTINUE; +} + +static VALUE +hash_rehash(hash) + struct RHash *hash; +{ + st_table *tbl = st_init_table_with_size(&objhash, hash->tbl->num_entries); + + st_foreach(hash->tbl, hash_rehash_i, tbl); + st_free_table(hash->tbl); + hash->tbl = tbl; + if (hash->iter_lev > 0) hash->status |= HASH_REHASHED; + + return (VALUE)hash; +} + VALUE hash_aref(hash, key) struct RHash *hash; @@ -164,23 +278,17 @@ hash_aref(hash, key) } static VALUE -hash_indexes(hash, args) +hash_indexes(argc, argv, hash) + int argc; + VALUE *argv; struct RHash *hash; - struct RArray *args; { - VALUE *p, *pend; struct RArray *indexes; - int i = 0; - - if (!args || NIL_P(args)) { - return ary_new2(0); - } - - indexes = (struct RArray*)ary_new2(args->len); + int i; - p = args->ptr; pend = p + args->len; - while (p < pend) { - indexes->ptr[i++] = hash_aref(hash, *p++); + indexes = (struct RArray*)ary_new2(argc); + for (i=0; i<argc; i++) { + indexes->ptr[i] = hash_aref(hash, argv[i]); } indexes->len = i; return (VALUE)indexes; @@ -193,9 +301,12 @@ hash_delete(hash, key) { VALUE val; - if (st_delete(hash->tbl, &key, &val)) + rb_secure(5); + if (hash->iter_lev > 0 && st_delete_safe(hash->tbl, &key, &val, Qnil)) + return val; + else if (st_delete(hash->tbl, &key, &val)) return val; - if (iterator_p()) rb_yield(Qnil); + if (iterator_p()) rb_yield(key); return Qnil; } @@ -205,11 +316,12 @@ struct shift_var { VALUE val; }; -static +static int shift_i(key, value, var) VALUE key, value; struct shift_var *var; { + if (key == Qnil) return ST_CONTINUE; if (var->stop) return ST_STOP; var->stop = 1; var->key = key; @@ -223,6 +335,7 @@ hash_shift(hash) { struct shift_var var; + rb_secure(5); var.stop = 0; st_foreach(hash->tbl, shift_i, &var); @@ -234,6 +347,7 @@ static int delete_if_i(key, value) VALUE key, value; { + if (key == Qnil) return ST_CONTINUE; if (rb_yield(assoc_new(key, value))) return ST_DELETE; return ST_CONTINUE; @@ -243,7 +357,8 @@ static VALUE hash_delete_if(hash) struct RHash *hash; { - st_foreach(hash->tbl, delete_if_i, 0); + rb_secure(5); + hash_foreach(hash, delete_if_i, 0); return (VALUE)hash; } @@ -259,6 +374,7 @@ static VALUE hash_clear(hash) struct RHash *hash; { + rb_secure(5); st_foreach(hash->tbl, clear_i); return (VALUE)hash; @@ -269,6 +385,7 @@ hash_aset(hash, key, val) struct RHash *hash; VALUE key, val; { + rb_secure(5); if (NIL_P(val)) { hash_delete(hash, key); return Qnil; @@ -300,6 +417,7 @@ static int each_value_i(key, value) VALUE key, value; { + if (key == Qnil) return ST_CONTINUE; rb_yield(value); return ST_CONTINUE; } @@ -308,7 +426,7 @@ static VALUE hash_each_value(hash) struct RHash *hash; { - st_foreach(hash->tbl, each_value_i); + hash_foreach(hash, each_value_i); return (VALUE)hash; } @@ -316,6 +434,7 @@ static int each_key_i(key, value) VALUE key, value; { + if (key == Qnil) return ST_CONTINUE; rb_yield(key); return ST_CONTINUE; } @@ -324,7 +443,7 @@ static VALUE hash_each_key(hash) struct RHash *hash; { - st_foreach(hash->tbl, each_key_i); + hash_foreach(hash, each_key_i); return (VALUE)hash; } @@ -332,6 +451,7 @@ static int each_pair_i(key, value) VALUE key, value; { + if (key == Qnil) return ST_CONTINUE; rb_yield(assoc_new(key, value)); return ST_CONTINUE; } @@ -340,7 +460,7 @@ static VALUE hash_each_pair(hash) struct RHash *hash; { - st_foreach(hash->tbl, each_pair_i); + hash_foreach(hash, each_pair_i); return (VALUE)hash; } @@ -348,6 +468,7 @@ static int to_a_i(key, value, ary) VALUE key, value, ary; { + if (key == Qnil) return ST_CONTINUE; ary_push(ary, assoc_new(key, value)); return ST_CONTINUE; } @@ -371,6 +492,7 @@ inspect_i(key, value, str) { VALUE str2; + if (key == Qnil) return ST_CONTINUE; if (str->len > 1) { str_cat(str, ", ", 2); } @@ -407,6 +529,7 @@ static int keys_i(key, value, ary) VALUE key, value, ary; { + if (key == Qnil) return ST_CONTINUE; ary_push(ary, key); return ST_CONTINUE; } @@ -427,6 +550,7 @@ static int values_i(key, value, ary) VALUE key, value, ary; { + if (key == Qnil) return ST_CONTINUE; ary_push(ary, value); return ST_CONTINUE; } @@ -443,17 +567,6 @@ hash_values(hash) return ary; } -static int -hash_search_value(key, value, data) - VALUE key, value, *data; -{ - if (rb_equal(value, data[1])) { - data[0] = TRUE; - return ST_STOP; - } - return ST_CONTINUE; -} - static VALUE hash_has_key(hash, key) struct RHash *hash; @@ -465,6 +578,18 @@ hash_has_key(hash, key) return FALSE; } +static int +hash_search_value(key, value, data) + VALUE key, value, *data; +{ + if (key == Qnil) return ST_CONTINUE; + if (rb_equal(value, data[1])) { + data[0] = TRUE; + return ST_STOP; + } + return ST_CONTINUE; +} + static VALUE hash_has_value(hash, val) struct RHash *hash; @@ -490,6 +615,7 @@ equal_i(key, val1, data) { VALUE val2; + if (key == Qnil) return ST_CONTINUE; if (!st_lookup(data->tbl, key, &val2)) { data->result = FALSE; return ST_STOP; @@ -519,45 +645,30 @@ hash_equal(hash1, hash2) } static int -hash_i(key, val, data) - VALUE key, val; - int *data; +hash_invert_i(key, value, hash) + VALUE key, value; + struct RHash *hash; { - *data ^= rb_funcall(key, hash, 0); - *data ^= rb_funcall(val, hash, 0); + if (key == Qnil) return ST_CONTINUE; + hash_aset(hash, value, key); return ST_CONTINUE; } static VALUE -hash_hash(hash) +hash_invert(hash) struct RHash *hash; { - int h; + VALUE h = hash_new(); - st_foreach(hash->tbl, hash_i, &h); - return INT2FIX(h); + st_foreach(hash->tbl, hash_invert_i, h); + return h; } -extern char **environ; - -static VALUE -env_each(hash) - VALUE hash; -{ - char **env; - - env = environ; - while (*env) { - VALUE var, val; - char *s = strchr(*env, '='); +int env_path_tainted = 0; - var = str_new(*env, s-*env); - val = str_new2(s+1); - rb_yield(assoc_new(var, val)); - env++; - } - return hash; -} +#ifndef NT +extern char **environ; +#endif static VALUE env_delete(obj, name) @@ -567,9 +678,11 @@ env_delete(obj, name) int i, len; char *nam, *val = 0; + rb_secure(4); Check_Type(name, T_STRING); nam = name->ptr; len = strlen(nam); + if (strcmp(nam, "PATH") == 0) env_path_tainted = 0; for(i=0; environ[i]; i++) { if (strncmp(environ[i], nam, len) == 0 && environ[i][len] == '=') { val = environ[i]+len+1; @@ -586,7 +699,7 @@ env_delete(obj, name) return Qnil; } -VALUE +static VALUE f_getenv(obj, name) VALUE obj; struct RString *name; @@ -600,43 +713,222 @@ f_getenv(obj, name) env = getenv(name->ptr); if (env) { - return str_new2(env); + if (strcmp(name->ptr, "PATH") == 0 && !env_path_tainted) + return str_new2(env); + return str_taint(str_new2(env)); } return Qnil; } -VALUE +static VALUE f_setenv(obj, name, value) VALUE obj; struct RString *name, *value; { - Check_Type(name, T_STRING); + if (rb_safe_level() >= 4) { + extern VALUE eSecurityError; + Raise(eSecurityError, "cannot change environment variable"); + } + + Check_SafeStr(name); if (NIL_P(value)) { env_delete(obj, name); return Qnil; } - Check_Type(value, T_STRING); - + Check_SafeStr(value); if (strlen(name->ptr) != name->len) ArgError("Bad environment name"); if (strlen(value->ptr) != value->len) ArgError("Bad environment value"); setenv(name->ptr, value->ptr, 1); + if (strcmp(name->ptr, "PATH") == 0) env_path_tainted = 0; return TRUE; } static VALUE +env_keys() +{ + char **env; + VALUE ary = ary_new(); + + env = environ; + while (*env) { + char *s = strchr(*env, '='); + ary_push(ary, str_taint(str_new(*env, s-*env))); + env++; + } + return ary; +} + +static VALUE +env_each_key(hash) + VALUE hash; +{ + return ary_each(env_keys()); +} + +static VALUE +env_values() +{ + char **env; + VALUE ary = ary_new(); + + env = environ; + while (*env) { + char *s = strchr(*env, '='); + ary_push(ary, str_taint(str_new2(s+1))); + env++; + } + return ary; +} + +static VALUE +env_each_value(hash) + VALUE hash; +{ + return ary_each(env_values()); +} + +static VALUE +env_each(hash) + VALUE hash; +{ + VALUE ary = env_keys(); + VALUE *ptr = RARRAY(ary)->ptr; + int len = RARRAY(ary)->len; + + while (len--) { + VALUE val = f_getenv(Qnil, *ptr); + if (!NIL_P(val)) { + rb_yield(assoc_new(*ptr, val)); + } + ptr++; + } + return hash; +} + +static VALUE +env_delete_if() +{ + VALUE ary = env_keys(); + VALUE *ptr = RARRAY(ary)->ptr; + int len = RARRAY(ary)->len; + + while (len--) { + VALUE val = f_getenv(Qnil, *ptr); + if (!NIL_P(val)) { + if (RTEST(rb_yield(assoc_new(*ptr, val)))) { + env_delete(Qnil, *ptr); + } + } + ptr++; + } + return envtbl; +} + +static VALUE env_to_s() { return str_new2("ENV"); } +static VALUE +env_to_a() +{ + char **env; + VALUE ary = ary_new(); + + env = environ; + while (*env) { + char *s = strchr(*env, '='); + ary_push(ary, assoc_new(str_taint(str_new(*env, s-*env)), + str_taint(str_new2(s+1)))); + env++; + } + return ary; +} + +static VALUE +env_none() +{ + return Qnil; +} + +static VALUE +env_size() +{ + int i; + + for(i=0; environ[i]; i++) + ; + return INT2FIX(i); +} + +static VALUE +env_empty_p() +{ + if (environ[0] == 0) return TRUE; + return FALSE; +} + +static VALUE +env_has_key(env, key) + VALUE env, key; +{ + if (TYPE(key) != T_STRING) return FALSE; + if (getenv(RSTRING(key)->ptr)) return TRUE; + return FALSE; +} + +static VALUE +env_has_value(dmy, value) + VALUE dmy, value; +{ + char **env; + VALUE ary; + + if (TYPE(value) != T_STRING) return FALSE; + ary = ary_new(); + env = environ; + while (*env) { + char *s = strchr(*env, '=')+1; + int len = strlen(s); + if (strncmp(s, RSTRING(value)->ptr, len) == 0) return TRUE; + env++; + } + return FALSE; +} + +static VALUE +env_indexes(argc, argv) + int argc; + VALUE *argv; +{ + int i; + VALUE indexes = ary_new2(argc); + + for (i=0;i<argc;i++) { + char *v = 0; + if (TYPE(argv[i]) == T_STRING) { + v = getenv(RSTRING(argv[i])->ptr); + } + if (v) { + RARRAY(indexes)->ptr[i] = str_new2(v); + } + else { + RARRAY(indexes)->ptr[i] = Qnil; + } + RARRAY(indexes)->len = i+1; + } + + return indexes; +} + void Init_Hash() { - extern VALUE cKernel; extern VALUE mEnumerable; hash = rb_intern("hash"); @@ -649,16 +941,16 @@ Init_Hash() rb_define_singleton_method(cHash, "[]", hash_s_create, -1); rb_define_method(cHash,"clone", hash_clone, 0); + rb_define_method(cHash,"rehash", hash_rehash, 0); rb_define_method(cHash,"to_a", hash_to_a, 0); rb_define_method(cHash,"to_s", hash_to_s, 0); rb_define_method(cHash,"inspect", hash_inspect, 0); rb_define_method(cHash,"==", hash_equal, 1); - rb_define_method(cHash,"hash", hash_hash, 0); rb_define_method(cHash,"[]", hash_aref, 1); rb_define_method(cHash,"[]=", hash_aset, 2); - rb_define_method(cHash,"indexes", hash_indexes, -2); + rb_define_method(cHash,"indexes", hash_indexes, -1); rb_define_method(cHash,"length", hash_length, 0); rb_define_alias(cHash, "size", "length"); rb_define_method(cHash,"empty?", hash_empty_p, 0); @@ -675,6 +967,7 @@ Init_Hash() rb_define_method(cHash,"delete", hash_delete, 1); rb_define_method(cHash,"delete_if", hash_delete_if, 0); rb_define_method(cHash,"clear", hash_clear, 0); + rb_define_method(cHash,"invert", hash_invert, 0); rb_define_method(cHash,"include?", hash_has_key, 1); rb_define_method(cHash,"has_key?", hash_has_key, 1); @@ -688,9 +981,24 @@ Init_Hash() rb_define_singleton_method(envtbl,"[]", f_getenv, 1); rb_define_singleton_method(envtbl,"[]=", f_setenv, 2); rb_define_singleton_method(envtbl,"each", env_each, 0); + rb_define_singleton_method(envtbl,"each_pair", env_each, 0); + rb_define_singleton_method(envtbl,"each_key", env_each_key, 0); + rb_define_singleton_method(envtbl,"each_value", env_each_value, 0); rb_define_singleton_method(envtbl,"delete", env_delete, 1); + rb_define_singleton_method(envtbl,"delete_if", env_delete_if, 0); rb_define_singleton_method(envtbl,"to_s", env_to_s, 0); + rb_define_singleton_method(envtbl,"rehash", env_none, 0); + rb_define_singleton_method(envtbl,"to_a", env_to_a, 0); + rb_define_singleton_method(envtbl,"indexes", env_indexes, -1); + rb_define_singleton_method(envtbl,"length", env_size, 0); + rb_define_singleton_method(envtbl,"empty?", env_empty_p, 0); + rb_define_singleton_method(envtbl,"keys", env_keys, 0); + rb_define_singleton_method(envtbl,"values", env_values, 0); + rb_define_singleton_method(envtbl,"include?", env_has_key, 1); + rb_define_singleton_method(envtbl,"has_key?", env_has_key, 1); + rb_define_singleton_method(envtbl,"has_value?", env_has_value, 1); + rb_define_singleton_method(envtbl,"key?", env_has_key, 1); + rb_define_singleton_method(envtbl,"value?", env_has_value, 1); - rb_define_readonly_variable("$ENV", &envtbl); rb_define_global_const("ENV", envtbl); } |