| 1 | /*************************************************
|
|---|
| 2 | * libucp - Unicode Property Table handler *
|
|---|
| 3 | *************************************************/
|
|---|
| 4 |
|
|---|
| 5 | /* Internal header file defining the layout of compact nodes in the tree. */
|
|---|
| 6 |
|
|---|
| 7 | typedef struct cnode {
|
|---|
| 8 | unsigned short int f0;
|
|---|
| 9 | unsigned short int f1;
|
|---|
| 10 | unsigned short int f2;
|
|---|
| 11 | } cnode;
|
|---|
| 12 |
|
|---|
| 13 | /* Things for the f0 field */
|
|---|
| 14 |
|
|---|
| 15 | #define f0_leftexists 0x8000 /* Left child exists */
|
|---|
| 16 | #define f0_typemask 0x3f00 /* Type bits */
|
|---|
| 17 | #define f0_typeshift 8 /* Type shift */
|
|---|
| 18 | #define f0_chhmask 0x00ff /* Character high bits */
|
|---|
| 19 |
|
|---|
| 20 | /* Things for the f2 field */
|
|---|
| 21 |
|
|---|
| 22 | #define f2_rightmask 0xf000 /* Mask for right offset bits */
|
|---|
| 23 | #define f2_rightshift 12 /* Shift for right offset */
|
|---|
| 24 | #define f2_casemask 0x0fff /* Mask for case offset */
|
|---|
| 25 |
|
|---|
| 26 | /* The tree consists of a vector of structures of type cnode, with the root
|
|---|
| 27 | node as the first element. The three short ints (16-bits) are used as follows:
|
|---|
| 28 |
|
|---|
| 29 | (f0) (1) The 0x8000 bit of f0 is set if a left child exists. The child's node
|
|---|
| 30 | is the next node in the vector.
|
|---|
| 31 | (2) The 0x4000 bits of f0 is spare.
|
|---|
| 32 | (3) The 0x3f00 bits of f0 contain the character type; this is a number
|
|---|
| 33 | defined by the enumeration in ucp.h (e.g. ucp_Lu).
|
|---|
| 34 | (4) The bottom 8 bits of f0 contain the most significant byte of the
|
|---|
| 35 | character's 24-bit codepoint.
|
|---|
| 36 |
|
|---|
| 37 | (f1) (1) The f1 field contains the two least significant bytes of the
|
|---|
| 38 | codepoint.
|
|---|
| 39 |
|
|---|
| 40 | (f2) (1) The 0xf000 bits of f2 contain zero if there is no right child of this
|
|---|
| 41 | node. Otherwise, they contain one plus the exponent of the power of
|
|---|
| 42 | two of the offset to the right node (e.g. a value of 3 means 8). The
|
|---|
| 43 | units of the offset are node items.
|
|---|
| 44 |
|
|---|
| 45 | (2) The 0x0fff bits of f2 contain the signed offset from this character to
|
|---|
| 46 | its alternate cased value. They are zero if there is no such
|
|---|
| 47 | character.
|
|---|
| 48 |
|
|---|
| 49 |
|
|---|
| 50 | -----------------------------------------------------------------------------
|
|---|
| 51 | ||.|.| type (6) | ms char (8) || ls char (16) ||....| case offset (12) ||
|
|---|
| 52 | -----------------------------------------------------------------------------
|
|---|
| 53 | | | |
|
|---|
| 54 | | |-> spare |
|
|---|
| 55 | | exponent of right
|
|---|
| 56 | |-> left child exists child offset
|
|---|
| 57 |
|
|---|
| 58 |
|
|---|
| 59 | The upper/lower casing information is set only for characters that come in
|
|---|
| 60 | pairs. There are (at present) four non-one-to-one mappings in the Unicode data.
|
|---|
| 61 | These are ignored. They are:
|
|---|
| 62 |
|
|---|
| 63 | 1FBE Greek Prosgegrammeni (lower, with upper -> capital iota)
|
|---|
| 64 | 2126 Ohm
|
|---|
| 65 | 212A Kelvin
|
|---|
| 66 | 212B Angstrom
|
|---|
| 67 |
|
|---|
| 68 | Certainly for the last three, having an alternate case would seem to be a
|
|---|
| 69 | mistake. I don't know any Greek, so cannot comment on the first one.
|
|---|
| 70 |
|
|---|
| 71 |
|
|---|
| 72 | When searching the tree, proceed as follows:
|
|---|
| 73 |
|
|---|
| 74 | (1) Start at the first node.
|
|---|
| 75 |
|
|---|
| 76 | (2) Extract the character value from f1 and the bottom 8 bits of f0;
|
|---|
| 77 |
|
|---|
| 78 | (3) Compare with the character being sought. If equal, we are done.
|
|---|
| 79 |
|
|---|
| 80 | (4) If the test character is smaller, inspect the f0_leftexists flag. If it is
|
|---|
| 81 | not set, the character is not in the tree. If it is set, move to the next
|
|---|
| 82 | node, and go to (2).
|
|---|
| 83 |
|
|---|
| 84 | (5) If the test character is bigger, extract the f2_rightmask bits from f2, and
|
|---|
| 85 | shift them right by f2_rightshift. If the result is zero, the character is
|
|---|
| 86 | not in the tree. Otherwise, calculate the number of nodes to skip by
|
|---|
| 87 | shifting the value 1 left by this number minus one. Go to (2).
|
|---|
| 88 | */
|
|---|
| 89 |
|
|---|
| 90 |
|
|---|
| 91 | /* End of internal.h */
|
|---|
