/* * Copyright 1995, 1996 Perforce Software. All rights reserved. * * This file is part of Perforce - the FAST SCM System. */ # define NEED_SLEEP # include # include # include # include # include # include # include "objhashmap.h" ObjectHashMap::ObjectHashMap( int size ) { // Force size to be reasonable: switch( size ) { default: size = SMALL; // fall-through... case EXTRA_SMALL: case SMALL: case MEDIUM: case LARGE: case EXTRA_LARGE: tableSize = size; break; } numObjects = 0; table = new ObjectHashBucket[ tableSize ]; memset( table, 0, tableSize * sizeof( ObjectHashBucket ) ); } ObjectHashMap::~ObjectHashMap() { Clear(); delete []table; } void ObjectHashMap::Clear() { for( int i = 0; i < tableSize; i++ ) { ObjectHashBucket *b = &table[ i ]; ObjectHashTableEntry *hte = b->head, *hteNext; while( hte ) { hteNext = hte->next; delete hte; hte = hteNext; } b->head = 0; } numObjects = 0; } void ObjectHashMap::DumpSummary() { int n = 0; p4debug.printf("Summary of hashmap with %d objects\n", numObjects); for( int i = 0; i < tableSize; i++ ) { ObjectHashBucket *b = &table[ i ]; ObjectHashTableEntry *hte = b->head; while( hte ) { n++; StrBuf shaBuf; hte->sha1.Fmt( shaBuf ); p4debug.printf("Obj %d: %s @%p\n", n, shaBuf.Text(), hte->object ); hte = hte->next; } } } int ObjectHashMap::Contains( const Sha1 &sha ) { return Get( sha ) != 0; } int ObjectHashMap::Contains( const unsigned char *sha ) { return Get( sha ) != 0; } void * ObjectHashMap::Get( const Sha1 &sha ) { return Get( sha.data ); } void * ObjectHashMap::Get( const unsigned char *sha ) { ObjectHashBucket *b = Bucket( sha ); ObjectHashTableEntry *hte = b->head; while( hte ) { int cmp = hte->Compare( sha ); if( !cmp ) return hte->object; if( cmp > 0 ) return 0; hte = hte->next; } return 0; } int ObjectHashMap::Put( const Sha1 &sha, void *object ) { if( numObjects >= MAX_OBJECTS ) return 0; ObjectHashBucket *b = Bucket( sha ); ObjectHashTableEntry *hte = b->head; ObjectHashTableEntry *last = 0; while( hte ) { int cmp = hte->Compare( sha ); if( !cmp ) return 0; // already exists, can't add if( cmp > 0 ) { // The new object goes immediately before this one: ObjectHashTableEntry *e = new ObjectHashTableEntry; e->sha1 = sha; e->object = object; e->next = hte; e->prev = hte->prev; if( !last ) b->head = e; else last->next = e; hte->prev = e; CheckForResize(); return 1; } last = hte; hte = hte->next; } // The new object goes at the end of the chain: ObjectHashTableEntry *e = new ObjectHashTableEntry; e->sha1 = sha; e->object = object; e->next = 0; e->prev = last; if( !last ) b->head = e; else last->next = e; CheckForResize(); return 1; } void * ObjectHashMap::Remove( const Sha1 &sha ) { ObjectHashBucket *b = Bucket( sha ); ObjectHashTableEntry *hte = b->head; while( hte ) { int cmp = hte->Compare( sha ); if( !cmp ) { void *result = hte->object; if( hte->next ) hte->next->prev = hte->prev; if( hte->prev ) hte->prev->next = hte->next; else b->head = hte->next; delete hte; numObjects--; return result; } if( cmp > 0 ) return 0; hte = hte->next; } return 0; } int ObjectHashMap::Size() { return numObjects; } void ObjectHashMap::CheckForResize() { ++numObjects; if( tableSize == EXTRA_SMALL && numObjects == EXTRA_SMALL ) Resize( SMALL ); else if( tableSize == SMALL && numObjects == SMALL ) Resize( MEDIUM ); else if( tableSize == MEDIUM && numObjects == MEDIUM ) Resize( LARGE ); else if( tableSize == LARGE && numObjects == LARGE ) Resize( EXTRA_LARGE ); } void ObjectHashMap::Resize( int newSize ) { // allocate a new table // copy all the objects to the new table // clear and delete the old table // use the new table ObjectHashBucket *newTable = new ObjectHashBucket[ newSize ]; memset( newTable, 0, newSize * sizeof( ObjectHashBucket ) ); for( int i = 0; i < tableSize; i++ ) { ObjectHashBucket *b = &table[ i ]; ObjectHashTableEntry *hte = b->head; while( hte ) { PutInNewTable( hte, newTable, newSize ); hte = hte->next; } } int oCount = numObjects; Clear(); delete []table; table = newTable; tableSize = newSize; numObjects = oCount; } ObjectHashBucket * ObjectHashMap::Bucket( const Sha1 &sha ) { return Bucket( tableSize, table, sha.data ); } ObjectHashBucket * ObjectHashMap::Bucket( int sz, ObjectHashBucket *tb, const unsigned char *sha ) { int bucketNo; switch( sz ) { case EXTRA_SMALL: // 8 bits bucketNo = sha[0]; break; case SMALL: // 12 bits bucketNo = ( sha[0] << 4 ) | ( ( sha[1] >> 4 ) & 0x0f ) ; break; case MEDIUM: // 16 bits bucketNo = ( sha[0] << 8 ) | sha[1]; break; case LARGE: // 18 bits bucketNo = ( sha[0] << 10 ) | ( sha[1] << 2 ) | ( ( sha[2] >> 6 ) & 0x03 ) ; break; case EXTRA_LARGE: // 20 bits bucketNo = ( sha[0] << 12 ) | ( sha[1] << 4 ) | ( ( sha[2] >> 4 ) & 0x0f ) ; break; } return tb + bucketNo; } void ObjectHashMap::PutInNewTable( ObjectHashTableEntry *o, ObjectHashBucket *newTable, int newSize ) { ObjectHashBucket *b = Bucket( newSize, newTable, o->sha1.data ); ObjectHashTableEntry *hte = b->head; ObjectHashTableEntry *last = 0; while( hte ) { int cmp = hte->Compare( o->sha1 ); if( !cmp ) return; // (can't happen, since old table contained no dups) if( cmp > 0 ) { // The new object goes immediately before this one: ObjectHashTableEntry *e = new ObjectHashTableEntry; e->sha1 = o->sha1; e->object = o->object; e->next = hte; e->prev = hte->prev; if( !last ) b->head = e; else last->next = e; hte->prev = e; return; } last = hte; hte = hte->next; } // The new object goes at the end of the chain: ObjectHashTableEntry *e = new ObjectHashTableEntry; e->sha1 = o->sha1; e->object = o->object; e->next = 0; e->prev = last; if( !last ) b->head = e; else last->next = e; } /***********************************************************************/ int ObjectHashMapIterator::Next( Sha1 &sha, void **object ) { if( entry && entry->next ) { entry = entry->next; sha = entry->sha1; *object = entry->object; return 1; } while( 1 ) { bucketNo++; if( bucketNo >= map->tableSize ) return 0; ObjectHashBucket *b = map->table + bucketNo; if( b->head ) { entry = b->head; sha = entry->sha1; *object = entry->object; return 1; } } }