From 87d86601022feb7a330fc6344cc85ec65563c1b6 Mon Sep 17 00:00:00 2001 From: Paul Eggert Date: Mon, 18 Nov 2013 10:37:25 -0800 Subject: [PATCH] Always allocate at least one bits_word per bool vector. See Daniel Colascione in: http://lists.gnu.org/archive/html/emacs-devel/2013-11/msg00518.html * alloc.c (make_uninit_bool_vector): Always allocate at least one word. * data.c (bool_vector_binop_driver): Rely on this. Tune. * lisp.h (struct Lisp_Bool_vector): Document this. --- src/ChangeLog | 9 ++++++ src/alloc.c | 21 ++++++------ src/data.c | 88 ++++++++++++++++++++++++++++++++++++--------------- src/lisp.h | 1 + 4 files changed, 84 insertions(+), 35 deletions(-) diff --git a/src/ChangeLog b/src/ChangeLog index a2dfa5bf613..21025c677fc 100644 --- a/src/ChangeLog +++ b/src/ChangeLog @@ -1,3 +1,12 @@ +2013-11-18 Paul Eggert + + Always allocate at least one bits_word per bool vector. + See Daniel Colascione in: + http://lists.gnu.org/archive/html/emacs-devel/2013-11/msg00518.html + * alloc.c (make_uninit_bool_vector): Always allocate at least one word. + * data.c (bool_vector_binop_driver): Rely on this. Tune. + * lisp.h (struct Lisp_Bool_vector): Document this. + 2013-11-18 Eli Zaretskii * insdel.c (invalidate_buffer_caches): New function, consolidated diff --git a/src/alloc.c b/src/alloc.c index f12fdc5c861..7c560fd0f0d 100644 --- a/src/alloc.c +++ b/src/alloc.c @@ -2066,20 +2066,21 @@ Lisp_Object make_uninit_bool_vector (EMACS_INT nbits) { Lisp_Object val; - struct Lisp_Bool_Vector *p; - EMACS_INT word_bytes, needed_elements; - word_bytes = bool_vector_words (nbits) * sizeof (bits_word); - needed_elements = ((bool_header_size - header_size + word_bytes - + word_size - 1) - / word_size); - p = (struct Lisp_Bool_Vector *) allocate_vector (needed_elements); + EMACS_INT words0 = bool_vector_words (nbits); + EMACS_INT words = words0 + !words0; /* Allocate at least one word. */ + EMACS_INT word_bytes = words * sizeof (bits_word); + EMACS_INT needed_elements = ((bool_header_size - header_size + word_bytes + + word_size - 1) + / word_size); + struct Lisp_Bool_Vector *p + = (struct Lisp_Bool_Vector *) allocate_vector (needed_elements); XSETVECTOR (val, p); XSETPVECTYPESIZE (XVECTOR (val), PVEC_BOOL_VECTOR, 0, 0); p->size = nbits; - /* Clear padding at the end. */ - if (nbits) - p->data[bool_vector_words (nbits) - 1] = 0; + /* Clear padding at the end. If NBITS != 0 this initializes more + than it needs to, but that's OK. */ + p->data[words - 1] = 0; return val; } diff --git a/src/data.c b/src/data.c index d0171b5d758..b8b0f248dfa 100644 --- a/src/data.c +++ b/src/data.c @@ -3025,9 +3025,7 @@ bool_vector_binop_driver (Lisp_Object op1, { EMACS_INT nr_bits; bits_word *adata, *bdata, *cdata; - ptrdiff_t i; - bool changed = 0; - bits_word mword; + ptrdiff_t i = 0; ptrdiff_t nr_words; CHECK_BOOL_VECTOR (op1); @@ -3037,45 +3035,82 @@ bool_vector_binop_driver (Lisp_Object op1, if (bool_vector_size (op2) != nr_bits) wrong_length_argument (op1, op2, dest); + nr_words = bool_vector_words (nr_bits); + bdata = bool_vector_data (op1); + cdata = bool_vector_data (op2); + if (NILP (dest)) { dest = make_uninit_bool_vector (nr_bits); - changed = 1; + adata = bool_vector_data (dest); } else { CHECK_BOOL_VECTOR (dest); + adata = bool_vector_data (dest); if (bool_vector_size (dest) != nr_bits) wrong_length_argument (op1, op2, dest); - } - nr_words = bool_vector_words (nr_bits); + switch (op) + { + case bool_vector_exclusive_or: + while (adata[i] == (bdata[i] ^ cdata[i])) + if (! (++i < nr_words)) + return Qnil; + break; - adata = bool_vector_data (dest); - bdata = bool_vector_data (op1); - cdata = bool_vector_data (op2); + case bool_vector_subsetp: + case bool_vector_union: + while (adata[i] == (bdata[i] | cdata[i])) + if (! (++i < nr_words)) + return Qnil; + break; + + case bool_vector_intersection: + while (adata[i] == (bdata[i] & cdata[i])) + if (! (++i < nr_words)) + return Qnil; + break; - for (i = 0; i < nr_words; i++) + case bool_vector_set_difference: + while (adata[i] == (bdata[i] &~ cdata[i])) + if (! (++i < nr_words)) + return Qnil; + break; + } + } + + switch (op) { - if (op == bool_vector_exclusive_or) - mword = bdata[i] ^ cdata[i]; - else if (op == bool_vector_union || op == bool_vector_subsetp) - mword = bdata[i] | cdata[i]; - else if (op == bool_vector_intersection) - mword = bdata[i] & cdata[i]; - else if (op == bool_vector_set_difference) - mword = bdata[i] &~ cdata[i]; - else - abort (); + case bool_vector_exclusive_or: + do + adata[i] = bdata[i] ^ cdata[i]; + while (++i < nr_words); + break; + + case bool_vector_subsetp: + break; + + case bool_vector_union: + do + adata[i] = bdata[i] | cdata[i]; + while (++i < nr_words); + break; - if (! changed) - changed = adata[i] != mword; + case bool_vector_intersection: + do + adata[i] = bdata[i] & cdata[i]; + while (++i < nr_words); + break; - if (op != bool_vector_subsetp) - adata[i] = mword; + case bool_vector_set_difference: + do + adata[i] = bdata[i] &~ cdata[i]; + while (++i < nr_words); + break; } - return changed ? dest : Qnil; + return dest; } /* PRECONDITION must be true. Return VALUE. This odd construction @@ -3314,7 +3349,10 @@ index into the vector. */) mword = bits_word_to_host_endian (adata[pos]); mword ^= twiddle; mword >>= offset; + + /* Do not count the pad bits. */ mword |= (bits_word) 1 << (BITS_PER_BITS_WORD - offset); + count = count_trailing_zero_bits (mword); pos++; if (count + offset < BITS_PER_BITS_WORD) diff --git a/src/lisp.h b/src/lisp.h index a5aec41be38..8521c87e5d7 100644 --- a/src/lisp.h +++ b/src/lisp.h @@ -1213,6 +1213,7 @@ struct Lisp_Bool_Vector /* This is the size in bits. */ EMACS_INT size; /* The actual bits, packed into bytes. + Zeros fill out the last word as needed; there's always at least one word. The bits are in little-endian order in the bytes, and the bytes are in little-endian order in the words. */ bits_word data[FLEXIBLE_ARRAY_MEMBER]; -- 2.39.2