repo_tree.c

   1 /******************************************************************************
   2  *
   3  * Copyright (C) 2010 David Barr <david.barr@cordelta.com>.
   4  * All rights reserved.
   5  *
   6  * Redistribution and use in source and binary forms, with or without
   7  * modification, are permitted provided that the following conditions
   8  * are met:
   9  * 1. Redistributions of source code must retain the above copyright
  10  *    notice(s), this list of conditions and the following disclaimer
  11  *    unmodified other than the allowable addition of one or more
  12  *    copyright notices.
  13  * 2. Redistributions in binary form must reproduce the above copyright
  14  *    notice(s), this list of conditions and the following disclaimer in
  15  *    the documentation and/or other materials provided with the
  16  *    distribution.
  17  *
  18  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDER(S) ``AS IS'' AND ANY
  19  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  20  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  21  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT HOLDER(S) BE
  22  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  23  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  24  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
  25  * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
  26  * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
  27  * OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
  28  * EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29  *
  30  ******************************************************************************/
  31
  32 #include <string.h>
  33 #include <stdio.h>
  34 #include <stdlib.h>
  35 #include <stdint.h>
  36
  37 #include "repo_tree.h"
  38
  39 static repo_t *repo;
  40
  41 static repo_commit_t*
  42 repo_commit_by_revision_id(uint32_t rev_id) {
  43     return &repo->commits[rev_id];
  44 }
  45
  46 static repo_dir_t*
  47 repo_commit_root_dir(repo_commit_t *commit) {
  48     return &repo->dirs[commit->root_dir_offset];
  49 }
  50
  51 static repo_dirent_t*
  52 repo_first_dirent(repo_dir_t* dir) {
  53     return &repo->dirents[dir->first_offset];
  54 }
  55
  56 static int
  57 repo_dirent_name_cmp(const void *a, const void *b) {
  58     return ((repo_dirent_t*)a)->name_offset
  59             - ((repo_dirent_t*)b)->name_offset;
  60 }
  61
  62 static repo_dirent_t*
  63 repo_dirent_by_name(repo_dir_t* dir, uint32_t name_offset) {
  64     repo_dirent_t key;
  65     if(dir->size == 0) return NULL;
  66     key.name_offset = name_offset;
  67     return bsearch(&key, repo_first_dirent(dir), dir->size,
  68                    sizeof(repo_dirent_t), repo_dirent_name_cmp);
  69 }
  70
  71 static int
  72 repo_dirent_is_dir(repo_dirent_t* dirent) {
  73     return dirent->mode == REPO_MODE_DIR;
  74 }
  75
  76 static int
  77 repo_dirent_is_blob(repo_dirent_t* dirent) {
  78     return dirent->mode == REPO_MODE_BLB || dirent->mode == REPO_MODE_EXE;
  79 }
  80
  81 static int
  82 repo_dirent_is_executable(repo_dirent_t* dirent) {
  83     return dirent->mode == REPO_MODE_EXE;
  84 }
  85
  86 static int
  87 repo_dirent_is_symlink(repo_dirent_t* dirent) {
  88     return dirent->mode == REPO_MODE_LNK;
  89 }
  90
  91 static repo_dir_t*
  92 repo_dir_from_dirent(repo_dirent_t* dirent) {
  93     if(!repo_dirent_is_dir(dirent)) return NULL;
  94     return &repo->dirs[dirent->content_offset];
  95 }
  96
  97 static uint32_t
  98 repo_alloc_dirents(uint32_t count) {
  99     uint32_t offset = repo->num_dirents;
 100     if(repo->num_dirents + count > repo->max_dirents) {
 101         repo->max_dirents *= 2;
 102         repo->dirents =
 103           realloc(repo->dirents, repo->max_dirents * sizeof(repo_dirent_t));
 104     }
 105     repo->num_dirents += count;
 106     return offset;
 107 }
 108
 109 static uint32_t
 110 repo_alloc_dir(uint32_t size) {
 111     uint32_t offset;
 112     if(repo->num_dirs == repo->max_dirs) {
 113         repo->max_dirs *= 2;
 114         repo->dirs =
 115           realloc(repo->dirs, repo->max_dirs * sizeof(repo_dir_t));
 116     }
 117     offset = repo->num_dirs++;
 118     repo->dirs[offset].size = size;
 119     repo->dirs[offset].first_offset = repo_alloc_dirents(size);
 120     return offset;
 121 }
 122
 123 static uint32_t
 124 repo_alloc_commit(uint32_t mark) {
 125     uint32_t offset;
 126     if(repo->num_commits > repo->max_commits) {
 127         repo->max_commits *= 2;
 128         repo->commits =
 129           realloc(repo->commits, repo->max_commits * sizeof(repo_commit_t));
 130     }
 131     offset = repo->num_commits++;
 132     repo->commits[offset].mark = mark;
 133     return offset;
 134 }
 135
 136 void
 137 repo_init(uint32_t max_commits, uint32_t max_dirs, uint32_t max_dirents) {
 138     repo = (repo_t*)malloc(sizeof(repo_t));
 139     repo->commits = malloc(max_commits * sizeof(repo_commit_t));
 140     repo->dirs = malloc(max_dirs * sizeof(repo_dir_t));
 141     repo->dirents = malloc(max_dirents * sizeof(repo_dirent_t));
 142     repo->num_commits = 0;
 143     repo->max_commits = max_commits;
 144     repo->num_dirs = 0;
 145     repo->max_dirs = max_dirs;
 146     repo->num_dirents = 0;
 147     repo->max_dirents = max_dirents;
 148     repo->active_commit = 1;
 149     repo_commit_by_revision_id(0)->root_dir_offset = repo_alloc_dir(0);
 150     repo->num_dirs_saved = repo->num_dirs;
 151 }
 152
 153 static repo_dir_t*
 154 repo_clone_dir(repo_dir_t* orig_dir, uint32_t padding) {
 155     uint32_t orig_offset, new_offset, dirent_offset;
 156     orig_offset = orig_dir - repo->dirs;
 157     if(orig_offset < repo->num_dirs_saved) {
 158         new_offset = repo_alloc_dir(orig_dir->size + padding);
 159         orig_dir = &repo->dirs[orig_offset];
 160         dirent_offset = repo->dirs[new_offset].first_offset;
 161         printf("Creating dir clone.\n");
 162     } else {
 163         if(padding == 0) return orig_dir;
 164         new_offset = orig_offset;
 165         dirent_offset = repo_alloc_dirents(orig_dir->size + padding);
 166         printf("Reallocating dir clone.\n");
 167     }
 168     printf("Copying %d entries.\n", orig_dir->size);
 169     memcpy(&repo->dirents[dirent_offset], repo_first_dirent(orig_dir),
 170         orig_dir->size * sizeof(repo_dirent_t));
 171     if(orig_offset >= repo->num_dirs_saved) {
 172        // bzero(repo_first_dirent(orig_dir),
 173        //     orig_dir->size * sizeof(repo_dirent_t));
 174     }
 175    // bzero(&repo->dirents[dirent_offset + orig_dir->size],
 176    //     padding * sizeof(repo_dirent_t));
 177     repo->dirs[new_offset].size = orig_dir->size + padding;
 178     repo->dirs[new_offset].first_offset = dirent_offset;
 179     return &repo->dirs[new_offset];
 180 }
 181
 182 static void
 183 repo_print_tree(uint32_t depth, repo_dir_t* dir) {
 184     uint32_t i,j;
 185     repo_dirent_t* dirent;
 186     for(j=0;j<dir->size;j++) {
 187         for(i=0;i<depth;i++) putchar(' ');
 188         dirent = &repo_first_dirent(dir)[j];
 189         printf("%d\n",dirent->name_offset);
 190         if(repo_dirent_is_dir(dirent)) {
 191             repo_print_tree(depth+1, repo_dir_from_dirent(dirent));
 192         }
 193     }
 194 }
 195
 196 static repo_dirent_t*
 197 repo_read_dirent(uint32_t revision, char* path) {
 198     char *ctx;
 199     uint32_t name;
 200     repo_dir_t* dir;
 201     repo_dirent_t* dirent;
 202     dir = repo_commit_root_dir(repo_commit_by_revision_id(revision));
 203     if(dir == NULL) {
 204         printf("No root dir.");
 205         return NULL;
 206     }
 207     for(name = pool_tok_r(path, "/", &ctx);
 208         name; name = pool_tok_r(NULL, "/", &ctx)) {
 209         printf("Descending: %d\n", (name));
 210         dirent = repo_dirent_by_name(dir, name);
 211         if(dirent == NULL) {
 212             printf("Not found.");
 213             return NULL;
 214         } else if(repo_dirent_is_dir(dirent)) {
 215             dir = repo_dir_from_dirent(dirent);
 216             printf("dirent: %d, %07o, %d\n",
 217                 dirent->name_offset, dirent->mode, dirent->content_offset);
 218         } else {
 219             printf("Not a directory: %d, %07o, %d\n",
 220                 dirent->name_offset, dirent->mode, dirent->content_offset);
 221             break;
 222         }
 223     }
 224     return name ? NULL : dirent;
 225 }
 226
 227 static void
 228 repo_write_dirent(char* path, uint32_t mode, uint32_t content_offset) {
 229     char *ctx;
 230     uint32_t name, revision, dirent_offset, dir_offset;
 231     repo_dir_t* dir;
 232     repo_dirent_t* dirent = NULL;
 233     revision = repo->active_commit;
 234     dir = repo_commit_root_dir(repo_commit_by_revision_id(revision));
 235     dir = repo_clone_dir(dir, 0);
 236     repo_commit_by_revision_id(revision)->root_dir_offset = dir - repo->dirs;
 237     for(name = pool_tok_r(path, "/", &ctx);
 238         name; name = pool_tok_r(NULL, "/", &ctx)) {
 239         repo_print_tree(0, repo_commit_root_dir(repo_commit_by_revision_id(revision)));
 240         printf("dir[%d]: %d, %d\n", dir - repo->dirs, dir->size, dir->first_offset);
 241         printf("Descending: %d\n", (name));
 242         dirent = repo_dirent_by_name(dir, name);
 243         if(dirent == NULL) {
 244             /* Add entry to dir */
 245             printf("Adding new entry.\n");
 246             dir = repo_clone_dir(dir, 1);
 247             printf("dir[%d]: %d, %d\n", dir - repo->dirs, dir->size, dir->first_offset);
 248             dirent = &repo_first_dirent(dir)[dir->size -1];
 249             dirent->name_offset = name;
 250             dirent->mode = REPO_MODE_BLB;
 251             dirent->content_offset = 0;
 252             printf("dirent[%d]: %d, %06o, %d\n", dirent - repo->dirents,
 253                 dirent->name_offset, dirent->mode, dirent->content_offset);
 254             if(*ctx /* not last name */) {
 255                 /* Allocate new directory */
 256                 printf("Populating entry with new directory.\n");
 257                 dirent->mode = REPO_MODE_DIR;
 258                 dir_offset = repo_alloc_dir(0);
 259                 dirent->content_offset = dir_offset;
 260                 dir = &repo->dirs[dir_offset];
 261                 printf("dirent[%d]: %d, %06o, %d\n", dirent - repo->dirents,
 262                     dirent->name_offset, dirent->mode, dirent->content_offset);
 263             }
 264             qsort(repo_first_dirent(dir), dir->size,
 265                 sizeof(repo_dirent_t), repo_dirent_name_cmp);
 266         } else if(dir = repo_dir_from_dirent(dirent)) {
 267             /* Clone dir for write */
 268             printf("Entering existing directory.\n");
 269             printf("dirent[%d]: %d, %06o, %d\n", dirent - repo->dirents,
 270                 dirent->name_offset, dirent->mode, dirent->content_offset);
 271             dirent_offset = dirent ? dirent - repo->dirents : ~0;
 272             dir = repo_clone_dir(dir, 0);
 273             if(dirent_offset != ~0)
 274                 repo->dirents[dirent_offset].content_offset = dir - repo->dirs;
 275         } else if(*ctx /* not last name */) {
 276             /* Allocate new directory */
 277             printf("Overwriting entry with new directory.\n");
 278             dirent->mode = REPO_MODE_DIR;
 279             dirent_offset = dirent - repo->dirents;
 280             dir_offset = repo_alloc_dir(0);
 281             dirent = &repo->dirents[dirent_offset];
 282             dir = &repo->dirs[dir_offset];
 283             dirent->content_offset = dir_offset;
 284             printf("dirent[%d]: %d, %06o, %d\n", dirent - repo->dirents,
 285                 dirent->name_offset, dirent->mode, dirent->content_offset);
 286         }
 287     }
 288     dirent->mode = mode;
 289     dirent->content_offset = content_offset;
 290     qsort(repo_first_dirent(dir), dir->size,
 291         sizeof(repo_dirent_t), repo_dirent_name_cmp);
 292 }
 293
 294 void
 295 repo_copy(uint32_t revision, char* src, char* dst) {
 296     repo_dirent_t *src_dirent;
 297     printf("C %d:%s %s\n", revision, src, dst);
 298     src_dirent = repo_read_dirent(revision, src);
 299     if(src_dirent == NULL) return;
 300     repo_write_dirent(dst, src_dirent->mode, src_dirent->content_offset);
 301     repo_print_tree(0, repo_commit_root_dir(repo_commit_by_revision_id(repo->active_commit)));
 302 }
 303
 304 void
 305 repo_add(char* path, uint32_t blob_mark) {
 306     printf("A %s %d\n", path, blob_mark);
 307     repo_write_dirent(path, REPO_MODE_BLB, blob_mark);
 308     repo_print_tree(0, repo_commit_root_dir(repo_commit_by_revision_id(repo->active_commit)));
 309 }
 310
 311 void
 312 repo_modify(char* path, uint32_t blob_mark) {
 313     printf("M %s %d\n", path, blob_mark);
 314     repo_write_dirent(path, REPO_MODE_BLB, blob_mark);
 315     repo_print_tree(0, repo_commit_root_dir(repo_commit_by_revision_id(repo->active_commit)));
 316 }
 317
 318 void
 319 repo_delete(char* path) {
 320     printf("D %s\n", path);
 321     repo_print_tree(0, repo_commit_root_dir(repo_commit_by_revision_id(repo->active_commit)));
 322 }
 323
 324 void
 325 repo_commit(uint32_t revision) {
 326     if(revision == 0) return;
 327     printf("R %d\n", revision);
 328     /* compact dirents */
 329     repo->num_dirs_saved = repo->num_dirs;
 330     repo->active_commit++;
 331     repo_alloc_commit(repo->active_commit);
 332     repo_commit_by_revision_id(repo->active_commit)->root_dir_offset =
 333         repo_commit_by_revision_id(repo->active_commit - 1)->root_dir_offset;
 334     printf("Number of dirs: %d\n", repo->num_dirs);
 335     printf("Number of dirents: %d\n", repo->num_dirents);
 336 }