aplfw/library/container/assoc/assoc.c

   1 /**
   2  *  Hyper Operating System  Application Framework
   3  *
   4  * @file  assoc.c
   5  * @brief %jp{連想配列クラス}
   6  *
   7  * Copyright (C) 2006 by Project HOS
   8  * http://sourceforge.jp/projects/hos/
   9  */
  10
  11 #include <stdio.h>
  12 #include <string.h>
  13 #include "hosaplfw.h"
  14 #include "assoc.h"
  15
  16
  17
  18 /* 連想バッファのコンストラクタ */
  19 /*void Assoc_Constructor(C_ASSOC *self, C_MEMHEAP *pMemHeap) */
  20 void Assoc_CreateEx(C_ASSOC *self, C_MEMHEAP *pMemHeap)
  21 {
  22         self->pMemHeap = pMemHeap;
  23         self->pRoot    = NULL;
  24 }
  25
  26
  27 /* 連想バッファのデストラクタ */
  28 void Assoc_Delete(C_ASSOC *self)
  29 {
  30 }
  31
  32
  33
  34 /* ノード追加 */
  35 static ASSOC_ERR Assoc_AddNode(T_ASSOC_NODE *pParent, T_ASSOC_NODE *pNode)
  36 {
  37         char    *pszParentKey;
  38         char    *pszNodeKey;
  39         int             iCmp;
  40
  41         pszParentKey = (char *)pParent + sizeof(T_ASSOC_NODE);
  42         pszNodeKey   = (char *)pNode   + sizeof(T_ASSOC_NODE);
  43         iCmp = strcmp(pszParentKey, pszNodeKey);
  44         if ( iCmp == 0 )
  45         {
  46                 return ASSOC_ERR_NG;    /* 既に存在する */
  47         }
  48
  49         if ( iCmp > 0 )
  50         {
  51                 if ( pParent->pLeft != NULL )
  52                 {
  53                         return Assoc_AddNode(pParent->pLeft, pNode);
  54                 }
  55                 pParent->pLeft = pNode;
  56                 pNode->pParent = pParent;
  57         }
  58         else
  59         {
  60                 if ( pParent->pRight != NULL )
  61                 {
  62                         return Assoc_AddNode(pParent->pRight, pNode);
  63                 }
  64                 pParent->pRight = pNode;
  65                 pNode->pParent = pParent;
  66         }
  67
  68         return ASSOC_ERR_OK;
  69 }
  70
  71
  72 /* データの登録 */
  73 ASSOC_ERR Assoc_Add(C_ASSOC *self, const char *pszKey, const void *pData, long lSize)
  74 {
  75         char                    *pMem;
  76         T_ASSOC_NODE    *pNode;
  77         int                             iKeyLen;
  78         ASSOC_ERR               ErrCode;
  79
  80         /* ノード生成 */
  81         iKeyLen = MemHeap_AlignSize(self->pMemHeap, strlen(pszKey) + 1);
  82         if ( (pMem = MemHeap_Alloc(self->pMemHeap, sizeof(T_ASSOC_NODE) + iKeyLen + lSize)) == NULL )
  83         {
  84                 return ASSOC_ERR_NG;
  85         }
  86         pNode = (T_ASSOC_NODE *)pMem;
  87         pMem += sizeof(T_ASSOC_NODE);
  88         strcpy(pMem, pszKey);
  89         pMem += iKeyLen;
  90         memcpy(pMem, pData, lSize);
  91
  92         /* 追加 */
  93         pNode->pLeft   = NULL;
  94         pNode->pRight  = NULL;
  95         if ( self->pRoot == NULL )
  96         {
  97                 pNode->pParent = NULL;
  98                 self->pRoot    = pNode;
  99                 ErrCode = ASSOC_ERR_OK;
 100         }
 101         else
 102         {
 103                 ErrCode = Assoc_AddNode(self->pRoot, pNode);
 104                 if ( ErrCode != ASSOC_ERR_OK )
 105                 {
 106                         MemHeap_Free(self->pMemHeap, pNode);
 107                 }
 108         }
 109
 110         return ErrCode;
 111 }
 112
 113
 114
 115 static void *Assoc_GetNode(C_ASSOC *self, T_ASSOC_NODE *pNode, const char *pszKey)
 116 {
 117         char    *pszNodeKey;
 118         int             iCmp;
 119         int             iKeyLen;
 120
 121         pszNodeKey   = (char *)pNode + sizeof(T_ASSOC_NODE);
 122         iCmp = strcmp(pszNodeKey, pszKey);
 123         if ( iCmp == 0 )
 124         {
 125                 iKeyLen = MemHeap_AlignSize(self->pMemHeap, strlen(pszKey) + 1);
 126                 return (void *)(pszNodeKey + iKeyLen);  /* ヒット */
 127         }
 128
 129         if ( iCmp > 0 )
 130         {
 131                 if ( pNode->pLeft == NULL )
 132                 {
 133                         return NULL;
 134                 }
 135                 return Assoc_GetNode(self, pNode->pLeft, pszKey);
 136         }
 137         else
 138         {
 139                 if ( pNode->pRight == NULL )
 140                 {
 141                         return NULL;
 142                 }
 143                 return Assoc_GetNode(self, pNode->pRight, pszKey);
 144         }
 145 }
 146
 147
 148 /* データの参照 */
 149 const void *Assoc_Get(C_ASSOC *self, const char *pszKey)
 150 {
 151         ASSOC_POS       Pos;
 152         char            *pDataKey;
 153
 154         if ( self->pRoot == NULL )
 155         {
 156                 return ASSOC_POS_NULL;
 157         }
 158
 159         return Assoc_GetNode(self, self->pRoot, pszKey);
 160 }
 161
 162
 163
 164 ASSOC_POS Assoc_GetFirst(C_ASSOC *self)
 165 {
 166         T_ASSOC_NODE *pNode;
 167
 168         if ( self->pRoot == NULL )
 169         {
 170                 return ASSOC_POS_NULL;
 171         }
 172
 173         pNode = self->pRoot;
 174         while ( pNode->pLeft != NULL )
 175         {
 176                 pNode = pNode->pLeft;
 177         }
 178
 179         return (ASSOC_POS)pNode;
 180 }
 181
 182
 183 ASSOC_POS Assoc_GetNext(C_ASSOC *self, ASSOC_POS *Pos)
 184 {
 185         T_ASSOC_NODE *pNode;
 186
 187         pNode = (T_ASSOC_NODE *)Pos;
 188
 189         /* 右に枝が残っているなら探す */
 190         if ( pNode->pRight != NULL )
 191         {
 192                 pNode = pNode->pRight;
 193                 while ( pNode->pLeft != NULL )
 194                 {
 195                         pNode = pNode->pLeft;
 196                 }
 197                 return (ASSOC_POS)pNode;
 198         }
 199
 200         /* 終了 */
 201         if ( pNode->pParent == NULL )
 202         {
 203                 return ASSOC_POS_NULL;
 204         }
 205
 206         /* 左の葉の場合 */
 207         if ( pNode->pParent->pLeft == pNode )
 208         {
 209                 return (ASSOC_POS)pNode->pParent;
 210         }
 211
 212         /* 右の葉の場合 */
 213         do
 214         {
 215                 pNode = pNode->pParent;
 216                 if ( pNode->pParent == NULL )
 217                 {
 218                         return ASSOC_POS_NULL;
 219                 }
 220         } while ( pNode->pParent->pRight == pNode );
 221         pNode = pNode->pParent;
 222
 223         return (ASSOC_POS)pNode;
 224 }
 225
 226
 227 const void *Assoc_GetAt(C_ASSOC *self, ASSOC_POS *Pos, const char **ppszKey)
 228 {
 229         T_ASSOC_NODE *pNode;
 230         char    *pszNodeKey;
 231         int             iCmp;
 232         int             iKeyLen;
 233
 234         pNode = (T_ASSOC_NODE *)Pos;
 235
 236         pszNodeKey = (char *)pNode + sizeof(T_ASSOC_NODE);
 237         *ppszKey   = pszNodeKey;
 238         iKeyLen    = MemHeap_AlignSize(self->pMemHeap, strlen(pszNodeKey) + 1);
 239
 240         return (void *)(pszNodeKey + iKeyLen);
 241 }
 242
 243
 244 /* end of file */