/*3:*/#line 110 "./tabuhash.w"#include <config.h> #include "lkconfig.h"/*4:*/#line 124 "./tabuhash.w"#include <stdio.h> #include <stdlib.h> #include <stddef.h> /*:4*//*10:*/#line 242 "./tabuhash.w"#include <limits.h> /*:10*/#line 113 "./tabuhash.w"#include "error.h"#include "memory.h"#include "tabuhash.h"/*12:*/#line 260 "./tabuhash.w"inttabu_hash_bd_includes(tabu_hash_t*th,int u,int v){tabu_hash_elem_t*here;int uu= u,vv= v;if(uu<vv){uu= v;vv= u;}for(here= th->chain[u^v];here;here= here->next){/*32:*/#line 521 "./tabuhash.w"#if TABUHASH_MAX_VERBOSE >= 160{extern int verbose;if(verbose>=200){printf("tabu_hash_includes: check chain %p for %d %d\n",here,uu,vv);}}#endif/*:32*/#line 268 "./tabuhash.w"if(here->u==uu&&here->v==vv){/*29:*/#line 497 "./tabuhash.w"#if TABUHASH_MAX_VERBOSE >= 180{extern int verbose;if(verbose>=180){printf("tabu_hash_includes: %d %d is tabu\n",u,v);}}#endif/*:29*/#line 270 "./tabuhash.w"return 1;}}/*28:*/#line 488 "./tabuhash.w"#if TABUHASH_MAX_VERBOSE >= 180{extern int verbose;if(verbose>=180){printf("tabu_hash_includes: %d %d is not tabu\n",u,v);}}#endif/*:28*/#line 274 "./tabuhash.w"return 0;}int(*tabu_hash_unbd_includes)(tabu_hash_t*th,int u,int v)= tabu_hash_bd_includes;/*:12*//*14:*/#line 298 "./tabuhash.w"tabu_hash_t*tabu_hash_bd_create(int vertex_bound,int max_size){tabu_hash_t*th;/*9:*/#line 224 "./tabuhash.w"th= new_of(tabu_hash_t);th->chain_limit= vertex_bound-1;th->chain_limit|= th->chain_limit>>1;th->chain_limit|= th->chain_limit>>2;th->chain_limit|= th->chain_limit>>4;th->chain_limit|= th->chain_limit>>8;th->chain_limit|= th->chain_limit>>16;#if SIZEOF_INT==8th->chain_limit|= th->chain_limit>>32;#endiferrorif(th->chain_limit==INT_MAX,"Too many vertices (%d) to use hashing",vertex_bound);th->chain_limit+= 1;th->chain= new_arr_of_zero(tabu_hash_elem_t*,th->chain_limit);th->dirty= dirty_create(th->chain_limit,0,0,__FILE__,__LINE__);/*:9*/#line 303 "./tabuhash.w"errorif(max_size<=0,"Maximum tabu list size (%d) must be positive.",max_size);th->thread= new_arr_of(tabu_hash_elem_t,max_size);th->max_size= max_size;th->size= 0;return th;}/*:14*//*15:*/#line 312 "./tabuhash.w"voidtabu_hash_bd_destroy(tabu_hash_t*th){if(th){free_mem(th->thread);mem_deduct(sizeof(tabu_hash_elem_t*)*th->max_size);th->max_size= 0;th->size= 0;/*11:*/#line 246 "./tabuhash.w"free_mem(th->chain);mem_deduct(sizeof(tabu_hash_elem_t*)*th->chain_limit);th->chain_limit= 0;dirty_destroy(th->dirty);free_mem(th);mem_deduct(sizeof(tabu_hash_t));/*:11*/#line 320 "./tabuhash.w"}}/*:15*//*16:*/#line 332 "./tabuhash.w"voidtabu_hash_bd_add(tabu_hash_t*th,int u,int v){const int h= u^v;tabu_hash_elem_t*was_dirty;int uu= u,vv= v;#if defined(TABUHASH_DEBUG)errorif(th->size>=th->max_size,"Bounded tabu list already saturated with %d elements.",th->size);#endifif(u<v){uu= v;vv= u;}th->thread[th->size].u= uu;th->thread[th->size].v= vv;was_dirty= th->thread[th->size].next= th->chain[h];th->chain[h]= th->thread+th->size;th->size++;if(!was_dirty)dirty_add(th->dirty,h);/*24:*/#line 459 "./tabuhash.w"#if TABUHASH_MAX_VERBOSE >= 160{extern int verbose;if(verbose>=160){printf("tabu_hash_bd_add: Added %d %d\n",u,v);}if(verbose>=500){/*26:*/#line 482 "./tabuhash.w"/*:26*/#line 464 "./tabuhash.w"}}#endif/*:24*/#line 350 "./tabuhash.w"}/*:16*//*17:*/#line 358 "./tabuhash.w"voidtabu_hash_bd_make_empty(tabu_hash_t*th){int c;dirty_set_t*dirty= th->dirty;while((c= dirty_remove(dirty))>=0)th->chain[c]= NULL;th->size= 0;/*30:*/#line 505 "./tabuhash.w"#if TABUHASH_MAX_VERBOSE >= 160{extern int verbose;if(verbose>=160){printf("tabu_hash_bd_make_empty\n");}}#endif/*:30*/#line 366 "./tabuhash.w"}/*:17*//*20:*/#line 390 "./tabuhash.w"tabu_hash_t*tabu_hash_unbd_create(int vertex_bound,int max_size){tabu_hash_t*th;/*9:*/#line 224 "./tabuhash.w"th= new_of(tabu_hash_t);th->chain_limit= vertex_bound-1;th->chain_limit|= th->chain_limit>>1;th->chain_limit|= th->chain_limit>>2;th->chain_limit|= th->chain_limit>>4;th->chain_limit|= th->chain_limit>>8;th->chain_limit|= th->chain_limit>>16;#if SIZEOF_INT==8th->chain_limit|= th->chain_limit>>32;#endiferrorif(th->chain_limit==INT_MAX,"Too many vertices (%d) to use hashing",vertex_bound);th->chain_limit+= 1;th->chain= new_arr_of_zero(tabu_hash_elem_t*,th->chain_limit);th->dirty= dirty_create(th->chain_limit,0,0,__FILE__,__LINE__);/*:9*/#line 395 "./tabuhash.w"th->elem_pool= pool_create(sizeof(tabu_hash_elem_t),max_size> 0?max_size:120);return th;}/*:20*//*21:*/#line 402 "./tabuhash.w"voidtabu_hash_unbd_destroy(tabu_hash_t*th){if(th){pool_destroy(th->elem_pool);/*11:*/#line 246 "./tabuhash.w"free_mem(th->chain);mem_deduct(sizeof(tabu_hash_elem_t*)*th->chain_limit);th->chain_limit= 0;dirty_destroy(th->dirty);free_mem(th);mem_deduct(sizeof(tabu_hash_t));/*:11*/#line 408 "./tabuhash.w"}}/*:21*//*22:*/#line 415 "./tabuhash.w"voidtabu_hash_unbd_add(tabu_hash_t*th,int u,int v){const int h= u^v;tabu_hash_elem_t*e= pool_alloc(th->elem_pool);tabu_hash_elem_t*was_dirty;int uu= u,vv= v;if(u<v){uu= v;vv= u;}e->u= uu;e->v= vv;was_dirty= e->next= th->chain[h];th->chain[h]= e;if(!was_dirty)dirty_add(th->dirty,h);/*25:*/#line 470 "./tabuhash.w"#if TABUHASH_MAX_VERBOSE >= 160{extern int verbose;if(verbose>=160){printf("tabu_hash_unbd_add: Added %d %d\n",u,v);}if(verbose>=500){/*27:*/#line 485 "./tabuhash.w"/*:27*/#line 475 "./tabuhash.w"}}#endif/*:25*/#line 429 "./tabuhash.w"}/*:22*//*23:*/#line 443 "./tabuhash.w"voidtabu_hash_unbd_make_empty(tabu_hash_t*th){int c;pool_t*pool= th->elem_pool;dirty_set_t*dirty= th->dirty;while((c= dirty_remove(dirty))>=0){tabu_hash_elem_t*here;for(here= th->chain[c];here;here= here->next)pool_free(pool,here);th->chain[c]= NULL;}/*31:*/#line 513 "./tabuhash.w"#if TABUHASH_MAX_VERBOSE >= 160{extern int verbose;if(verbose>=160){printf("tabu_hash_unbd_make_empty\n");}}#endif/*:31*/#line 455 "./tabuhash.w"}/*:23*/#line 118 "./tabuhash.w"const char*tabuhash_rcs_id= "$Id: tabuhash.w,v 1.5 2000/09/17 03:12:55 neto Exp neto $";/*:3*/