1 //========================================================================
2 //
3 // Dict.cc
4 //
5 // Copyright 1996-2003 Glyph & Cog, LLC
6 //
7 //========================================================================
8
9 #include <aconf.h>
10
11 #ifdef USE_GCC_PRAGMAS
12 #pragma implementation
13 #endif
14
15 #include <stddef.h>
16 #include <string.h>
17 #include "gmem.h"
18 #include "Object.h"
19 #include "XRef.h"
20 #include "Dict.h"
21
22 //------------------------------------------------------------------------
23
24 struct DictEntry {
25 char *key;
26 Object val;
27 DictEntry *next;
28 };
29
30 //------------------------------------------------------------------------
31 // Dict
32 //------------------------------------------------------------------------
33
Dict(XRef * xrefA)34 Dict::Dict(XRef *xrefA) {
35 xref = xrefA;
36 size = 8;
37 length = 0;
38 entries = (DictEntry *)gmallocn(size, sizeof(DictEntry));
39 hashTab = (DictEntry **)gmallocn(2 * size - 1, sizeof(DictEntry *));
40 memset(hashTab, 0, (2 * size - 1) * sizeof(DictEntry *));
41 ref = 1;
42 }
43
~Dict()44 Dict::~Dict() {
45 int i;
46
47 for (i = 0; i < length; ++i) {
48 gfree(entries[i].key);
49 entries[i].val.free();
50 }
51 gfree(entries);
52 gfree(hashTab);
53 }
54
add(char * key,Object * val)55 void Dict::add(char *key, Object *val) {
56 DictEntry *e;
57 int h;
58
59 if ((e = find(key))) {
60 e->val.free();
61 e->val = *val;
62 gfree(key);
63 } else {
64 if (length == size) {
65 expand();
66 }
67 h = hash(key);
68 entries[length].key = key;
69 entries[length].val = *val;
70 entries[length].next = hashTab[h];
71 hashTab[h] = &entries[length];
72 ++length;
73 }
74 }
75
expand()76 void Dict::expand() {
77 int h, i;
78
79 size *= 2;
80 entries = (DictEntry *)greallocn(entries, size, sizeof(DictEntry));
81 hashTab = (DictEntry **)greallocn(hashTab, 2 * size - 1,
82 sizeof(DictEntry *));
83 memset(hashTab, 0, (2 * size - 1) * sizeof(DictEntry *));
84 for (i = 0; i < length; ++i) {
85 h = hash(entries[i].key);
86 entries[i].next = hashTab[h];
87 hashTab[h] = &entries[i];
88 }
89 }
90
find(const char * key)91 inline DictEntry *Dict::find(const char *key) {
92 DictEntry *e;
93 int h;
94
95 h = hash(key);
96 for (e = hashTab[h]; e; e = e->next) {
97 if (!strcmp(key, e->key)) {
98 return e;
99 }
100 }
101 return NULL;
102 }
103
hash(const char * key)104 int Dict::hash(const char *key) {
105 const char *p;
106 unsigned int h;
107
108 h = 0;
109 for (p = key; *p; ++p) {
110 h = 17 * h + (int)(*p & 0xff);
111 }
112 return (int)(h % (2 * size - 1));
113 }
114
is(const char * type)115 GBool Dict::is(const char *type) {
116 DictEntry *e;
117
118 return (e = find("Type")) && e->val.isName(type);
119 }
120
lookup(const char * key,Object * obj,int recursion)121 Object *Dict::lookup(const char *key, Object *obj, int recursion) {
122 DictEntry *e;
123
124 return (e = find(key)) ? e->val.fetch(xref, obj, recursion)
125 : obj->initNull();
126 }
127
lookupNF(const char * key,Object * obj)128 Object *Dict::lookupNF(const char *key, Object *obj) {
129 DictEntry *e;
130
131 return (e = find(key)) ? e->val.copy(obj) : obj->initNull();
132 }
133
getKey(int i)134 char *Dict::getKey(int i) {
135 return entries[i].key;
136 }
137
getVal(int i,Object * obj)138 Object *Dict::getVal(int i, Object *obj) {
139 return entries[i].val.fetch(xref, obj);
140 }
141
getValNF(int i,Object * obj)142 Object *Dict::getValNF(int i, Object *obj) {
143 return entries[i].val.copy(obj);
144 }
145