Andrew's git - gitweb.git/blob

   1/**
   2 * Copyright 2013, GitHub, Inc
   3 * Copyright 2009-2013, Daniel Lemire, Cliff Moon,
   4 *      David McIntosh, Robert Becho, Google Inc. and Veronika Zenz
   5 *
   6 * This program is free software; you can redistribute it and/or
   7 * modify it under the terms of the GNU General Public License
   8 * as published by the Free Software Foundation; either version 2
   9 * of the License, or (at your option) any later version.
  10 *
  11 * This program is distributed in the hope that it will be useful,
  12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 * GNU General Public License for more details.
  15 *
  16 * You should have received a copy of the GNU General Public License
  17 * along with this program; if not, see <http://www.gnu.org/licenses/>.
  18 */
  19#include "git-compat-util.h"
  20#include "ewok.h"
  21#include "ewok_rlw.h"
  22
  23static inline int next_word(struct rlw_iterator *it)
  24{
  25        if (it->pointer >= it->size)
  26                return 0;
  27
  28        it->rlw.word = &it->buffer[it->pointer];
  29        it->pointer += rlw_get_literal_words(it->rlw.word) + 1;
  30
  31        it->rlw.literal_words = rlw_get_literal_words(it->rlw.word);
  32        it->rlw.running_len = rlw_get_running_len(it->rlw.word);
  33        it->rlw.running_bit = rlw_get_run_bit(it->rlw.word);
  34        it->rlw.literal_word_offset = 0;
  35
  36        return 1;
  37}
  38
  39void rlwit_init(struct rlw_iterator *it, struct ewah_bitmap *from_ewah)
  40{
  41        it->buffer = from_ewah->buffer;
  42        it->size = from_ewah->buffer_size;
  43        it->pointer = 0;
  44
  45        next_word(it);
  46
  47        it->literal_word_start = rlwit_literal_words(it) +
  48                it->rlw.literal_word_offset;
  49}
  50
  51void rlwit_discard_first_words(struct rlw_iterator *it, size_t x)
  52{
  53        while (x > 0) {
  54                size_t discard;
  55
  56                if (it->rlw.running_len > x) {
  57                        it->rlw.running_len -= x;
  58                        return;
  59                }
  60
  61                x -= it->rlw.running_len;
  62                it->rlw.running_len = 0;
  63
  64                discard = (x > it->rlw.literal_words) ? it->rlw.literal_words : x;
  65
  66                it->literal_word_start += discard;
  67                it->rlw.literal_words -= discard;
  68                x -= discard;
  69
  70                if (x > 0 || rlwit_word_size(it) == 0) {
  71                        if (!next_word(it))
  72                                break;
  73
  74                        it->literal_word_start =
  75                                rlwit_literal_words(it) + it->rlw.literal_word_offset;
  76                }
  77        }
  78}
  79
  80size_t rlwit_discharge(
  81        struct rlw_iterator *it, struct ewah_bitmap *out, size_t max, int negate)
  82{
  83        size_t index = 0;
  84
  85        while (index < max && rlwit_word_size(it) > 0) {
  86                size_t pd, pl = it->rlw.running_len;
  87
  88                if (index + pl > max)
  89                        pl = max - index;
  90
  91                ewah_add_empty_words(out, it->rlw.running_bit ^ negate, pl);
  92                index += pl;
  93
  94                pd = it->rlw.literal_words;
  95                if (pd + index > max)
  96                        pd = max - index;
  97
  98                ewah_add_dirty_words(out,
  99                        it->buffer + it->literal_word_start, pd, negate);
 100
 101                rlwit_discard_first_words(it, pd + pl);
 102                index += pd;
 103        }
 104
 105        return index;
 106}