libguile/vectors.c

   1 /* Copyright (C) 1995,1996,1998,1999,2000,2001, 2006, 2008, 2009, 2010, 2011 Free Software Foundation, Inc.
   2  *
   3  * This library is free software; you can redistribute it and/or
   4  * modify it under the terms of the GNU Lesser General Public License
   5  * as published by the Free Software Foundation; either version 3 of
   6  * the License, or (at your option) any later version.
   7  *
   8  * This library is distributed in the hope that it will be useful, but
   9  * WITHOUT ANY WARRANTY; without even the implied warranty of
  10  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  11  * Lesser General Public License for more details.
  12  *
  13  * You should have received a copy of the GNU Lesser General Public
  14  * License along with this library; if not, write to the Free Software
  15  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
  16  * 02110-1301 USA
  17  */
  18
  19
  20 \f
  21 #ifdef HAVE_CONFIG_H
  22 # include <config.h>
  23 #endif
  24
  25 #include "libguile/_scm.h"
  26 #include "libguile/eq.h"
  27 #include "libguile/root.h"
  28 #include "libguile/strings.h"
  29
  30 #include "libguile/validate.h"
  31 #include "libguile/vectors.h"
  32 #include "libguile/arrays.h" /* Hit me with the ugly stick */
  33 #include "libguile/generalized-vectors.h"
  34 #include "libguile/strings.h"
  35 #include "libguile/srfi-13.h"
  36 #include "libguile/dynwind.h"
  37 #include "libguile/deprecation.h"
  38
  39 #include "libguile/bdw-gc.h"
  40
  41
  42 \f
  43
  44 #define VECTOR_MAX_LENGTH (SCM_T_BITS_MAX >> 8)
  45
  46 int
  47 scm_is_vector (SCM obj)
  48 {
  49   if (SCM_I_IS_VECTOR (obj))
  50     return 1;
  51   if  (SCM_I_ARRAYP (obj) && SCM_I_ARRAY_NDIM (obj) == 1)
  52     {
  53       SCM v = SCM_I_ARRAY_V (obj);
  54       return SCM_I_IS_VECTOR (v);
  55     }
  56   return 0;
  57 }
  58
  59 int
  60 scm_is_simple_vector (SCM obj)
  61 {
  62   return SCM_I_IS_VECTOR (obj);
  63 }
  64
  65 const SCM *
  66 scm_vector_elements (SCM vec, scm_t_array_handle *h,
  67                      size_t *lenp, ssize_t *incp)
  68 {
  69   if (SCM_I_WVECTP (vec))
  70     scm_wrong_type_arg_msg (NULL, 0, vec, "non-weak vector");
  71
  72   scm_generalized_vector_get_handle (vec, h);
  73   if (lenp)
  74     {
  75       scm_t_array_dim *dim = scm_array_handle_dims (h);
  76       *lenp = dim->ubnd - dim->lbnd + 1;
  77       *incp = dim->inc;
  78     }
  79   return scm_array_handle_elements (h);
  80 }
  81
  82 SCM *
  83 scm_vector_writable_elements (SCM vec, scm_t_array_handle *h,
  84                               size_t *lenp, ssize_t *incp)
  85 {
  86   if (SCM_I_WVECTP (vec))
  87     scm_wrong_type_arg_msg (NULL, 0, vec, "non-weak vector");
  88
  89   scm_generalized_vector_get_handle (vec, h);
  90   if (lenp)
  91     {
  92       scm_t_array_dim *dim = scm_array_handle_dims (h);
  93       *lenp = dim->ubnd - dim->lbnd + 1;
  94       *incp = dim->inc;
  95     }
  96   return scm_array_handle_writable_elements (h);
  97 }
  98
  99 SCM_DEFINE (scm_vector_p, "vector?", 1, 0, 0,
 100             (SCM obj),
 101             "Return @code{#t} if @var{obj} is a vector, otherwise return\n"
 102             "@code{#f}.")
 103 #define FUNC_NAME s_scm_vector_p
 104 {
 105   return scm_from_bool (scm_is_vector (obj));
 106 }
 107 #undef FUNC_NAME
 108
 109 SCM_GPROC (s_vector_length, "vector-length", 1, 0, 0, scm_vector_length, g_vector_length);
 110 /* Returns the number of elements in @var{vector} as an exact integer.  */
 111 SCM
 112 scm_vector_length (SCM v)
 113 {
 114   if (SCM_I_IS_VECTOR (v))
 115     return scm_from_size_t (SCM_I_VECTOR_LENGTH (v));
 116   else if (SCM_I_ARRAYP (v) && SCM_I_ARRAY_NDIM (v) == 1)
 117     {
 118       scm_t_array_dim *dim = SCM_I_ARRAY_DIMS (v);
 119       return scm_from_size_t (dim->ubnd - dim->lbnd + 1);
 120     }
 121   else
 122     return scm_wta_dispatch_1 (g_vector_length, v, 1, "vector-length");
 123 }
 124
 125 size_t
 126 scm_c_vector_length (SCM v)
 127 {
 128   if (SCM_I_IS_VECTOR (v))
 129     return SCM_I_VECTOR_LENGTH (v);
 130   else
 131     return scm_to_size_t (scm_vector_length (v));
 132 }
 133
 134 SCM_REGISTER_PROC (s_list_to_vector, "list->vector", 1, 0, 0, scm_vector);
 135 /*
 136             "Return a newly created vector initialized to the elements of"
 137             "the list @var{list}.\n\n"
 138             "@lisp\n"
 139             "(vector->list '#(dah dah didah)) @result{} (dah dah didah)\n"
 140             "(list->vector '(dididit dah)) @result{}   #(dididit dah)\n"
 141             "@end lisp")
 142 */
 143 SCM_DEFINE (scm_vector, "vector", 0, 0, 1,
 144             (SCM l),
 145             "@deffnx {Scheme Procedure} list->vector l\n"
 146             "Return a newly allocated vector composed of the\n"
 147             "given arguments.  Analogous to @code{list}.\n"
 148             "\n"
 149             "@lisp\n"
 150             "(vector 'a 'b 'c) @result{} #(a b c)\n"
 151             "@end lisp")
 152 #define FUNC_NAME s_scm_vector
 153 {
 154   SCM res;
 155   SCM *data;
 156   long i, len;
 157   scm_t_array_handle handle;
 158
 159   SCM_VALIDATE_LIST_COPYLEN (1, l, len);
 160
 161   res = scm_c_make_vector (len, SCM_UNSPECIFIED);
 162   data = scm_vector_writable_elements (res, &handle, NULL, NULL);
 163   i = 0;
 164   while (scm_is_pair (l) && i < len)
 165     {
 166       data[i] = SCM_CAR (l);
 167       l = SCM_CDR (l);
 168       i += 1;
 169     }
 170
 171   scm_array_handle_release (&handle);
 172
 173   return res;
 174 }
 175 #undef FUNC_NAME
 176
 177 SCM_GPROC (s_vector_ref, "vector-ref", 2, 0, 0, scm_vector_ref, g_vector_ref);
 178
 179 /*
 180            "@var{k} must be a valid index of @var{vector}.\n"
 181            "@samp{Vector-ref} returns the contents of element @var{k} of\n"
 182            "@var{vector}.\n\n"
 183            "@lisp\n"
 184            "(vector-ref '#(1 1 2 3 5 8 13 21) 5) @result{} 8\n"
 185            "(vector-ref '#(1 1 2 3 5 8 13 21)\n"
 186            "    (let ((i (round (* 2 (acos -1)))))\n"
 187            "      (if (inexact? i)\n"
 188            "        (inexact->exact i)\n"
 189            "           i))) @result{} 13\n"
 190            "@end lisp"
 191 */
 192
 193 SCM
 194 scm_vector_ref (SCM v, SCM k)
 195 #define FUNC_NAME s_vector_ref
 196 {
 197   return scm_c_vector_ref (v, scm_to_size_t (k));
 198 }
 199 #undef FUNC_NAME
 200
 201 SCM
 202 scm_c_vector_ref (SCM v, size_t k)
 203 {
 204   if (SCM_I_IS_NONWEAK_VECTOR (v))
 205     {
 206       if (k >= SCM_I_VECTOR_LENGTH (v))
 207         scm_out_of_range (NULL, scm_from_size_t (k));
 208       return SCM_SIMPLE_VECTOR_REF (v, k);
 209     }
 210   else if (SCM_I_WVECTP (v))
 211     return scm_c_weak_vector_ref (v, k);
 212   else if (SCM_I_ARRAYP (v) && SCM_I_ARRAY_NDIM (v) == 1)
 213     {
 214       scm_t_array_dim *dim = SCM_I_ARRAY_DIMS (v);
 215       SCM vv = SCM_I_ARRAY_V (v);
 216
 217       k = SCM_I_ARRAY_BASE (v) + k*dim->inc;
 218       if (k >= dim->ubnd - dim->lbnd + 1)
 219         scm_out_of_range (NULL, scm_from_size_t (k));
 220
 221       if (SCM_I_IS_NONWEAK_VECTOR (vv))
 222         return SCM_SIMPLE_VECTOR_REF (vv, k);
 223       else if (SCM_I_WVECTP (vv))
 224         return scm_c_weak_vector_ref (vv, k);
 225       else
 226         scm_wrong_type_arg_msg (NULL, 0, v, "non-uniform vector");
 227     }
 228   else
 229     return scm_wta_dispatch_2 (g_vector_ref, v, scm_from_size_t (k), 2,
 230                                "vector-ref");
 231 }
 232
 233 SCM_GPROC (s_vector_set_x, "vector-set!", 3, 0, 0, scm_vector_set_x, g_vector_set_x);
 234
 235 /* "@var{k} must be a valid index of @var{vector}.\n"
 236    "@code{Vector-set!} stores @var{obj} in element @var{k} of @var{vector}.\n"
 237    "The value returned by @samp{vector-set!} is unspecified.\n"
 238    "@lisp\n"
 239    "(let ((vec (vector 0 '(2 2 2 2) "Anna")))\n"
 240    "  (vector-set! vec 1 '("Sue" "Sue"))\n"
 241    "  vec) @result{}  #(0 ("Sue" "Sue") "Anna")\n"
 242    "(vector-set! '#(0 1 2) 1 "doe") @result{} @emph{error} ; constant vector\n"
 243    "@end lisp"
 244 */
 245
 246 SCM
 247 scm_vector_set_x (SCM v, SCM k, SCM obj)
 248 #define FUNC_NAME s_vector_set_x
 249 {
 250   scm_c_vector_set_x (v, scm_to_size_t (k), obj);
 251   return SCM_UNSPECIFIED;
 252 }
 253 #undef FUNC_NAME
 254
 255 void
 256 scm_c_vector_set_x (SCM v, size_t k, SCM obj)
 257 {
 258   if (SCM_I_IS_NONWEAK_VECTOR (v))
 259     {
 260       if (k >= SCM_I_VECTOR_LENGTH (v))
 261         scm_out_of_range (NULL, scm_from_size_t (k));
 262       SCM_SIMPLE_VECTOR_SET (v, k, obj);
 263     }
 264   else if (SCM_I_WVECTP (v))
 265     scm_c_weak_vector_set_x (v, k, obj);
 266   else if (SCM_I_ARRAYP (v) && SCM_I_ARRAY_NDIM (v) == 1)
 267     {
 268       scm_t_array_dim *dim = SCM_I_ARRAY_DIMS (v);
 269       SCM vv = SCM_I_ARRAY_V (v);
 270
 271       k = SCM_I_ARRAY_BASE (v) + k*dim->inc;
 272       if (k >= dim->ubnd - dim->lbnd + 1)
 273         scm_out_of_range (NULL, scm_from_size_t (k));
 274
 275       if (SCM_I_IS_NONWEAK_VECTOR (vv))
 276         SCM_SIMPLE_VECTOR_SET (vv, k, obj);
 277       else if (SCM_I_WVECTP (vv))
 278         scm_c_weak_vector_set_x (vv, k, obj);
 279       else
 280         scm_wrong_type_arg_msg (NULL, 0, v, "non-uniform vector");
 281     }
 282   else
 283     {
 284       if (SCM_UNPACK (g_vector_set_x))
 285         scm_wta_dispatch_n (g_vector_set_x,
 286                             scm_list_3 (v, scm_from_size_t (k), obj),
 287                             0,
 288                             "vector-set!");
 289       else
 290         scm_wrong_type_arg_msg (NULL, 0, v, "vector");
 291     }
 292 }
 293
 294 SCM_DEFINE (scm_make_vector, "make-vector", 1, 1, 0,
 295             (SCM k, SCM fill),
 296             "Return a newly allocated vector of @var{k} elements.  If a\n"
 297             "second argument is given, then each position is initialized to\n"
 298             "@var{fill}.  Otherwise the initial contents of each position is\n"
 299             "unspecified.")
 300 #define FUNC_NAME s_scm_make_vector
 301 {
 302   size_t l = scm_to_unsigned_integer (k, 0, VECTOR_MAX_LENGTH);
 303
 304   if (SCM_UNBNDP (fill))
 305     fill = SCM_UNSPECIFIED;
 306
 307   return scm_c_make_vector (l, fill);
 308 }
 309 #undef FUNC_NAME
 310
 311
 312 SCM
 313 scm_c_make_vector (size_t k, SCM fill)
 314 #define FUNC_NAME s_scm_make_vector
 315 {
 316   SCM vector;
 317   unsigned long int j;
 318
 319   SCM_ASSERT_RANGE (1, scm_from_size_t (k), k <= VECTOR_MAX_LENGTH);
 320
 321   vector = scm_words ((k << 8) | scm_tc7_vector, k + 1);
 322
 323   for (j = 0; j < k; ++j)
 324     SCM_SIMPLE_VECTOR_SET (vector, j, fill);
 325
 326   return vector;
 327 }
 328 #undef FUNC_NAME
 329
 330 SCM_DEFINE (scm_vector_copy, "vector-copy", 1, 0, 0,
 331             (SCM vec),
 332             "Return a copy of @var{vec}.")
 333 #define FUNC_NAME s_scm_vector_copy
 334 {
 335   scm_t_array_handle handle;
 336   size_t i, len;
 337   ssize_t inc;
 338   const SCM *src;
 339   SCM result, *dst;
 340
 341   src = scm_vector_elements (vec, &handle, &len, &inc);
 342
 343   result = scm_c_make_vector (len, SCM_UNDEFINED);
 344   dst = SCM_I_VECTOR_WELTS (result);
 345   for (i = 0; i < len; i++, src += inc)
 346     dst[i] = *src;
 347
 348   scm_array_handle_release (&handle);
 349
 350   return result;
 351 }
 352 #undef FUNC_NAME
 353
 354 \f
 355 SCM_DEFINE (scm_vector_to_list, "vector->list", 1, 0, 0,
 356             (SCM v),
 357             "Return a newly allocated list composed of the elements of @var{v}.\n"
 358             "\n"
 359             "@lisp\n"
 360             "(vector->list '#(dah dah didah)) @result{}  (dah dah didah)\n"
 361             "(list->vector '(dididit dah)) @result{}  #(dididit dah)\n"
 362             "@end lisp")
 363 #define FUNC_NAME s_scm_vector_to_list
 364 {
 365   SCM res = SCM_EOL;
 366   const SCM *data;
 367   scm_t_array_handle handle;
 368   size_t i, count, len;
 369   ssize_t inc;
 370
 371   data = scm_vector_elements (v, &handle, &len, &inc);
 372   for (i = (len - 1) * inc, count = 0;
 373        count < len;
 374        i -= inc, count++)
 375     res = scm_cons (data[i], res);
 376
 377   scm_array_handle_release (&handle);
 378   return res;
 379 }
 380 #undef FUNC_NAME
 381
 382
 383 SCM_DEFINE (scm_vector_fill_x, "vector-fill!", 2, 0, 0,
 384             (SCM v, SCM fill),
 385             "Store @var{fill} in every position of @var{vector}.  The value\n"
 386             "returned by @code{vector-fill!} is unspecified.")
 387 #define FUNC_NAME s_scm_vector_fill_x
 388 {
 389   scm_t_array_handle handle;
 390   SCM *data;
 391   size_t i, len;
 392   ssize_t inc;
 393
 394   data = scm_vector_writable_elements (v, &handle, &len, &inc);
 395   for (i = 0; i < len; i += inc)
 396     data[i] = fill;
 397   scm_array_handle_release (&handle);
 398   return SCM_UNSPECIFIED;
 399 }
 400 #undef FUNC_NAME
 401
 402
 403 SCM
 404 scm_i_vector_equal_p (SCM x, SCM y)
 405 {
 406   long i;
 407   for (i = SCM_I_VECTOR_LENGTH (x) - 1; i >= 0; i--)
 408     if (scm_is_false (scm_equal_p (SCM_I_VECTOR_ELTS (x)[i],
 409                                    SCM_I_VECTOR_ELTS (y)[i])))
 410       return SCM_BOOL_F;
 411   return SCM_BOOL_T;
 412 }
 413
 414
 415 SCM_DEFINE (scm_vector_move_left_x, "vector-move-left!", 5, 0, 0,
 416             (SCM vec1, SCM start1, SCM end1, SCM vec2, SCM start2),
 417             "Copy elements from @var{vec1}, positions @var{start1} to @var{end1},\n"
 418             "to @var{vec2} starting at position @var{start2}.  @var{start1} and\n"
 419             "@var{start2} are inclusive indices; @var{end1} is exclusive.\n\n"
 420             "@code{vector-move-left!} copies elements in leftmost order.\n"
 421             "Therefore, in the case where @var{vec1} and @var{vec2} refer to the\n"
 422             "same vector, @code{vector-move-left!} is usually appropriate when\n"
 423             "@var{start1} is greater than @var{start2}.")
 424 #define FUNC_NAME s_scm_vector_move_left_x
 425 {
 426   scm_t_array_handle handle1, handle2;
 427   const SCM *elts1;
 428   SCM *elts2;
 429   size_t len1, len2;
 430   ssize_t inc1, inc2;
 431   size_t i, j, e;
 432
 433   elts1 = scm_vector_elements (vec1, &handle1, &len1, &inc1);
 434   elts2 = scm_vector_writable_elements (vec2, &handle2, &len2, &inc2);
 435
 436   i = scm_to_unsigned_integer (start1, 0, len1);
 437   e = scm_to_unsigned_integer (end1, i, len1);
 438   SCM_ASSERT_RANGE (SCM_ARG3, end1, (e-i) <= len2);
 439   j = scm_to_unsigned_integer (start2, 0, len2);
 440   SCM_ASSERT_RANGE (SCM_ARG5, start2, j <= len2 - (e - i));
 441
 442   i *= inc1;
 443   e *= inc1;
 444   j *= inc2;
 445   for (; i < e; i += inc1, j += inc2)
 446     elts2[j] = elts1[i];
 447
 448   scm_array_handle_release (&handle2);
 449   scm_array_handle_release (&handle1);
 450
 451   return SCM_UNSPECIFIED;
 452 }
 453 #undef FUNC_NAME
 454
 455 SCM_DEFINE (scm_vector_move_right_x, "vector-move-right!", 5, 0, 0,
 456             (SCM vec1, SCM start1, SCM end1, SCM vec2, SCM start2),
 457             "Copy elements from @var{vec1}, positions @var{start1} to @var{end1},\n"
 458             "to @var{vec2} starting at position @var{start2}.  @var{start1} and\n"
 459             "@var{start2} are inclusive indices; @var{end1} is exclusive.\n\n"
 460             "@code{vector-move-right!} copies elements in rightmost order.\n"
 461             "Therefore, in the case where @var{vec1} and @var{vec2} refer to the\n"
 462             "same vector, @code{vector-move-right!} is usually appropriate when\n"
 463             "@var{start1} is less than @var{start2}.")
 464 #define FUNC_NAME s_scm_vector_move_right_x
 465 {
 466   scm_t_array_handle handle1, handle2;
 467   const SCM *elts1;
 468   SCM *elts2;
 469   size_t len1, len2;
 470   ssize_t inc1, inc2;
 471   size_t i, j, e;
 472
 473   elts1 = scm_vector_elements (vec1, &handle1, &len1, &inc1);
 474   elts2 = scm_vector_writable_elements (vec2, &handle2, &len2, &inc2);
 475
 476   i = scm_to_unsigned_integer (start1, 0, len1);
 477   e = scm_to_unsigned_integer (end1, i, len1);
 478   SCM_ASSERT_RANGE (SCM_ARG3, end1, (e-i) <= len2);
 479   j = scm_to_unsigned_integer (start2, 0, len2);
 480   SCM_ASSERT_RANGE (SCM_ARG5, start2, j <= len2 - (e - i));
 481
 482   j += (e - i);
 483
 484   i *= inc1;
 485   e *= inc1;
 486   j *= inc2;
 487   while (i < e)
 488     {
 489       e -= inc1;
 490       j -= inc2;
 491       elts2[j] = elts1[e];
 492     }
 493
 494   scm_array_handle_release (&handle2);
 495   scm_array_handle_release (&handle1);
 496
 497   return SCM_UNSPECIFIED;
 498 }
 499 #undef FUNC_NAME
 500
 501 \f
 502 static SCM
 503 vector_handle_ref (scm_t_array_handle *h, size_t idx)
 504 {
 505   if (idx > h->dims[0].ubnd)
 506     scm_out_of_range ("vector-handle-ref", scm_from_size_t (idx));
 507   return ((SCM*)h->elements)[idx];
 508 }
 509
 510 static void
 511 vector_handle_set (scm_t_array_handle *h, size_t idx, SCM val)
 512 {
 513   if (idx > h->dims[0].ubnd)
 514     scm_out_of_range ("vector-handle-set!", scm_from_size_t (idx));
 515   ((SCM*)h->writable_elements)[idx] = val;
 516 }
 517
 518 static void
 519 vector_get_handle (SCM v, scm_t_array_handle *h)
 520 {
 521   h->array = v;
 522   h->ndims = 1;
 523   h->dims = &h->dim0;
 524   h->dim0.lbnd = 0;
 525   h->dim0.ubnd = SCM_I_VECTOR_LENGTH (v) - 1;
 526   h->dim0.inc = 1;
 527   h->element_type = SCM_ARRAY_ELEMENT_TYPE_SCM;
 528   h->elements = h->writable_elements = SCM_I_VECTOR_WELTS (v);
 529 }
 530
 531 /* the & ~2 allows catching scm_tc7_wvect as well. needs changing if you change
 532    tags.h. */
 533 SCM_ARRAY_IMPLEMENTATION (scm_tc7_vector, 0x7f & ~2,
 534                           vector_handle_ref, vector_handle_set,
 535                           vector_get_handle)
 536 SCM_VECTOR_IMPLEMENTATION (SCM_ARRAY_ELEMENT_TYPE_SCM, scm_make_vector)
 537
 538
 539 void
 540 scm_init_vectors ()
 541 {
 542 #include "libguile/vectors.x"
 543 }
 544
 545
 546 /*
 547   Local Variables:
 548   c-file-style: "gnu"
 549   End:
 550 */