Библиотека INI: проблема со связанным списком (аннотация) - PullRequest
Новая
       26

Библиотека INI: проблема со связанным списком (аннотация)

0 голосов
/ 16 мая 2011

Я работаю над своей собственной - простой, короткой, глупой библиотекой ini, которую я буду использовать для других проектов.Я до сих пор кодировал ini-парсер, довольно простой и эффективный, и теперь пришло время перейти к более сложной части - как и где хранить проанализированные данные из INI-файла.

Я подумал об использовании простого связанного списка(может быть, двойной связанный список), но я не могу изобразить это в своей голове. 

struct keys
{
 char *keyname;
 char *keyval;
 unsigned long hashkey;
 struct keys *next;
 struct keys *prev;
}

struct ini
{
 char *section;
 struct keys *okeys;
 unsigned long hashkey;
 struct ini *next;
 struct ini *prev;
}

Сначала я подумал закодировать это таким образом, но я вроде как выглядит глупо иЯ знаю, что не достаточно эффективно, я знаю, что есть лучший способ хранить разделы, ключи и значения ключей в связанном списке, но я не могу придумать ни одного.Или, может быть, я должен попробовать использовать какую-то другую структуру данных?Я не думаю, что для создания библиотеки ini таким способом потребуется слишком много функций, таких как - отдельная функция для добавления разделов, и одна для добавления ключей и т. Д. Я действительно пытаюсь понять, что использовать, и я застрял.

Вот код моего простого ini-парсера: 

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

#define BUFF_SIZE 1024
#define INI_FILE "config.ini"
#define ERROR_FILE "error.log"

void load_ini(const char *name);
void log_it(const char *filename, const char *format, ...);
void trim(char *str);
unsigned int hash(const char *key);

int main(int argc, char *argv[])
{
 load_ini(INI_FILE);
 return 0;
}

/*2. load ini function */
void load_ini(const char *name)
{
 char *line = NULL;
 char *p = NULL;
 FILE *ifile = NULL;

 ifile = fopen(name, "r");
 if(ifile == NULL)
 {
  log_it(ERROR_FILE, "(load_ini) can't open %s file", name);
  return;
 }

 line = malloc(BUFF_SIZE * sizeof(char) + 1);
 if(line == NULL)
 {
  log_it(ERROR_FILE, "(load_ini) malloc fail");
  return;
 }

 while(fgets(line, BUFF_SIZE+1, ifile) != NULL)
 {
  trim(line);

  if(strlen(line) < 3 || *line == ';' || *line == '#')
  {
   continue;
  }

  if(*line == '[')
  {
   if(p = strchr(line, ']'))
   {
    *p = '\0';
    trim(line+1);
    /* add section here */
   }
  }
  else if(p = strchr(line, '='))
  {
   *p = '\0';
   trim(line);
   trim(p+1);
   /* add key, and key value here */
  }
 }
 free(line);
 fclose(ifile);
}

/* 3. multifunctional log function with variable number of arguments */
void log_it(const char *filename, const char *format, ...)
{
 va_list arglist;
 FILE *fp = NULL; 

 fp = fopen(filename,"a");
 if(fp == NULL)
 {
  /* :) */
  return;
 }

 va_start(arglist, format);
 vfprintf (fp, format, arglist);
 va_end (arglist);
 fclose (fp);
}

/* 4. trim function */

void trim(char *str)
{
 char *start = str;
 char *end = start + strlen(str);

 while (--end >= start) 
 { 
  if (!isspace(*end))
  {
   break;
  }
 }

 *(++end) = '\0';

 while (isspace(*start)) 
 {
  start++;
 }

 if (start != str)
 {
  memmove(str, start, end - start + 1);
 }
}

/* Bernstein hash */
unsigned int hash(const char *key) 
{
 unsigned int hash = 5381;
 unsigned int i = 0;
 int len = strlen(key);

 for(i; i < len; ++i)
 {
  hash = 33 * hash + key[i];
 }
 return hash ^ (hash >> 16);
}

1 Ответ

0 голосов
/ 16 мая 2011

Я бы держал разделы в связанном списке. Скорее всего, в среднем INI-файле недостаточно разделов, чтобы гарантировать создание хеш-таблицы. Кроме того, вы можете использовать двоичное дерево поиска, которое требует минимальных усилий.

Другой подход заключается в использовании одной хеш-таблицы и добавлении к каждому значению префикса с именем раздела и токеном разделения. Недостаток этого подхода заключается в том, что вы не можете использовать токен разделения в именах ключей и имен разделов. Если вы контролируете формат INI, то это не проблема. Если это обычный ini-парсер, он будет.

Для любого из подходов вам нужно придумать имя раздела для безсекционного, т.е. глобального раздела.

Несмотря на то, что бинарные деревья поиска и хеш-таблицы являются более быстрыми поисками, чем связанные списки, вам необходимо решить, стоит ли оно того для вашего приложения. Если ваше приложение считывает INI-файл только один раз и значения набора состояний в приложении, которые больше не запрашиваются в течение его срока службы, скорость поиска не важна. Однако, если приложение постоянно запрашивает эти значения, тогда предпочтительнее использовать хеш-таблицы. Если определенные значения будут с большей вероятностью запрашиваться в течение времени жизни приложения, деревья Splay могут работать благоприятно. С другой стороны, если доступ к значениям конфигурации является важной и измеримой частью приложения, то, возможно, пришло время отделить некоторые функциональные возможности.

...