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 static const double max_load_factor = 0.65;
  30
  31 static unsigned int git_revpool_table__hash(const git_oid *id)
  32 {
  33         unsigned int r;
  34         memcpy(&r, id->id, sizeof(r));
  35         return r;
  36 }
  37
  38 git_revpool_table *git_revpool_table_create(unsigned int min_size)
  39 {
  40         git_revpool_table *table;
  41         unsigned int i;
  42
  43         table = git__malloc(sizeof(*table));
  44
  45         if (table == NULL)
  46                 return NULL;
  47
  48         /* round up size to closest power of 2 */
  49         min_size--;
  50         min_size |= min_size >> 1;
  51         min_size |= min_size >> 2;
  52         min_size |= min_size >> 4;
  53         min_size |= min_size >> 8;
  54         min_size |= min_size >> 16;
  55
  56         table->size_mask = min_size;
  57         table->count = 0;
  58         table->max_count = (unsigned int)((min_size + 1) * max_load_factor);
  59
  60         table->nodes = git__malloc((min_size + 1) * sizeof(git_revpool_node *));
  61
  62         if (table->nodes == NULL) {
  63                 free(table);
  64                 return NULL;
  65         }
  66
  67         for (i = 0; i <= min_size; ++i)
  68                 table->nodes[i] = NULL;
  69
  70         return table;
  71 }
  72
  73 int git_revpool_table_insert(git_revpool_table *table, git_revpool_object *object)
  74 {
  75         git_revpool_node *node;
  76         unsigned int index, hash;
  77
  78         if (table == NULL)
  79                 return GIT_ERROR;
  80
  81         if (table->count + 1 > table->max_count)
  82                 git_revpool_table_resize(table);
  83
  84         node = git__malloc(sizeof(git_revpool_node));
  85         if (node == NULL)
  86                 return GIT_ENOMEM;
  87
  88         hash = git_revpool_table__hash(&object->id);
  89         index = (hash & table->size_mask);
  90
  91         node->object = object;
  92         node->hash = hash;
  93         node->next = table->nodes[index];
  94
  95         table->nodes[index] = node;
  96         table->count++;
  97
  98         return 0;
  99 }
 100
 101 git_revpool_object *git_revpool_table_lookup(git_revpool_table *table, const git_oid *id)
 102 {
 103         git_revpool_node *node;
 104         unsigned int index, hash;
 105
 106         if (table == NULL)
 107                 return NULL;
 108
 109         hash = git_revpool_table__hash(id);
 110         index = (hash & table->size_mask);
 111         node = table->nodes[index];
 112
 113         while (node != NULL) {
 114                 if (node->hash == hash && git_oid_cmp(id, &node->object->id) == 0)
 115                         return node->object;
 116
 117                 node = node->next;
 118         }
 119
 120         return NULL;
 121 }
 122
 123 void git_revpool_table_resize(git_revpool_table *table)
 124 {
 125         git_revpool_node **new_nodes;
 126         unsigned int new_size, i;
 127
 128         new_size = (table->size_mask + 1) * 2;
 129
 130         new_nodes = git__malloc(new_size * sizeof(git_revpool_node *));
 131         if (new_nodes == NULL)
 132                 return;
 133
 134         memset(new_nodes, 0x0, new_size * sizeof(git_revpool_node *));
 135
 136         for (i = 0; i <= table->size_mask; ++i) {
 137                 git_revpool_node *n;
 138                 unsigned int index;
 139
 140                 while ((n = table->nodes[i]) != NULL) {
 141                         table->nodes[i] = n->next;
 142                         index = n->hash & (new_size - 1);
 143                         n->next = new_nodes[index];
 144                         new_nodes[index] = n;
 145                 }
 146         }
 147
 148         free(table->nodes);
 149         table->nodes = new_nodes;
 150         table->size_mask = (new_size - 1);
 151         table->max_count = (unsigned int)(new_size * max_load_factor);
 152 }
 153
 154
 155 void git_revpool_table_free(git_revpool_table *table)
 156 {
 157         unsigned int index;
 158
 159         for (index = 0; index <= table->size_mask; ++index) {
 160                 git_revpool_node *node, *next_node;
 161
 162                 node = table->nodes[index];
 163                 while (node != NULL) {
 164                         next_node = node->next;
 165                         free(node);
 166                         node = next_node;
 167                 }
 168         }
 169
 170         free(table->nodes);
 171         free(table);
 172 }
 173
 174 void git_revpool_tableit_init(git_revpool_table *table, git_revpool_tableit *it)
 175 {
 176         memset(it, 0x0, sizeof(git_revpool_tableit));
 177
 178         it->nodes = table->nodes;
 179         it->current_node = NULL;
 180         it->current_pos = 0;
 181         it->size = table->size_mask + 1;
 182 }
 183
 184 git_revpool_object *git_revpool_tableit_next(git_revpool_tableit *it)
 185 {
 186         git_revpool_node *next = NULL;
 187
 188         while (it->current_node == NULL) {
 189                 if (it->current_pos >= it->size)
 190                         return NULL;
 191
 192                 it->current_node = it->nodes[it->current_pos++];
 193         }
 194
 195         next = it->current_node;
 196         it->current_node = it->current_node->next;
 197
 198         return next->object;
 199 }