Changeset 208885f7930551213d294117aa06fa7ebb1cf8b1

Show
Ignore:
Timestamp:
05/11/08 12:33:25 (8 months ago)
Author:
krayouva <krayouva@…>
Parents:
d0c804297259976d08303935ebc0332aec812118
Children:
eab9f0d2223000ae286e7126d71ccf9f70b7cdd4
git-committer:
krayouva <krayouva@gmail.com> / 2008-05-10T22:33:25Z-0400
Message:

* Finished refactoring bitvector implementation

Location:
c
Files:
3 modified

Legend:

Unmodified
Added
Removed

  • c/include/bitvector.h

    rd0c804 r208885f  
    374374void frt_bv_capa(FrtBitVector *bv, int capa, int size) 
    375375{ 
    376     int word_size = (size >> 5) + 1; 
    377     FRT_REALLOC_N(bv->bits, frt_u32, capa); 
    378     bv->capa = capa; 
     376    int word_size = FRT_TO_WORD(size); 
     377    if (bv->capa < capa) 
     378    { 
     379        FRT_REALLOC_N(bv->bits, frt_u32, capa); 
     380        bv->capa = capa; 
     381        memset(bv->bits + word_size, (bv->extends_as_ones ? 0xFF : 0), 
     382               sizeof(frt_u32) * (capa - word_size)); 
     383    } 
    379384    bv->size = size; 
    380     memset(bv->bits + word_size, (bv->extends_as_ones ? 0xFF : 0), 
    381            sizeof(frt_u32) * (capa - word_size)); 
    382 } 
    383  
    384 extern FRT_ATTR_ALWAYS_INLINE 
    385 void frt_bv_recapa(FrtBitVector *bv, int new_capa) 
    386 { 
    387     if (bv->capa < new_capa) { 
    388         FRT_REALLOC_N(bv->bits, frt_u32, new_capa); 
    389         memset(bv->bits + bv->capa, (bv->extends_as_ones ? 0xFF : 0), 
    390                sizeof(frt_u32) * (new_capa - bv->capa)); 
    391         bv->capa = new_capa; 
    392     } 
    393 } 
    394  
    395 extern FRT_ATTR_ALWAYS_INLINE 
    396 FrtBitVector *frt_bv_and_i(FrtBitVector *bv, FrtBitVector *bv1, 
    397                            FrtBitVector *bv2) 
    398 { 
    399     int i, size, word_size, capa = 4; 
    400  
    401     bv->extends_as_ones = (bv1->extends_as_ones & bv2->extends_as_ones); 
    402  
    403     if (bv1->extends_as_ones || bv2->extends_as_ones) 
    404          size = frt_max2(bv1->size, bv2->size); 
    405     else size = frt_min2(bv1->size, bv2->size); 
    406  
    407     word_size = (size >> 5) + 1; 
    408     capa = frt_max2(frt_round2(word_size), 4); 
    409  
    410     frt_bv_recapa(bv1, capa); 
    411     frt_bv_recapa(bv2, capa); 
    412     frt_bv_capa(bv, capa, size); 
    413  
    414     for (i = 0; i < word_size; i++) 
    415         bv->bits[i] = bv1->bits[i] & bv2->bits[i]; 
    416  
    417     frt_bv_recount(bv); 
     385} 
     386 
     387#define frt_bv_and_ext(dest, src, extends_as_ones, i, max) do { \ 
     388    if (extends_as_ones)                                        \ 
     389         memcpy(&dest[i], &src[i], sizeof(*dest)*(max - i));    \ 
     390    else memset(&dest[i], 0x00   , sizeof(*dest)*(max - i));    \ 
     391} while(0) 
     392 
     393#define frt_bv_or_ext(dest, src, extends_as_ones, i, max) do { \ 
     394    if (extends_as_ones)                                       \ 
     395         memset(&dest[i], 0xFF   , sizeof(*dest)*(max - i));   \ 
     396    else memcpy(&dest[i], &src[i], sizeof(*dest)*(max - i));   \ 
     397} while(0) 
     398 
     399#define frt_bv_xor_ext(dest, src, extends_as_ones, i, max) do { \ 
     400    frt_u32 n = (extends_as_ones ? 0xffffffff : 0);             \ 
     401    for (; i < max; ++i)                                        \ 
     402        dest[i] = src[i] ^ n;                                   \ 
     403} while(0) 
     404 
     405#define FRT_BV_OP(bv, a, b, op, ext_cb) do {                          \ 
     406    int i;                                                            \ 
     407    int a_wsz = FRT_TO_WORD(a->size);                                 \ 
     408    int b_wsz = FRT_TO_WORD(b->size);                                 \ 
     409    int max_size = frt_max2(a->size, b->size);                        \ 
     410    int min_size = frt_min2(a->size, b->size);                        \ 
     411    int max_word_size = FRT_TO_WORD(max_size);                        \ 
     412    int min_word_size = FRT_TO_WORD(min_size);                        \ 
     413    int capa = frt_max2(frt_round2(max_word_size), 4);                \ 
     414                                                                      \ 
     415    bv->extends_as_ones = (a->extends_as_ones op b->extends_as_ones); \ 
     416    frt_bv_capa(bv, capa, max_size);                                  \ 
     417                                                                      \ 
     418    for (i = 0; i < min_word_size; ++i)                               \ 
     419        bv->bits[i] = a->bits[i] op b->bits[i];                       \ 
     420                                                                      \ 
     421    if (a_wsz != b_wsz) {                                             \ 
     422        frt_u32 *bits = a->bits;                                      \ 
     423        bool extends_as_ones = b->extends_as_ones;                    \ 
     424        if (a_wsz < b_wsz) {                                          \ 
     425            bits = b->bits;                                           \ 
     426            extends_as_ones = a->extends_as_ones;                     \ 
     427        }                                                             \ 
     428        ext_cb(bv->bits, bits, extends_as_ones, i, max_word_size);    \ 
     429    }                                                                 \ 
     430    frt_bv_recount(bv);                                               \ 
     431} while(0) 
     432 
     433extern FRT_ATTR_ALWAYS_INLINE 
     434FrtBitVector *frt_bv_and_i(FrtBitVector *bv, 
     435                           FrtBitVector *a, FrtBitVector *b) 
     436{ 
     437    FRT_BV_OP(bv, a, b, &, frt_bv_and_ext); 
    418438    return bv; 
    419439} 
    … …  
    421441extern FRT_ATTR_ALWAYS_INLINE 
    422442FrtBitVector *frt_bv_or_i(FrtBitVector *bv, 
    423                           FrtBitVector *bv1, FrtBitVector *bv2) 
     443                          FrtBitVector *a, FrtBitVector *b) 
     444{ 
     445    FRT_BV_OP(bv, a, b, |, frt_bv_or_ext); 
     446    return bv; 
     447} 
     448 
     449extern FRT_ATTR_ALWAYS_INLINE 
     450FrtBitVector *frt_bv_xor_i(FrtBitVector *bv, 
     451                           FrtBitVector *a, FrtBitVector *b) 
     452{ 
     453    FRT_BV_OP(bv, a, b, ^, frt_bv_xor_ext); 
     454    return bv; 
     455} 
     456 
     457extern FRT_ATTR_ALWAYS_INLINE 
     458FrtBitVector *frt_bv_not_i(FrtBitVector *bv, FrtBitVector *bv1) 
    424459{ 
    425460    int i; 
    426     int max_size = frt_max2(bv1->size, bv2->size); 
    427     int word_size = (max_size >> 5) + 1; 
    428     int capa = frt_max2(frt_round2(word_size), 4); 
    429  
    430     bv->extends_as_ones = (bv1->extends_as_ones | bv2->extends_as_ones); 
    431     frt_bv_recapa(bv1, capa); 
    432     frt_bv_recapa(bv2, capa); 
    433     frt_bv_capa(bv, capa, max_size); 
    434  
    435     for (i = 0; i < word_size; i++) { 
    436         bv->bits[i] = bv1->bits[i] | bv2->bits[i]; 
    437     } 
    438     frt_bv_recount(bv); 
    439     return bv; 
    440 } 
    441  
    442 extern FRT_ATTR_ALWAYS_INLINE 
    443 FrtBitVector *frt_bv_xor_i(FrtBitVector *bv, 
    444                            FrtBitVector *bv1, FrtBitVector *bv2) 
    445 { 
    446     int i; 
    447     int max_size = frt_max2(bv1->size, bv2->size); 
    448     int word_size = (max_size >> 5) + 1; 
    449     int capa = frt_max2(frt_round2(word_size), 4); 
    450  
    451     bv->extends_as_ones = (bv1->extends_as_ones ^ bv2->extends_as_ones); 
    452     frt_bv_recapa(bv1, capa); 
    453     frt_bv_recapa(bv2, capa); 
    454     frt_bv_capa(bv, capa, max_size); 
    455  
    456     for (i = 0; i < word_size; i++) { 
    457         bv->bits[i] = bv1->bits[i] ^ bv2->bits[i]; 
    458     } 
    459     frt_bv_recount(bv); 
    460     return bv; 
    461 } 
    462  
    463 extern FRT_ATTR_ALWAYS_INLINE 
    464 FrtBitVector *frt_bv_not_i(FrtBitVector *bv, FrtBitVector *bv1) 
    465 { 
    466     int i; 
    467     int word_size = (bv1->size >> 5) + 1; 
     461    int word_size = FRT_TO_WORD(bv1->size); 
    468462    int capa = frt_max2(frt_round2(word_size), 4); 
    469463 
    … …  
    471465    frt_bv_capa(bv, capa, bv1->size); 
    472466 
    473     for (i = 0; i < word_size; i++) { 
     467    for (i = 0; i < word_size; i++) 
    474468        bv->bits[i] = ~(bv1->bits[i]); 
    475     } 
     469 
    476470    frt_bv_recount(bv); 
    477471    return bv; 

  • c/include/global.h

    r1bc545 r208885f  
    7171 
    7272#define FRT_ABS(n) ((n >= 0) ? n : -n) 
     73#define FRT_TO_WORD(n) (((n) >> 5) + 1) 
    7374 
    7475#define FRT_RECAPA(self, len, capa, ptr, type) \ 

  • c/src/bitvector.c

    rd0c804 r208885f  
    4444int bv_eq(BitVector *bv1, BitVector *bv2) 
    4545{ 
    46     if (bv1 == bv2) { 
     46    if (bv1 == bv2) 
    4747        return true; 
     48 
     49    if (bv1->extends_as_ones != bv2->extends_as_ones) 
     50        return false; 
     51 
     52    u32 *bits = bv1->bits; 
     53    u32 *bits2 = bv2->bits; 
     54    int min_size = min2(bv1->size, bv2->size); 
     55    int word_size = FRT_TO_WORD(min_size); 
     56    int ext_word_size = 0; 
     57    int i; 
     58 
     59    for (i = 0; i < word_size; i++) { 
     60        if (bits[i] != bits2[i]) 
     61            return false; 
    4862    } 
    49     else if (bv1->extends_as_ones != bv2->extends_as_ones) { 
    50         return false; 
     63    if (bv1->size > min_size) { 
     64        bits = bv1->bits; 
     65        ext_word_size = FRT_TO_WORD(bv1->size); 
    5166    } 
    52     else { 
    53         u32 *bits = bv1->bits; 
    54         u32 *bits2 = bv2->bits; 
    55         int min_size = min2(bv1->size, bv2->size); 
    56         int word_size = (min_size >> 5) + 1; 
    57         int ext_word_size = 0; 
    58  
    59         int i; 
    60  
    61         for (i = 0; i < word_size; i++) { 
    62             if (bits[i] != bits2[i]) { 
     67    else if (bv2->size > min_size) { 
     68        bits = bv2->bits; 
     69        ext_word_size = FRT_TO_WORD(bv2->size); 
     70    } 
     71    if (ext_word_size) { 
     72        const u32 expected = (bv1->extends_as_ones ? 0xFFFFFFFF : 0); 
     73        for (i = word_size; i < ext_word_size; i++) { 
     74            if (bits[i] != expected) 
    6375                return false; 
    64             } 
    65         } 
    66         if (bv1->size > min_size) { 
    67             bits = bv1->bits; 
    68             ext_word_size = (bv1->size >> 5) + 1; 
    69         } 
    70         else if (bv2->size > min_size) { 
    71             bits = bv2->bits; 
    72             ext_word_size = (bv2->size >> 5) + 1; 
    73         } 
    74         if (ext_word_size) { 
    75             const u32 expected = (bv1->extends_as_ones ? 0xFFFFFFFF : 0); 
    76             for (i = word_size; i < ext_word_size; i++) { 
    77                 if (bits[i] != expected) { 
    78                     return false; 
    79                 } 
    80             } 
    8176        } 
    8277    } 
    … …  
    8984    const u32 empty_word = bv->extends_as_ones ? 0xFFFFFFFF : 0; 
    9085    int i; 
    91     for (i = (bv->size >> 5); i >= 0; i--) { 
     86    for (i = FRT_TO_WORD(bv->size) - 1; i >= 0; i--) { 
    9287        const u32 word = bv->bits[i]; 
    93         if (word != empty_word) { 
     88        if (word != empty_word) 
    9489            hash = (hash << 1) ^ word; 
    95         } 
    9690    } 
    9791    return (hash << 1) | bv->extends_as_ones; 
    9892} 
    99