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