/*--------------------------------
 * usage: 在键树中查找键值指向的链头。并将经过的节点的changed字段置1
 *  表示该节点的子节点要发生变化。如节点不存在，则生成该节点
 * arguments: trie  -- 键树头指针
 *   str   -- 键值字符串
 *   level -- 键值长度
 *   list  -- 保存指向链头list指针的指针，由于要保存指针的指针，
 *     使用3层指针
 * return: 找到 -- 返回指向该链表头的指针 没找到 -- NULL
 * comment:
 *---------------------------------*/
int TouchHTrie (trie_t **trie, const char str[], const int level, list_t ***list)
{
 int i;
 int key;
 trie_t *curnode;

 if (*trie == NULL)
 {
  *trie = NewNode ();
  if (*trie == NULL) {
   pr_error("errorcode:%d,msg:TouchHTrie:NewNode () return NULL\n");
                
   return -1;
  }
 }

 curnode = *trie;
 for (i = 0; i < level ; i++)
 {
  key = (int) keyarray[ (int)str[i]];
  if (curnode->subtrie[key] == NULL)
  {
   if ((curnode->subtrie[key] = NewNode ()) == NULL) {
    pr_error("errorcode:%d,msg:NewNode () error\n");
    return -1;
   }
  }
  curnode->subchanged[key] = 1;
 
  curnode = curnode->subtrie[key];
 }
 
 curnode->listchanged = 1;
 
 *list = &(curnode->list);
 
 return 0;
}

/*-------------------------------------------
 *
 *-------------------------------------------*/
list_t *GetListofHTrie (trie_t *trie, const char str[], const int level)
{
 int i;
 int key;
 trie_t *curnode;
 
 if (trie == NULL)
  return NULL;
 
 curnode = trie;
 for (i = 0; i < level ; i++)
 {
  key = (int) keyarray[(int)str[i]];
  if (curnode->subtrie[key] == NULL)
   return NULL;
  
  curnode = curnode->subtrie[key];
 }
 
 return curnode->list;
}

list_t *MatchHTrie (trie_t *trie, const char str[], const int level)
{
 int i;
 int key;
 trie_t *curnode;
 
 if (trie == NULL)
  return NULL;
 
 curnode = trie;
 
 for (i = 0; i < level ; i++)
 {
  key = (int) keyarray[(int)str[i]];
  if (curnode->subtrie[key] == NULL)
   return curnode->list;
  
  curnode = curnode->subtrie[key];
 }
 
 return curnode->list;
}

/*-------------------------------
 * usage: 释放键树
 * arguments: trie -- the head of trie
 *-------------------------------*/
void FreeHTrie (trie_t *trie)
{
 int i;

 if (trie)
 {
  for (i = 0; i < TRIE_FANOUT; i++)
   FreeHTrie (trie->subtrie[i]);
  FreeList (trie->list);
  free (trie);
 }
}

/*----------------------------------
 * usage: print the data of the trie
 *----------------------------------*/
void PrintHTrie (trie_t *trie, const int level, const int key, void (*print) (const void *data))
{
 int i;
 
 if (trie)
 {
  fprintf (stderr, "enter subtrie -- level:%d,key:%d\n", level, key);
  for (i = 0; i < TRIE_FANOUT; i++)
  {
   PrintHTrie (trie->subtrie[i], level + 1, i, print);
  }
  PrintList (trie->list, print);
 }
}
/*
void OperateHTrie (trie_t *trie, void (* op_list) (void *data))
{
 
}
*/

/*------------------------------------------
 * usage: 刷新TRIE，对changed为1的节点的子节点的链表做op_list指定的操作
 * parameters: trie   -- trie head pointer
 *   op_list-- 对list的操作
 *------------------------------------------*/
void RefreshHTrie (trie_t *trie, void (* op_data) (void *data))
{
 int i;
 
 if (trie)
 {
  for (i = 0; i < TRIE_FANOUT; i++)
  {
   if (trie->subchanged[i]) /* 子节点发生过变化 */
   {
    RefreshHTrie (trie->subtrie[i], op_data);
    trie->subchanged[i] = 0;
   }
  }
  if (trie->listchanged)
  {
   OperateList (trie->list, op_data);
   trie->listchanged = 0;
  }
 }
}

int NeedRefresh (trie_t *trie)
{
 int i;
 
 if (trie)
 {
  for (i = 0; i < TRIE_FANOUT; i++)
  {
   if (trie->subchanged[i]) /* 子节点发生过变化 */
   {
    return 1;
   }
  }
  if (trie->listchanged)
  {
   return 1;
  }
 }
 
 return 0;
}

/*
 * 功能： TRIE树遍历操作函数
 *
 * 注意 节点操作可中断
 *
 * 返回 0 未执行完毕 1 执行完毕
 */
int DealHTrie (trie_t *trie, int (* op_data) (void *data))
{
 int i;
 
 if (trie)
 {
  for (i = 0; i < TRIE_FANOUT; i++)
  {
   if (trie->subchanged[i]) /* 子节点发生过变化 */
   {
    /* 字节点操作中断， 返回 0 */
    if (DealHTrie (trie->subtrie[i], op_data) == 0)
     return 0;
    
    trie->subchanged[i] = 0;
   }
  }
  if (trie->listchanged)
  {
   if (DealList (trie->list, op_data) == 0)
    return 0;
   trie->listchanged = 0;
  }
 }
 
 return 1;
}

 测试主程序在vs2005中编译通过

#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>

#include "alloc.h"
#include "list.h"
#include "h_trie.h"

static trie_t *pTrie;
struct testdata
{
 int key;
 char data[20];
};

int _tmain(int argc, _TCHAR* argv[])
{
 struct testdata *pData;
    int i;
    char key[10];

 InitShm(sizeof(trie_t)*100+sizeof(list_t)*20);

 PrintFreelistAndCookie();

 InitHTrie(&pTrie);

 for(i = 0 ;i<10; i++)
 {
  printf("main:i=%d\n",i);
  pData = (struct testdata*)malloc(sizeof(struct testdata));
  if (pData == NULL)
  {
   pr_error("allocate fail\n");
  }

  pData->key = i;
  sprintf(pData->data ,"%d", i*9999);
        sprintf(key, "%d", pData->key);

  if ( - 1 == InsertHTrie(&pTrie, key, sizeof(int), pData,
   sizeof(struct testdata), 0) )
  {
   pr_error("errorcode:%d,msg:insert tree error\n");
  }

  PrintFreelistAndCookie();
 }

 free(getShm());
 return 0;
};

上一页  [1] [2]