The Machine Perception Toolbox
[Introduction]- [News]- [Download]- [Screenshots]- [Manual (pdf)]- [Forums]- [API Reference]- [Repository ]

 

Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages
boost-build / jam_src

hash.c File Reference

#include "jam.h"
#include "hash.h"
#include <assert.h>

Include dependency graph for hash.c:

Include dependency graph

Go to the source code of this file.

Classes

struct  hash
struct  hashdata
struct  hashhdr
struct  item

Defines

#define ALIGNED(x)   ( ( x + sizeof( ITEM ) - 1 ) & ~( sizeof( ITEM ) - 1 ) )
#define MAX_LISTS   32

Typedefs

typedef item ITEM

Functions

int hash_free (register struct hash *hp, HASHDATA *data)
void hashdone (struct hash *hp)
void hashenumerate (struct hash *hp, void(*f)(void *, void *), void *data)
hash * hashinit (int datalen, char *name)
int hashitem (register struct hash *hp, HASHDATA **data, int enter)
void hashrehash (register struct hash *hp)
void hashrehash (struct hash *hp)
void hashstat (struct hash *hp)

Variables

char * hashsccssid = "@(#)hash.c 1.14 () 6/20/88"

Define Documentation

#define ALIGNED (  x   )     ( ( x + sizeof( ITEM ) - 1 ) & ~( sizeof( ITEM ) - 1 ) )
 

Definition at line 258 of file hash.c.

Referenced by hashinit().

#define MAX_LISTS   32
 

Definition at line 49 of file hash.c.

Typedef Documentation

typedef struct item ITEM
 

Referenced by hash_free(), hashenumerate(), hashinit(), hashitem(), hashrehash(), and hashstat().

Function Documentation

int hash_free (  register struct hash *  hp,
HASHDATA *  data
) 
 

Definition at line 96 of file hash.c.

References item::data, data, HASHDATA, item::hdr, i, ITEM, hashdata::key, hashhdr::keyval, and hashhdr::next.

00099 {
00100         ITEM **prev;
00101         register ITEM **i;
00102         unsigned char *b = (unsigned char*)data->key;
00103         unsigned int keyval;
00104 
00105         keyval = *b;
00106 
00107         while( *b )
00108                 keyval = keyval * 2147059363 + *b++;
00109 
00110     prev = hp->tab.base + ( keyval % hp->tab.nel );
00111         while(*prev )
00112     {
00113         register ITEM* i = *prev;
00114             if( keyval == i->hdr.keyval && 
00115             !strcmp( i->data.key, data->key ) )
00116         {
00117             /* unlink the record from the hash chain */
00118             *prev = i->hdr.next;
00119             /* link it into the freelist */
00120             i->hdr.next = hp->items.free;
00121             hp->items.free = i;
00122             /* mark it free so we skip it during enumeration */
00123             i->data.key = 0;
00124             /* we have another item */
00125             hp->items.more++;
00126             return 1;
00127         }
00128         prev = &i->hdr.next;
00129     }
00130     return 0;
00131 }

void hashdone (  struct hash *  hp  ) 
 

Definition at line 291 of file hash.c.

References hash::base, hashstat(), i, hash::items, hash::list, and hash::tab.

Referenced by delete_module(), donerules(), donestamps(), donestr(), and var_done().

00292 {
00293         int i;
00294 
00295         if( !hp )
00296             return;
00297 
00298         if( DEBUG_MEM )
00299             hashstat( hp );
00300 
00301         if( hp->tab.base )
00302                 free( (char *)hp->tab.base );
00303         for( i = 0; i <= hp->items.list; i++ )
00304                 free( hp->items.lists[i].base );
00305         free( (char *)hp );
00306 }

Here is the call graph for this function:

void hashenumerate (  struct hash *  hp,
void(*)(void *, void *)  f,
void *  data
) 
 

Definition at line 236 of file hash.c.

References hash::base, item::data, data, f(), i, ITEM, hash::items, hashdata::key, hash::list, hash::more, hash::nel, and hash::size.

Referenced by bind_explicitly_located_targets(), builtin_rulenames(), builtin_varnames(), delete_module(), donerules(), import_base_rules(), imported_modules(), profile_dump(), and var_done().

00237 {
00238     int i;
00239     for( i = 0; i <= hp->items.list; i++ )
00240     {
00241         char *next = hp->items.lists[i].base;
00242         int nel = hp->items.lists[i].nel;
00243         if ( i == hp->items.list )
00244             nel -= hp->items.more;
00245 
00246         for( ; nel--; next += hp->items.size )
00247         {
00248             register ITEM *i = (ITEM *)next;
00249             
00250             if ( i->data.key != 0 ) /* don't enumerate freed items */
00251                 f(&i->data, data);
00252         }
00253     }
00254 }

Here is the call graph for this function:

struct hash* hashinit (  int  datalen,
char *  name
) 
 

Definition at line 265 of file hash.c.

References ALIGNED, hash::base, hash::bloat, ITEM, hash::nel, and hash::tab.

Referenced by bindmodule(), bindtarget(), demand_rules(), import_module(), macro_headers(), make_class_module(), newstr(), profile_enter(), regex_compile(), search(), search_for_target(), timestamp(), and var_enter().

00268 {
00269         struct hash *hp = (struct hash *)malloc( sizeof( *hp ) );
00270 
00271         hp->bloat = 3;
00272         hp->tab.nel = 0;
00273         hp->tab.base = (ITEM **)0;
00274         hp->items.more = 0;
00275     hp->items.free = 0;
00276         hp->items.datalen = datalen;
00277         hp->items.size = sizeof( struct hashhdr ) + ALIGNED( datalen );
00278         hp->items.list = -1;
00279         hp->items.nel = 0;
00280         hp->inel = 11;
00281         hp->name = name;
00282 
00283         return hp;
00284 }

int hashitem (  register struct hash *  hp,
HASHDATA **  data,
int  enter
) 
 

Definition at line 138 of file hash.c.

References data, item::data, HASHDATA, hashrehash(), item::hdr, i, ITEM, hashdata::key, hashhdr::keyval, and hashhdr::next.

00142 {
00143         ITEM **base;
00144         register ITEM *i;
00145         unsigned char *b = (unsigned char*)(*data)->key;
00146         unsigned int keyval;
00147 
00148         if( enter && !hp->items.more )
00149             hashrehash( hp );
00150 
00151         if( !enter && !hp->items.nel )
00152             return 0;
00153 
00154         keyval = *b;
00155 
00156         while( *b )
00157                 keyval = keyval * 2147059363 + *b++;
00158 
00159         base = hp->tab.base + ( keyval % hp->tab.nel );
00160 
00161         for( i = *base; i; i = i->hdr.next )
00162             if( keyval == i->hdr.keyval && 
00163                 !strcmp( i->data.key, (*data)->key ) )
00164         {
00165                 *data = &i->data;
00166                 return !0;
00167         }
00168 
00169         if( enter ) 
00170         {
00171         /* try to grab one from the free list */
00172         if ( hp->items.free )
00173         {
00174             i = hp->items.free;
00175             hp->items.free = i->hdr.next;
00176             assert( i->data.key == 0 );
00177         }
00178         else
00179         {
00180             i = (ITEM *)hp->items.next;
00181             hp->items.next += hp->items.size;
00182         }
00183                 hp->items.more--;
00184                 memcpy( (char *)&i->data, (char *)*data, hp->items.datalen );
00185                 i->hdr.keyval = keyval;
00186                 i->hdr.next = *base;
00187                 *base = i;
00188                 *data = &i->data;
00189         }
00190 
00191         return 0;
00192 }

Here is the call graph for this function:

void hashrehash (  register struct hash *  hp  )  [static]
 

Definition at line 198 of file hash.c.

References item::data, item::hdr, i, ITEM, hashdata::key, hashhdr::keyval, and hashhdr::next.

Referenced by hashitem().

00199 {
00200         int i = ++hp->items.list;
00201 
00202         hp->items.more = i ? 2 * hp->items.nel : hp->inel;
00203         hp->items.next = (char *)malloc( hp->items.more * hp->items.size );
00204     hp->items.free = 0;
00205     
00206         hp->items.lists[i].nel = hp->items.more;
00207         hp->items.lists[i].base = hp->items.next;
00208         hp->items.nel += hp->items.more;
00209 
00210         if( hp->tab.base )
00211                 free( (char *)hp->tab.base );
00212 
00213         hp->tab.nel = hp->items.nel * hp->bloat;
00214         hp->tab.base = (ITEM **)malloc( hp->tab.nel * sizeof(ITEM **) );
00215 
00216         memset( (char *)hp->tab.base, '\0', hp->tab.nel * sizeof( ITEM * ) );
00217 
00218         for( i = 0; i < hp->items.list; i++ )
00219         {
00220                 int nel = hp->items.lists[i].nel;
00221                 char *next = hp->items.lists[i].base;
00222 
00223                 for( ; nel--; next += hp->items.size )
00224                 {
00225                         register ITEM *i = (ITEM *)next;
00226                         ITEM **ip = hp->tab.base + i->hdr.keyval % hp->tab.nel;
00227             /* code currently assumes rehashing only when there are no free items */
00228             assert( i->data.key != 0 ); 
00229             
00230                         i->hdr.next = *ip;
00231                         *ip = i;
00232                 }
00233         }
00234 }

void hashrehash (  struct hash *  hp  )  [static]
 

void hashstat (  struct hash *  hp  )  [static]
 

Definition at line 311 of file hash.c.

References hash::base, i, ITEM, hash::items, hash::name, hash::nel, hash::size, and hash::tab.

Referenced by hashdone().

00312 {
00313         ITEM **tab = hp->tab.base;
00314         int nel = hp->tab.nel;
00315         int count = 0;
00316         int sets = 0;
00317         int run = ( tab[ nel - 1 ] != (ITEM *)0 );
00318         int i, here;
00319 
00320         for( i = nel; i > 0; i-- )
00321         {
00322                 if( here = ( *tab++ != (ITEM *)0 ) )
00323                         count++;
00324                 if( here && !run )
00325                         sets++;
00326                 run = here;
00327         }
00328 
00329         printf( "%s table: %d+%d+%d (%dK+%dK) items+table+hash, %f density\n",
00330                 hp->name, 
00331                 count, 
00332                 hp->items.nel,
00333                 hp->tab.nel,
00334                 hp->items.nel * hp->items.size / 1024,
00335                 hp->tab.nel * sizeof( ITEM ** ) / 1024,
00336                 (float)count / (float)sets );
00337 }

Variable Documentation

char* hashsccssid = "@(#)hash.c 1.14 () 6/20/88"
 

Definition at line 27 of file hash.c.

Generated on Mon Nov 8 17:08:01 2004 for MPT by  doxygen 1.3.9.1