BSD tree

Overview

BSD tree 내용 정리.

Basic

BSD tree 는 Red-Black tree 및 Splay tree 를 손쉽게 사용할 수 있는 매크로들이 정리되어 있다. BSD tree 소스 최신본은 이곳<ref>https://svnweb.freebsd.org/base/head/sys/sys/tree.h</ref>에서 다운받을 수 있다.

RB Macros

RB_INITIALIZER

typedef struct StrList StrList; This typedef basically defines a name which will be used to refer to the tree. Some of the macros in tree.h require this name as a parameter.

typedef struct StrListNode StrListNode; The StrListNode type defines our custom structure to store our data. It must contain an `entry' member with a type of RB_ENTRY(StrListNode). The name that you choose for the `entry' member must be provided to the tree generation macro.

static int StrListNode_compar(StrListNode *a, StrListNode *b); This function defines a comparator for objects of type StrListNode. It should work similarly to the compar function provided to bsearch(3) and qsort(3). Normally, the comparator function should return 0 if the objects are equal, and in this case, the tree macros will not re-insert that item. However, in the program listing, I have slightly abused this rule in order to force duplicate strings to be stored in the tree. A more robust implementation would probably instead store a counter along as part of the StrListNode and simply increment the counter when a duplicate string is encountered.

RB_HEAD(StrList, StrListNode) StrListHead = RB_INITIALIZER(&StrListHead); RB_GENERATE_STATIC(StrList, StrListNode, entry_, StrListNode_compar); These two lines will generate the struct(s) and function(s) which allow tree.h to do its magic. The name StrListHead is defined here, which will be needed for some macro calls. For compatibility purposes, I have used the RB_GENERATE_STATIC version of the macro in order to limit visibility of this tree structure to file scope.

StrListNode *sln = malloc(sizeof *sln + (n+1)); Allocate a new node which will store a string of length n. In this particular case, I am adding n+1 to the size of the node in order to allow the flexible struct member to store a character string with a string lenth of n characters. A pre-C99 implementation would instead create a struct hack member of 1 byte in size, and then allocate (sizeof *sln + n) bytes, which should be enough to hold the n bytes of the string plus the null terminator.

RB_INSERT(StrList, &StrListHead, sln); Insert the object pointed to by sln into our StrList headed by StrListHead.

for (sln = RB_MIN(StrList, &StrListHead); sln != NULL; sln = RB_NEXT(StrList, &StrListHead, sln)) Implement an idiomatic "foreach-style loop". The call to RB_MIN returns a pointer to the smallest member, and the call to RB_NEXT advances the pointer to the next item. At the end of the list, the pointer will contain NULL. There is also a RB_FOREACH macro which simplifies this notation. However, in my tests I noticed that the above version performs better. In addition, the above notation, although a bit lengthy in terms of typing out the symbol names, is easy to follow logically.

Sample

<source lang=c>

#include <stdio.h>  
#include <stdlib.h>  
#include <string.h>  
#include <sys/tree.h>  
#define MAXLINE 1000  
/******************************************************************************/  
typedef struct StrList StrList;  
typedef struct StrListNode StrListNode;  
  
struct StrListNode {  
    RB_ENTRY(StrListNode) entry_;  
    char buf[];  
};  
static int StrListNode_compar(StrListNode *a, StrListNode *b) {  
    char *akey = a->buf;  
    char *bkey = b->buf;  
    int r;  
    if ((r = strcmp(akey, bkey)) == 0)  
        return 1; // force duplicate strings to be stored   
    return r;  
}  
RB_HEAD(StrList, StrListNode) StrListHead = RB_INITIALIZER(&StrListHead);  
RB_GENERATE_STATIC(StrList, StrListNode, entry_, StrListNode_compar);  
/******************************************************************************/  
  
#define fatal(...) do{\  
    printf("Fatal error: ");\  
    printf(__VA_ARGS__);\  
    exit(EXIT_FAILURE);\  
}while(0)  
  
static char buf[MAXLINE];  
  
// Read strings from stdin and print them in order  
int main(int argc, char *argv[])  
{  
    if (argc != 1) {  
        printf("Syntax: mysort\n");  
        (void)argv;  
        exit(EXIT_SUCCESS);  
    }  
      
    // Read integers into StrList headed by StrListHead  
    StrListNode *sln;  
    while ((fgets(buf, sizeof(buf), stdin)) != NULL) {  
        size_t n = strlen(buf);  
        if ((sln = malloc(sizeof *sln + n + 1)) == NULL) {  
            fatal("memory allocation error\n");  
        }  
        strcpy(sln->buf, buf);  
        RB_INSERT(StrList, &StrListHead, sln);  
    }  
    if (!(feof(stdin))) {  
        fatal("error reading from stdin\n");  
    }  
      
    // Start from the lowest string and print keys in order  
    for (sln = RB_MIN(StrList, &StrListHead); sln != NULL; sln = RB_NEXT(  
            StrList, &StrListHead, sln))   
    {  
        printf("%s", sln->buf);  
    }  
  return EXIT_SUCCESS;  
}  

</source>

See also

• http://privatemisc.blogspot.dk/2013/02/freebsd-treeh-example.html - FreeBSD tree.h Example