source/libs/poppler/poppler-src/poppler/Dict.cc

   1 //========================================================================
   2 //
   3 // Dict.cc
   4 //
   5 // Copyright 1996-2003 Glyph & Cog, LLC
   6 //
   7 //========================================================================
   8
   9 //========================================================================
  10 //
  11 // Modified under the Poppler project - http://poppler.freedesktop.org
  12 //
  13 // All changes made under the Poppler project to this file are licensed
  14 // under GPL version 2 or later
  15 //
  16 // Copyright (C) 2005 Kristian Høgsberg <krh@redhat.com>
  17 // Copyright (C) 2006 Krzysztof Kowalczyk <kkowalczyk@gmail.com>
  18 // Copyright (C) 2007-2008 Julien Rebetez <julienr@svn.gnome.org>
  19 // Copyright (C) 2008, 2010, 2013, 2014 Albert Astals Cid <aacid@kde.org>
  20 // Copyright (C) 2010 Paweł Wiejacha <pawel.wiejacha@gmail.com>
  21 // Copyright (C) 2012 Fabio D'Urso <fabiodurso@hotmail.it>
  22 // Copyright (C) 2013 Thomas Freitag <Thomas.Freitag@alfa.de>
  23 // Copyright (C) 2014 Scott West <scott.gregory.west@gmail.com>
  24 //
  25 // To see a description of the changes please see the Changelog file that
  26 // came with your tarball or type make ChangeLog if you are building from git
  27 //
  28 //========================================================================
  29
  30 #include <config.h>
  31
  32 #ifdef USE_GCC_PRAGMAS
  33 #pragma implementation
  34 #endif
  35
  36 #include <algorithm>
  37 #include <stddef.h>
  38 #include <string.h>
  39 #include "goo/gmem.h"
  40 #include "Object.h"
  41 #include "XRef.h"
  42 #include "Dict.h"
  43
  44 #if MULTITHREADED
  45 #  define dictLocker()   MutexLocker locker(&mutex)
  46 #else
  47 #  define dictLocker()
  48 #endif
  49 //------------------------------------------------------------------------
  50 // Dict
  51 //------------------------------------------------------------------------
  52
  53 static const int SORT_LENGTH_LOWER_LIMIT = 32;
  54
  55 static inline bool cmpDictEntries(const DictEntry &e1, const DictEntry &e2)
  56 {
  57   return strcmp(e1.key, e2.key) < 0;
  58 }
  59
  60 static int binarySearch(const char *key, DictEntry *entries, int length)
  61 {
  62   int first = 0;
  63   int end = length - 1;
  64   while (first <= end) {
  65     const int middle = (first + end) / 2;
  66     const int res = strcmp(key, entries[middle].key);
  67     if (res == 0) {
  68       return middle;
  69     } else if (res < 0) {
  70       end = middle - 1;
  71     } else {
  72       first = middle + 1;
  73     }
  74   }
  75   return -1;
  76 }
  77
  78 Dict::Dict(XRef *xrefA) {
  79   xref = xrefA;
  80   entries = NULL;
  81   size = length = 0;
  82   ref = 1;
  83   sorted = gFalse;
  84 #if MULTITHREADED
  85   gInitMutex(&mutex);
  86 #endif
  87 }
  88
  89 Dict::Dict(Dict* dictA) {
  90   xref = dictA->xref;
  91   size = length = dictA->length;
  92   ref = 1;
  93 #if MULTITHREADED
  94   gInitMutex(&mutex);
  95 #endif
  96
  97   sorted = dictA->sorted;
  98   entries = (DictEntry *)gmallocn(size, sizeof(DictEntry));
  99   for (int i=0; i<length; i++) {
 100     entries[i].key = copyString(dictA->entries[i].key);
 101     dictA->entries[i].val.copy(&entries[i].val);
 102   }
 103 }
 104
 105 Dict *Dict::copy(XRef *xrefA) {
 106   dictLocker();
 107   Dict *dictA = new Dict(this);
 108   dictA->xref = xrefA;
 109   for (int i=0; i<length; i++) {
 110     if (dictA->entries[i].val.getType() == objDict) {
 111        Dict *dict = dictA->entries[i].val.getDict();
 112        Object obj;
 113        obj.initDict(dict->copy(xrefA));
 114        dictA->entries[i].val.free();
 115        dictA->entries[i].val = obj;
 116        obj.free();
 117     }
 118   }
 119   return dictA;
 120 }
 121
 122 Dict::~Dict() {
 123   int i;
 124
 125   for (i = 0; i < length; ++i) {
 126     gfree(entries[i].key);
 127     entries[i].val.free();
 128   }
 129   gfree(entries);
 130 #if MULTITHREADED
 131   gDestroyMutex(&mutex);
 132 #endif
 133 }
 134
 135 int Dict::incRef() {
 136   dictLocker();
 137   ++ref;
 138   return ref;
 139 }
 140
 141 int Dict::decRef() {
 142   dictLocker();
 143   --ref;
 144   return ref;
 145 }
 146
 147 void Dict::add(char *key, Object *val) {
 148   dictLocker();
 149   if (sorted) {
 150     // We use add on very few occasions so
 151     // virtually this will never be hit
 152     sorted = gFalse;
 153   }
 154
 155   if (length == size) {
 156     if (length == 0) {
 157       size = 8;
 158     } else {
 159       size *= 2;
 160     }
 161     entries = (DictEntry *)greallocn(entries, size, sizeof(DictEntry));
 162   }
 163   entries[length].key = key;
 164   entries[length].val = *val;
 165   ++length;
 166 }
 167
 168 inline DictEntry *Dict::find(const char *key) {
 169   if (!sorted && length >= SORT_LENGTH_LOWER_LIMIT)
 170   {
 171       dictLocker();
 172       sorted = gTrue;
 173       std::sort(entries, entries+length, cmpDictEntries);
 174   }
 175
 176   if (sorted) {
 177     const int pos = binarySearch(key, entries, length);
 178     if (pos != -1) {
 179       return &entries[pos];
 180     }
 181   } else {
 182     int i;
 183
 184     for (i = length - 1; i >=0; --i) {
 185       if (!strcmp(key, entries[i].key))
 186         return &entries[i];
 187     }
 188   }
 189   return NULL;
 190 }
 191
 192 GBool Dict::hasKey(const char *key) {
 193   return find(key) != NULL;
 194 }
 195
 196 void Dict::remove(const char *key) {
 197   dictLocker();
 198   if (sorted) {
 199     const int pos = binarySearch(key, entries, length);
 200     if (pos != -1) {
 201       length -= 1;
 202       gfree(entries[pos].key);
 203       entries[pos].val.free();
 204       if (pos != length) {
 205         memmove(&entries[pos], &entries[pos + 1], (length - pos) * sizeof(DictEntry));
 206       }
 207     }
 208   } else {
 209     int i;
 210     bool found = false;
 211     DictEntry tmp;
 212     if(length == 0) {
 213       return;
 214     }
 215
 216     for(i=0; i<length; i++) {
 217       if (!strcmp(key, entries[i].key)) {
 218         found = true;
 219         break;
 220       }
 221     }
 222     if(!found) {
 223       return;
 224     }
 225     //replace the deleted entry with the last entry
 226     gfree(entries[i].key);
 227     entries[i].val.free();
 228     length -= 1;
 229     tmp = entries[length];
 230     if (i!=length) //don't copy the last entry if it is deleted
 231       entries[i] = tmp;
 232   }
 233 }
 234
 235 void Dict::set(const char *key, Object *val) {
 236   DictEntry *e;
 237   if (val->isNull()) {
 238     remove(key);
 239     return;
 240   }
 241   e = find (key);
 242   if (e) {
 243     dictLocker();
 244     e->val.free();
 245     e->val = *val;
 246   } else {
 247     add (copyString(key), val);
 248   }
 249 }
 250
 251
 252 GBool Dict::is(const char *type) {
 253   DictEntry *e;
 254
 255   return (e = find("Type")) && e->val.isName(type);
 256 }
 257
 258 Object *Dict::lookup(const char *key, Object *obj, int recursion) {
 259   DictEntry *e;
 260
 261   return (e = find(key)) ? e->val.fetch(xref, obj, recursion) : obj->initNull();
 262 }
 263
 264 Object *Dict::lookupNF(const char *key, Object *obj) {
 265   DictEntry *e;
 266
 267   return (e = find(key)) ? e->val.copy(obj) : obj->initNull();
 268 }
 269
 270 GBool Dict::lookupInt(const char *key, const char *alt_key, int *value)
 271 {
 272   Object obj1;
 273   GBool success = gFalse;
 274
 275   lookup ((char *) key, &obj1);
 276   if (obj1.isNull () && alt_key != NULL) {
 277     obj1.free ();
 278     lookup ((char *) alt_key, &obj1);
 279   }
 280   if (obj1.isInt ()) {
 281     *value = obj1.getInt ();
 282     success = gTrue;
 283   }
 284
 285   obj1.free ();
 286
 287   return success;
 288 }
 289
 290 char *Dict::getKey(int i) {
 291   return entries[i].key;
 292 }
 293
 294 Object *Dict::getVal(int i, Object *obj) {
 295   return entries[i].val.fetch(xref, obj);
 296 }
 297
 298 Object *Dict::getValNF(int i, Object *obj) {
 299   return entries[i].val.copy(obj);
 300 }