Bit Vectors
[libbu (utility functions)]

Collaboration diagram for Bit Vectors:


Files

file  bitv.c
 Routines for managing bit vectors of arbitrary length.
file  printb.c
 print bitfields

Data Structures

struct  bu_bitv
 Bit vector data structure. More...

Defines

#define BU_BITV_MAGIC   0x62697476
#define BU_CK_BITV(_vp)   BU_CKMAG(_vp, BU_BITV_MAGIC, "bu_bitv")
#define BU_BITS2BYTES(_nb)   (BU_BITS2WORDS(_nb)*sizeof(bitv_t))
#define BU_BITS2WORDS(_nb)   (((_nb)+BITV_MASK)>>BITV_SHIFT)
#define BU_WORDS2BITS(_nw)   ((_nw)*sizeof(bitv_t)*8)
#define BU_BITTEST(_bv, bit)   (((_bv)->bits[(bit)>>BITV_SHIFT] & (((bitv_t)1)<<((bit)&BITV_MASK)))!=0)
#define BU_BITSET(_bv, bit)   ((_bv)->bits[(bit)>>BITV_SHIFT] |= (((bitv_t)1)<<((bit)&BITV_MASK)))
#define BU_BITCLR(_bv, bit)   ((_bv)->bits[(bit)>>BITV_SHIFT] &= ~(((bitv_t)1)<<((bit)&BITV_MASK)))
#define BU_BITV_ZEROALL(_bv)   { memset( (char *)((_bv)->bits), 0, BU_BITS2BYTES( (_bv)->nbits ) ); }
#define BU_BITV_BITNUM_CHECK(_bv, _bit)
#define BU_BITV_NBITS_CHECK(_bv, _nbits)
#define BU_BITV_LOOP_START(_bv)
#define BU_BITV_LOOP_INDEX   ((_wd << BITV_SHIFT) | _b)
#define BU_BITV_LOOP_END

Functions

bu_bitvbu_bitv_new (unsigned int nbits)
 Allocate storage for a new bit vector of at least 'nbits' in length. For efficiency, the bit vector itself is not initialized.
void bu_bitv_clear (struct bu_bitv *bv)
 Set all the bits in the bit vector to zero.
void bu_bitv_or (struct bu_bitv *ov, const struct bu_bitv *iv)
void bu_bitv_and (struct bu_bitv *ov, const struct bu_bitv *iv)
void bu_bitv_vls (struct bu_vls *v, const struct bu_bitv *bv)
void bu_pr_bitv (const char *str, const struct bu_bitv *bv)
void bu_bitv_to_hex (struct bu_vls *v, const struct bu_bitv *bv)
bu_bitvbu_hex_to_bitv (const char *str)
 Convert a string of HEX digits (as produces by bu_bitv_to_hex) into a bit vector.
bu_bitvbu_bitv_dup (const struct bu_bitv *bv)
void bu_bitv_free (struct bu_bitv *bv)
 Release all internal storage for this bit vector.
void bu_vls_printb (struct bu_vls *vls, const char *s, unsigned long v, const char *bits)
void bu_printb (const char *s, unsigned long v, const char *bits)
void bu_ptbl_init (struct bu_ptbl *b, int len, const char *str)
void bu_ptbl_reset (struct bu_ptbl *b)
int bu_ptbl_ins (struct bu_ptbl *b, long *p)
int bu_ptbl_locate (const struct bu_ptbl *b, const long *p)
void bu_ptbl_zero (struct bu_ptbl *b, const long *p)
int bu_ptbl_ins_unique (struct bu_ptbl *b, long *p)
int bu_ptbl_rm (struct bu_ptbl *b, const long *p)
void bu_ptbl_cat (struct bu_ptbl *dest, const struct bu_ptbl *src)
void bu_ptbl_cat_uniq (struct bu_ptbl *dest, const struct bu_ptbl *src)
void bu_ptbl_free (struct bu_ptbl *b)
int bu_ptbl (struct bu_ptbl *b, int func, long *p)
void bu_pr_ptbl (const char *title, const struct bu_ptbl *tbl, int verbose)
void bu_ptbl_trunc (struct bu_ptbl *tbl, int end)
void bu_bitv_vls (struct bu_vls *v, register const struct bu_bitv *bv)
 Print the bits set in a bit vector.
void bu_pr_bitv (const char *str, register const struct bu_bitv *bv)
 Print the bits set in a bit vector. Use bu_vls stuff, to make only a single call to bu_log().
void bu_bitv_to_hex (struct bu_vls *v, register const struct bu_bitv *bv)
 Convert a bit vector to an ascii string of hex digits. The string is from MSB to LSB (bytes and bits).
bu_bitvbu_bitv_dup (register const struct bu_bitv *bv)
 Make a copy of a bit vector.
void bu_vls_printb (struct bu_vls *vls, const char *s, register long unsigned int v, register const char *bits)
void bu_printb (const char *s, register long unsigned int v, register const char *bits)

Define Documentation

#define BU_BITV_MAGIC   0x62697476
 

Definition at line 847 of file bu.h.

Referenced by bu_bitv_new(), and bu_identify_magic().

#define BU_CK_BITV _vp   )     BU_CKMAG(_vp, BU_BITV_MAGIC, "bu_bitv")
 

Definition at line 848 of file bu.h.

Referenced by bu_bitv_clear(), bu_bitv_free(), bu_bitv_to_hex(), bu_bitv_vls(), bu_pr_bitv(), get_solidbitv(), rt_bool_partition_eligible(), rt_boolfinal(), rt_clean_resource(), and rt_tree_test_ready().

#define BU_BITS2BYTES _nb   )     (BU_BITS2WORDS(_nb)*sizeof(bitv_t))
 

Definition at line 854 of file bu.h.

Referenced by bu_bitv_new().

#define BU_BITS2WORDS _nb   )     (((_nb)+BITV_MASK)>>BITV_SHIFT)
 

Definition at line 855 of file bu.h.

Referenced by bu_bitv_and(), and bu_bitv_or().

#define BU_WORDS2BITS _nw   )     ((_nw)*sizeof(bitv_t)*8)
 

Definition at line 856 of file bu.h.

#define BU_BITTEST _bv,
bit   )     (((_bv)->bits[(bit)>>BITV_SHIFT] & (((bitv_t)1)<<((bit)&BITV_MASK)))!=0)
 

Definition at line 859 of file bu.h.

Referenced by bu_bitv_vls(), rt_find_backing_dist(), rt_shootray(), rt_shootray_bundle(), and rt_tree_test_ready().

#define BU_BITSET _bv,
bit   )     ((_bv)->bits[(bit)>>BITV_SHIFT] |= (((bitv_t)1)<<((bit)&BITV_MASK)))
 

Definition at line 874 of file bu.h.

Referenced by rt_bot_tcladjust(), rt_find_backing_dist(), rt_shootray(), and rt_shootray_bundle().

#define BU_BITCLR _bv,
bit   )     ((_bv)->bits[(bit)>>BITV_SHIFT] &= ~(((bitv_t)1)<<((bit)&BITV_MASK)))
 

Definition at line 876 of file bu.h.

Referenced by rt_bot_tcladjust().

#define BU_BITV_ZEROALL _bv   )     { memset( (char *)((_bv)->bits), 0, BU_BITS2BYTES( (_bv)->nbits ) ); }
 

Definition at line 878 of file bu.h.

Referenced by bu_bitv_clear(), and rt_shootray().

#define BU_BITV_BITNUM_CHECK _bv,
_bit   ) 
 

Value:

/* Validate bit number */ \
        if( ((unsigned)(_bit)) >= (_bv)->nbits )  {\
                bu_log("BU_BITV_BITNUM_CHECK bit number (%u) out of range (0..%u)\n", \
                        ((unsigned)(_bit)), (_bv)->nbits); \
                bu_bomb("process self-terminating\n");\
        }

Definition at line 885 of file bu.h.

#define BU_BITV_NBITS_CHECK _bv,
_nbits   ) 
 

Value:

/* Validate number of bits */ \
        if( ((unsigned)(_nbits)) > (_bv)->nbits )  {\
                bu_log("BU_BITV_NBITS_CHECK number of bits (%u) out of range (> %u)", \
                        ((unsigned)(_nbits)), (_bv)->nbits ); \
                bu_bomb("process self-terminating"); \
                }

Definition at line 896 of file bu.h.

#define BU_BITV_LOOP_START _bv   ) 
 

Value:

{ \
        register int            _wd;    /* Current word number */  \
        BU_CK_BITV(_bv); \
        for( _wd=BU_BITS2WORDS((_bv)->nbits)-1; _wd>=0; _wd-- )  {  \
                register int    _b;     /* Current bit-in-word number */  \
                register bitv_t _val;   /* Current word value */  \
                if((_val = (_bv)->bits[_wd])==0) continue;  \
                for(_b=0; _b < BITV_MASK+1; _b++, _val >>= 1 ) { \
                        if( !(_val & 1) )  continue;
Macros to efficiently find all the ONE bits in a bit vector. Counts words down, counts bits in words going up, for speed & portability. It does not matter if the shift causes the sign bit to smear to the right.

Example:

Definition at line 918 of file bu.h.

#define BU_BITV_LOOP_INDEX   ((_wd << BITV_SHIFT) | _b)
 

This macro is valid only between a BU_BITV_LOOP_START/LOOP_END pair, and gives the bit number of the current iteration.

Definition at line 933 of file bu.h.

#define BU_BITV_LOOP_END
 

Value:

} /* end for(_b) */ \
        } /* end for(_wd) */ \
}

Definition at line 935 of file bu.h.


Function Documentation

struct bu_bitv * bu_bitv_new unsigned int  nbits  ) 
 

Allocate storage for a new bit vector of at least 'nbits' in length. For efficiency, the bit vector itself is not initialized.

B U _ B I T V _ N E W

Definition at line 67 of file bitv.c.

References BU_BITS2BYTES, BU_BITV_MAGIC, BU_LIST_INIT, bu_malloc(), bu_bitv::l, bu_list::magic, and bu_bitv::nbits.

Referenced by bu_bitv_dup(), bu_hex_to_bitv(), get_solidbitv(), rt_bot_export(), and rt_res_pieces_init().

Here is the call graph for this function:

void bu_bitv_clear struct bu_bitv bv  ) 
 

Set all the bits in the bit vector to zero.

B U _ B I T V _ C L E A R

Also available as a macro if you don't desire the pointer checking.

Definition at line 108 of file bitv.c.

References BU_BITV_ZEROALL, and BU_CK_BITV.

Referenced by bu_bitv_dup(), bu_hex_to_bitv(), rt_bot_export(), rt_find_backing_dist(), rt_shootray(), and rt_shootray_bundle().

void bu_bitv_or struct bu_bitv ov,
const struct bu_bitv iv
 

B U _ B I T V _ O R

Definition at line 119 of file bitv.c.

References bu_bitv::bits, BU_BITS2WORDS, bu_bomb(), and bu_bitv::nbits.

Referenced by bu_bitv_dup().

Here is the call graph for this function:

void bu_bitv_and struct bu_bitv ov,
const struct bu_bitv iv
 

Definition at line 143 of file bitv.c.

References bu_bitv::bits, BU_BITS2WORDS, bu_bomb(), and bu_bitv::nbits.

Here is the call graph for this function:

void bu_bitv_vls struct bu_vls v,
const struct bu_bitv bv
 

Referenced by bu_pr_bitv().

void bu_pr_bitv const char *  str,
const struct bu_bitv bv
 

void bu_bitv_to_hex struct bu_vls v,
const struct bu_bitv bv
 

Referenced by rt_bot_export(), rt_bot_export5(), and rt_bot_tclget().

struct bu_bitv * bu_hex_to_bitv const char *  str  ) 
 

Convert a string of HEX digits (as produces by bu_bitv_to_hex) into a bit vector.

B U _ H E X _ T O _ B I T V

Definition at line 247 of file bitv.c.

References bu_bitv::bits, bu_bitv_clear(), bu_bitv_new(), bu_log(), and NULL.

Referenced by rt_bot_tcladjust().

Here is the call graph for this function:

struct bu_bitv* bu_bitv_dup const struct bu_bitv bv  ) 
 

Referenced by rt_bot_xform(), and XGLUE().

void bu_bitv_free struct bu_bitv bv  ) 
 

Release all internal storage for this bit vector.

B U _ B I T V _ F R E E

It is the caller's responsibility to not use the pointer 'bv' any longer. It is the caller's responsibility to dequeue from any linked list first.

Definition at line 92 of file bitv.c.

References bu_list::back, BU_CK_BITV, bu_free(), BU_LIST_NULL, bu_list::forw, and bu_bitv::l.

Referenced by rt_res_pieces_clean().

Here is the call graph for this function:

void bu_vls_printb struct bu_vls vls,
const char *  s,
unsigned long  v,
const char *  bits
 

Referenced by bu_printb(), and bu_tcl_printb().

void bu_printb const char *  s,
unsigned long  v,
const char *  bits
 

Referenced by db_pr_tree_state().

void bu_ptbl_init struct bu_ptbl b,
int  len,
const char *  str
 

B U _ P T B L _ I N I T

Initialize struct & get storage for table. Recommend 8 or 64 for initial len.

Definition at line 72 of file ptbl.c.

References bu_ptbl::blen, bu_calloc(), bu_debug, BU_DEBUG_PTBL, BU_LIST_INIT, bu_log(), BU_PTBL_MAGIC, bu_ptbl::buffer, bu_ptbl::end, bu_ptbl::l, and bu_list::magic.

Referenced by bu_ptbl(), bu_ptbl_ins(), db_lookup_by_attr(), db_open(), dgo_E_cmd(), Eplot(), nmg_break_edge_at_verts(), nmg_check_radial_angles(), nmg_ck_geometry(), nmg_ck_vs_in_region(), nmg_close_shell(), nmg_crackshells(), nmg_cut_lu_into_coplanar_and_non(), nmg_decompose_shell(), nmg_dup_shell(), nmg_e_and_v_tabulate(), nmg_edge_g_tabulate(), nmg_edge_tabulate(), nmg_edgeuse_on_line_tabulate(), nmg_edgeuse_tabulate(), nmg_edgeuse_with_eg_tabulate(), nmg_extrude_shell(), nmg_face_tabulate(), nmg_find_outer_and_void_shells(), nmg_find_zero_length_edges(), nmg_fix_normals(), nmg_fix_overlapping_loops(), nmg_get_touching_jaunts(), nmg_hollow_shell(), nmg_in_vert(), nmg_intersect_loops_self(), nmg_isect_eu_fu(), nmg_isect_shell_self(), nmg_kill_anti_loops(), nmg_kill_cracks_at_vertex(), nmg_make_faces_within_tol(), nmg_model_break_e_on_v(), nmg_move_edge_thru_pt(), nmg_open_shells_connect(), nmg_propagate_normals(), nmg_radial_join_eu_NEW(), nmg_split_loops_handler(), nmg_tabulate_face_g_verts(), nmg_translate_face(), nmg_vertex_tabulate(), nmg_vertexuse_normal_tabulate(), rt_comb_import5(), rt_ct_get(), rt_cut_it(), rt_extrude_tess(), rt_find_identical_solid(), rt_get_region_seglist_for_partition(), rt_get_seg(), rt_init_resource(), rt_nmg_tclget(), rt_rebuild_overlaps(), rt_shootray(), rt_shootray_bundle(), and rt_unprep().

Here is the call graph for this function:

void bu_ptbl_reset struct bu_ptbl b  ) 
 

B U _ P T B L _ R E S E T

Reset the table to have no elements, but retain any existing storage.

Definition at line 91 of file ptbl.c.

References bu_ptbl::blen, BU_CK_PTBL, bu_debug, BU_DEBUG_PTBL, bu_log(), bu_ptbl::buffer, and bu_ptbl::end.

Referenced by bu_ptbl(), dgo_E_cmd(), nmg_decompose_shell(), nmg_fix_overlapping_loops(), nmg_intersect_loops_self(), nmg_move_edge_thru_pt(), nmg_split_loops_handler(), and rt_shootray().

Here is the call graph for this function:

int bu_ptbl_ins struct bu_ptbl b,
long *  p
 

Referenced by add_solid(), bu_ptbl(), bu_ptbl_ins_unique(), db_get_directory(), nmg_break_edge_at_verts(), nmg_ck_vu_ptbl(), nmg_close_shell(), nmg_cut_lu_into_coplanar_and_non(), nmg_dup_shell(), nmg_extrude_shell(), nmg_find_isect_faces(), nmg_find_outer_and_void_shells(), nmg_fix_normals(), nmg_follow_free_edges_to_vertex(), nmg_get_touching_jaunts(), nmg_hollow_shell(), nmg_intersect_loops_self(), nmg_isect_shell_self(), nmg_kill_anti_loops(), nmg_make_faces_within_tol(), nmg_model_break_e_on_v(), nmg_open_shells_connect(), nmg_split_loops_handler(), rt_comb_import5(), rt_ct_get(), rt_cut_one_axis(), rt_extrude_tess(), rt_find_paths(), rt_get_seg(), rt_gettree_leaf(), rt_rebuild_overlaps(), and rt_solid_bitfinder().

int bu_ptbl_locate const struct bu_ptbl b,
const long *  p
 

Referenced by bu_ptbl(), nmg_ck_vu_ptbl(), nmg_enlist_one_vu(), nmg_enlist_vu(), nmg_fix_normals(), nmg_follow_free_edges_to_vertex(), and rt_nmg_tclget().

void bu_ptbl_zero struct bu_ptbl b,
const long *  p
 

Referenced by bu_ptbl(), nmg_edge_collapse(), and nmg_model_edge_fuse().

int bu_ptbl_ins_unique struct bu_ptbl b,
long *  p
 

Referenced by bu_ptbl(), bu_ptbl_cat_uniq(), db_clone_dbi(), nmg_decompose_shell(), nmg_edgeuse_with_eg_tabulate(), nmg_enlist_one_vu(), nmg_enlist_vu(), nmg_isect_2colinear_edge2p(), nmg_isect_eu_eu(), nmg_isect_eu_fu(), nmg_isect_eu_verts(), nmg_isect_fu_jra(), nmg_kill_cracks_at_vertex(), nmg_radial_build_list(), nmg_tabulate_face_g_verts(), rt_boolweave(), rt_get_region_seglist_for_partition(), rt_shootray(), and rt_weave0seg().

int bu_ptbl_rm struct bu_ptbl b,
const long *  p
 

Referenced by bu_ptbl(), db_close_client(), nmg_break_edge_at_verts(), nmg_follow_free_edges_to_vertex(), nmg_kill_anti_loops(), nmg_pop_eu(), nmg_ptbl_vfuse(), and rt_shootray().

void bu_ptbl_cat struct bu_ptbl dest,
const struct bu_ptbl src
 

B U _ P T B L _ C A T

Catenate one table onto end of another. There is no checking for duplication.

Definition at line 271 of file ptbl.c.

References bcopy, bu_ptbl::blen, BU_CK_PTBL, bu_debug, BU_DEBUG_PTBL, bu_log(), bu_realloc(), bu_ptbl::buffer, and bu_ptbl::end.

Referenced by bu_ptbl().

Here is the call graph for this function:

void bu_ptbl_cat_uniq struct bu_ptbl dest,
const struct bu_ptbl src
 

B U _ P T B L _ C A T _ U N I Q

Catenate one table onto end of another, ensuring that no entry is duplicated. Duplications between multiple items in 'src' are not caught. The search is a nasty n**2 one. The tables are expected to be short.

Definition at line 299 of file ptbl.c.

References bu_ptbl::blen, BU_CK_PTBL, bu_debug, BU_DEBUG_PTBL, bu_log(), BU_PTBL_FOR, bu_ptbl_ins_unique(), bu_realloc(), bu_ptbl::buffer, and bu_ptbl::end.

Referenced by rt_rebuild_overlaps().

Here is the call graph for this function:

void bu_ptbl_free struct bu_ptbl b  ) 
 

B U _ P T B L _ F R E E

Deallocate dynamic buffer associated with a table, and render this table unusable without a subsequent bu_ptbl_init().

Definition at line 327 of file ptbl.c.

References BU_CK_PTBL, bu_debug, BU_DEBUG_PTBL, bu_free(), bu_log(), and bu_ptbl::buffer.

Referenced by bu_ptbl(), db_close(), dgo_E_cmd(), free_etree(), nmg_calc_face_plane(), nmg_ck_vs_in_region(), nmg_classify_s_vs_s(), nmg_close_shell(), nmg_crackshells(), nmg_decompose_shell(), nmg_dup_shell(), nmg_fix_normals(), nmg_fix_overlapping_loops(), nmg_in_vert(), nmg_isect_fu_jra(), nmg_isect_two_generic_faces(), nmg_model_vertex_fuse(), nmg_move_edge_thru_pt(), nmg_open_shells_connect(), nmg_propagate_normals(), nmg_radial_join_eu_NEW(), nmg_split_loops_handler(), nmg_to_arb(), rt_clean_resource(), rt_comb_import5(), rt_cut_clean(), rt_extrude_tess(), rt_fastgen_vol_vol_overlap(), rt_free_rti(), rt_free_soltab(), rt_nmg_tclget(), rt_res_pieces_clean(), and rt_unprep().

Here is the call graph for this function:

int bu_ptbl struct bu_ptbl b,
int  func,
long *  p
 

void bu_pr_ptbl const char *  title,
const struct bu_ptbl tbl,
int  verbose
 

B U _ P R _ P T B L

Print a bu_ptbl array for inspection.

Definition at line 385 of file ptbl.c.

References BU_CK_PTBL, bu_log(), BU_PTBL_BASEADDR, BU_PTBL_LASTADDR, and bu_ptbl::end.

Referenced by rt_pr_soltab(), and rt_prep_parallel().

Here is the call graph for this function:

void bu_ptbl_trunc struct bu_ptbl tbl,
int  end
 

B U _ P T B L _ T R U N C

truncate a bu_ptbl

Definition at line 414 of file ptbl.c.

References BU_CK_PTBL, and bu_ptbl::end.

Referenced by rt_comb_import5(), and rt_rebuild_overlaps().

void bu_bitv_vls struct bu_vls v,
register const struct bu_bitv bv
 

Print the bits set in a bit vector.

B U _ B I T V _ V L S

Definition at line 169 of file bitv.c.

References BU_BITTEST, BU_CK_BITV, BU_CK_VLS, bu_vls_printf(), and bu_vls_strcat().

Here is the call graph for this function:

void bu_pr_bitv const char *  str,
register const struct bu_bitv bv
 

Print the bits set in a bit vector. Use bu_vls stuff, to make only a single call to bu_log().

B U _ P R _ B I T V

Definition at line 199 of file bitv.c.

References bu_bitv_vls(), BU_CK_BITV, bu_log(), bu_vls_addr(), bu_vls_free(), bu_vls_init(), and bu_vls_strcat().

Here is the call graph for this function:

void bu_bitv_to_hex struct bu_vls v,
register const struct bu_bitv bv
 

Convert a bit vector to an ascii string of hex digits. The string is from MSB to LSB (bytes and bits).

B U _ B I T V _ T O _ H E X

Definition at line 219 of file bitv.c.

References BU_CK_BITV, BU_CK_VLS, bu_vls_extend(), and bu_vls_printf().

Here is the call graph for this function:

struct bu_bitv* bu_bitv_dup register const struct bu_bitv bv  ) 
 

Make a copy of a bit vector.

B U _ B I T V _ D U P

Definition at line 314 of file bitv.c.

References bu_bitv_clear(), bu_bitv_new(), and bu_bitv_or().

Here is the call graph for this function:

void bu_vls_printb struct bu_vls vls,
const char *  s,
register long unsigned int  v,
register const char *  bits
 

B U _ V L S _ P R I N T B

Format a value a la the b format of the kernel's printf

Parameters:
vls variable length string to put output in
s title string
v the integer with the bits in it
bits a string which starts with the desired base (8 or 16) as \010 or \020, followed by words preceeded with embedded low-value bytes indicating bit number plus one, in little-endian order, eg: "\010\2Bit_one\1BIT_zero"

Definition at line 66 of file printb.c.

References bu_vls_printf(), and bu_vls_strcat().

Here is the call graph for this function:

void bu_printb const char *  s,
register long unsigned int  v,
register const char *  bits
 

B U _ P R I N T B

Format and print, like bu_vls_printb().

Definition at line 95 of file printb.c.

References bu_log(), bu_vls_addr(), bu_vls_free(), bu_vls_init(), and bu_vls_printb().

Here is the call graph for this function:


Generated on Mon Sep 18 01:25:19 2006 for BRL-CAD by  doxygen 1.4.6