欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

trie 树 的代码

程序员文章站 2022-06-03 18:09:57
...
想起搜狐老大的一句话
看代码先看h文件,擦,当初感觉他这句话很2,现在想想,诶。

代码摘自
shellinabox
// trie.h -- Basic implementation of a trie abstract data type

#ifndef TRIE_H__
#define TRIE_H__

#include "libhttp/http.h"

struct Trie {
  void       (*destructor)(void *, char *);
  void        *arg;
  char        *key;
  char        *value;
  int         idx;
  char        ch;
  struct Trie *children;
  int         numChildren;
};

struct Trie *newTrie(void (*destructor)(void *, char *), void *arg);
void initTrie(struct Trie *trie, void (*destructor)(void *, char *),
                 void *arg);
void destroyTrie(struct Trie *trie);
void deleteTrie(struct Trie *trie);
void addToTrie(struct Trie *trie, const char *key, char *value);
char *getFromTrie(const struct Trie *trie, const char *key, char **diff);

#endif /* TRIE_H__ */



// trie.c -- Basic implementation of a trie abstract data type

#include "config.h"

#include <stdlib.h>
#include <string.h>

#include "libhttp/trie.h"
#include "logging/logging.h"

struct Trie *newTrie(void (*destructor)(void *, char *), void *arg) {
  struct Trie *trie;
  check(trie = malloc(sizeof(struct Trie)));
  initTrie(trie, destructor, arg);
  return trie;
}

void initTrie(struct Trie *trie, void (*destructor)(void *, char *),
              void *arg) {
  trie->destructor  = destructor;
  trie->arg         = arg;
  trie->key         = NULL;
  trie->value       = NULL;
  trie->idx         = -1;
  trie->ch          = '\000';
  trie->children    = NULL;
  trie->numChildren = 0;
}

void destroyTrie(struct Trie *trie) {
  if (trie) {
    free(trie->key);
    for (int i = 0; i < trie->numChildren; i++) {
      if (trie->destructor && !trie->children[i].ch) {
        trie->destructor(trie->arg, trie->children[i].value);
      } else {
        check(!trie->children[i].value);
      }
      destroyTrie(&trie->children[i]);
    }
    free(trie->children);
  }
}

void deleteTrie(struct Trie *trie) {
  destroyTrie(trie);
  free(trie);
}

static void addLeafToTrie(struct Trie *trie, char ch, const char *key, int len,
                          void *value) {
  check (len >= 0);
  if (len) {
    check(trie->key     = malloc(len));
    memcpy(trie->key, key, len);
  } else {
    trie->key           = NULL;
  }
  trie->value           = NULL;
  trie->idx             = len;
  trie->ch              = ch;
  check(trie->children  = malloc(sizeof(struct Trie)));
  trie->numChildren     = 1;
  initTrie(trie->children, trie->destructor, trie->arg);
  trie->children->value = value;
}

void addToTrie(struct Trie *trie, const char *key, char *value) {
  if (trie->numChildren == 0) {
    addLeafToTrie(trie, '\000', key, strlen(key), value);
  } else {
 nextNode:;
    int len                       = strlen(key);
    for (int i = 0; i < trie->idx; i++) {
      if (key[i] != trie->key[i]) {
        struct Trie *child;
        check(child               = malloc(2*sizeof(struct Trie)));
        child->destructor         = trie->destructor;
        child->arg                = trie->arg;
        check(child->key          = malloc(trie->idx - i - 1));
        memcpy(child->key, trie->key + i + 1, trie->idx - i - 1);
        child->value              = trie->value;
        child->idx                = trie->idx - i - 1;
        child->ch                 = trie->key[i];
        child->children           = trie->children;
        child->numChildren        = trie->numChildren;
        trie->value               = NULL;
        trie->idx                 = i;
        trie->children            = child;
        trie->numChildren         = 2;
        child++;
        child->destructor         = trie->destructor;
        child->arg                = trie->arg;
        if (key[i]) {
          addLeafToTrie(child, key[i], key + i + 1, len - i - 1, value);
        } else {
          initTrie(child, trie->destructor, trie->arg);
          child->value            = value;
        }
        return;
      }
    }
    for (int i = 0; i < trie->numChildren; i++) {
      if (key[trie->idx] == trie->children[i].ch) {
        if (trie->children[i].ch) {
          key                    += trie->idx + 1;
          trie                    = &trie->children[i];
          goto nextNode;
        } else {
          if (trie->destructor) {
            trie->destructor(trie->arg, trie->children[i].value);
          }
          trie->children[i].value = value;
          return;
        }
      }
    }
    key                          += trie->idx;
    len                          -= trie->idx;
    check(trie->children          = realloc(
                     trie->children, ++trie->numChildren*sizeof(struct Trie)));
    struct Trie *newNode          = &trie->children[trie->numChildren-1];
    if (*key) {
      newNode->destructor         = trie->destructor;
      newNode->arg                = trie->arg;
      addLeafToTrie(newNode, *key, key + 1, len - 1, value);
    } else {
      initTrie(newNode, trie->destructor, trie->arg);
      newNode->value              = value;
    }
  }
}

char *getFromTrie(const struct Trie *trie, const char *key, char **diff) {
  if (diff) {
    *diff              = NULL;
  }
  struct Trie *partial = NULL;
  char *partialKey     = NULL;
  for (;;) {
    if (trie->idx > 0) {
      if (memcmp(trie->key, key, trie->idx)) {
        if (diff && partial != NULL) {
          *diff        = partialKey;
          return partial->value;
        }
        return NULL;
      }
      key             += trie->idx;
    }
    for (int i = 0; ; i++) {
      if (i >= trie->numChildren) {
        if (diff && partial != NULL) {
          // If the caller provided a "diff" pointer, then we allow partial
          // matches for the longest possible prefix that is a key in the
          // trie. Upon return, the "diff" pointer points to the first
          // character in the key does not match.
          *diff        = partialKey;
          return partial->value;
        }
        return NULL;
      } else if (*key == trie->children[i].ch) {
        if (!*key) {
          if (diff) {
            *diff      = (char *)key;
          }
          return trie->children[i].value;
        }
        for (int j = i + 1; j < trie->numChildren; j++) {
          if (!trie->children[j].ch) {
            partial    = trie->children + j;
            partialKey = (char *)key;
            break;
          }
        }
        trie = &trie->children[i];
        key++;
        break;
      } else if (!trie->children[i].ch) {
        partial        = trie->children + i;
        partialKey     = (char *)key;
      }
    }
  }
}

相关标签: c trie