BSD tree

Overview

BSD tree 내용 정리.

Basic

BSD tree 는 Red-Black tree 를 손쉽게 사용할 수 있는 매크로들이 정리되어 있다.

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