home *** CD-ROM | disk | FTP | other *** search
- /*
- klex.c
-
- % Keyboard scancode lexical scanning code.
-
- VMS OWL DIG
- Copyright (c) 1990 by Oakland Group, Inc.
- ALL RIGHTS RESERVED.
-
- Revision History:
- -----------------
- 6/1/90 bkd Created (on SunOS).
- 6/6/90 bkd Ansi-fied (on VAX/VMS).
- 6/12/90 bkd Renamed from kparse to klex.
- 7/12/90 bkd Removed retro.h include.
- 7/19/90 bkd Undefined KLEX_DEBUG, changed OA_NOTAG to OA_KLEX,
- changed include "bt.h" to "btree.h"
- 9/12/90 bkd Removed comment that choked de-ansifier.
- 9/24/90 jsm Added cast for C++
- */
-
- #include "oakhead.h"
- #include "disppriv.h"
- #include "digutil.h"
-
- /* #define KLEXDEBUG */
-
- #ifdef KLEXDEBUG
- #include <stdio.h>
- #endif
-
- #define BPB 8 /* Bits per byte */
- #define NUMBYTES 0x100 /* How many unique bytes there are */
- #define MAXSTACK 10 /* STACK SIZE */
-
- #define KEY_SECONDARY 0x01 /* Key has secondaries attached */
- #define KEY_TERMINAL 0x02 /* Key can be terminal */
-
- struct keyinfo {
- byte in_byte; /* Byte read */
- byte flags;
- struct keyinfo *previous; /* Previous key */
- scancode_type scode; /* Scancode here */
- btree_type secondary; /* Secondary bytes */
- };
-
- typedef struct klex {
- /* Front-line map */
- union {
- scancode_type map_scode;
- struct keyinfo *map_kinfo;
- } primary_map[NUMBYTES];
- byte primary_secondary[NUMBYTES/BPB]; /* Bitmap */
- /* Scancode stack: */
- scancode_type scode_stack[MAXSTACK];
- int ss_head;
- int ss_tail;
- int ss_depth; /* Scancode stack head, tail and depth */
- /* Input state information */
- struct keyinfo *kstate;
- } *klexp_type;
-
- #define NELEM(x) (sizeof((x)) / sizeof((x)[0]))
-
- #define LOGBPB 3 /* 2 ^ LOGBPB = BPB */
- #define MASKBPB 0x7 /* x & MASKBPB = x % BPB */
-
- #define ISBITSET(bm, bnum) ( *((byte *)(bm) + ((bnum) >> LOGBPB)) & \
- (byte) (1 << ((bnum) & MASKBPB)))
- #define ISBITCLR(bm, bnum) (( *((byte *)(bm) + ((bnum) >> LOGBPB)) & \
- (byte) (1 << ((bnum) & MASKBPB))) == 0)
- #define SETBIT(bm, bnum) ( *((byte *)(bm) + ((bnum) >> LOGBPB)) |= \
- (byte) (1 << ((bnum) & MASKBPB)))
- #define CLRBIT(bm, bnum) ( *((byte *)(bm) + ((bnum) >> LOGBPB)) &= \
- (byte) ~ ((byte) \
- (1 << ((bnum) & MASKBPB))))
-
- #define KLEXPSCODE(kl, bn) ((kl)->primary_map[bn].map_scode)
- #define KLEXPKINFO(kl, bn) ((kl)->primary_map[bn].map_kinfo)
-
- OSTATIC btree_nodecomp_func(klex_Compare);
- OSTATIC btree_keycomp_func(klex_KeyCompare);
- OSTATIC btree_freertn_func(klex_Free);
- OSTATIC scancode_type DIGPRIV klex_MakeScode(byte b);
- OSTATIC int DIGPRIV klex_TreeAddCode(btree_type bt, struct keyinfo *prev,
- byte *seq, int seqlen, scancode_type code);
- OSTATIC void DIGPRIV klex_StackAppend(klexp_type kl, scancode_type scode);
- OSTATIC scancode_type DIGPRIV klex_StackPop(klexp_type kl);
- OSTATIC void DIGPRIV klex_TreeUnroll(klexp_type kl, struct keyinfo *ki);
-
- /***************************************** ANCILLARY CODE ********************/
- /*
- Ancillary code: None of these routines are called directly.
-
- klex_Compare, klex_KeyCompare and klex_Free are used
- in the btree that stores the lexicon tables.
- */
-
-
- /*
- These next three routines are used by the btree code. They
- are associated with the btree in the btree_Open calls in the
- klex_AddCode below.
- */
-
- static int klex_Compare(VOID *kinfo1, VOID *kinfo2)
- {
- return((int) (((struct keyinfo *) kinfo1)->in_byte -
- ((struct keyinfo *) kinfo2)->in_byte));
- }
-
- static int klex_KeyCompare(VOID *kinfo, byte *key)
- {
- return((int) (((struct keyinfo *) kinfo)->in_byte - *key));
- }
-
- static void klex_Free(VOID *kinfo)
- {
- if ((((struct keyinfo *) kinfo)->flags & KEY_SECONDARY) != 0) {
- btree_Close(((struct keyinfo *) kinfo)->secondary);
- }
- ofree(OA_KLEX, kinfo);
- }
- /***************************************** INTERNAL CODE *********************/
-
- /*
- Default byte->scode mapper. Used to establish the initial map
- if no default is specified.
- */
-
- static scancode_type DIGPRIV klex_MakeScode(byte b)
- {
- return((scancode_type) b);
- }
-
-
- static int DIGPRIV klex_TreeAddCode(
- btree_type bt,
- struct keyinfo *prev,
- byte *seq,
- int seqlen,
- scancode_type code)
- /*
- This is a recursive subroutine of klex_AddCode. It is used only internally.
- */
- {
- register struct keyinfo *kinfo;
-
- if (bt == NULL || seq == NULL) { /* SHOULDN'T HAPPEN */
- #ifdef KLEXDEBUG
- fprintf(stderr, "klex_TreeAddCode: bt or seq is NULL.\n");
- #endif /* KLEXDEBUG */
- return(-1);
- }
-
- if (seqlen == 0) { /* SHOULDN'T HAPPEN */
- return(0);
- }
-
- kinfo = (struct keyinfo *) btree_Get(bt, seq);
-
-
- if (kinfo == NULL) {
- kinfo = (struct keyinfo *) omalloc(OA_KLEX,
- sizeof(struct keyinfo));
-
- if (kinfo == NULL) {
- #ifdef KLEXDEBUG
- fprintf(stderr,
- "klex_TreeAddCode: couldn't allocate kinfo.\n");
- #endif /* KLEXDEBUG */
- return(-1);
- }
-
- kinfo->in_byte = *seq;
- kinfo->previous = prev;
-
- if (btree_Insert(bt, kinfo) != BTREE_OK) {
- ofree(OA_KLEX, kinfo);
- #ifdef KLEXDEBUG
- fprintf(stderr,
- "klex_TreeAddCode: error inserting into btree.\n");
- #endif /* KLEXDEBUG */
- return(-1);
- }
-
- if (seqlen == 1) {
- kinfo->scode = code;
- kinfo->flags = KEY_TERMINAL;
-
- return(0);
- }
- else {
- if ((bt = btree_Open(klex_Compare, klex_KeyCompare,
- klex_Free)) == NULL) {
- ofree(OA_KLEX, kinfo);
- #ifdef KLEXDEBUG
- fprintf(stderr,
- "klex_TreeAddCode: couldn't open new btree #1.\n");
- #endif /* KLEXDEBUG */
- return(-1);
- }
-
- kinfo->secondary = bt;
- kinfo->flags = KEY_SECONDARY;
-
- return(klex_TreeAddCode(bt, kinfo, seq + 1, seqlen - 1, code));
- }
-
- }
- else {
- if (seqlen == 1) {
- /* If KEY_TERMINAL is already set, than there is
- an ambiguity */
- kinfo->scode = code;
- kinfo->flags |= KEY_TERMINAL;
-
- return(0);
- }
- else {
- if ((kinfo->flags & KEY_SECONDARY) != 0) {
- return(klex_TreeAddCode(
- kinfo->secondary, kinfo,
- seq + 1, seqlen - 1, code));
- }
- else {
- if ((bt = btree_Open(klex_Compare,
- klex_KeyCompare,
- klex_Free)) == NULL) {
- #ifdef KLEXDEBUG
- fprintf(stderr,
- "klex_TreeAddCode: couldn't open new btree #2.\n");
- #endif /* KLEXDEBUG */
- return(-1);
- }
-
- kinfo->secondary = bt;
- kinfo->flags |= KEY_SECONDARY;
-
- return(klex_TreeAddCode(bt, kinfo,
- seq + 1, seqlen - 1, code));
- }
- }
- }
- /* NOTREACHED */
- }
-
-
- static void DIGPRIV klex_StackAppend(klexp_type kl, scancode_type scode)
- /*
- Used to manipulate the scancode "stack" (it's really a ring buffer).
- */
- {
- if (kl->ss_depth >= MAXSTACK) {
- return; /* ERROR CONDITION UNFLAGGED */
- }
-
- kl->scode_stack[kl->ss_tail++] = scode;
-
- if (kl->ss_tail >= MAXSTACK) {
- kl->ss_tail -= MAXSTACK;
- }
- kl->ss_depth++;
- }
-
-
- static scancode_type DIGPRIV klex_StackPop(klexp_type kl)
- /*
- Used to manipulate the scancode "stack" (it's really a ring buffer).
- */
- {
- scancode_type scode;
-
- if (kl->ss_depth <= 0) {
- #ifdef KLEXDEBUG
- fprintf(stderr, "klex_StacKop: popping from empty stack.\n");
- #endif /* KLEXDEBUG */
- return((scancode_type) 0); /* ERROR CONDITION UNFLAGGED */
- }
-
- scode = kl->scode_stack[kl->ss_head++];
- kl->ss_depth--;
-
- if (kl->ss_depth == 0) {
- kl->ss_head = kl->ss_tail = 0;
- }
- else {
- if (kl->ss_head >= MAXSTACK) {
- kl->ss_head -= MAXSTACK;
- }
- }
-
- return(scode);
- }
-
- static void DIGPRIV klex_TreeUnroll(klexp_type kl, struct keyinfo *ki)
- /*
- klex_TreeUnroll - This routine will:
- 1) Roll backward from the current keyinfo to find the
- first "terminal." It will then push that scancode
- on the stack.
- 2) Reset the state machine to the "base state."
- 3) Feed the extra bytes back into the state machine, using
- klex_InByte.
-
- This routine is a little nasty because it calls klex_InByte, which
- can call TreeUnroll. Totally nasty.
- */
- {
- if (ki == NULL) { /* Shouldn't happen */
- #ifdef KLEXDEBUG
- fprintf(stderr, "klex_TreeUnroll: ki is NULL.\n");
- #endif /* KLEXDEBUG */
- return;
- }
-
- if ((ki->flags & KEY_TERMINAL) != 0) {
- klex_StackAppend(kl, ki->scode);
- kl->kstate = NULL;
- }
- else {
- klex_TreeUnroll(kl, ki->previous);
- klex_InByte(kl, ki->in_byte);
- }
- }
-
- /***************************************** PUBLIC CODE ***********************/
-
- /*
- klex_Open - Create a new klex object,
- prepare the klex lexicon table to accept definitions,
- initialize the klex state machine and the scancode stack.
- */
-
- klex_type DIGPRIV klex_Open(scancode_type *def_map)
- {
- register int i;
- register klexp_type kl;
-
- if ((kl = (klexp_type) omalloc(OA_KLEX, sizeof(* (klexp_type) 0)))
- == NULL) {
- #ifdef KLEXDEBUG
- fprintf(stderr, "klex_Open: couldn't allocate klex.\n");
- #endif /* KLEXDEBUG */
- return(NULL);
- }
-
- if (def_map != NULL) {
- for (i = 0; i < NELEM(kl->primary_map); i++) {
- KLEXPSCODE(kl, i) = *def_map++;
- }
- }
- else {
- for (i = 0; i < NELEM(kl->primary_map); i++) {
- KLEXPSCODE(kl, i) = (scancode_type)
- klex_MakeScode((byte) i);
- }
- }
-
- /* Reset the bitmap */
- for (i = 0; i < NELEM(kl->primary_secondary); i++) {
- kl->primary_secondary[i] = (byte) 0;
- }
- kl->kstate = NULL; /* Reset */
-
- kl->ss_head = kl->ss_tail = kl->ss_depth = 0;
-
- return((klex_type) kl);
- }
-
- void DIGPRIV klex_Close(klex_type klp)
- /*
- Closes out a klex and return its storage to the heap.
- */
- {
- register int i;
- register klexp_type kl;
-
- kl = (klexp_type) klp;
-
- if (kl == NULL) {
- #ifdef KLEXDEBUG
- fprintf(stderr, "klex_Close: kl is NULL.\n");
- #endif /* KLEXDEBUG */
- return;
- }
-
- /* Go through the bitmap, find all secondary entries and zap 'em */
-
- for (i = 0; i < NELEM(kl->primary_map); i++) {
- if (ISBITSET(kl->primary_secondary, i)) {
- if ((KLEXPKINFO(kl, i)->flags & KEY_SECONDARY) != 0) {
- btree_Close(KLEXPKINFO(kl, i)->secondary);
- }
- ofree(OA_KLEX, KLEXPKINFO(kl, i));
- }
- }
-
- /* Now zap the thing itself */
-
- ofree(OA_KLEX, kl);
- }
-
-
- int DIGPRIV klex_AddCode(klex_type klp, byte *seq, int seqlen, scancode_type code)
- /*
- Defines a mapping between a given sequence of bytes and a scancode.
- */
- {
- register byte firstbyte;
- register struct keyinfo *kinfo;
- register btree_type bt;
- register int retval;
- register klexp_type kl;
-
- kl = (klexp_type) klp;
-
- if (kl == NULL || seq == NULL) {
- #ifdef KLEXDEBUG
- fprintf(stderr, "klex_AddCode: kl or seq is NULL.\n");
- #endif /* KLEXDEBUG */
- return(-1);
- }
-
- if (seqlen <= 0) {
- #ifdef KLEXDEBUG
- fprintf(stderr, "klex_AddCode: seqlen <= 0.\n");
- #endif /* KLEXDEBUG */
- return(-1);
- }
-
- firstbyte = *seq;
-
- if (ISBITSET(kl->primary_secondary, firstbyte)) {
- kinfo = KLEXPKINFO(kl, firstbyte);
-
- /* kinfo shouldn't be NULL */
-
- /* Single byte sequence */
- if (seqlen == 1) {
- kinfo->scode = code;
- kinfo->flags |= KEY_TERMINAL;
- /* (SHOULD ALREADY BE SET) */
-
- }
- /* Multi-byte sequence: */
- else {
- return(klex_TreeAddCode(kinfo->secondary, kinfo,
- seq + 1, seqlen - 1, code));
- }
- }
- else {
- if (seqlen == 1) {
- KLEXPSCODE(kl, firstbyte) = code;
- }
- else {
- if ((kinfo = (struct keyinfo *) omalloc(OA_KLEX,
- sizeof(struct keyinfo)))
- == NULL) {
- #ifdef KLEXDEBUG
- fprintf(stderr,
- "klex_AddCode: couldn't allocate new kinfo.\n");
- #endif /* KLEXDEBUG */
- return(-1);
- }
-
- if ((bt = btree_Open(klex_Compare,
- klex_KeyCompare,
- klex_Free)) == NULL) {
- ofree(OA_KLEX, kinfo);
- #ifdef KLEXDEBUG
- fprintf(stderr,
- "klex_AddCode: couldn't open new btree.\n");
- #endif /* KLEXDEBUG */
- return(-1);
- }
-
- kinfo->previous = NULL;
- kinfo->in_byte = firstbyte;
- kinfo->secondary = bt;
- kinfo->scode = KLEXPSCODE(kl, firstbyte);
- kinfo->flags = KEY_SECONDARY | KEY_TERMINAL;
-
- retval = klex_TreeAddCode(bt, kinfo,
- seq + 1, seqlen - 1, code);
- if (retval != 0) {
- btree_Close(bt);
- ofree(OA_KLEX, kinfo);
- return(retval);
- }
-
- KLEXPKINFO(kl, firstbyte) = kinfo;
- SETBIT(kl->primary_secondary, firstbyte);
- }
- }
- return(0);
- }
-
- /*
- The following three routines: klex_InByte, klex_ShouldTimeOut and
- klex_TimeOut are the extent of interaction with a given OS.
-
- klex_InByte - When a byte is read from the input stream,
- klex_InByte is called to register its receipt. This
- routine resets the state of the "state machine" and
- (possibly) sticks a scancode on the stack for reading.
- klex_TimeOut - This is called by the OS code after a read
- completed that yielded a timeout. Note that this
- routine will ALWAYS reset the state machine to its
- base state.
- klex_ShouldTimeOut - This routine should be called by the OS
- specific code before starting a read. It returns a boolean:
- whether or not to start a timeout timer on the next
- read. This information is gathered by looking at the
- current state.
-
- So, in short, the routines klex_InByte and klex_TimeOut are used
- for declaring state information from the OS and the klex_ShouldTimeOut
- routine is a question of the current state.
- */
-
-
- void DIGPRIV klex_InByte(klex_type klp, byte b)
- {
- register struct keyinfo *kinfo;
- byte btmp;
- register klexp_type kl;
-
- kl = (klexp_type) klp;
-
- if (kl == NULL) {
- #ifdef KLEXDEBUG
- fprintf(stderr, "klex_InByte: kl is NULL.\n");
- #endif /* KLEXDEBUG */
- return;
- }
-
- if (kl->kstate == NULL) {
- if (ISBITCLR(kl->primary_secondary, b)) {
- klex_StackAppend(kl, KLEXPSCODE(kl, b));
- }
- else {
- kl->kstate = KLEXPKINFO(kl, b);
-
- /* BELOW SHOULDN'T HAPPEN */
- if ((kl->kstate->flags & KEY_SECONDARY) == 0) {
- #ifdef KLEXDEBUG
- fprintf(stderr,
- "klex_InByte: warning, kstate is NULL & no secondaries.\n");
- #endif /* KLEXDEBUG */
- klex_StackAppend(kl, kl->kstate->scode);
- kl->kstate = NULL;
- }
- }
- }
- else {
- /* kstate->flags should have KEY_SECONDARY set AND
- kstate->secondary should be valid */
-
- btmp = b;
- if ((kinfo = (struct keyinfo *) btree_Get(
- kl->kstate->secondary,
- &btmp)) == NULL) {
- /* This is an "error" state. A byte has been
- received that wasn't on the guest list. */
- klex_TreeUnroll(kl, kl->kstate);
- klex_InByte(kl, b); /* Try again */
- }
- else {
- if ((kinfo->flags & KEY_SECONDARY) == 0) {
- klex_StackAppend(kl, kinfo->scode);
- kl->kstate = NULL;
- }
- else {
- kl->kstate = kinfo;
- }
- }
- }
- }
-
- void DIGPRIV klex_TimeOut(klex_type klp)
- {
- register klexp_type kl;
-
- kl = (klexp_type) klp;
-
- if (kl == NULL) {
- #ifdef KLEXDEBUG
- fprintf(stderr, "klex_TimeOut: kl is NULL.\n");
- #endif /* KLEXDEBUG */
- return;
- }
-
- if (kl->kstate != NULL) {
- if ((kl->kstate->flags & KEY_TERMINAL) != 0) {
- klex_StackAppend(kl, kl->kstate->scode);
- kl->kstate = NULL;
- }
- else {
- klex_TreeUnroll(kl, kl->kstate);
- klex_TimeOut(kl);
- }
- }
- }
-
- boolean DIGPRIV klex_ShouldTimeOut(klex_type klp)
- {
- register klexp_type kl;
-
- kl = (klexp_type) klp;
-
- if (kl == NULL) {
- #ifdef KLEXDEBUG
- fprintf(stderr, "klex_ShouldTimeOut: kl is NULL.\n");
- #endif /* KLEXDEBUG */
- return(FALSE);
- }
- else if (kl->kstate == NULL) {
- return(FALSE);
- }
- else {
- if ((kl->kstate->flags & (KEY_SECONDARY | KEY_TERMINAL))
- == (KEY_SECONDARY | KEY_TERMINAL)) {
- return(TRUE);
- }
- else {
- return(FALSE);
- }
- }
- }
-
-
- /*
- There are two routines provided for getting scancodes.
-
- klex_ScanCodeReady - This routine asks whether or not there is
- scancode ready for reading, either on the stack or
- in the state machine.
- klex_ReadScanCode - This routine pops a scancode off the stack
- or from the state machine.
- */
-
- scancode_type DIGPRIV klex_ReadScanCode(klex_type klp)
- {
- return(klex_StackPop((klexp_type) klp));
- }
-
- boolean DIGPRIV klex_ScanCodeReady(klex_type klp)
- {
- return(((klexp_type) klp)->ss_depth > 0);
- }
-
-