Previous Table of Contents Next


LISTING 15.7 L15-7.ASM

; C near-callable assembly function for inserting a new node in a
; linked list sorted by ascending order of the Value field. The list
; is circular; that is, it has a dummy node as both the head and the
; tail of the list. The dummy node is a sentinel, containing the
; largest possible Value field setting. Tested with TASM.
MAX_TEXT_LENGTH equ 100         ;longest allowed Text field
SENTINEL equ  32767             ;largest possible Value field
LinkNode struc
NextNode dw     ?
Value    dw     ?
Text     db     MAX_TEXT_LENGTH+1 dup(?)
;*** Any number of additional data fields may by present ***
LinkNode ends

        .model  small
        .code

; Inserts the specified node into a ascending-value-sorted linked
; list, such that value-sorting is maintained. Returns a pointer to
; the node after which the new node is inserted.
; C near-callable as:
; struct LinkNode *InsertNodeSorted(struct LinkNode *HeadOfListNode,
;      struct LinkNode *NodeToInsert)
parms   struc
        dw      2 dup (?)       ;pushed return address & BP
HeadOfListNode dw       ?       ;pointer to head node of list
NodeToInsert dw         ?       ;pointer to node to insert
parms   ends

        public  _InsertNodeSorted
_InsertNodeSorted proc  near
        push    bp
        mov     bp,sp                   ;point to stack frame
        push    si                      ;preserve register vars
        push    di
        mov     si,[bp].NodeToInsert    ;point to node to insert
        mov     ax,[si].Value           ;search value
        mov     di,[bp].HeadOfListNode  ;point to linked list in
                                        ; which to insert
SearchLoop:
        mov     bx,di                   ;advance to the next node
        mov     di,[bx].NextNode        ;point to following node
        cmp     [di].Value,ax           ;is the following node's
                                        ; value less than the value
                                        ; from the node to insert?
        jl      SearchLoop              ;yes, so continue searching
                                        ;no, so we have found our
                                        ; insert point
        mov     ax,[bx].NextNode        ;link the new node between
        mov     [si].NextNode,ax        ; the current node and the
        mov     [bx].NextNode,si        ; following node
        mov     ax,bx                   ;return pointer to node
                                        ; after which we inserted
        pop     di                      ;restore register vars
        pop     si
        pop     bp
        ret
_InsertNodeSorted endp
        end

LISTING 15.8 L15-8.C

/* Sample linked list program. Tested with Borland C++. */
#include <stdlib.h>
#include <stdio.h>
#include <conio.h>
#include <ctype.h>
#include <string.h>
#include “llist.h”

void main()
{ int Done = 0, Char, TempValue;
   struct LinkNode *TempPtr, *ListPtr, *TempPtr2;
   char TempBuffer[MAX_TEXT_LENGTH+3];

   if ((ListPtr = InitLinkedList()) == NULL) {
       printf(“Out of memory\n”);
       exit(1);
   }
   while (!Done) {
      printf(“\nA=add; D=delete; F=find; L=list all; Q=quit\n>”);
      Char = toupper(getche());
      printf(“\n”);
      switch (Char) {
         case 'A':               /* add a node */
            if ((TempPtr = malloc(sizeof(struct LinkNode))) == NULL)
            {
               printf(“Out of memory\n  );
               exit(1);
             }
            printf(“Node value: ”);
            scanf(“%d”, &TempPtr->Value);
            if ((FindNodeBeforeValue(ListPtr,TempPtr->Value))!=NULL)
            {  printf(“*** value already in list; try again ***\n”);
               free(TempPtr);
            } else {printf(“Node text: ”);
               TempBuffer[0] = MAX_TEXT_LENGTH;
               cgets(TempBuffer);
               strcpy(TempPtr->Text, &TempBuffer[2]);
               InsertNodeSorted(ListPtr, TempPtr);
               printf(“\n”);
            }
            break;
         case 'D':               /* delete a node */
            printf(“Value field of node to delete: ”);
            scanf(“%d”, &TempValue);
            if ((TempPtr = FindNodeBeforeValue(ListPtr, TempValue))
                 != NULL) {
               TempPtr2 = TempPtr->NextNode; /* -> node to delete */
               DeleteNodeAfter(TempPtr);     /* delete it */
               free(TempPtr2);               /* free its memory */
            } else {
               printf(“*** no such value field in list ***\n”)
            break;
         case 'F':               /* find a node */
            printf(“Value field of node to find: ”);
            scanf(“%d”, &TempValue);
            if ((TempPtr = FindNodeBeforeValue(ListPtr, TempValue))
                  != NULL)
               printf(“Value: %d\nText: %s\n”,
                 TempPtr->NextNode->Value, TempPtr->NextNode->Text);
            else
               printf(“*** no such value field in list ***\n”);
            break;
         case 'L':               /* list all nodes */
            TempPtr = ListPtr->NextNode;  /* point to first node */
            if (TempPtr == ListPtr) {     /* empty if at sentinel */
               printf(“*** List is empty ***\n”);
            } else {
               do {printf(“Value: %d\n  Text: %s\n”, TempPtr->Value,
                        TempPtr->Text);
                  TempPtr = TempPtr->NextNode;
               } while (TempPtr != ListPtr);
            }
            break;
         case 'Q':
            Done = 1;
            break;
         default:
            break;
      }
   }
}

Hi/Lo in 24 Bytes

In one of my PC TECHNIQUES “Pushing the Envelope” columns, I passed along one of David Stafford’s fiendish programming puzzles: Write a C-callable function to find the greatest or smallest unsigned int. Not a big deal—except that David had already done it in 24 bytes, so the challenge was to do it in 24 bytes or less.

Such routines soon began coming at me from all angles. However (and I hate to say this because some of my correspondents were very pleased with the thought that they had bested David), no one has yet met the challenge—because most of you folks missed a key point. When David said, “Write a function to find the greatest or smallest unsigned int in 24 bytes or less,” he meant, “Write the hi and the lo functions in 24 bytes or less—combined.”

Oh.

Yes, a 24-byte hi/lo function is possible, anatomically improbable as it might seem. Which I guess goes to show that when one of David’s puzzles seems less than impossible, odds are you’re missing something. Listing 15.9 is David’s 24-byte solution, from which a lot may be learned if one reads closely enough.

LISTING 15.9 L15-9.ASM

; Find the greatest or smallest unsigned int.
; C callable (small model); 24 bytes.
; By David Stafford.
; unsigned hi( int num, unsigned a[] );
; unsigned lo( int num, unsigned a[] );

                public _hi, _lo

_hi:            db      0b9h            ;mov cx,immediate
_lo:            xor     cx,cx
                pop     ax              ;get return address
                pop     dx              ;get count
                pop     bx              ;get pointer
                push    bx              ;restore pointer
                push    dx              ;restore count
                push    ax              ;restore return address
save:           mov     ax,[bx]
top:            cmp     ax,[bx]
                jcxz    around
                cmc
around:         ja      save
                inc     bx
                inc     bx
                dec     dx
                jnz     top

                ret

Before I end this chapter, let me say that I get a lot of feedback from my readers, and it’s much appreciated. Keep those cards, letters, and email messages coming. And if any of you know Jeannie Schweigert, have her drop me a line and let me know how she’s doing these days....


Previous Table of Contents Next

Graphics Programming Black Book © 2001 Michael Abrash