Other possible dispatch table formats

The first suggested format for the dispatch table was rather redundant. After some consultation with gcc, here are two dispatch routines to consider:

typedef struct{int sa; int cohash; void * what;} OC;
typedef struct{void * what; int arg;} Response;
typedef struct{int db; OC* dt[0];} hh;

Response disp(unsigned int oc, hh* ht){
  OC** opp = &ht->dt[oc >> ht->db];
  OC* op, *lp = *(opp+1);
  for(op = *opp; op < lp; ++op)
  {int tv = oc ^ op->cohash;
    if(!(tv >> (op->sa&63))) return (Response){op->what, tv};
  }
  return (Response){0, 0};
}

typedef struct{int sa; int cohash; void * what;} OC;
typedef struct{void * what; int arg;} Response;
typedef struct{int db; OC* dt[0];} hh;

Response disp(unsigned int oc, hh* ht){
  OC* op = ht->dt[oc >> ht->db];
  if(!op) goto fail;
l: {int ctl = op->sa, tv = oc ^ op->cohash;
    if(!(tv >> (ctl&63))) return (Response){op->what, tv};
    if(ctl < 0) {++op; goto l;}
   }
fail: return (Response){0, 0};
}

Sparc doesn't return structures very well and that detail should be changed somehow. I like the first routine as being easier to understand, more conventional and about the same speed. That routine presumes an array of OC values, whose name is not required by the code. I think it is about 20 cycles on a modern Sparc. If KCCP emits such code at the end of some construct that looks like a switch block, then no struct value needs to be returned and some of the passed values might be compile time constants.

Presuming this, the code emitted by KCPP might look more like:

typedef struct{int sa; int cohash; void * what;} OC;
...
int narg;
...
{
  static OC* ht[(1<<6)+1] = {..., ...};
  static OC dt[] = {{...,...,...} ...};
  OC** opp = dt[oc >> 18];
  OC* op, *lp = *(opp+1);
  for(op = *opp; op < lp; ++op)
  {narg = oc ^ op->cohash;
    if(!(narg >> (op->sa&63))) goto *op->what;
  }
  default error condition;
}

Now I will imagine input and corresponding output from KCPP to explore and illustrate this scheme.
Input:

{
  KSwitch(ocexp, Node, nde);
  void Make_type_Key(int type){};
  KCase(Fetch, 16): ...
  ...
  ...
  KCase(Swap, 16): ...
  ...
  ...
  KCase(ndeMake_Segment_Key): Make_type_Key(0);
  KCase(ndeMake_Meter_Key): Make_type_Key(1);
  KCase(ndeMake_Node_Key): Make_type_Key(2);
  KCase(ndeMake_Fetch_Key): Make_type_Key(3);

  KCase(Data_Byte): ...
  ...
  KDefault: ...
}

In the above "ocexp" is an expression providing the order code to be dispatched upon. "Node" is the string name of the type which enters into the hash calculation. "nde" is a prefix for generated symbols. This helps avoid name collision. The expansion of KCase and KDefault begins with a goto end of block that began this KSwitch.

Output:

{goto dispatch;{
  unsigned int __oc__ = ocexp, narg;
  void Make_type_Key(int type){...};
  ndeFetch: ...
  ...
  ...
  ndeSwap: ...
  ...
  ...
  ndeMake_Segment_Key: Make_type_Key(0); goto ndeend;
  ndeMake_Meter_Key: Make_type_Key(1); goto ndeend;
  ndeMake_Node_Key: Make_type_Key(2); goto ndeend;
  ndeMake_Fetch_Key: Make_type_Key(3); goto ndeend;

  ndeData_Bytex: ...
  ...
  ndeDefault: ...
  dispatch:
  {
    static OC dt[] = {
      {0, 0X138D7E22, &&ndeMake_Segment_Key},
      {0, 0x2B784A02, &&ndeSwap},
      {0, 0x374B23C0, &&ndeMake_Node_Key},
      {0, 0x806BE205, &&ndeMake_Fetch_Key},
      {0, 0x8FAF3E32, &&ndeData_Bytex},
      {4, 0xBBE1E0E4, &&ndeFetch},
      {0, 0xC9EB83B1, &&ndeMake_Meter_Key}};
    static OC* ht[] = {&dt[0], &dt[1], &dt[3], &dt[3], &dt[3],
           &dt[5], &dt[6], &dt[7], &dt[7]};

  OC** opp = &ht[__oc__ >> 29];
  OC* op, *lp = *(opp+1);
  for(op = *opp; op < lp; ++op){
    narg = __oc__ ^ op->cohash;
    if(!(narg >> (op->sa&63))) goto *op->what;
  }
  goto ndeDefault;
}}
ndeend:}

The logic of the dispatch code requires that the array dt of OC values be sorted by hash and the j'th entry of array ht locate the first element of the array dt whose hash is at least j << (32 - number of bits extracted from hash to form ht index).