1 files changed, 167 insertions, 0 deletions
diff --git a/sys/gty/gtyindex.x b/sys/gty/gtyindex.x
new file mode 100644
index 00000000..b91456ca
--- /dev/null
+++ b/sys/gty/gtyindex.x
@@ -0,0 +1,167 @@
+# Copyright(c) 1986 Association of Universities for Research in Astronomy Inc.
+
+include	<syserr.h>
+include	<chars.h>
+include	"gty.h"
+
+# GTY_INDEX_CAPS -- Prepare an index into the caplist string, stored in
+# the tty descriptor.  Each two character capability name maps into a unique
+# integer code, called the capcode.  We prepare a list of capcodes, keeping
+# only the first such code encountered in the case of multiple entries.
+# The offset of the capability in the caplist string is associated with each
+# capcode.  When these lists have been prepared, they are sorted to permit
+# a binary search for capabilities at runtime.
+
+procedure gty_index_caps (tty, t_capcode, t_capindex, ncaps)
+
+pointer	tty
+int	t_capcode[ARB], t_capindex[ARB]
+int	ncaps
+
+pointer	ip, caplist
+int	i, swap, capcode, temp
+int	gty_encode_capability()
+pointer	coerce()
+errchk	syserr
+
+begin
+	caplist = coerce (tty + T_OFFCAP, TY_STRUCT, TY_CHAR)
+	ip = caplist
+
+	# Scan the caplist and prepare the capcode and capindex lists.
+	for (ncaps=0;  ncaps <= MAX_CAPS;  ) {
+	    # Advance to the next capability field.  Normal exit occurs
+	    # when ':' is followed immediately by EOS.
+
+	    while (Memc[ip] != ':' && Memc[ip] != EOS)
+		ip = ip + 1
+	    if (Memc[ip+1] == EOS || Memc[ip] == EOS)
+		break
+
+	    ip = ip + 1					# skip the ':'
+	    capcode = gty_encode_capability (Memc[ip])
+
+	    # Is the capcode already in the list?  If not found, add it to
+	    # the list.
+	    for (i=1;  i <= ncaps && t_capcode[i] != capcode;  i=i+1)
+		;
+	    if (i > ncaps) {				# not found
+		ncaps = ncaps + 1
+		t_capcode[ncaps] = capcode
+		t_capindex[ncaps] = ip - caplist + 1
+	    }
+	}
+
+	if (ncaps > MAX_CAPS)
+	    call syserr (SYS_TTYOVFL)
+
+	# A simple interchange sort is sufficient here, even though it would
+	# not be hard to interface to qsort.  The longest termcap entries are
+	# about 50 caps, and the time req'd to sort such a short list is
+	# negligible compared to the time spent searching the termcap file.
+
+	if (ncaps > 1)
+	    repeat {
+		swap = 0
+		do i = 1, ncaps-1
+		    if (t_capcode[i] > t_capcode[i+1]) {
+			temp = t_capcode[i]
+			t_capcode[i] = t_capcode[i+1]
+			t_capcode[i+1] = temp
+			temp = t_capindex[i]
+			t_capindex[i] = t_capindex[i+1]
+			t_capindex[i+1] = temp
+			swap = 1
+		    }
+	    } until (swap == 0)
+end
+
+
+# GTY_FIND_CAPABILITY -- Search the caplist for the named capability.
+# If found, return the char pointer IP to the first char of the value field,
+# and YES as the function value.  If the first char in the capability string
+# is '@', the capability "is not present".
+
+int procedure gty_find_capability (tty, cap, ip)
+
+pointer	tty			# tty descriptor
+char	cap[ARB]		# two character name of capability
+pointer	ip			# pointer to capability string
+
+int	capcode, capnum
+int	gty_binsearch(), gty_encode_capability()
+pointer	coerce()
+errchk	syserr
+
+begin
+	if (tty == NULL)
+	    call syserr (SYS_TTYINVDES)
+
+	capcode = gty_encode_capability (cap)
+	capnum = gty_binsearch (capcode, T_CAPCODE(tty), T_NCAPS(tty))
+
+	if (capnum > 0) {
+	    # Add 2 to skip the two capname chars.
+	    ip = coerce (tty + T_OFFCAP, TY_STRUCT, TY_CHAR) +
+		T_CAPINDEX(tty+capnum-1) - 1 + 2
+	    if (Memc[ip] != '@')
+		return (YES)
+	}
+
+	return (NO)
+end
+
+
+# GTY_BINSEARCH -- Perform a binary search of the capcode array for the
+# indicated capability.  Return the array index of the capability if found,
+# else zero.
+
+int procedure gty_binsearch (capcode, t_capcode, ncaps)
+
+int	capcode
+int	t_capcode[ARB], ncaps
+int	low, high, pos, ntrips
+define	err_ 91
+
+begin
+	pos = 0
+	low = 1
+	high = ncaps
+	if (high < low)
+	    goto err_
+
+	# Cut range of search in half until code is found, or until range
+	# vanishes (high - low <= 1).  If neither high or low is the one,
+	# code is not found in the list.
+
+	do ntrips = 1, ncaps {
+	    pos = (high - low) / 2 + low
+	    if (t_capcode[low] == capcode)
+		return (low)
+	    else if (t_capcode[high] == capcode)
+		return (high)
+	    else if (pos == low)			# (high-low)/2 == 0
+		return (0)				# not found
+	    else if (t_capcode[pos] < capcode)
+		low = pos
+	    else
+		high = pos
+	}
+
+	# Search cannot fail to converge unless there is a bug in the software
+	# somewhere.
+err_
+	call syserr (SYS_TTYBINSRCH)
+end
+
+
+# GTY_ENCODE_CAPABILITY -- Encode the two character capability string
+# as a unique integer value.
+
+int procedure gty_encode_capability (cap)
+
+char	cap[ARB]
+
+begin
+	return (ENCODE(cap))
+end