Liren Large Software Subsidy 7/07.iso/c/c100/3.ddi/BRENT.ZIP/BRENT.CPP

Text File | 1990-09-27 | 11.4 KB | 421 lines

Brent's technique was invented R.P. Brent, a computer scientist and
mathematician, about whom I know little, other than his citations in Donald
Knuth's The Art of Computer Programming Volume 3: Sorting and Searching.  It
is a variation on the primary/secondary hashing technique Knuth calls
Algorithm D (SEE FIGURE 1).

************************* FIGURE 1 ********************************
Psuedocode for Algorithm D:

Define two mapping functions -- H1 and H2

INSERT IS
  address = H1(data)
  if table[address] is empty
    insert data in table[address]
  else
    address = H1(data) + H2(data)
    while table[address] isn't empty
      address = address + H2(data)
    end while
  end if
  insert data in table[address]

LOOKUP IS
  address = H1(data)
  if table[address] isn't equal to data then
    address = H1(data) + H2(data)
    while table[address] isn't equal to data and
      table[address] isn't empty
      address = address + H2(data)
    end while
  end if
  if table[address] is empty then
    return empty
  else
    return table[address]
  end if
************************* END FIGURE 1 ********************************

Brent's technique is a method for optimizing the time complexity of successful
LOOKUP operations.  For certain applications (notable compilers) the number of
successful LOOKUPS is overwhelmingly larger than the number of INSERTS. Brent's
technique works by spending more time inserting objects into the table, in
hopes of making the table better suited for LOOKUP. (SEE FIGURE 2)

************************* FIGURE 2 ********************************
Psuedocode for Brent's Technique:
INSERT IS
  address = H1(data)
  depth = 0
  while table[address] isn't empty
    address = address + H2(data)
    increment(depth)
  end while
  if depth < 2 then
    table[address] = data
  else
    address = H1(data)
    for i = 0 to depth
      address2 = address + H2(table[address])
      depth2 = 0
      while depth2 <= i and table[address2] isn't empty
        address2 = address + H2(table[address])
        increment(depth2)
      end while
      if depth2 <= i
        table[address2] = table[address]
        return
      end if
      address = address + H2(data)
    end for
    table[address] = data
  end if
  insert data in table[address]
************************* END FIGURE 2 ********************************

BRENT'S TECHNIQUE IN C++:

HASHTAB.HPP

#define DEBUG_HASHTAB
//
// hashtab.hpp -- class definition for hash table
class hashtab {
  size_t tablesize;                    // size of the table
  size_t inserted;                     // # of elements inserted
  void **table;                        // actual table
  size_t (*map)(void *element);        // map a key to the table index type
  int (*compare)(void *e1,void *e2);   // compare two elements a la strcmp
  size_t _lookup(void *element);       // internal lookup function
public:
  hashtab(size_t tablesize,
    size_t (*map)(void *element),
    int (*compare)(void *e1, void *e2));
  ~hashtab(void) {
    delete table;
  }
  void *lookup(void *element);
  void insert(void *element);
  void remove(void *element);
#if  defined(DEBUG_HASHTAB) && defined(__ZTC__)
  void dump_tab(void (*d)(void *e));
#endif
};


BRENT.CPP

#include <stdio.h>
#if !defined(__ZTC__)
#include <stream.h>
// Bad old unix doesn't have ansi headers
#define UINT_MAX ((unsigned)-1)
typedef unsigned size_t;  // should be correct most places.
#else
#include <stream.hpp>
#include <limits.h>
#endif
#include "hashtab.hpp"

//
// find_tabsize returns the next twin prime >= the desired table size
static size_t find_tabsize(size_t tabsize) {
//
// each element of primes is the lower twin of a twin prime.  The table
// also has the property that primes[i] >= (primes[i]+100) to keep the
// table size down.
  static unsigned primes[] = {
  5,107,227,347,461,569,809,1019,1151,1277,1427,1607,1721,
  1871,1997,2111,2237,2339,2549,2657,2789,2969,3119,3251,3359,
  3461,3581,3767,3917,4019,4127,4229,4337,4481,4637,4787,4931,
  5099,5231,5417,5519,5639,5741,5849,6089,6197,6299,6449,6551,
  6659,6761,6869,7127,7307,7457,7559,7757,7877,8009,8219,8387,
  8537,8819,8969,9239,9341,9461,9629,9767,9929,10037,10139,10271,
  10427,10529,10709,10859,11057,11159,11351,11489,11699,11831,11939,12041,
  12161,12377,12539,12821,13001,13217,13337,13679,13829,13931,14081,14249,
  14387,14549,14867,15137,15269,15581,15731,15887,16061,16187,16361,16631,
  16829,16979,17189,17291,17417,17579,17681,17789,17909,18041,18251,18521,
  18911,19079,19181,19379,19541,19697,19841,19961,20147,20357,20477,20639,
  20747,20897,21011,21191,21317,21491,21599,21737,21839,22037,22157,22271,
  22481,22619,22739,22859,22961,23201,23369,23537,23669,23831,24107,24371,
  24917,25031,25169,25301,25409,25577,25799,25931,26111,26249,26681,26861,
  27059,27239,27407,27527,27689,27791,27917,28097,28277,28409,28547,28661,
  29021,29129,29387,29567,29669,29879,30011,30137,30269,30389,30491,30839,
  31079,31181,31319,31511,31721,31847,
  };
#  define PTABSIZ  (sizeof(primes)/sizeof(size_t))

  int i;
  for(i = 0; i < PTABSIZ; i++)
    if(tabsize <= primes[i])
      return primes[i] + 2;
  cerr << "Table size too big!\n";
  exit(-1);
}

#define empty ((void *) 0)
#define deleted ((void *) -1)

//
// constructor for the hashtab class
hashtab::hashtab(size_t tablesize,
    size_t (*map)(void *element),
    int (*compare)(void *e1, void *e2)) {
  //
  // round up table size to nearest twin prime
  this->tablesize = find_tabsize(tablesize);
  //
  // allocate the table
  table = new void *[this->tablesize];
  if(table == NULL) {
    cerr << "Out of memory in hashtab constructor";
    exit(1);
  }
  //
  // clear the table
  for(int i = 0; i < this->tablesize; i++)
    table[i] = empty;
  //
  // store comparison and mapping functions
  this->map = map;
  this->compare = compare;
  //
  // clear insertion count
  inserted = 0;
}

//
// insert an element into the hash table, using brent's technique.
void hashtab::insert(void *element) {
  size_t mapped_val,h1,h2,cur,depth,i;
  size_t c2,cur2,depth2;

  //
  // test predicate for finding an empty slot in the table.
#  define VACANT(x) (table[(x)] == empty || table[(x)] == deleted)
  //
  // check for table full -- always leave at least
  // one empty slot in the table, or you'll search endlessly for
  // keys not in a full table!
  if(++inserted == tablesize) {
    cerr << "hash table full\n";
    exit(1);
  }
  //
  // map key to value, and do primary hash
  mapped_val = map(element);
  h1 = mapped_val % tablesize;
  //
  // secondary hash
  h2 = (mapped_val % (tablesize - 2)) + 1;
  //
  // compute depth of collision list
  for(cur = h1, depth = 0; !VACANT(cur); cur = (cur + h2) % tablesize) {
    //
    // if the element is already in the table then replace it and
    // return
    if(compare(element,table[cur]) == 0) {
      table[cur] = element;
      return;
    }
    depth++;
  }
  //
  // if we aren't too deep, just jam the element here.
  if(depth < 2) {
    table[cur] = element;
    return;
  }
  for(i = 0,cur = h1; i < depth; i++,cur = (h1+h2) % tablesize) {
    //
    // secondary hash of current element of collision list
    c2 = (map(table[cur]) % (tablesize - 2)) + 1;
    //
    // see if this table element would be displaced fewer
    // positions than the object being inserted.
    for(depth2 = 0,cur2 = (cur + c2) % tablesize;
      !VACANT(cur2) && depth2 <= i;
      depth2++,cur2 = (cur2 + c2) % tablesize)
      ;
    //
    // if we're still going to improve matters by inserting here
    if(depth2 <= i) {
      table[cur2] = table[cur];
      break;
    }
  }
  //
  // postcondition : cur is the index of an empty slot in which
  // to place element.
  table[cur] = element;
}

#define NOTFOUND (UINT_MAX)

//
// lookup function private to hashtab class.
size_t hashtab::_lookup(void *element) {
  size_t mapped_val,h1,h2,cur;
  //
  // map key to value, and do primary hash
  mapped_val = map(element);
  h1 = mapped_val % tablesize;
  //
  // secondary hash.
  h2 = (mapped_val % (tablesize - 2)) + 1;
  for(cur = h1;
    table[cur] != empty &&
    (table[cur] == deleted ? 1 : compare(element,table[cur]) != 0);
    cur = (cur + h2) % tablesize)
    ;
  return (table[cur] == empty ? NOTFOUND : cur);
}

//
// find an element in the table
void *hashtab::lookup(void *element) {
  size_t index = _lookup(element);
  return (index == NOTFOUND ? empty : table[index]);
}

//
// remove an element from the table.
void hashtab::remove(void *element) {
  int x;
  if(inserted-- == 0) {
    cerr << "deletion from empty hash table\n";
    exit(1);
  }
  x = _lookup(element);
  if(x != NOTFOUND)
    table[x] = deleted;
}

#if defined(DEBUG_HASHTAB) && defined(__ZTC__)
void hashtab::dump_tab(void (*display)(void *e)) {
  size_t i;
  for(i = 0; i < tablesize; i++) {
    if(table[i] == empty)
      cout << "empty";
    else if(table[i] == deleted)
      cout << "deleted";
    else
      display(table[i]);
    if (i && (i % 5 == 0))
      cout.put('\n');
    else
      cout.put(' ');
  }
  if (i % 5 == 0)
    cout.put('\n');
}
#endif


HASHTEST.CPP

//
// hashtest.cpp -- test generic hash table classes

#if !defined(__ZTC__)
#include <stream.h>
typedef unsigned size_t;  // should be correct most places.
#else
#include <stdio.h>    // to pull in size_t
#include <stream.hpp>
#endif

#include <ctype.h>
#include "hashtab.hpp"

size_t imap(void *element) {
  return *((int *)element);
}

int icompare(void *e1,void *e2) {
  if(*(int *)e1 > *(int *)e2)
    return 1;
  else if(*(int *)e1 == *(int *)e2)
    return 0;
  else
    return -1;
}

#if  defined(DEBUG_HASHTAB) && defined(__ZTC__)
void idisplay(void *e1) {
  cout << *(int *)e1;
}
#endif

class inthashtab : hashtab {
public:
  inthashtab(size_t size) : (size,imap,icompare) {}
  int *lookup(int x) {
    return (int *)hashtab::lookup((void *)&x);
  }
  void insert(int x) {
    int *ip = new int;
    *ip = x;
    hashtab::insert((void *)ip);
  }
  void remove(int x) {
    // get a pointer to the storage for this object,
    // so we can delete it.
    int *ip = (int *)hashtab::lookup((void *)&x);
    if(ip != NULL) {
      hashtab::remove((void *)ip);
      delete ip;
    }
  }
#if defined(DEBUG_HASHTAB)
  void dump_tab(void) {
    hashtab::dump_tab(idisplay);
  }
#endif
};

inthashtab inttab(4);

main() {
  char command;
  int *current;
  int i;
  while(!cin.eof()) {
    // prompt and pickup command
    cout << "i = insert l = lookup d = delete s = show table q = quit : ";
    eatwhite(cin);
    cin.get(command);
    // act upon commands
    switch(tolower(command)) {
    case 'i':
      // grab an integer
      cin >> i;
      inttab.insert(i);
      cout << i << " inserted.";
      break;
    case 'l':
      // grab an integer
      cin >> i;
      current = inttab.lookup(i);
      cout << i << " " <<
        (current == NULL  ? "isn't" : "is") << " in the table";
      break;
    case 'd':
      // grab an integer
      cin >> i;
      inttab.remove(i);
      cout << i << " deleted";
      break;
    case 'q':
      exit(0);
#if defined(DEBUG_HASHTAB) && defined(__ZTC__)
    case 's':
      inttab.dump_tab();
      break;
#endif
    }
    cout.put('\n');
  }
}