Chinaunix首页 | 论坛 | 博客
  • 博客访问: 81343
  • 博文数量: 31
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 380
  • 用 户 组: 普通用户
  • 注册时间: 2014-02-24 22:04
文章分类

全部博文(31)

文章存档

2014年(31)

我的朋友

分类: C/C++

2014-07-23 11:32:07



iniLoadFromFile
    |-----iniInitContext
    |            |-----hash_init_ex
    |                    |-----_has_alloc_buckets
    |-----iniDoLoadFormFile
    |       |-----get_url_content          
    |       |-----getFileContent
   
    |       |-----iniDoLoadItemsFromBuffer

    |               |-----iniDoloadFromFile(这里再次调用,是为了处理#include)
    |               |-----hash_find
    |                       |-----_chain_find_entry
    |               |-----hash_insert
    |                       |-----hash_insert_ex
    |-----iniSortItems
    |        |-----hash_walk


iniDoLoadItemsFromBuffer:从缓冲区中的无结构数据,转化成IniContext结构数据

点击(此处)折叠或打开

  1. //用content缓冲区中的数据初始化pContext
  2. static int iniDoLoadItemsFromBuffer(char *content, IniContext *pContext)  //content:从文件中读取的信息,pContext:需要初始化的IniContext结构
  3. {
  4.     IniSection *pSection;
  5.     IniItem *pItem;
  6.     char *pLine;
  7.     char *pLastEnd;
  8.     char *pEqualChar;
  9.     char *pIncludeFilename;
  10.     int nLineLen;
  11.     int nNameLen;
  12.     int nValueLen;
  13.     int result;

  14.     result = 0;
  15.     pLastEnd = content - 1;//content的上一个字符
  16.     pSection = pContext->current_section;//psection指向当前section
  17.     if (pSection->count > 0)
  18.     {
  19.         pItem = pSection->items + pSection->count; //pitem指向当前item
  20.     }
  21.     else
  22.     {
  23.         pItem = pSection->items;//如果count=0,则让pitem指向第一个item
  24.     }

  25.     while (pLastEnd != NULL)
  26.     {
  27.         pLine = pLastEnd + 1;//
  28.         pLastEnd = strchr(pLine, '\n');//找到第一个\n,这两句表示每次检索一行
  29.         if (pLastEnd != NULL)//找到\n后,把\n替换成\0
  30.         {
  31.             *pLastEnd = '\0';
  32.         }

  33.         if (*pLine == '#' && \//寻找#include http.conf这种格式的字符串
  34.             strncasecmp(pLine+1, "include", 7) == 0 && \//与include相比较
  35.             (*(pLine+8) == ' ' || *(pLine+8) == '\t'))//include与文件名以' '或者'\t'分开
  36.         {
  37.             pIncludeFilename = strdup(pLine + 9);//字符串复制,复制include后的文件名,strdup函数在内部分配了内存,在外部需要释放内存
  38.             if (pIncludeFilename == NULL)
  39.             {
  40.                 logError("file: "__FILE__", line: %d, " \
  41.                     "strdup %d bytes fail", __LINE__, \
  42.                     (int)strlen(pLine + 9) + 1);
  43.                 result = errno != 0 ? errno : ENOMEM;
  44.                 break;
  45.             }

  46.             trim(pIncludeFilename);//去除文件名前后空格
  47.             if (strncasecmp(pIncludeFilename, "http://", 7) != 0 \//如果文件名不是网络地址
  48.                 && !fileExists(pIncludeFilename)) //并且文件不存在
  49.             {
  50.                 logError("file: "__FILE__", line: %d, " \
  51.                     "include file \"%s\" not exists, " \
  52.                     "line: \"%s\"", __LINE__, \
  53.                     pIncludeFilename, pLine);
  54.                 free(pIncludeFilename);
  55.                 result = ENOENT;
  56.                 break;
  57.             }

  58.             result = iniDoLoadFromFile(pIncludeFilename, \
  59.                     pContext);//读取include包含的文件的信息
  60.             if (result != 0)
  61.             {
  62.                 free(pIncludeFilename);
  63.                 break;
  64.             }

  65.             pSection = pContext->current_section;
  66.             if (pSection->count > 0)
  67.             {
  68.                 pItem = pSection->items + pSection->count; //must re-asign
  69.             }
  70.             else
  71.             {
  72.                 pItem = pSection->items;
  73.             }

  74.             free(pIncludeFilename);
  75.             continue;
  76.         }

  77.         trim(pLine);
  78.         if (*pLine == '#' || *pLine == '\0')//以#号开始或者是\0的字符串,直接continue,这里的\0是在函数开头由\n替换而来
  79.         {
  80.             continue;
  81.         }

  82.         nLineLen = strlen(pLine);
  83.         if (*pLine == '[' && *(pLine + (nLineLen - 1)) == ']') //section,寻找[seciontname]的字符串
  84.         {//这里表示遇到了section
  85.             char *section_name;
  86.             int section_len;

  87.             *(pLine + (nLineLen - 1)) = '\0';//把‘]’置为 ‘\0’
  88.             section_name = pLine + 1; //skip [

  89.             trim(section_name);
  90.             if (*section_name == '\0') //global section
  91.             {
  92.                 pContext->current_section = &pContext->global;
  93.                 pSection = pContext->current_section;
  94.                 if (pSection->count > 0)
  95.                 {
  96.                     pItem = pSection->items + pSection->count;
  97.                 }
  98.                 else
  99.                 {
  100.                     pItem = pSection->items;
  101.                 }
  102.                 continue;
  103.             }

  104.             section_len = strlen(section_name);
  105.             pSection = (IniSection *)hash_find(&pContext->sections,\
  106.                     section_name, section_len);//根据section name找section
  107.             if (pSection == NULL)//若section没有找到
  108.             {
  109.                 pSection = (IniSection *)malloc(sizeof(IniSection));//先分配空间
  110.                 if (pSection == NULL)
  111.                 {
  112.                     result = errno != 0 ? errno : ENOMEM;
  113.                     logError("file: "__FILE__", line: %d, "\
  114.                         "malloc %d bytes fail, " \
  115.                         "errno: %d, error info: %s", \
  116.                         __LINE__, \
  117.                         (int)sizeof(IniSection), \
  118.                         result, STRERROR(result));
  119.                     
  120.                     break;
  121.                 }

  122.                 memset(pSection, 0, sizeof(IniSection));//置0
  123.                 result = hash_insert(&pContext->sections, \//将section插入到hash表
  124.                      section_name, section_len, pSection);
  125.                 if (result < 0)
  126.                 {
  127.                     result *= -1;
  128.                     logError("file: "__FILE__", line: %d, "\
  129.                         "insert into hash table fail, "\
  130.                         "errno: %d, error info: %s", \
  131.                         __LINE__, result, \
  132.                         STRERROR(result));
  133.                     break;
  134.                 }
  135.                 else
  136.                 {
  137.                     result = 0;
  138.                 }
  139.             }

  140.             pContext->current_section = pSection;
  141.             if (pSection->count > 0)
  142.             {
  143.                 pItem = pSection->items + pSection->count;
  144.             }
  145.             else
  146.             {
  147.                 pItem = pSection->items;
  148.             }
  149.             continue;
  150.         }
  151.         
  152.         pEqualChar = strchr(pLine, '=');//寻找name=value的字符串
  153.         if (pEqualChar == NULL)
  154.         {
  155.             continue;
  156.         }
  157.         
  158.         nNameLen = pEqualChar - pLine;//name的长度
  159.         nValueLen = strlen(pLine) - (nNameLen + 1);//value的长度
  160.         if (nNameLen > FAST_INI_ITEM_NAME_LEN)
  161.         {
  162.             nNameLen = FAST_INI_ITEM_NAME_LEN;
  163.         }
  164.         
  165.         if (nValueLen > FAST_INI_ITEM_VALUE_LEN)
  166.         {
  167.             nValueLen = FAST_INI_ITEM_VALUE_LEN;
  168.         }
  169.     
  170.         if (pSection->count >= pSection->alloc_count)
  171.         {
  172.             pSection->alloc_count += _ALLOC_ITEMS_ONCE;//每次增加8个
  173.             pSection->items=(IniItem *)realloc(pSection->items, //扩大空间
  174.                 sizeof(IniItem) * pSection->alloc_count);
  175.             if (pSection->items == NULL)
  176.             {
  177.                 logError("file: "__FILE__", line: %d, " \
  178.                     "realloc %d bytes fail", __LINE__, \
  179.                     (int)sizeof(IniItem) * \
  180.                     pSection->alloc_count);
  181.                 result = errno != 0 ? errno : ENOMEM;
  182.                 break;
  183.             }

  184.             pItem = pSection->items + pSection->count;
  185.             memset(pItem, 0, sizeof(IniItem) * \ //把剩余的部分置0
  186.                 (pSection->alloc_count - pSection->count));
  187.         }

  188.         memcpy(pItem->name, pLine, nNameLen);
  189.         memcpy(pItem->value, pEqualChar + 1, nValueLen);
  190.         
  191.         trim(pItem->name);
  192.         trim(pItem->value);
  193.         
  194.         pSection->count++;
  195.         pItem++;
  196.     }

  197.     return result;
  198. }
iniDoLoadItemsFromBuffer函数首先把所有的\n替换成\0,然后一行一行的读取数据,如果读取的这个数据是“#include”,则再次去读取inlcude后的文件信息到pContext中。如果读到的数据是包含[],则说明遇到一个section,把该section加入到hash表中,若读到的数据是name=value,则把该数据放入到全局section中。


|-----hash_find
     |-----_chain_find_entry

点击(此处)折叠或打开

  1. //在hash表中查找key是否存在
  2. void *hash_find(HashArray *pHash, const void *key, const int key_len)  //pHash:指向hash表的指针,key:sectionName,key_len:sectionName的长度
  3. {
  4.     unsigned int hash_code;
  5.     HashData **ppBucket;
  6.     HashData *hash_data;

  7.     hash_code = pHash->hash_func(key, key_len); //计算hashcode
  8.     ppBucket = pHash->buckets + (hash_code % (*pHash->capacity)); //通过这种策略,确定hash的表的入口条目

  9.     hash_data = _chain_find_entry(ppBucket, key, key_len, hash_code);//从入口条目开始,遍历链表
  10.     if (hash_data != NULL)
  11.     {
  12.         return hash_data->value;
  13.     }
  14.     else
  15.     {
  16.         return NULL;
  17.     }
  18. }

点击(此处)折叠或打开

  1. //从hash表的入口条目开始,遍历链表
  2. static HashData *_chain_find_entry(HashData **ppBucket, const void *key, \  //ppBucket:指向hashcode对应的入口的指针
  3.         const int key_len, const unsigned int hash_code)
  4. {
  5.     HashData *hash_data;

  6.     hash_data = *ppBucket;//获取第一个节点
  7.     while (hash_data != NULL)
  8.     {
  9.         if (key_len == hash_data->key_len && \//若hashdata的key_len与参数key_len相同
  10.             memcmp(key, hash_data->key, key_len) == 0) //并且hashdata的key与参数key相同
  11.         {
  12.             return hash_data;
  13.         }

  14.         hash_data = hash_data->next;
  15.     }

  16.     return NULL;
  17. }

|-----hash_insert     
    |-----hash_insert_ex

            |-----DELETE_FROM_BUCKET
            |-----CALC_NODE_MALLOC_BYTES
            |-----ADD_TO_BUCKET
            |-----_rehash
            

点击(此处)折叠或打开

  1. //把hashdata插入hash表
  2. int hash_insert_ex(HashArray *pHash, const void *key, const int key_len, \ //pHash:hash表,key:sectionName,key_len:sectionName的长度,value:section整个结构的值,value_len:section结构的长度
  3.         void *value, const int value_len)
  4. {
  5.     unsigned int hash_code;
  6.     HashData **ppBucket;
  7.     HashData *hash_data;
  8.     HashData *previous;
  9.     char *pBuff;
  10.     int bytes;
  11.     int malloc_value_size;

  12.     hash_code = pHash->hash_func(key, key_len);//通过name与len计算hashcode
  13.     ppBucket = pHash->buckets + (hash_code % (*pHash->capacity));//通过hashcode获取指针数组位置

  14.     previous = NULL;
  15.     hash_data = *ppBucket;
  16.     while (hash_data != NULL)//hashdata存在
  17.     {
  18.         if (key_len == hash_data->key_len && \
  19.             memcmp(key, hash_data->key, key_len) == 0)
  20.         {
  21.             break;
  22.         }

  23.         previous = hash_data;
  24.         hash_data = hash_data->next;
  25.     }

  26.     if (hash_data != NULL) //exists
  27.     {
  28.         if (!pHash->is_malloc_value)//该值若为0,表示hash表不会为value预留空间,value直接从外部传入
  29.         {
  30.             hash_data->value_len = value_len;
  31.             hash_data->value = (char *)value;
  32.             return 0;
  33.         }
  34.         else//表示hash表为value预留空间
  35.         {
  36.             if (hash_data->malloc_value_size >= value_len && \
  37.                 hash_data->malloc_value_size / 2 < value_len)
  38.             {
  39.                 hash_data->value_len = value_len;
  40.                 memcpy(hash_data->value, value, value_len);
  41.                 return 0;
  42.             }

  43.             DELETE_FROM_BUCKET(pHash, ppBucket, previous, hash_data)
  44.         }
  45.     }

  46.     if (!pHash->is_malloc_value)//表示value不在hashdata结构后
  47.     {
  48.         malloc_value_size = 0;
  49.     }
  50.     else //表示value在hashdata结构后,这里把value的长度放入hashdata结构中
  51.     {
  52.         malloc_value_size = value_len;
  53.     }

  54.     bytes = CALC_NODE_MALLOC_BYTES(key_len, malloc_value_size);//计算一个hashdata需要分配的空间
  55.     if (pHash->max_bytes > 0 && pHash->bytes_used+bytes > pHash->max_bytes)
  56.     {
  57.         return -ENOSPC;
  58.     }

  59.     pBuff = (char *)malloc(bytes);
  60.     if (pBuff == NULL)
  61.     {
  62.         return -ENOMEM;
  63.     }

  64.     pHash->bytes_used += bytes;//改变used变量

  65.     hash_data = (HashData *)pBuff;
  66.     hash_data->malloc_value_size = malloc_value_size;

  67.     hash_data->key_len = key_len;
  68.     memcpy(hash_data->key, key, key_len);
  69. #ifdef HASH_STORE_HASH_CODE
  70.     hash_data->hash_code = hash_code;
  71. #endif
  72.     hash_data->value_len = value_len;

  73.     if (!pHash->is_malloc_value) //这里表示value已经在外面分配了空间,而不是放在hashdata后面
  74.     {
  75.         hash_data->value = (char *)value;
  76.     }
  77.     else //这里表示value需要放在hashdata后,[hashdata][key][value]
  78.     {
  79.         hash_data->value = hash_data->key + hash_data->key_len;//指向value的首地址
  80.         memcpy(hash_data->value, value, value_len);//拷贝value
  81.     }

  82.     ADD_TO_BUCKET(pHash, ppBucket, hash_data)//添加hashdata到hash表

  83.     if ((double)pHash->item_count / (double)*pHash->capacity >= \
  84.         pHash->load_factor)//
  85.     {
  86.         _rehash(pHash);//重新hash
  87.     }

  88.     return 1;
  89. }
hash_insert_ex函数在hash表中查找key是对应的hashdata否存在与hash表中,若存在,则直接修改hashdata的value与value_len,若不存在,调用CALC_NODE_MALLOC_BYTES计算需要分配的空间,创建hashdata,并分配空间,并调用ADD_TO_BUCKET插入到hash表中,检查是否rehash,若需要,则执行rehash

|-----hash_insert
     
    |-----hash_insert_ex           
            |-----
DELETE_FROM_BUCKET
            |-----CALC_NODE_MALLOC_BYTES           
            |-----
ADD_TO_BUCKET
            |-----_rehash


点击(此处)折叠或打开

  1. #define CALC_NODE_MALLOC_BYTES(key_len, value_size) \
  2.         sizeof(HashData) + key_len + value_size
CALC_NODE_MALLOC_BYTES宏,计算一个hashdata需要分配的空间的大小,这里在hashdata后面预留了key与value的空间


|-----hash_insert     
    |-----hash_insert_ex            
            |-----
DELETE_FROM_BUCKET
            |-----CALC_NODE_MALLOC_BYTES            
            |-----
ADD_TO_BUCKET
            |-----_rehash

                            |-----_rehash_1


点击(此处)折叠或打开

  1. static int _rehash(HashArray *pHash) //对hash表中的hashdata数据重新进行排列
  2. {
  3.     int result;
  4.     unsigned int *pOldCapacity;

  5.     pOldCapacity = pHash->capacity;
  6.     if (pHash->is_malloc_capacity) //这里先重新计算capacity
  7.     {
  8.         unsigned int *pprime;
  9.         unsigned int *prime_end;

  10.         pHash->capacity = NULL;

  11.         prime_end = prime_array + PRIME_ARRAY_SIZE;
  12.         for (pprime = prime_array; pprime!=prime_end; pprime++)//寻找大于pOldCapacity的最大质数
  13.         {
  14.             if (*pprime > *pOldCapacity)
  15.             {
  16.                 pHash->capacity = pprime;
  17.                 break;
  18.             }
  19.         }
  20.     }
  21.     else
  22.     {
  23.         pHash->capacity++;
  24.     }

  25.     if ((result=_rehash1(pHash, *pOldCapacity, pHash->capacity)) != 0)
  26.     {
  27.         pHash->capacity = pOldCapacity; //rollback
  28.     }
  29.     else
  30.     {
  31.         if (pHash->is_malloc_capacity)   //
  32.         {
  33.             free(pOldCapacity);
  34.             pHash->is_malloc_capacity = false;
  35.         }
  36.     }

  37.     /*printf("rehash, old_capacity=%d, new_capacity=%d\n", \
  38.         old_capacity, *pHash->capacity);
  39.     */
  40.     return result;
  41. }
rehash首先重新计算capacity,再调用_rehash对hash表中的数据重新排列

点击(此处)折叠或打开

  1. static int _rehash1(HashArray *pHash, const int old_capacity, \
  2.         unsigned int *new_capacity)
  3. {
  4.     HashData **old_buckets;
  5.     HashData **ppBucket;
  6.     HashData **bucket_end;
  7.     HashData *hash_data;
  8.     HashData *pNext;
  9.     int result;

  10.     old_buckets = pHash->buckets;//保留的老的hashdata的地址
  11.     pHash->capacity = new_capacity;
  12.     if ((result=_hash_alloc_buckets(pHash, old_capacity)) != 0)//重新给老的hashdata分配空间
  13.     {//失败了,则rollback
  14.         pHash->buckets = old_buckets;
  15.         return result;
  16.     }

  17.     //printf("old: %d, new: %d\n", old_capacity, *pHash->capacity);

  18.     pHash->item_count = 0;
  19.     bucket_end = old_buckets + old_capacity;
  20.     for (ppBucket=old_buckets; ppBucket<bucket_end; ppBucket++)
  21.     {
  22.         if (*ppBucket == NULL)
  23.         {
  24.             continue;
  25.         }

  26.         hash_data = *ppBucket;
  27.         while (hash_data != NULL)
  28.         {
  29.             pNext = hash_data->next;

  30.             ADD_TO_BUCKET(pHash, (pHash->buckets + \//将老的hashdata按照新的规则放入hash表中
  31.                 (HASH_CODE(pHash, hash_data) % \//因为capacity变化了,造成了计算出的%运算的值发生了变化
  32.                 (*pHash->capacity))), hash_data)

  33.             hash_data = pNext;
  34.         }
  35.     }

  36.     free(old_buckets);//释放老的空间
  37.     return 0;
  38. }

_rehash1函数先按照新的capacity为hash分配空间,再把hashdata按照新规则计算的位置,放入到hash表中,最后释放老的hashdata的空间



阅读(512) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~