lib/backend/dbiset.c

   1 #include "system.h"
   2 #include <string.h>
   3 #include <stdlib.h>
   4 #include "dbiset.h"
   5 #include "debug.h"
   6
   7 dbiIndexSet dbiIndexSetNew(unsigned int sizehint)
   8 {
   9     dbiIndexSet set = xcalloc(1, sizeof(*set));
  10     if (sizehint > 0)
  11         dbiIndexSetGrow(set, sizehint);
  12     return set;
  13 }
  14
  15 /*
  16  * Ensure sufficient memory for nrecs of new records in dbiIndexSet.
  17  * Allocate in power of two sizes to avoid memory fragmentation, so
  18  * realloc is not always needed.
  19  */
  20 void dbiIndexSetGrow(dbiIndexSet set, unsigned int nrecs)
  21 {
  22     size_t need = (set->count + nrecs) * sizeof(*(set->recs));
  23     size_t alloced = set->alloced ? set->alloced : 1 << 4;
  24
  25     while (alloced < need)
  26         alloced <<= 1;
  27
  28     if (alloced != set->alloced) {
  29         set->recs = xrealloc(set->recs, alloced);
  30         set->alloced = alloced;
  31     }
  32 }
  33
  34 static int hdrNumCmp(const void * one, const void * two)
  35 {
  36     const struct dbiIndexItem_s *a = one, *b = two;
  37     if (a->hdrNum - b->hdrNum != 0)
  38         return a->hdrNum - b->hdrNum;
  39     return a->tagNum - b->tagNum;
  40 }
  41
  42 void dbiIndexSetSort(dbiIndexSet set)
  43 {
  44     /*
  45      * mergesort is much (~10x with lots of identical basenames) faster
  46      * than pure quicksort, but glibc uses msort_with_tmp() on stack.
  47      */
  48     if (set && set->recs && set->count > 1) {
  49 #if HAVE_MERGESORT
  50         mergesort(set->recs, set->count, sizeof(*set->recs), hdrNumCmp);
  51 #else
  52         qsort(set->recs, set->count, sizeof(*set->recs), hdrNumCmp);
  53 #endif
  54     }
  55 }
  56
  57 void dbiIndexSetUniq(dbiIndexSet set, int sorted)
  58 {
  59     unsigned int from;
  60     unsigned int to = 0;
  61     unsigned int num = set->count;
  62
  63     if (set->count < 2)
  64         return;
  65
  66     if (!sorted)
  67         dbiIndexSetSort(set);
  68
  69     for (from = 0; from < num; from++) {
  70         if (from > 0 && set->recs[from - 1].hdrNum == set->recs[from].hdrNum) {
  71             set->count--;
  72             continue;
  73         }
  74         if (from != to)
  75             set->recs[to] = set->recs[from]; /* structure assignment */
  76         to++;
  77     }
  78 }
  79
  80 int dbiIndexSetAppend(dbiIndexSet set, dbiIndexItem recs,
  81                       unsigned int nrecs, int sortset)
  82 {
  83     if (set == NULL || recs == NULL)
  84         return 1;
  85
  86     if (nrecs) {
  87         dbiIndexSetGrow(set, nrecs);
  88         memcpy(set->recs + set->count, recs, nrecs * sizeof(*(set->recs)));
  89         set->count += nrecs;
  90     }
  91
  92     if (sortset && set->count > 1)
  93         qsort(set->recs, set->count, sizeof(*(set->recs)), hdrNumCmp);
  94
  95     return 0;
  96 }
  97
  98 int dbiIndexSetAppendSet(dbiIndexSet set, dbiIndexSet oset, int sortset)
  99 {
 100     if (oset == NULL)
 101         return 1;
 102     return dbiIndexSetAppend(set, oset->recs, oset->count, sortset);
 103 }
 104
 105 int dbiIndexSetAppendOne(dbiIndexSet set, unsigned int hdrNum,
 106                          unsigned int tagNum, int sortset)
 107 {
 108     if (set == NULL)
 109         return 1;
 110     dbiIndexSetGrow(set, 1);
 111
 112     set->recs[set->count].hdrNum = hdrNum;
 113     set->recs[set->count].tagNum = tagNum;
 114     set->count += 1;
 115
 116     if (sortset && set->count > 1)
 117         qsort(set->recs, set->count, sizeof(*(set->recs)), hdrNumCmp);
 118
 119     return 0;
 120 }
 121
 122 int dbiIndexSetPrune(dbiIndexSet set, dbiIndexItem recs,
 123                      unsigned int nrecs, int sorted)
 124 {
 125     unsigned int from;
 126     unsigned int to = 0;
 127     unsigned int num = set->count;
 128     unsigned int numCopied = 0;
 129     size_t recsize = sizeof(*recs);
 130
 131     if (num == 0 || nrecs == 0)
 132         return 1;
 133
 134     if (nrecs > 1 && !sorted)
 135         qsort(recs, nrecs, recsize, hdrNumCmp);
 136
 137     for (from = 0; from < num; from++) {
 138         if (bsearch(&set->recs[from], recs, nrecs, recsize, hdrNumCmp)) {
 139             set->count--;
 140             continue;
 141         }
 142         if (from != to)
 143             set->recs[to] = set->recs[from]; /* structure assignment */
 144         to++;
 145         numCopied++;
 146     }
 147     return (numCopied == num);
 148 }
 149
 150 int dbiIndexSetPruneSet(dbiIndexSet set, dbiIndexSet oset, int sortset)
 151 {
 152     if (oset == NULL)
 153         return 1;
 154     return dbiIndexSetPrune(set, oset->recs, oset->count, sortset);
 155 }
 156
 157 int dbiIndexSetFilter(dbiIndexSet set, dbiIndexItem recs,
 158                         unsigned int nrecs, int sorted)
 159 {
 160     unsigned int from;
 161     unsigned int to = 0;
 162     unsigned int num = set->count;
 163     unsigned int numCopied = 0;
 164     size_t recsize = sizeof(*recs);
 165
 166     if (num == 0 || nrecs == 0) {
 167         set->count = 0;
 168         return num ? 0 : 1;
 169     }
 170     if (nrecs > 1 && !sorted)
 171         qsort(recs, nrecs, recsize, hdrNumCmp);
 172     for (from = 0; from < num; from++) {
 173         if (!bsearch(&set->recs[from], recs, nrecs, recsize, hdrNumCmp)) {
 174             set->count--;
 175             continue;
 176         }
 177         if (from != to)
 178             set->recs[to] = set->recs[from]; /* structure assignment */
 179         to++;
 180         numCopied++;
 181     }
 182     return (numCopied == num);
 183 }
 184
 185 int dbiIndexSetFilterSet(dbiIndexSet set, dbiIndexSet oset, int sorted)
 186 {
 187     return dbiIndexSetFilter(set, oset->recs, oset->count, sorted);
 188 }
 189
 190 unsigned int dbiIndexSetCount(dbiIndexSet set)
 191 {
 192     return (set != NULL) ? set->count : 0;
 193 }
 194
 195 unsigned int dbiIndexRecordOffset(dbiIndexSet set, unsigned int recno)
 196 {
 197     return set->recs[recno].hdrNum;
 198 }
 199
 200 unsigned int dbiIndexRecordFileNumber(dbiIndexSet set, unsigned int recno)
 201 {
 202     return set->recs[recno].tagNum;
 203 }
 204
 205 dbiIndexSet dbiIndexSetFree(dbiIndexSet set)
 206 {
 207     if (set) {
 208         free(set->recs);
 209         memset(set, 0, sizeof(*set)); /* trash and burn */
 210         free(set);
 211     }
 212     return NULL;
 213 }
 214