"Fossies" - the Fresh Open Source Software Archive

Member "detox-1.4.5/src/table.c" (15 Aug 2021, 3262 Bytes) of package /linux/privat/detox-1.4.5.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "table.c" see the Fossies "Dox" file reference documentation.

    1 /**
    2  * This file is part of the Detox package.
    3  *
    4  * Copyright (c) Doug Harple <detox.dharple@gmail.com>
    5  *
    6  * For the full copyright and license information, please view the LICENSE
    7  * file that was distributed with this source code.
    8  */
    9 
   10 #include "config.h"
   11 
   12 #include <stdio.h>
   13 #include <stdlib.h>
   14 #include <string.h>
   15 #include <ctype.h>
   16 #include <errno.h>
   17 
   18 #include "table.h"
   19 
   20 /*
   21  * Internal function declarations
   22  */
   23 static int table_hash1(int table_length, unsigned int key);
   24 static int table_hash2(int table_length, unsigned int key);
   25 
   26 struct translation_table *table_init(int max_rows)
   27 {
   28     struct translation_table *ret;
   29     size_t row_length;
   30 
   31     if (max_rows <= 0) {
   32         max_rows = 500;
   33     }
   34 
   35     row_length = max_rows * sizeof(struct translation_table_row);
   36 
   37     ret = malloc(sizeof(struct translation_table));
   38     if (ret == NULL) {
   39         return NULL;
   40     }
   41 
   42     memset(ret, 0, sizeof(struct translation_table));
   43 
   44     ret->rows = malloc(row_length);
   45     if (ret->rows == NULL) {
   46         free(ret);
   47         return NULL;
   48     }
   49 
   50     memset(ret->rows, 0, row_length);
   51 
   52     ret->length = max_rows;
   53 
   54     return ret;
   55 }
   56 
   57 struct translation_table *table_resize(struct translation_table *table, int rows)
   58 {
   59     struct translation_table *ret;
   60     int i;
   61 
   62     ret = table_init(rows);
   63 
   64     if (ret == NULL)
   65         return table;
   66 
   67     if (table == NULL)
   68         return ret;
   69 
   70     for (i = 0; i < table->length; i++) {
   71         if (table->rows[i].key > 0 && table->rows[i].data != NULL) {
   72             table_put(ret, table->rows[i].key, table->rows[i].data);
   73         }
   74     }
   75 
   76     return ret;
   77 }
   78 
   79 void table_free(struct translation_table *table)
   80 {
   81     int i;
   82 
   83     if (table == NULL)
   84         return;
   85 
   86     for (i = 0; i < table->length; i++) {
   87         if (table->rows[i].key > 0 && table->rows[i].data != NULL) {
   88             free(table->rows[i].data);
   89         }
   90     }
   91 
   92     free(table->rows);
   93     free(table);
   94 }
   95 
   96 static int table_hash1(int table_length, unsigned int key)
   97 {
   98     return key % table_length;
   99 }
  100 
  101 static int table_hash2(int table_length, unsigned int key)
  102 {
  103     return (key >> 8) % table_length;
  104 }
  105 
  106 /*
  107  * 0 is an invalid key (sorry)
  108  */
  109 int table_put(struct translation_table *table, unsigned int key, char *data)
  110 {
  111     int hashed;
  112     int hashed2;
  113     int i;
  114 
  115     if (table->length == table->used) {
  116         return -1;
  117     }
  118 
  119     hashed = table_hash1(table->length, key);
  120 
  121     if (table->rows[hashed].key != 0 && table->rows[hashed].key != key) {
  122         hashed2 = table_hash2(table->length, key);
  123         i = 0;
  124         while (table->rows[hashed].key != 0 && table->rows[hashed].key != key) {
  125             hashed += i + hashed2;
  126             hashed %= table->length;
  127         }
  128     }
  129 
  130     if (table->rows[hashed].key == key) {
  131         table->overwrites++;
  132     }
  133 
  134     table->rows[hashed].key = key;
  135     table->rows[hashed].data = strdup(data);
  136     table->used++;
  137     return hashed;
  138 }
  139 
  140 /*
  141  * 0 is an invalid key (sorry)
  142  */
  143 char *table_get(struct translation_table *table, unsigned int key)
  144 {
  145     int hashed;
  146     int hashed2;
  147     int i;
  148 
  149     if (table == NULL) {
  150         return NULL;
  151     }
  152 
  153     hashed = table_hash1(table->length, key);
  154 
  155     if (table->rows[hashed].key == 0) {
  156         return NULL;
  157     }
  158 
  159     if (table->rows[hashed].key != key) {
  160         hashed2 = table_hash2(table->length, key);
  161         i = 0;
  162         while (table->rows[hashed].key != key && table->rows[hashed].key != 0) {
  163             table->misses++;
  164 
  165             hashed += i + hashed2;
  166             hashed %= table->length;
  167         }
  168     }
  169 
  170     if (table->rows[hashed].key == 0) {
  171         return NULL;
  172     }
  173 
  174     table->hits++;
  175 
  176     return table->rows[hashed].data;
  177 }