6.3 Hash tables

We use dynamic hash tables in the relocation tables to find a local off_id_t given a remote off_id_t.

The hash table uses a block allocator to keep the elements being hashed. Every entry in the table is actually a list of elements with the same hash value. It is a somewhat generic hash table for in-kernel use: The hashed element, the hash function, the element key, and the number of entries can be specified.

<Hash table. >= (U->)
// A dynamic hash table for El elements, using hash function Hasher,
// and Key as the element Key. It contains Nents entries.
//
template<class T, class Hasher, class Key, int nents>
class DHashTbl {
private:
  DLinkedList            h_entries[nents]; // Hash table entries (w/ ovf lists)
  Hasher                 h_hash;           // Hash function implementor
public:
  // Returns the number of entries.
  int get_nents(void) const { return nents; }

  <Other public methods of DHashTbl. >

};

Defines DHashTbl (links are to index).

<Hash table dependencies. >= (U->) [D->]
#include <assert.h>              // for assert.
#include <klib/dlist.h>          // for DLinkedList.

The important methods are lookup, insert and delete.

<Other public methods of DHashTbl. >= (U->)
// Looks up an element with the given key.
T *lookup(const Key &akey);

// Inserts the given element in the table.
void insert(T *el);

// Deletes the element with the given key.
void remove(const Key &el);

<Hash table dependencies. >+= (U->) [<-D]
#include <flux/types.h>         // for boolean_t natural_t et al.

<DHashTbl::lookup implementation. >= (U->)
// Looks up an entry and returns a pointer to it or NULL when not found.
template<class T, class Hasher, class Key, int nents>
T *DHashTbl<T,Hasher,Key,nents>::lookup(const Key &akey)
{ 
  DLinkedListItr itr(h_entries[h_hash.hash(akey)]);
  DLinkedListItr hd  = itr;

  if (itr.is_null())
    return FALSE;
  else {
    do {
      if (h_hash.match((T*)itr.get_element(),akey))
        return (T*)itr.get_element();
      ++itr;
    } while( itr != hd );
    return NULL;
  }
}

<DHashTbl::insert implementation. >= (U->)
// Inserts a new entry in the table. Returns zero if error.
template<class T, class Hasher, class Key, int nents>
void DHashTbl<T,Hasher,Key,nents>::insert( T *el) 
{
  assert(el);
  h_entries[h_hash.hash(el->get_key())].link_first(el);
}

<DHashTbl::remove implementation. >= (U->)
// Removes an entry from the table. 
template<class T, class Hasher, class Key, int nents>
void DHashTbl<T,Hasher,Key,nents>::remove(const Key &el) 
{
  DLinkedList *l=h_entries+h_hash.hash(el);
  DLinkedListItr itr(l);
  DLinkedListItr hd  = itr;
  assert(l);
  if (!itr.is_null()) {
    do {
      if (el == itr.get_element()->get_key()){
        unlink(itr);
        return;
      }
      ++itr;
    } while( itr != hd );
  }
}

\subsection{Hash tables \cpp{} source files}

The hash table declaration is kept in klib/dhash.h.

<dhash.h*>=
<Read the literate code instead warning. >
#ifndef __D_HASH_H
#define __D_HASH_H 1

<Hash table dependencies. >

#ifdef __KERNEL__
<Hash table. >
#endif // __KERNEL__

#endif // __D_HASH_H

#ifndef __D_HASH_C
#define __D_HASH_C 1

<DHashTbl::lookup implementation. >
<DHashTbl::insert implementation. >
<DHashTbl::remove implementation. >

#endif // __D_HASH_C

\section{Bitmaps}

This is a simple bitmap which can be used for resource allocation.

<Bitmap. >= (U->)
// A bitmap.
class Bitmap {
private:
  unsigned32_t *b_bits;
public:
  // Creates a bitmap.
  Bitmap(natural_t len);

  boolean_t get_bit(natural_t at) const {
    return ::test_bit(at, b_bits);
  };
  // Sets the bit and return its old value atomically. 
  boolean_t set_bit(natural_t at) {
    return ::set_bit(at,b_bits);
  }
  // Clears the bit and returns its old value atomically. 
  boolean_t clr_bit(natural_t at) {
    return ::clear_bit(at,b_bits);
  }
};

Defines Bitmap (links are to index).

This bitmap uses the \oskit{} bit operations.

<Bitmap dependencies. >= (U->)
#include <flux/types.h>          // for boolean_t natural_t et al.
#include <flux/machine/bitops.h> // for set_,clear_ and test_bit

<Bitmap::Bitmap implementation. >= (U->)
// Creates a bitmap.
Bitmap::Bitmap(natural_t len)
{
    natural_t nwords=len>>5;
    b_bits= new unsigned32_t[nwords];
    assert(b_bits);
    for (natural_t i=0; i<nwords; i++)
      b_bits[i]=0;
}

<Bitmap implementation dependencies. >= (U->)
#include <assert.h>

\subsection{Bitmaps \cpp{} source files}

It is all kept in klib/bmap.h and klib/bmap.C.

<bmap.h*>=
<Read the literate code instead warning. >
#ifndef __BITMAP_H
#define __BITMAP_H 1

<Bitmap dependencies. >

<Bitmap. >

#endif // __BITMAP_H

<bmap.C*>=
<Read the literate code instead warning. >

#include <klib/bmap.h>          // Exported interface.
<Bitmap implementation dependencies. >

<Bitmap::Bitmap implementation. >

\section{Simple output streams}

A simple stream class is provided for in-kernel use.

<Output stream. >= (U->)
// A very simple output stream.
//
class OStr {
  int using_hex;
  int raw_chars;
public:
  // Creates a simple output stream.
  OStr(void): using_hex(0), raw_chars(0) {}

  // Switch numeric output format
  void hex(void){using_hex=1;}
  void dec(void){using_hex=0;}

  // Prints the given string.
  virtual void print(const char *s)=0;
  // Prints the given number in hexa
  virtual void printh(const unsigned int  i)=0;
  // Prints the given number in dec
  virtual void printd(const unsigned int  i)=0;

  // Starts a new line.
  virtual void newline(void)=0;
  virtual OStr &operator<<(const char *s) { print(s); return *this; }
  virtual OStr &operator<<(const unsigned int i) {
    if (!raw_chars && i == '\n'){
        newline();
        return *this;
    }
    if (using_hex) printh(i); else printd(i);
    return *this;
  }

  <Other public methods of OStr. >
};

Defines OStr (links are to index).

A few related utilities are provided. First, to print new-lines, a dummy object is provided. OStr will recognize it and dump a newline.

<Output stream new line. >= (U->)
class OStrCtrl { public: char o_c; };
extern const OStrCtrl nl; // A new line.

<Output stream new line initializer. >= (U->)
const OStrCtrl nl= { '\n' };    // A new line.

<Other public methods of OStr. >= (<-U)
  virtual OStr &operator<<(const OStrCtrl c) {
    (void)c;
    newline();
    return *this;
  }

Second, utility routines to specify the way numbers are printed are provided. They return a formatted string which can be printed on an output stream.

<Output stream utilities. >= (U->)

// Returns a printable representation of the given number. 
extern inline char *fmt(const char *fs, const unsigned int n){
  static char buf[OFF_FMT_NSTR_MAX];
  sprintf(buf,fs,n);
  return buf;
}

Defines fmt (links are to index).

We now have OFF_FMT_NSTR_MAX as a new system limit.

<Off limits. >+= [<-D]
const int OFF_FMT_NSTR_MAX= 32;  // max length for a formatted number string.

Defines OFF_FMT_NSTR_MAX (links are to index).

<Console output stream dependencies. >= (U->) [D->]
#include <klib/limits.h>        // for OFF_FMT_NSTR_MAX

This concrete subclass uses the in-kernel printf routine to do its job.

<Console output stream. >= (U->)
// A very simple console output stream.
//
class ConsOStr : public OStr {
private:
  off_Lockable lock;
protected:
  // Prints the given string.
  void print(const char *s) { lock.w_lock(); printf("%s",s); lock.w_unlock();}
  // Starts a new line.
  virtual void newline(void) { printf("\n"); }
  // Prints the given number in hexa
  virtual void printh(const unsigned int  i) { 
    lock.w_lock(); printf("%08x",i); lock.w_unlock(); }
  // Prints the given number in dec
  virtual void printd(const unsigned int  i) { 
    lock.w_lock(); printf("%d",i); lock.w_unlock();}

};

Defines ConsOStr (links are to index).

<Console output stream dependencies. >+= (U->) [<-D]
#include <stdio.h>              // for printf et al
#include <klib/Lockable.h>      // for off_Lockable

There is a ConsOStr defined staticly. It is named kcout.