Пример 7

/* Работа с хэш-таблицей. Часть функций написана так, чтобы
 * быть независимой от типов ключа и значения и легко
 * подвергаться модификации.
 */
#include <stdio.h>
#include <string.h>     /* prototype for strchr() */
extern void *malloc(unsigned size);
/* типы ключа и значения: в нашем случае это строки */
typedef unsigned char uchar;
typedef uchar *VAL; typedef uchar *KEY;

/* Для использования следует реализовать операции
int  HASHFUNC(KEY); int  EQKEY(KEY, KEY);
void FREEVAL(VAL);  void SETVAL(VAL, VAL);
void FREEKEY(KEY);  void SETKEY(KEY, KEY);
*/
#define HASHSIZE 21     /* размер таблицы: очень хорошо 2**n */

uchar *strudup(const uchar *s){ /* создание копии строки в "куче" */
  uchar *p =  (uchar *) malloc(strlen(s)+1); strcpy(p, s); return p;
}
/* одна из возможных хэш-функций */
unsigned int hash; /* последнее вычисленное значение хэш-функции */
int HASHFUNC(KEY key){
        unsigned int i = 0; uchar *keysrc = key;
        while(*key){
          i = (i << 1)|(i >> 15); /* ROL */
          i ^= *key++;
        }
        hash = i % HASHSIZE;
        printf( "hash(%s)=%d\n", keysrc, hash);  /* отладка */
        return hash;
}
#define EQKEY(s1, s2)   (strcmp(s1, s2) == 0)
#define FREEKEY(s)      free(s)
#define FREEVAL(s)      free(s)
#define SETVAL(at,s)    at = strudup(s)
#define SETKEY(at,s)    at = strudup(s)
#define KEYFMT          "%s"
#define VALFMT          "%s"

/* ================== типо-независимая часть ================= */
struct cell {
        struct cell *next; /* ссылка на очередной элемент */
        KEY key;           /* ключ     */
        VAL val;           /* значение */
} *hashtable[ HASHSIZE ];  /* хэш-таблица */

/* получение значения по ключу */
struct cell *get(KEY key){
        struct cell *p;
        for(p = hashtable[HASHFUNC(key)]; p; p = p->next)
                if(EQKEY(p->key, key))
                        return p;
        return NULL;    /* отсутствует */
}

/* занести пару ключ:значение в таблицу */
void set(KEY key, VAL val){
        struct cell *p;

        /* проверить - не было ли звена с таким ключом */
        if((p = get(key)) == NULL){       /* не было   */
            if(!(p = (struct cell *) malloc(sizeof(*p)))) return;
            SETKEY(p->key, key);
            p->next = hashtable[hash]; /* hash вычислено в get() */
            hashtable[hash] = p;
        } else /* уже было: изменить значение */
            FREEVAL(p->val);
        SETVAL(p->val, val);
}

/* удаление по ключу */
int del(KEY key){
        int indx = HASHFUNC(key);
        struct cell *p, *prev = NULL;

        if((p = hashtable[indx]) == NULL) return 0;
        for( ;p ;prev = p, p=p->next)
                if(EQKEY(p->key, key)){
                    FREEVAL(p->val); FREEKEY(p->key);
                    if( p == hashtable[indx] ) /* голова списка */
                             hashtable[indx] = p->next;
                    else     prev->next = p->next;
                    free((void *) p ); return 1; /* удален */
                }
        return 0;  /* не было такого */
}

/* распечатать пару ключ:значение */
void printcell(struct cell *ptr){
        putchar('(');
        printf( KEYFMT, ptr->key ); putchar(',');
        printf( VALFMT, ptr->val ); putchar(')');
}

/* распечатка таблицы (для отладки) */
void printtable(){
  register i; struct cell *p;
  printf("----TABLE CONTENTS----\n");
  for(i=0; i < HASHSIZE; i++)
      if((p = hashtable[i]) != NULL){
          printf( "%d: ", i);
          for(; p; p=p->next)
             printcell(p), putchar(' ');
          putchar('\n');
      }
}

/* итератор */
struct celliter {
        int index; struct cell *ptr;
};
/* выдать очередное значение */
struct cell *nextpair(struct celliter *ci){
        struct cell *result;
        while((result = ci->ptr) == NULL){
                if( ++(ci->index) >= HASHSIZE )
                        return NULL;    /* больше нет */
                ci->ptr = hashtable[ci->index];
        }
        ci->ptr = result->next; return result;
}
/* инициализация итератора */
struct cell *resetiter(struct celliter *ci){
        ci->index = (-1); ci->ptr = NULL;
        return nextpair(ci);  /* первое значение */
}
/* =========================================================== */

void main(){ /* таблица из имен и размеров файлов текущего каталога */
 struct celliter ci; struct cell *cl;
 char key[40], value[40]; struct cell *val;
 extern FILE *popen();    FILE *fp;     char *s ;

 /* popen() читает вывод команды, заданной в 1-ом аргументе */
 fp = popen( "ls -s", "r" );
 while( fscanf( fp, "%s%s", value, key) == 2 )
        set(key, value);
 pclose(fp);  /* popen() надо закрывать pclose(); */

 for(;;){
        printf( "-> " );  /* приглашение */
        if( !gets( key )) break;   /* EOF */
        if( *key == '-' ){         /* -КЛЮЧ          :удалить     */
                printf( del( key+1 ) ? "OK\n" : "нет такого\n");
                continue;
        }
        if( !*key || !strcmp(key, "=")){ /* = :распечатать таблицу*/
                printtable();    continue;
        }
        if(s = strchr(key, '=')){ /* КЛЮЧ=ЗНАЧЕНИЕ  :добавить     */
                *s++ = '\0';
                set(key, s); continue;
        }
        if((val = get( key )) == NULL) /* КЛЮЧ :найти значение */
             printf( "нет такого ключа\n");
        else{ printf( "значение "); printf(VALFMT, val->val);
              putchar('\n');
        }
 }
 /* распечатка таблицы при помощи итератора */
 for( cl = resetiter(&ci) ; cl ; cl = nextpair(&ci))
        printcell(cl), putchar('\n');
}

© Copyright А. Богатырев, 1992-95 www.abyss-group.narod.ru
Си в UNIX