X-Git-Url: http://git.hcoop.net/bpt/guile.git/blobdiff_plain/4c9419ac31f8364db51ccf25f7f9d5d31dd412e7..0d959103f985bbb60959c7ef4738235527792e47:/libguile/vectors.c diff --git a/libguile/vectors.c b/libguile/vectors.c index c1dfe840f..1640725e5 100644 --- a/libguile/vectors.c +++ b/libguile/vectors.c @@ -1,65 +1,108 @@ -/* Copyright (C) 1995,1996,1998,1999,2000,2001 Free Software Foundation, Inc. +/* Copyright (C) 1995,1996,1998,1999,2000,2001, 2006, 2008, 2009, 2010, 2011 Free Software Foundation, Inc. * - * This program is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation; either version 2, or (at your option) - * any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this software; see the file COPYING. If not, write to - * the Free Software Foundation, Inc., 59 Temple Place, Suite 330, - * Boston, MA 02111-1307 USA - * - * As a special exception, the Free Software Foundation gives permission - * for additional uses of the text contained in its release of GUILE. - * - * The exception is that, if you link the GUILE library with other files - * to produce an executable, this does not by itself cause the - * resulting executable to be covered by the GNU General Public License. - * Your use of that executable is in no way restricted on account of - * linking the GUILE library code into it. + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public License + * as published by the Free Software Foundation; either version 3 of + * the License, or (at your option) any later version. * - * This exception does not however invalidate any other reasons why - * the executable file might be covered by the GNU General Public License. + * This library is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. * - * This exception applies only to the code released by the - * Free Software Foundation under the name GUILE. If you copy - * code from other Free Software Foundation releases into a copy of - * GUILE, as the General Public License permits, the exception does - * not apply to the code that you add in this way. To avoid misleading - * anyone as to the status of such modified files, you must delete - * this exception notice from them. - * - * If you write modifications of your own for GUILE, it is your choice - * whether to permit this exception to apply to your modifications. - * If you do not wish that, delete this exception notice. */ + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA + * 02110-1301 USA + */ +#ifdef HAVE_CONFIG_H +# include +#endif #include "libguile/_scm.h" #include "libguile/eq.h" #include "libguile/root.h" #include "libguile/strings.h" -#include "libguile/lang.h" #include "libguile/validate.h" #include "libguile/vectors.h" -#include "libguile/unif.h" +#include "libguile/arrays.h" /* Hit me with the ugly stick */ +#include "libguile/generalized-vectors.h" +#include "libguile/strings.h" +#include "libguile/srfi-13.h" +#include "libguile/dynwind.h" +#include "libguile/deprecation.h" + +#include "libguile/bdw-gc.h" + + +#define VECTOR_MAX_LENGTH (SCM_T_BITS_MAX >> 8) + +int +scm_is_vector (SCM obj) +{ + if (SCM_I_IS_VECTOR (obj)) + return 1; + if (SCM_I_ARRAYP (obj) && SCM_I_ARRAY_NDIM (obj) == 1) + { + SCM v = SCM_I_ARRAY_V (obj); + return SCM_I_IS_VECTOR (v); + } + return 0; +} + +int +scm_is_simple_vector (SCM obj) +{ + return SCM_I_IS_VECTOR (obj); +} + +const SCM * +scm_vector_elements (SCM vec, scm_t_array_handle *h, + size_t *lenp, ssize_t *incp) +{ + if (SCM_I_WVECTP (vec)) + scm_wrong_type_arg_msg (NULL, 0, vec, "non-weak vector"); + + scm_generalized_vector_get_handle (vec, h); + if (lenp) + { + scm_t_array_dim *dim = scm_array_handle_dims (h); + *lenp = dim->ubnd - dim->lbnd + 1; + *incp = dim->inc; + } + return scm_array_handle_elements (h); +} + +SCM * +scm_vector_writable_elements (SCM vec, scm_t_array_handle *h, + size_t *lenp, ssize_t *incp) +{ + if (SCM_I_WVECTP (vec)) + scm_wrong_type_arg_msg (NULL, 0, vec, "non-weak vector"); + + scm_generalized_vector_get_handle (vec, h); + if (lenp) + { + scm_t_array_dim *dim = scm_array_handle_dims (h); + *lenp = dim->ubnd - dim->lbnd + 1; + *incp = dim->inc; + } + return scm_array_handle_writable_elements (h); +} + SCM_DEFINE (scm_vector_p, "vector?", 1, 0, 0, (SCM obj), "Return @code{#t} if @var{obj} is a vector, otherwise return\n" "@code{#f}.") #define FUNC_NAME s_scm_vector_p { - return SCM_BOOL (SCM_VECTORP (obj)); + return scm_from_bool (scm_is_vector (obj)); } #undef FUNC_NAME @@ -68,9 +111,24 @@ SCM_GPROC (s_vector_length, "vector-length", 1, 0, 0, scm_vector_length, g_vecto SCM scm_vector_length (SCM v) { - SCM_GASSERT1 (SCM_VECTORP(v), - g_vector_length, v, SCM_ARG1, s_vector_length); - return SCM_MAKINUM (SCM_VECTOR_LENGTH (v)); + if (SCM_I_IS_VECTOR (v)) + return scm_from_size_t (SCM_I_VECTOR_LENGTH (v)); + else if (SCM_I_ARRAYP (v) && SCM_I_ARRAY_NDIM (v) == 1) + { + scm_t_array_dim *dim = SCM_I_ARRAY_DIMS (v); + return scm_from_size_t (dim->ubnd - dim->lbnd + 1); + } + else + return scm_wta_dispatch_1 (g_vector_length, v, 1, "vector-length"); +} + +size_t +scm_c_vector_length (SCM v) +{ + if (SCM_I_IS_VECTOR (v)) + return SCM_I_VECTOR_LENGTH (v); + else + return scm_to_size_t (scm_vector_length (v)); } SCM_REGISTER_PROC (s_list_to_vector, "list->vector", 1, 0, 0, scm_vector); @@ -95,19 +153,23 @@ SCM_DEFINE (scm_vector, "vector", 0, 0, 1, { SCM res; SCM *data; - long i; + long i, len; + scm_t_array_handle handle; + + SCM_VALIDATE_LIST_COPYLEN (1, l, len); - /* Dirk:FIXME:: In case of multiple threads, the list might get corrupted - while the vector is being created. */ - SCM_VALIDATE_LIST_COPYLEN (1, l, i); - res = scm_c_make_vector (i, SCM_UNSPECIFIED); - data = SCM_VELTS (res); - while (!SCM_NULL_OR_NIL_P (l)) + res = scm_c_make_vector (len, SCM_UNSPECIFIED); + data = scm_vector_writable_elements (res, &handle, NULL, NULL); + i = 0; + while (scm_is_pair (l) && i < len) { - *data++ = SCM_CAR (l); + data[i] = SCM_CAR (l); l = SCM_CDR (l); + i += 1; } + scm_array_handle_release (&handle); + return res; } #undef FUNC_NAME @@ -132,15 +194,42 @@ SCM scm_vector_ref (SCM v, SCM k) #define FUNC_NAME s_vector_ref { - SCM_GASSERT2 (SCM_VECTORP (v), - g_vector_ref, v, k, SCM_ARG1, s_vector_ref); - SCM_GASSERT2 (SCM_INUMP (k), - g_vector_ref, v, k, SCM_ARG2, s_vector_ref); - SCM_ASSERT_RANGE (2, k, SCM_INUM (k) < SCM_VECTOR_LENGTH (v) && SCM_INUM (k) >= 0); - return SCM_VELTS (v)[(long) SCM_INUM (k)]; + return scm_c_vector_ref (v, scm_to_size_t (k)); } #undef FUNC_NAME +SCM +scm_c_vector_ref (SCM v, size_t k) +{ + if (SCM_I_IS_NONWEAK_VECTOR (v)) + { + if (k >= SCM_I_VECTOR_LENGTH (v)) + scm_out_of_range (NULL, scm_from_size_t (k)); + return SCM_SIMPLE_VECTOR_REF (v, k); + } + else if (SCM_I_WVECTP (v)) + return scm_c_weak_vector_ref (v, k); + else if (SCM_I_ARRAYP (v) && SCM_I_ARRAY_NDIM (v) == 1) + { + scm_t_array_dim *dim = SCM_I_ARRAY_DIMS (v); + SCM vv = SCM_I_ARRAY_V (v); + + k = SCM_I_ARRAY_BASE (v) + k*dim->inc; + if (k >= dim->ubnd - dim->lbnd + 1) + scm_out_of_range (NULL, scm_from_size_t (k)); + + if (SCM_I_IS_NONWEAK_VECTOR (vv)) + return SCM_SIMPLE_VECTOR_REF (vv, k); + else if (SCM_I_WVECTP (vv)) + return scm_c_weak_vector_ref (vv, k); + else + scm_wrong_type_arg_msg (NULL, 0, v, "non-uniform vector"); + } + else + return scm_wta_dispatch_2 (g_vector_ref, v, scm_from_size_t (k), 2, + "vector-ref"); +} + SCM_GPROC (s_vector_set_x, "vector-set!", 3, 0, 0, scm_vector_set_x, g_vector_set_x); /* "@var{k} must be a valid index of @var{vector}.\n" @@ -158,18 +247,49 @@ SCM scm_vector_set_x (SCM v, SCM k, SCM obj) #define FUNC_NAME s_vector_set_x { - SCM_GASSERTn (SCM_VECTORP (v), - g_vector_set_x, scm_list_3 (v, k, obj), - SCM_ARG1, s_vector_set_x); - SCM_GASSERTn (SCM_INUMP (k), - g_vector_set_x, scm_list_3 (v, k, obj), - SCM_ARG2, s_vector_set_x); - SCM_ASSERT_RANGE (2, k, SCM_INUM (k) < SCM_VECTOR_LENGTH (v) && SCM_INUM (k) >= 0); - SCM_VELTS(v)[(long) SCM_INUM(k)] = obj; + scm_c_vector_set_x (v, scm_to_size_t (k), obj); return SCM_UNSPECIFIED; } #undef FUNC_NAME +void +scm_c_vector_set_x (SCM v, size_t k, SCM obj) +{ + if (SCM_I_IS_NONWEAK_VECTOR (v)) + { + if (k >= SCM_I_VECTOR_LENGTH (v)) + scm_out_of_range (NULL, scm_from_size_t (k)); + SCM_SIMPLE_VECTOR_SET (v, k, obj); + } + else if (SCM_I_WVECTP (v)) + scm_c_weak_vector_set_x (v, k, obj); + else if (SCM_I_ARRAYP (v) && SCM_I_ARRAY_NDIM (v) == 1) + { + scm_t_array_dim *dim = SCM_I_ARRAY_DIMS (v); + SCM vv = SCM_I_ARRAY_V (v); + + k = SCM_I_ARRAY_BASE (v) + k*dim->inc; + if (k >= dim->ubnd - dim->lbnd + 1) + scm_out_of_range (NULL, scm_from_size_t (k)); + + if (SCM_I_IS_NONWEAK_VECTOR (vv)) + SCM_SIMPLE_VECTOR_SET (vv, k, obj); + else if (SCM_I_WVECTP (vv)) + scm_c_weak_vector_set_x (vv, k, obj); + else + scm_wrong_type_arg_msg (NULL, 0, v, "non-uniform vector"); + } + else + { + if (SCM_UNPACK (g_vector_set_x)) + scm_wta_dispatch_n (g_vector_set_x, + scm_list_3 (v, scm_from_size_t (k), obj), + 0, + "vector-set!"); + else + scm_wrong_type_arg_msg (NULL, 0, v, "vector"); + } +} SCM_DEFINE (scm_make_vector, "make-vector", 1, 1, 0, (SCM k, SCM fill), @@ -179,51 +299,59 @@ SCM_DEFINE (scm_make_vector, "make-vector", 1, 1, 0, "unspecified.") #define FUNC_NAME s_scm_make_vector { + size_t l = scm_to_unsigned_integer (k, 0, VECTOR_MAX_LENGTH); + if (SCM_UNBNDP (fill)) fill = SCM_UNSPECIFIED; - - if (SCM_INUMP (k)) - { - SCM_ASSERT_RANGE (1, k, SCM_INUM (k) >= 0); - return scm_c_make_vector (SCM_INUM (k), fill); - } - else if (SCM_BIGP (k)) - SCM_OUT_OF_RANGE (1, k); - else - SCM_WRONG_TYPE_ARG (1, k); + + return scm_c_make_vector (l, fill); } #undef FUNC_NAME SCM -scm_c_make_vector (unsigned long int k, SCM fill) +scm_c_make_vector (size_t k, SCM fill) #define FUNC_NAME s_scm_make_vector { - SCM v; - scm_t_bits *base; + SCM vector; + unsigned long int j; - if (k > 0) - { - unsigned long int j; + SCM_ASSERT_RANGE (1, scm_from_size_t (k), k <= VECTOR_MAX_LENGTH); - SCM_ASSERT_RANGE (1, scm_ulong2num (k), k <= SCM_VECTOR_MAX_LENGTH); + vector = scm_words ((k << 8) | scm_tc7_vector, k + 1); - base = scm_gc_malloc (k * sizeof (scm_t_bits), "vector"); - for (j = 0; j != k; ++j) - base[j] = SCM_UNPACK (fill); - } - else - base = NULL; + for (j = 0; j < k; ++j) + SCM_SIMPLE_VECTOR_SET (vector, j, fill); - v = scm_alloc_cell (SCM_MAKE_VECTOR_TAG (k, scm_tc7_vector), - (scm_t_bits) base); - scm_remember_upto_here_1 (fill); - - return v; + return vector; } #undef FUNC_NAME +SCM_DEFINE (scm_vector_copy, "vector-copy", 1, 0, 0, + (SCM vec), + "Return a copy of @var{vec}.") +#define FUNC_NAME s_scm_vector_copy +{ + scm_t_array_handle handle; + size_t i, len; + ssize_t inc; + const SCM *src; + SCM result, *dst; + + src = scm_vector_elements (vec, &handle, &len, &inc); + + result = scm_c_make_vector (len, SCM_UNDEFINED); + dst = SCM_I_VECTOR_WELTS (result); + for (i = 0; i < len; i++, src += inc) + dst[i] = *src; + + scm_array_handle_release (&handle); + return result; +} +#undef FUNC_NAME + + SCM_DEFINE (scm_vector_to_list, "vector->list", 1, 0, 0, (SCM v), "Return a newly allocated list composed of the elements of @var{v}.\n" @@ -235,11 +363,18 @@ SCM_DEFINE (scm_vector_to_list, "vector->list", 1, 0, 0, #define FUNC_NAME s_scm_vector_to_list { SCM res = SCM_EOL; - long i; - SCM *data; - SCM_VALIDATE_VECTOR (1,v); - data = SCM_VELTS(v); - for(i = SCM_VECTOR_LENGTH(v)-1;i >= 0;i--) res = scm_cons(data[i], res); + const SCM *data; + scm_t_array_handle handle; + size_t i, count, len; + ssize_t inc; + + data = scm_vector_elements (v, &handle, &len, &inc); + for (i = (len - 1) * inc, count = 0; + count < len; + i -= inc, count++) + res = scm_cons (data[i], res); + + scm_array_handle_release (&handle); return res; } #undef FUNC_NAME @@ -251,23 +386,27 @@ SCM_DEFINE (scm_vector_fill_x, "vector-fill!", 2, 0, 0, "returned by @code{vector-fill!} is unspecified.") #define FUNC_NAME s_scm_vector_fill_x { - register long i; - register SCM *data; - SCM_VALIDATE_VECTOR (1, v); - data = SCM_VELTS (v); - for(i = SCM_VECTOR_LENGTH (v) - 1; i >= 0; i--) + scm_t_array_handle handle; + SCM *data; + size_t i, len; + ssize_t inc; + + data = scm_vector_writable_elements (v, &handle, &len, &inc); + for (i = 0; i < len; i += inc) data[i] = fill; + scm_array_handle_release (&handle); return SCM_UNSPECIFIED; } #undef FUNC_NAME SCM -scm_vector_equal_p(SCM x, SCM y) +scm_i_vector_equal_p (SCM x, SCM y) { long i; - for(i = SCM_VECTOR_LENGTH (x) - 1; i >= 0; i--) - if (SCM_FALSEP (scm_equal_p (SCM_VELTS (x)[i], SCM_VELTS (y)[i]))) + for (i = SCM_I_VECTOR_LENGTH (x) - 1; i >= 0; i--) + if (scm_is_false (scm_equal_p (SCM_I_VECTOR_ELTS (x)[i], + SCM_I_VECTOR_ELTS (y)[i]))) return SCM_BOOL_F; return SCM_BOOL_T; } @@ -284,20 +423,31 @@ SCM_DEFINE (scm_vector_move_left_x, "vector-move-left!", 5, 0, 0, "@var{start1} is greater than @var{start2}.") #define FUNC_NAME s_scm_vector_move_left_x { - long i; - long j; - long e; + scm_t_array_handle handle1, handle2; + const SCM *elts1; + SCM *elts2; + size_t len1, len2; + ssize_t inc1, inc2; + size_t i, j, e; + + elts1 = scm_vector_elements (vec1, &handle1, &len1, &inc1); + elts2 = scm_vector_writable_elements (vec2, &handle2, &len2, &inc2); + + i = scm_to_unsigned_integer (start1, 0, len1); + e = scm_to_unsigned_integer (end1, i, len1); + SCM_ASSERT_RANGE (SCM_ARG3, end1, (e-i) <= len2); + j = scm_to_unsigned_integer (start2, 0, len2); + SCM_ASSERT_RANGE (SCM_ARG5, start2, j <= len2 - (e - i)); - SCM_VALIDATE_VECTOR (1,vec1); - SCM_VALIDATE_INUM_COPY (2,start1,i); - SCM_VALIDATE_INUM_COPY (3,end1,e); - SCM_VALIDATE_VECTOR (4,vec2); - SCM_VALIDATE_INUM_COPY (5,start2,j); - SCM_ASSERT_RANGE (2, start1, i <= SCM_VECTOR_LENGTH (vec1) && i >= 0); - SCM_ASSERT_RANGE (5, start2, j <= SCM_VECTOR_LENGTH (vec2) && j >= 0); - SCM_ASSERT_RANGE (3, end1, e <= SCM_VECTOR_LENGTH (vec1) && e >= 0); - SCM_ASSERT_RANGE (5, start2, e-i+j <= SCM_VECTOR_LENGTH (vec2)); - while (i= 0); - SCM_ASSERT_RANGE (5, start2, j <= SCM_VECTOR_LENGTH (vec2) && j >= 0); - SCM_ASSERT_RANGE (3, end1, e <= SCM_VECTOR_LENGTH (vec1) && e >= 0); - j = e - i + j; - SCM_ASSERT_RANGE (5, start2, j <= SCM_VECTOR_LENGTH (vec2)); + scm_t_array_handle handle1, handle2; + const SCM *elts1; + SCM *elts2; + size_t len1, len2; + ssize_t inc1, inc2; + size_t i, j, e; + + elts1 = scm_vector_elements (vec1, &handle1, &len1, &inc1); + elts2 = scm_vector_writable_elements (vec2, &handle2, &len2, &inc2); + + i = scm_to_unsigned_integer (start1, 0, len1); + e = scm_to_unsigned_integer (end1, i, len1); + SCM_ASSERT_RANGE (SCM_ARG3, end1, (e-i) <= len2); + j = scm_to_unsigned_integer (start2, 0, len2); + SCM_ASSERT_RANGE (SCM_ARG5, start2, j <= len2 - (e - i)); + + j += (e - i); + + i *= inc1; + e *= inc1; + j *= inc2; while (i < e) - SCM_VELTS (vec2)[--j] = SCM_VELTS (vec1)[--e]; + { + e -= inc1; + j -= inc2; + elts2[j] = elts1[e]; + } + + scm_array_handle_release (&handle2); + scm_array_handle_release (&handle1); + return SCM_UNSPECIFIED; } #undef FUNC_NAME + +static SCM +vector_handle_ref (scm_t_array_handle *h, size_t idx) +{ + if (idx > h->dims[0].ubnd) + scm_out_of_range ("vector-handle-ref", scm_from_size_t (idx)); + return ((SCM*)h->elements)[idx]; +} + +static void +vector_handle_set (scm_t_array_handle *h, size_t idx, SCM val) +{ + if (idx > h->dims[0].ubnd) + scm_out_of_range ("vector-handle-set!", scm_from_size_t (idx)); + ((SCM*)h->writable_elements)[idx] = val; +} + +static void +vector_get_handle (SCM v, scm_t_array_handle *h) +{ + h->array = v; + h->ndims = 1; + h->dims = &h->dim0; + h->dim0.lbnd = 0; + h->dim0.ubnd = SCM_I_VECTOR_LENGTH (v) - 1; + h->dim0.inc = 1; + h->element_type = SCM_ARRAY_ELEMENT_TYPE_SCM; + h->elements = h->writable_elements = SCM_I_VECTOR_WELTS (v); +} + +/* the & ~2 allows catching scm_tc7_wvect as well. needs changing if you change + tags.h. */ +SCM_ARRAY_IMPLEMENTATION (scm_tc7_vector, 0x7f & ~2, + vector_handle_ref, vector_handle_set, + vector_get_handle) +SCM_VECTOR_IMPLEMENTATION (SCM_ARRAY_ELEMENT_TYPE_SCM, scm_make_vector) void scm_init_vectors () { - scm_nullvect = scm_c_make_vector (0, SCM_UNDEFINED); - -#ifndef SCM_MAGIC_SNARFER #include "libguile/vectors.x" -#endif }