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