This is the mail archive of the gcc@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Efficiently encoding a hierarchy


(I don't follow this list regularly, but ran into the GIMPLE tuples
proposal and had a suggestion.  Apologies if you were already aware of
this technique.)

The proposed tuple structure has the fields "code" and "subcode".  My
reading of its intent is to allow a simple two-level hierarchy of types.
Another way to encode a hierarchy is to use only a single "code" field
and associate each type with a range of IDs.  For example:

- A (0,5)
  - B (1,1)
  - C (2,4)
    - D (3,3) 
    - E (4,4)
  - F (5,5)
- G (6,7)
  - H (7,7)

A given instance is of type "C" if its "code" field is between 2 and 4,
inclusive.

Advantages of this approach:
- the type hierarchy can be as deep as you like
- checking the exact type is a single comparison
- the subtype check is only two comparisons.
- the ID range is used efficiently (one ID per type)

However, if your hierarchy is really only two levels deep, then the
code/subcode approach has some advantages:
- the subtype check is a single comparison
- you can do a C "switch" on non-leaf types as well

- Kannan


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]