libguile/vectors.c

   1 /* Copyright (C) 1995,1996,1998,1999,2000,2001, 2006, 2008, 2009, 2010,
   2  *   2011, 2012, 2014 Free Software Foundation, Inc.
   3  *
   4  * This library is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU Lesser General Public License
   6  * as published by the Free Software Foundation; either version 3 of
   7  * the License, or (at your option) any later version.
   8  *
   9  * This library is distributed in the hope that it will be useful, but
  10  * WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12  * Lesser General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU Lesser General Public
  15  * License along with this library; if not, write to the Free Software
  16  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
  17  * 02110-1301 USA
  18  */
  19
  20
  21 \f
  22 #ifdef HAVE_CONFIG_H
  23 # include <config.h>
  24 #endif
  25
  26 #include "libguile/_scm.h"
  27 #include "libguile/eq.h"
  28 #include "libguile/root.h"
  29 #include "libguile/strings.h"
  30
  31 #include "libguile/validate.h"
  32 #include "libguile/vectors.h"
  33 #include "libguile/arrays.h" /* Hit me with the ugly stick */
  34 #include "libguile/generalized-vectors.h"
  35 #include "libguile/strings.h"
  36 #include "libguile/srfi-13.h"
  37 #include "libguile/dynwind.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_NONWEAK_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_NONWEAK_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_ARRAYP (v) && SCM_I_ARRAY_NDIM (v) == 1)
 211     {
 212       scm_t_array_dim *dim = SCM_I_ARRAY_DIMS (v);
 213       SCM vv = SCM_I_ARRAY_V (v);
 214
 215       k = SCM_I_ARRAY_BASE (v) + k*dim->inc;
 216       if (k >= dim->ubnd - dim->lbnd + 1)
 217         scm_out_of_range (NULL, scm_from_size_t (k));
 218
 219       if (SCM_I_IS_NONWEAK_VECTOR (vv))
 220         return SCM_SIMPLE_VECTOR_REF (vv, k);
 221       else
 222         scm_wrong_type_arg_msg (NULL, 0, v, "non-uniform vector");
 223     }
 224   else
 225     return scm_wta_dispatch_2 (g_vector_ref, v, scm_from_size_t (k), 2,
 226                                "vector-ref");
 227 }
 228
 229 SCM_GPROC (s_vector_set_x, "vector-set!", 3, 0, 0, scm_vector_set_x, g_vector_set_x);
 230
 231 /* "@var{k} must be a valid index of @var{vector}.\n"
 232    "@code{Vector-set!} stores @var{obj} in element @var{k} of @var{vector}.\n"
 233    "The value returned by @samp{vector-set!} is unspecified.\n"
 234    "@lisp\n"
 235    "(let ((vec (vector 0 '(2 2 2 2) "Anna")))\n"
 236    "  (vector-set! vec 1 '("Sue" "Sue"))\n"
 237    "  vec) @result{}  #(0 ("Sue" "Sue") "Anna")\n"
 238    "(vector-set! '#(0 1 2) 1 "doe") @result{} @emph{error} ; constant vector\n"
 239    "@end lisp"
 240 */
 241
 242 SCM
 243 scm_vector_set_x (SCM v, SCM k, SCM obj)
 244 #define FUNC_NAME s_vector_set_x
 245 {
 246   scm_c_vector_set_x (v, scm_to_size_t (k), obj);
 247   return SCM_UNSPECIFIED;
 248 }
 249 #undef FUNC_NAME
 250
 251 void
 252 scm_c_vector_set_x (SCM v, size_t k, SCM obj)
 253 {
 254   if (SCM_I_IS_NONWEAK_VECTOR (v))
 255     {
 256       if (k >= SCM_I_VECTOR_LENGTH (v))
 257         scm_out_of_range (NULL, scm_from_size_t (k));
 258       SCM_SIMPLE_VECTOR_SET (v, k, obj);
 259     }
 260   else if (SCM_I_ARRAYP (v) && SCM_I_ARRAY_NDIM (v) == 1)
 261     {
 262       scm_t_array_dim *dim = SCM_I_ARRAY_DIMS (v);
 263       SCM vv = SCM_I_ARRAY_V (v);
 264
 265       k = SCM_I_ARRAY_BASE (v) + k*dim->inc;
 266       if (k >= dim->ubnd - dim->lbnd + 1)
 267         scm_out_of_range (NULL, scm_from_size_t (k));
 268
 269       if (SCM_I_IS_NONWEAK_VECTOR (vv))
 270         SCM_SIMPLE_VECTOR_SET (vv, k, obj);
 271       else
 272         scm_wrong_type_arg_msg (NULL, 0, v, "non-uniform vector");
 273     }
 274   else
 275     {
 276       if (SCM_UNPACK (g_vector_set_x))
 277         scm_wta_dispatch_n (g_vector_set_x,
 278                             scm_list_3 (v, scm_from_size_t (k), obj),
 279                             0,
 280                             "vector-set!");
 281       else
 282         scm_wrong_type_arg_msg (NULL, 0, v, "vector");
 283     }
 284 }
 285
 286 SCM_DEFINE (scm_make_vector, "make-vector", 1, 1, 0,
 287             (SCM k, SCM fill),
 288             "Return a newly allocated vector of @var{k} elements.  If a\n"
 289             "second argument is given, then each position is initialized to\n"
 290             "@var{fill}.  Otherwise the initial contents of each position is\n"
 291             "unspecified.")
 292 #define FUNC_NAME s_scm_make_vector
 293 {
 294   size_t l = scm_to_unsigned_integer (k, 0, VECTOR_MAX_LENGTH);
 295
 296   if (SCM_UNBNDP (fill))
 297     fill = SCM_UNSPECIFIED;
 298
 299   return scm_c_make_vector (l, fill);
 300 }
 301 #undef FUNC_NAME
 302
 303
 304 SCM
 305 scm_c_make_vector (size_t k, SCM fill)
 306 #define FUNC_NAME s_scm_make_vector
 307 {
 308   SCM vector;
 309   unsigned long int j;
 310
 311   SCM_ASSERT_RANGE (1, scm_from_size_t (k), k <= VECTOR_MAX_LENGTH);
 312
 313   vector = scm_words ((k << 8) | scm_tc7_vector, k + 1);
 314
 315   for (j = 0; j < k; ++j)
 316     SCM_SIMPLE_VECTOR_SET (vector, j, fill);
 317
 318   return vector;
 319 }
 320 #undef FUNC_NAME
 321
 322 SCM_DEFINE (scm_vector_copy, "vector-copy", 1, 0, 0,
 323             (SCM vec),
 324             "Return a copy of @var{vec}.")
 325 #define FUNC_NAME s_scm_vector_copy
 326 {
 327   scm_t_array_handle handle;
 328   size_t i, len;
 329   ssize_t inc;
 330   const SCM *src;
 331   SCM result, *dst;
 332
 333   src = scm_vector_elements (vec, &handle, &len, &inc);
 334
 335   result = scm_c_make_vector (len, SCM_UNDEFINED);
 336   dst = SCM_I_VECTOR_WELTS (result);
 337   for (i = 0; i < len; i++, src += inc)
 338     dst[i] = *src;
 339
 340   scm_array_handle_release (&handle);
 341
 342   return result;
 343 }
 344 #undef FUNC_NAME
 345
 346 \f
 347 SCM_DEFINE (scm_vector_to_list, "vector->list", 1, 0, 0,
 348             (SCM v),
 349             "Return a newly allocated list composed of the elements of @var{v}.\n"
 350             "\n"
 351             "@lisp\n"
 352             "(vector->list '#(dah dah didah)) @result{}  (dah dah didah)\n"
 353             "(list->vector '(dididit dah)) @result{}  #(dididit dah)\n"
 354             "@end lisp")
 355 #define FUNC_NAME s_scm_vector_to_list
 356 {
 357   SCM res = SCM_EOL;
 358   const SCM *data;
 359   scm_t_array_handle handle;
 360   size_t i, count, len;
 361   ssize_t inc;
 362
 363   data = scm_vector_elements (v, &handle, &len, &inc);
 364   for (i = (len - 1) * inc, count = 0;
 365        count < len;
 366        i -= inc, count++)
 367     res = scm_cons (data[i], res);
 368
 369   scm_array_handle_release (&handle);
 370   return res;
 371 }
 372 #undef FUNC_NAME
 373
 374
 375 SCM_DEFINE (scm_vector_fill_x, "vector-fill!", 2, 0, 0,
 376             (SCM v, SCM fill),
 377             "Store @var{fill} in every position of @var{vector}.  The value\n"
 378             "returned by @code{vector-fill!} is unspecified.")
 379 #define FUNC_NAME s_scm_vector_fill_x
 380 {
 381   scm_t_array_handle handle;
 382   SCM *data;
 383   size_t i, len;
 384   ssize_t inc;
 385
 386   data = scm_vector_writable_elements (v, &handle, &len, &inc);
 387   for (i = 0; i < len; i += inc)
 388     data[i] = fill;
 389   scm_array_handle_release (&handle);
 390   return SCM_UNSPECIFIED;
 391 }
 392 #undef FUNC_NAME
 393
 394
 395 SCM
 396 scm_i_vector_equal_p (SCM x, SCM y)
 397 {
 398   long i;
 399   for (i = SCM_I_VECTOR_LENGTH (x) - 1; i >= 0; i--)
 400     if (scm_is_false (scm_equal_p (SCM_I_VECTOR_ELTS (x)[i],
 401                                    SCM_I_VECTOR_ELTS (y)[i])))
 402       return SCM_BOOL_F;
 403   return SCM_BOOL_T;
 404 }
 405
 406
 407 SCM_DEFINE (scm_vector_move_left_x, "vector-move-left!", 5, 0, 0,
 408             (SCM vec1, SCM start1, SCM end1, SCM vec2, SCM start2),
 409             "Copy elements from @var{vec1}, positions @var{start1} to @var{end1},\n"
 410             "to @var{vec2} starting at position @var{start2}.  @var{start1} and\n"
 411             "@var{start2} are inclusive indices; @var{end1} is exclusive.\n\n"
 412             "@code{vector-move-left!} copies elements in leftmost order.\n"
 413             "Therefore, in the case where @var{vec1} and @var{vec2} refer to the\n"
 414             "same vector, @code{vector-move-left!} is usually appropriate when\n"
 415             "@var{start1} is greater than @var{start2}.")
 416 #define FUNC_NAME s_scm_vector_move_left_x
 417 {
 418   scm_t_array_handle handle1, handle2;
 419   const SCM *elts1;
 420   SCM *elts2;
 421   size_t len1, len2;
 422   ssize_t inc1, inc2;
 423   size_t i, j, e;
 424
 425   elts1 = scm_vector_elements (vec1, &handle1, &len1, &inc1);
 426   elts2 = scm_vector_writable_elements (vec2, &handle2, &len2, &inc2);
 427
 428   i = scm_to_unsigned_integer (start1, 0, len1);
 429   e = scm_to_unsigned_integer (end1, i, len1);
 430   SCM_ASSERT_RANGE (SCM_ARG3, end1, (e-i) <= len2);
 431   j = scm_to_unsigned_integer (start2, 0, len2);
 432   SCM_ASSERT_RANGE (SCM_ARG5, start2, j <= len2 - (e - i));
 433
 434   i *= inc1;
 435   e *= inc1;
 436   j *= inc2;
 437   for (; i < e; i += inc1, j += inc2)
 438     elts2[j] = elts1[i];
 439
 440   scm_array_handle_release (&handle2);
 441   scm_array_handle_release (&handle1);
 442
 443   return SCM_UNSPECIFIED;
 444 }
 445 #undef FUNC_NAME
 446
 447 SCM_DEFINE (scm_vector_move_right_x, "vector-move-right!", 5, 0, 0,
 448             (SCM vec1, SCM start1, SCM end1, SCM vec2, SCM start2),
 449             "Copy elements from @var{vec1}, positions @var{start1} to @var{end1},\n"
 450             "to @var{vec2} starting at position @var{start2}.  @var{start1} and\n"
 451             "@var{start2} are inclusive indices; @var{end1} is exclusive.\n\n"
 452             "@code{vector-move-right!} copies elements in rightmost order.\n"
 453             "Therefore, in the case where @var{vec1} and @var{vec2} refer to the\n"
 454             "same vector, @code{vector-move-right!} is usually appropriate when\n"
 455             "@var{start1} is less than @var{start2}.")
 456 #define FUNC_NAME s_scm_vector_move_right_x
 457 {
 458   scm_t_array_handle handle1, handle2;
 459   const SCM *elts1;
 460   SCM *elts2;
 461   size_t len1, len2;
 462   ssize_t inc1, inc2;
 463   size_t i, j, e;
 464
 465   elts1 = scm_vector_elements (vec1, &handle1, &len1, &inc1);
 466   elts2 = scm_vector_writable_elements (vec2, &handle2, &len2, &inc2);
 467
 468   i = scm_to_unsigned_integer (start1, 0, len1);
 469   e = scm_to_unsigned_integer (end1, i, len1);
 470   SCM_ASSERT_RANGE (SCM_ARG3, end1, (e-i) <= len2);
 471   j = scm_to_unsigned_integer (start2, 0, len2);
 472   SCM_ASSERT_RANGE (SCM_ARG5, start2, j <= len2 - (e - i));
 473
 474   j += (e - i);
 475
 476   i *= inc1;
 477   e *= inc1;
 478   j *= inc2;
 479   while (i < e)
 480     {
 481       e -= inc1;
 482       j -= inc2;
 483       elts2[j] = elts1[e];
 484     }
 485
 486   scm_array_handle_release (&handle2);
 487   scm_array_handle_release (&handle1);
 488
 489   return SCM_UNSPECIFIED;
 490 }
 491 #undef FUNC_NAME
 492
 493 \f
 494 static SCM
 495 vector_handle_ref (scm_t_array_handle *h, size_t idx)
 496 {
 497   if (idx > h->dims[0].ubnd)
 498     scm_out_of_range ("vector-handle-ref", scm_from_size_t (idx));
 499   return ((SCM*)h->elements)[idx];
 500 }
 501
 502 static void
 503 vector_handle_set (scm_t_array_handle *h, size_t idx, SCM val)
 504 {
 505   if (idx > h->dims[0].ubnd)
 506     scm_out_of_range ("vector-handle-set!", scm_from_size_t (idx));
 507   ((SCM*)h->writable_elements)[idx] = val;
 508 }
 509
 510 static void
 511 vector_get_handle (SCM v, scm_t_array_handle *h)
 512 {
 513   h->array = v;
 514   h->ndims = 1;
 515   h->dims = &h->dim0;
 516   h->dim0.lbnd = 0;
 517   h->dim0.ubnd = SCM_I_VECTOR_LENGTH (v) - 1;
 518   h->dim0.inc = 1;
 519   h->element_type = SCM_ARRAY_ELEMENT_TYPE_SCM;
 520   h->elements = h->writable_elements = SCM_I_VECTOR_WELTS (v);
 521 }
 522
 523 /* the & ~2 allows catching scm_tc7_wvect as well. needs changing if you change
 524    tags.h. */
 525 SCM_ARRAY_IMPLEMENTATION (scm_tc7_vector, 0x7f & ~2,
 526                           vector_handle_ref, vector_handle_set,
 527                           vector_get_handle)
 528 SCM_VECTOR_IMPLEMENTATION (SCM_ARRAY_ELEMENT_TYPE_SCM, scm_make_vector)
 529
 530
 531 void
 532 scm_init_vectors ()
 533 {
 534 #include "libguile/vectors.x"
 535 }
 536
 537
 538 /*
 539   Local Variables:
 540   c-file-style: "gnu"
 541   End:
 542 */