Virtual table

A virtual table is a mechanism used in Programming languages to support dynamic polymorphism, i.e. run-time method binding.

Suppose a program contains several classes in an inheritance hierarchy: a superclass, Cat, and two subclasses, Tiger and HouseCat. Class Cat defines a method named "speak" but provides no implementation. Instead, its subclasses must provide an appropriate implementation (i.e. either meow or roar). In a compiled language such as C++, the run-time environment must be able to determine which version of the speak method to call through a base class pointer. This is called polymorphism on the programmer's side, but is implemented using virtual tables (a.k.a. vtables).

When a class is compiled, it also includes data and function pointers from its parent classes. In this example, a Tiger also includes everything a Cat does when compiled. However, the actual function code is not duplicated: rather, a pointer to the parent class code is included. This helps reduce code bloat and redundancy. When one calls a method through a derived class, it knows exactly where to find the relevant code. When one calls a method through the superclass, it does not necessarily know what code to execute for e.g. a virtual method (C++) or a non-final method (Java). Instead, the compiler creates a virtual table that is, essentially, a dispatch table: a table of pointers pointing to possible implementations.

If an object is referenced through a base-class pointer or reference at run-time, the program uses the virtual table to "look up" which method to call. This does incur a speed hit, however, as compilers mature they are better able to optimize virtual tables as well as the code that uses them.

Implementation Example

An object's dispatch table will contain the addresses of the object's dynamically bound methods. Method calls are performed by fetching the method's address from the object's dispatch table. The dispatch table is the same for all objects belonging to the same class, and is therefore typically shared between them. Objects belonging to type-compatible classes (for example siblings in an inheritance hierarchy) will have dispatch tables with the same layout: the address of a given method will appear at the same offset for all type-compatible classes. Thus, fetching the method's address from a given dispatch table offset will get the method corresponding to the object's actual class. (Ellis & Stroustrup 1990, pp. 227–232)

Consider the SymmetricAlgorithm and the BlockCipher abstract classes, as declared in the [OpenCL (http://opencl.sourceforge.net/)] cryptographic library:

class SymmetricAlgorithm : public Algorithm
   {
   public:
      virtual void set_key(const byte[], u32bit) throw(InvalidKeyLength) = 0;
      virtual bool valid_keylength(u32bit) const;
      SymmetricAlgorithm(const std::string&, u32bit, u32bit, u32bit);
   };

class BlockCipher : public SymmetricAlgorithm
   {
   public:
      virtual void encrypt(const byte[], byte[]) const = 0;
      virtual void decrypt(const byte[], byte[]) const = 0;
      virtual void encrypt(byte block[]) const = 0;
      virtual void decrypt(byte block[]) const = 0;
      BlockCipher(const std::string&, u32bit, u32bit, u32bit = 0, u32bit = 1);
      virtual ~BlockCipher() {}
   };

used to derive the following DES class:

class DES : public BlockCipher
   {
   public:
      void encrypt(const byte[BLOCKSIZE], byte[BLOCKSIZE]) const;
      void decrypt(const byte[BLOCKSIZE], byte[BLOCKSIZE]) const;
      void encrypt(byte block[BLOCKSIZE]) const;
      void decrypt(byte block[BLOCKSIZE]) const;
      void set_key(const byte[], u32bit = KEYLENGTH) throw(InvalidKeyLength);
      void clear() throw();
      DES() : BlockCipher(name(), BLOCKSIZE, KEYLENGTH);
   };

The corresponding virtual table will be:

OpenCL::DES virtual table:
	.long OpenCL::DES type_info function
	.long OpenCL::DES::clear(void)
	.long OpenCL::DES::~DES(void)
	.long OpenCL::DES::set_key(u_char const *, u_int)
	.long OpenCL::SymmetricAlgorithm::valid_keylength(u_int) const
	.long OpenCL::DES::encrypt(u_char const *, u_char *) const
	.long OpenCL::DES::decrypt(u_char const *, u_char *) const
	.long OpenCL::DES::encrypt(u_char *) const
	.long OpenCL::DES::decrypt(u_char *) const

Note how the valid_keylength method is inherited from the SymmetricAlgorithm class.

Now consider a DES sibling class TripleDES:

class TripleDES : public BlockCipher
   {
   public:
      void encrypt(const byte[BLOCKSIZE], byte[BLOCKSIZE]) const;
      void decrypt(const byte[BLOCKSIZE], byte[BLOCKSIZE]) const;
      void encrypt(byte block[BLOCKSIZE]) const;
      void decrypt(byte block[BLOCKSIZE]) const;
      void set_key(const byte[], u32bit = KEYLENGTH) throw(InvalidKeyLength);
      void clear() throw();
      TripleDES() : BlockCipher(name(), BLOCKSIZE, KEYLENGTH);
   };

This will implemented with a virtual table with exactly the same layout, but different contents:

OpenCL::TripleDES virtual table:
	.long OpenCL::TripleDES type_info function
	.long OpenCL::TripleDES::clear(void)
	.long OpenCL::TripleDES::~TripleDES(void)
	.long OpenCL::TripleDES::set_key(u_char const *, u_int)
	.long OpenCL::SymmetricAlgorithm::valid_keylength(u_int) const
	.long OpenCL::TripleDES::encrypt(u_char const *, u_char *) const
	.long OpenCL::TripleDES::decrypt(u_char const *, u_char *) const
	.long OpenCL::TripleDES::encrypt(u_char *) const
	.long OpenCL::TripleDES::decrypt(u_char *) const

Thus, method calls using a pointer to a SymmetricAlgorithm class will use the object's virtual table to fetch the method address corresponding to the object's type.

References

• Margaret A. Ellis and Bjarne Stroustrup (1990). The Annotated C++ Reference Manual. Reading, MA: Addison-Wesley. (ISBN 0201514591)