src/revobject.c

   1 /*
   2  * This file is free software; you can redistribute it and/or modify
   3  * it under the terms of the GNU General Public License, version 2,
   4  * as published by the Free Software Foundation.
   5  *
   6  * In addition to the permissions in the GNU General Public License,
   7  * the authors give you unlimited permission to link the compiled
   8  * version of this file into combinations with other programs,
   9  * and to distribute those combinations without any restriction
  10  * coming from the use of this file.  (The General Public License
  11  * restrictions do apply in other respects; for example, they cover
  12  * modification of the file, and distribution when not linked into
  13  * a combined executable.)
  14  *
  15  * This file is distributed in the hope that it will be useful, but
  16  * WITHOUT ANY WARRANTY; without even the implied warranty of
  17  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  18  * General Public License for more details.
  19  *
  20  * You should have received a copy of the GNU General Public License
  21  * along with this program; see the file COPYING.  If not, write to
  22  * the Free Software Foundation, 51 Franklin Street, Fifth Floor,
  23  * Boston, MA 02110-1301, USA.
  24  */
  25
  26 #include "common.h"
  27 #include "revobject.h"
  28
  29 const float max_load_factor = 0.65;
  30
  31 unsigned int git_revpool_table__hash(const git_oid *id)
  32 {
  33         const unsigned int m = 0x5bd1e995;
  34         const int r = 24;
  35
  36         unsigned int h = 0xA8A3D5;
  37     int i;
  38
  39     for (i = 0; i < GIT_OID_RAWSZ / 4; ++i)
  40     {
  41                 unsigned int k = ((unsigned int *)id->id)[i];
  42
  43                 k *= m;
  44                 k ^= k >> r;
  45                 k *= m;
  46                 h *= m;
  47                 h ^= k;
  48     }
  49
  50         h ^= h >> 13;
  51         h *= m;
  52         h ^= h >> 15;
  53
  54         return h;
  55 }
  56
  57 git_revpool_table *git_revpool_table_create(unsigned int min_size)
  58 {
  59     git_revpool_table *table;
  60     int i;
  61
  62     table = git__malloc(sizeof(table));
  63
  64     if (table == NULL)
  65         return NULL;
  66
  67     // round up size to closest power of 2
  68     min_size--;
  69     min_size |= min_size >> 1;
  70     min_size |= min_size >> 2;
  71     min_size |= min_size >> 4;
  72     min_size |= min_size >> 8;
  73     min_size |= min_size >> 16;
  74
  75     table->size_mask = min_size;
  76     table->count = 0;
  77     table->max_count = (min_size + 1) * max_load_factor;
  78
  79     table->nodes = git__malloc((min_size + 1) * sizeof(git_revpool_node *));
  80
  81     if (table->nodes == NULL)
  82     {
  83         free(table);
  84         return NULL;
  85     }
  86
  87     for (i = 0; i <= min_size; ++i)
  88         table->nodes[i] = NULL;
  89
  90     return table;
  91 }
  92
  93 int git_revpool_table_insert(git_revpool_table *table, git_revpool_object *object)
  94 {
  95     git_revpool_node *node;
  96     unsigned int index, hash;
  97
  98     if (table == NULL)
  99         return -1;
 100
 101     if (table->count + 1 > table->max_count)
 102         git_revpool_table_resize(table);
 103
 104     node = git__malloc(sizeof(git_revpool_node));
 105     if (node == NULL)
 106         return -1;
 107
 108     hash = git_revpool_table__hash(&object->id);
 109     index = (hash & table->size_mask);
 110
 111     node->object = object;
 112     node->hash = hash;
 113     node->next = table->nodes[index];
 114
 115     table->nodes[index] = node;
 116     table->count++;
 117
 118     return 0;
 119 }
 120
 121 git_revpool_object *git_revpool_table_lookup(git_revpool_table *table, const git_oid *id)
 122 {
 123     git_revpool_node *node;
 124     unsigned int index, hash;
 125
 126     if (table == NULL)
 127         return NULL;
 128
 129     hash = git_revpool_table__hash(id);
 130     index = (hash & table->size_mask);
 131     node = table->nodes[index];
 132
 133     while (node != NULL)
 134     {
 135         if (node->hash == hash && git_oid_cmp(id, &node->object->id) == 0)
 136             return node->object;
 137
 138         node = node->next;
 139     }
 140
 141     return NULL;
 142 }
 143
 144 void git_revpool_table_resize(git_revpool_table *table)
 145 {
 146     git_revpool_node **new_nodes;
 147     unsigned int new_size, i;
 148
 149     new_size = (table->size_mask + 1) * 2;
 150
 151     new_nodes = git__malloc(new_size * sizeof(git_revpool_node *));
 152     if (new_nodes == NULL)
 153         return;
 154
 155     memset(new_nodes, 0x0, new_size * sizeof(git_revpool_node *));
 156
 157     for (i = 0; i <= table->size_mask; ++i)
 158     {
 159         git_revpool_node *n;
 160         unsigned int index;
 161
 162         while ((n = table->nodes[i]) != NULL)
 163         {
 164             table->nodes[i] = n->next;
 165             index = n->hash & (new_size - 1);
 166             n->next = new_nodes[index];
 167             new_nodes[index] = n;
 168         }
 169     }
 170
 171     free(table->nodes);
 172     table->nodes = new_nodes;
 173     table->size_mask = (new_size - 1);
 174     table->max_count = new_size * max_load_factor;
 175 }
 176
 177
 178 void git_revpool_table_free(git_revpool_table *table)
 179 {
 180
 181 }