Table of Contents

About

This is a small program that will print out any files or directories starting with a path supplied by the command-line arguments. The program makes partial use of a Wizardry and Steamworks string-queue implementation for AmigaOS.

In order to compile using SAS/C, issue:

sc link breadthTraversal.c

After that, you can issue for example:

breadthTraversal RAM:

which will result in output similar to:

Specified path: RAM:
Dirs: RAM:T
Dirs: RAM:Clipboards
File: RAM:Disk.info
Dirs: RAM:T/UCC
Dirs: RAM:T/FMS
File: RAM:T/AmiTCP.log
File: RAM:T/FMS/Unit4
File: RAM:T/FMS/Unit3
File: RAM:T/FMS/Unit2
File: RAM:T/FMS/Unit1
File: RAM:T/FMS/Unit0

Related

Code

breadthTraversal.c
/*************************************************************************/
/*    Copyright (C) 2015 Wizardry and Steamworks - License: GNU GPLv3    */
/*************************************************************************/
/*                                                                       */
/*  breadthTraversal                                                     */
/*                                                                       */
/*  Traverses a directory path breadth-first starting from an initial    */
/*  user-supplied path.                                                  */
/*                                                                       */
/*  This program uses a queue implementation for Amiga OS found at:      */
/*  http://grimore.org/amiga/development/data_structures/queues/strings  */
/*                                                                       */
/*  Amiga OS using SAS/C and issuing: sc link breadthTraversal.c         */
/*                                                                       */
/*************************************************************************/
 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <setjmp.h>
 
#include <proto/exec.h>
#include <proto/dos.h>
 
/*************************************************************************/
/*          Wizardry and Steamworks' string queue implementation.        */
/*************************************************************************/
 
/* The stringQueue structure with front being the index of the front-mode
 * element and rear being the index of the last element in the queue
 */
typedef struct {
    ULONG size;
    UBYTE **store;
    ULONG front, rear;
} stringQueue;
 
/*
 * Creates a new stringQueue with a given size.
 */
stringQueue* stringQueueCreate(ULONG size) {
    stringQueue *q = (stringQueue*)AllocMem(
        sizeof(stringQueue), 
        MEMF_ANY|MEMF_CLEAR
    );
    if ((q->store = 
        (UBYTE**)AllocMem(
            size * sizeof(UBYTE **), 
            MEMF_ANY|MEMF_CLEAR
        )) == NULL) return NULL;
    q->size = size;
    q->front = 0;
    q->rear = 0;
    return q;
}
 
/*
 * Takes as parameter a stringQueue and returns 1 if the queue is empty or 
 * 0 if the queue is not empty.
 */
BOOL stringQueueIsEmpty(stringQueue *q) {
    return (BOOL)(q->rear == q->front);
}
 
/*
 * Enqueues an element to the stringQueue.
 */
void stringQueueEnqueue(stringQueue *q, UBYTE *e) {
    UBYTE **qStore;
    if (q->rear > q->size - 1) { // realloc for AmigaOS
        qStore = (UBYTE **)AllocMem(
            (q->size + 1) * sizeof(UBYTE **), 
            MEMF_ANY|MEMF_CLEAR
        );
        CopyMem(q->store, qStore, q->size * sizeof(UBYTE **));
        FreeMem(q->store, sizeof(q->store));
        q->store = qStore;
        ++q->size;
    }
    q->store[q->rear] = (UBYTE*)AllocMem(
        strlen(e) * sizeof(UBYTE *) + 1, 
        MEMF_ANY|MEMF_CLEAR
    );
    CopyMem(e, q->store[q->rear], strlen(e) * sizeof(UBYTE *) + 1);
    ++q->rear;
}
 
/*
 * Dequeues an element from the stringQueue or returns NULL in case the
 * queue is empty.
 */
UBYTE *stringQueueDequeue(stringQueue *q) {
    UBYTE *e;
    if (stringQueueIsEmpty(q))
        return NULL;
    e = (UBYTE *)AllocMem(
        strlen(q->store[q->front]) * sizeof(UBYTE *) + 1, 
        MEMF_ANY|MEMF_CLEAR
    );
    CopyMem(
        q->store[q->front], 
        e, 
        strlen(q->store[q->front]) * sizeof(UBYTE *) + 1
    );
    ++q->front;
    return e;
}
 
/*
 * Prints out the elements of the stringQueue.
 */
void stringQueuePrint(stringQueue *q) {
    ULONG i;
    if (stringQueueIsEmpty(q)) {
        Printf("Queue is empty.\n");
        return;
    }
    Printf("Elements in the queue: ");
    i = q->front;
    do {
        Printf("%s ", q->store[i]);
    } while (++i < q->rear);
    Printf("\n");
}
 
/*************************************************************************/
/*        Version string used for querying the program version.          */
/*************************************************************************/
GLOBAL TEXT version_string[] = 
  "\0$VER: breadthTraversal 1.0 (29 Jul 2015) by Wizardry and Steamworks";
 
/*************************************************************************/
/*              Amiga OS command-line arguments parameters.              */
/*************************************************************************/
STATIC CONST TEXT template[] = "PATH/A";
enum {
    PATH,
    NUM_ARGS
};
 
/*************************************************************************/
/*    Traverses a queue of paths and prints out files and directories.   */
/*************************************************************************/
LONG TraversePath(stringQueue *dirQueue) {
    struct FileInfoBlock *FIB = NULL;
    UBYTE *path;
    BPTR lock = NULL;
    UBYTE *nextPath;
    ULONG nextSize;
    jmp_buf env;
    LONG error;
 
    /* jump: Free any resources before returning an error. */
    error = setjmp(env);
    if(error != 0) {
        /* Free the file information block. */
        if(FIB != NULL) FreeDosObject(DOS_FIB, FIB);
        /* Release the lock. */
        if(lock != NULL) UnLock(lock);
        /* And return the error. */
        return error;
    }
 
    /* The directory queue is empty so return. */
    if(stringQueueIsEmpty(dirQueue))
        return 0;
 
    /* Dequeue the first lined-up element in the queue. */
    path = stringQueueDequeue(dirQueue);
 
    /* Lock the path. */
    if((lock = Lock(path, ACCESS_READ)) == NULL) {
        Printf("Unable to acquire a read lock to the specified path.\n");
        longjmp(env, RETURN_ERROR);
    }
 
    /* Create a new file information block to scan the path. */
    if((FIB = (struct FileInfoBlock *)
        AllocDosObject(DOS_FIB, NULL)) == NULL) {
        Printf("Unable to allocate file information block.\n");
        longjmp(env, RETURN_ERROR);
    }
 
    if(Examine(lock, FIB)) {
        /* Examine the rest of the entries in the directory. */
        while(ExNext(lock, FIB)) {
            /* check for Ctrl-C */
            if(CheckSignal(SIGBREAKF_CTRL_C) != FALSE)
                longjmp(env, RETURN_WARN);
            nextSize = strlen(path) + 
                strlen(FIB->fib_FileName) * 
                sizeof(UBYTE *) + 1;
            if((nextPath = (UBYTE*)
                AllocMem(nextSize, MEMF_ANY|MEMF_CLEAR)) == NULL) {
                Printf("Unable to allocate memory for path.\n");
                longjmp(env, RETURN_ERROR);
            }
            CopyMem(path, nextPath, nextSize);
            if(AddPart(nextPath, FIB->fib_FileName, nextSize) == FALSE) {
                Printf("Unable to add the file to the path.\n");
                longjmp(env, RETURN_ERROR);
            }
            /* Check whether the path is a file or a directory. */
            switch(FIB->fib_DirEntryType > 0) {
                case TRUE: // We have a directory.
                    Printf("Dirs: %s\n", nextPath);
 
                    // So we enqueue it.
                    stringQueueEnqueue(dirQueue, nextPath);
 
                    break;
                default: // We have a file.
                    Printf("File: %s\n", nextPath);
                    break;
            }
        }
    }
 
    /* Free the file information block. */
    if(FIB != NULL) FreeDosObject(DOS_FIB, FIB);
 
    /* Release the lock. */
    if(lock != NULL) UnLock(lock);
 
    /* DEBUG: print the queue. */
    /* stringQueuePrint(dirQueue); */
 
    /* Recurse over the queue till it is empty. */
    return TraversePath(dirQueue);
}
 
/*************************************************************************/
/*                          Program entry.                               */
/*************************************************************************/
int main(int argc, char **argv) {
    stringQueue *dirQueue = NULL;
    struct FileInfoBlock *FIB = NULL;
    BPTR lock = NULL;
    LONG size;
    jmp_buf env;
    LONG error;
 
    /* Setup command-line arguments to retrieve path.*/
    LONG *arg_array;
    struct RDArgs *rdargs;
    UBYTE *path;
 
    /* jump: Free any resources before returning an error. */
    error = setjmp(env);
    if(error != 0) {
        /* Free the file information block. */
        if(FIB != NULL) FreeDosObject(DOS_FIB, FIB);
        /* Release the lock. */
        if(lock != NULL) UnLock(lock);
        /* And return the error. */
        return error;
    }
 
    /* Allocate memory for arg array. */
    if((arg_array = AllocMem(NUM_ARGS, MEMF_ANY|MEMF_CLEAR)) == NULL) {
        Printf("Unable to allocate memory for command-line arguments.\n");
        longjmp(env, RETURN_ERROR);
    }
 
    /* Read command-line arguments */
    if((rdargs = ReadArgs(template, arg_array, NULL)) == NULL) {
        FreeArgs(rdargs);
        longjmp(env, RETURN_ERROR);
    }
    /* Allocate memory for the path name as the product between the lengh 
     * of the path name and the size of UBYTE plus a termination character. 
     */
    size = strlen((STRPTR)arg_array[PATH]) * sizeof(UBYTE) + 1;
    /* Allocate memory for path name. */
    if((path = AllocMem(size, MEMF_ANY|MEMF_CLEAR)) == NULL) {
        Printf("Unable to allocate memory for path name.\n");
        longjmp(env, RETURN_ERROR);
    }
    /* Copy path name to be able to free the command-line arguments. */
    CopyMem((STRPTR)arg_array[PATH], path, size);
    FreeArgs(rdargs);
 
    Printf("Specified path: %s\n", path);
 
    /* Lock the path. */
    if((lock = Lock(path, ACCESS_READ)) == NULL) {
        Printf("Unable to acquire a read lock to the specified path.\n");
        longjmp(env, RETURN_ERROR);
    }
 
    /* Create a new file information block to scan the path. */
    if((FIB = (struct FileInfoBlock *)
        AllocDosObject(DOS_FIB, NULL)) == NULL) {
        Printf("Unable to allocate file information block.\n");
        longjmp(env, RETURN_ERROR);
    }
 
    /* Attempt to examine the path. */
    if(!Examine(lock, FIB)) {
        Printf("Unable to examine %s\n", path);
        longjmp(env, RETURN_ERROR);
    }
 
    /* If the specified path is a file bail out. */
    if(FIB->fib_DirEntryType < 0) {
        Printf("Specified path is a file.\n");
        longjmp(env, RETURN_ERROR);
    }
 
    /* Free the file information block. */
    if(FIB != NULL) FreeDosObject(DOS_FIB, FIB);
 
    /* Release the lock. */
    if(lock != NULL) UnLock(lock);
 
    /* Allocate a new queue. */
    dirQueue = stringQueueCreate(1);
    /* Enqueue the specified path. */
    stringQueueEnqueue(dirQueue, path);
 
    /* Now traverse the path and return any errors. */
    return TraversePath(dirQueue);
}

amiga/development/algorithms/path_traversal/breadth-first.txt ยท Last modified: 2022/04/19 08:28 by 127.0.0.1

Access website using Tor Access website using i2p Wizardry and Steamworks PGP Key


For the contact, copyright, license, warranty and privacy terms for the usage of this website please see the contact, license, privacy, copyright.