btrfs: Attempt to fix GCC2 build.
[haiku.git] / src / kits / interface / textview_support / WidthBuffer.cpp
blobe4e8ce3d57ac65f6a172e9ae2c61c6d7adf3e2a5
1 /*
2 * Copyright 2003-2008, Haiku, Inc.
3 * Distributed under the terms of the MIT License.
5 * Authors:
6 * Stefano Ceccherini (stefano.ceccherini@gmail.com)
7 */
9 //! Caches string widths in a hash table, to avoid a trip to the app server.
12 #include "utf8_functions.h"
13 #include "TextGapBuffer.h"
14 #include "WidthBuffer.h"
16 #include <Autolock.h>
17 #include <Debug.h>
18 #include <Font.h>
19 #include <Locker.h>
21 #include <stdio.h>
24 //! NetPositive binary compatibility support
25 class _BWidthBuffer_;
28 namespace BPrivate {
31 const static uint32 kTableCount = 128;
32 const static uint32 kInvalidCode = 0xFFFFFFFF;
33 WidthBuffer* gWidthBuffer = NULL;
34 // initialized in InterfaceDefs.cpp
37 struct hashed_escapement {
38 uint32 code;
39 float escapement;
41 hashed_escapement()
43 code = kInvalidCode;
44 escapement = 0;
49 /*! \brief Convert a UTF8 char to a code, which will be used
50 to uniquely identify the character in the hash table.
51 \param text A pointer to the character to examine.
52 \param charLen the length of the character to examine.
53 \return The code for the given character,
55 static inline uint32
56 CharToCode(const char* text, const int32 charLen)
58 uint32 value = 0;
59 int32 shiftVal = 24;
60 for (int32 c = 0; c < charLen; c++) {
61 value |= ((unsigned char)text[c] << shiftVal);
62 shiftVal -= 8;
64 return value;
68 /*! \brief Initializes the object.
70 WidthBuffer::WidthBuffer()
72 _BTextViewSupportBuffer_<_width_table_>(1, 0),
73 fLock("width buffer")
78 /*! \brief Frees the allocated resources.
80 WidthBuffer::~WidthBuffer()
82 for (int32 x = 0; x < fItemCount; x++)
83 delete[] (hashed_escapement*)fBuffer[x].widths;
87 /*! \brief Returns how much room is required to draw a string in the font.
88 \param inText The string to be examined.
89 \param fromOffset The offset in the string where to begin the examination.
90 \param lenght The amount of bytes to be examined.
91 \param inStyle The font.
92 \return The space (in pixels) required to draw the given string.
94 float
95 WidthBuffer::StringWidth(const char* inText, int32 fromOffset, int32 length,
96 const BFont* inStyle)
98 if (inText == NULL || length <= 0)
99 return 0;
101 BAutolock _(fLock);
103 int32 index = 0;
104 if (!FindTable(inStyle, &index))
105 index = InsertTable(inStyle);
107 char* text = NULL;
108 int32 numChars = 0;
109 int32 textLen = 0;
111 const char* sourceText = inText + fromOffset;
112 const float fontSize = inStyle->Size();
113 float stringWidth = 0;
115 for (int32 charLen = 0; length > 0;
116 sourceText += charLen, length -= charLen) {
117 charLen = UTF8NextCharLen(sourceText, length);
119 // End of string, bail out
120 if (charLen <= 0)
121 break;
123 // Some magic, to uniquely identify this character
124 const uint32 value = CharToCode(sourceText, charLen);
126 float escapement;
127 if (GetEscapement(value, index, &escapement)) {
128 // Well, we've got a match for this character
129 stringWidth += escapement;
130 } else {
131 // Store this character into an array, which we'll
132 // pass to HashEscapements() later
133 int32 offset = textLen;
134 textLen += charLen;
135 numChars++;
136 char* newText = (char*)realloc(text, textLen + 1);
137 if (newText == NULL) {
138 free(text);
139 return 0;
142 text = newText;
143 memcpy(&text[offset], sourceText, charLen);
147 if (text != NULL) {
148 // We've found some characters which aren't yet in the hash table.
149 // Get their width via HashEscapements()
150 text[textLen] = 0;
151 stringWidth += HashEscapements(text, numChars, textLen, index, inStyle);
152 free(text);
155 return stringWidth * fontSize;
159 /*! \brief Returns how much room is required to draw a string in the font.
160 \param inBuffer The TextGapBuffer to be examined.
161 \param fromOffset The offset in the TextGapBuffer where to begin the
162 examination.
163 \param lenght The amount of bytes to be examined.
164 \param inStyle The font.
165 \return The space (in pixels) required to draw the given string.
167 float
168 WidthBuffer::StringWidth(TextGapBuffer &inBuffer, int32 fromOffset,
169 int32 length, const BFont* inStyle)
171 const char* text = inBuffer.GetString(fromOffset, &length);
172 return StringWidth(text, 0, length, inStyle);
176 /*! \brief Searches for the table for the given font.
177 \param inStyle The font to search for.
178 \param outIndex a pointer to an int32, where the function will store
179 the index of the table, if found, or -1, if not.
180 \return \c true if the function founds the table,
181 \c false if not.
183 bool
184 WidthBuffer::FindTable(const BFont* inStyle, int32* outIndex)
186 if (inStyle == NULL)
187 return false;
189 int32 tableIndex = -1;
191 for (int32 i = 0; i < fItemCount; i++) {
192 if (*inStyle == fBuffer[i].font) {
193 tableIndex = i;
194 break;
197 if (outIndex != NULL)
198 *outIndex = tableIndex;
200 return tableIndex != -1;
204 /*! \brief Creates and insert an empty table for the given font.
205 \param font The font to create the table for.
206 \return The index of the newly created table.
208 int32
209 WidthBuffer::InsertTable(const BFont* font)
211 _width_table_ table;
213 table.font = *font;
214 table.hashCount = 0;
215 table.tableCount = kTableCount;
216 table.widths = new hashed_escapement[kTableCount];
218 uint32 position = fItemCount;
219 InsertItemsAt(1, position, &table);
221 return position;
225 /*! \brief Gets the escapement for the given character.
226 \param value An integer which uniquely identifies a character.
227 \param index The index of the table to search.
228 \param escapement A pointer to a float, where the function will
229 store the escapement.
230 \return \c true if the function could find the escapement
231 for the given character, \c false if not.
233 bool
234 WidthBuffer::GetEscapement(uint32 value, int32 index, float* escapement)
236 const _width_table_ &table = fBuffer[index];
237 const hashed_escapement* widths
238 = static_cast<hashed_escapement*>(table.widths);
239 uint32 hashed = Hash(value) & (table.tableCount - 1);
241 uint32 found;
242 while ((found = widths[hashed].code) != kInvalidCode) {
243 if (found == value)
244 break;
246 if (++hashed >= (uint32)table.tableCount)
247 hashed = 0;
250 if (found == kInvalidCode)
251 return false;
253 if (escapement != NULL)
254 *escapement = widths[hashed].escapement;
256 return true;
260 uint32
261 WidthBuffer::Hash(uint32 val)
263 uint32 shifted = val >> 24;
264 uint32 result = (val >> 15) + (shifted * 3);
266 result ^= (val >> 6) - (shifted * 22);
267 result ^= (val << 3);
269 return result;
273 /*! \brief Gets the escapements for the given string, and put them into
274 the hash table.
275 \param inText The string to be examined.
276 \param numChars The amount of characters contained in the string.
277 \param textLen the amount of bytes contained in the string.
278 \param tableIndex the index of the table where the escapements
279 should be put.
280 \param inStyle the font.
281 \return The width of the supplied string (which should be multiplied by
282 the size of the font).
284 float
285 WidthBuffer::HashEscapements(const char* inText, int32 numChars, int32 textLen,
286 int32 tableIndex, const BFont* inStyle)
288 ASSERT(inText != NULL);
289 ASSERT(numChars > 0);
290 ASSERT(textLen > 0);
292 float* escapements = new float[numChars];
293 inStyle->GetEscapements(inText, numChars, escapements);
295 _width_table_ &table = fBuffer[tableIndex];
296 hashed_escapement* widths = static_cast<hashed_escapement*>(table.widths);
298 int32 charCount = 0;
299 char* text = (char*)inText;
300 const char* textEnd = inText + textLen;
301 // Insert the escapements into the hash table
302 do {
303 // Using this variant is safe as the handed in string is guaranteed to
304 // be 0 terminated.
305 const int32 charLen = UTF8NextCharLen(text);
306 if (charLen == 0)
307 break;
309 const uint32 value = CharToCode(text, charLen);
311 uint32 hashed = Hash(value) & (table.tableCount - 1);
312 uint32 found;
313 while ((found = widths[hashed].code) != kInvalidCode) {
314 if (found == value)
315 break;
316 if (++hashed >= (uint32)table.tableCount)
317 hashed = 0;
320 if (found == kInvalidCode) {
321 // The value is not in the table. Add it.
322 widths[hashed].code = value;
323 widths[hashed].escapement = escapements[charCount];
324 table.hashCount++;
326 // We always keep some free space in the hash table:
327 // we double the current size when hashCount is 2/3 of
328 // the total size.
329 if (table.tableCount * 2 / 3 <= table.hashCount) {
330 const int32 newSize = table.tableCount * 2;
332 // Create and initialize a new hash table
333 hashed_escapement* newWidths = new hashed_escapement[newSize];
335 // Rehash the values, and put them into the new table
336 for (uint32 oldPos = 0; oldPos < (uint32)table.tableCount;
337 oldPos++) {
338 if (widths[oldPos].code != kInvalidCode) {
339 uint32 newPos
340 = Hash(widths[oldPos].code) & (newSize - 1);
341 while (newWidths[newPos].code != kInvalidCode) {
342 if (++newPos >= (uint32)newSize)
343 newPos = 0;
345 newWidths[newPos] = widths[oldPos];
349 // Delete the old table, and put the new pointer into the
350 // _width_table_
351 delete[] widths;
352 table.tableCount = newSize;
353 table.widths = widths = newWidths;
356 charCount++;
357 text += charLen;
358 } while (text < textEnd);
360 // Calculate the width of the string
361 float width = 0;
362 for (int32 x = 0; x < numChars; x++)
363 width += escapements[x];
365 delete[] escapements;
367 return width;
370 } // namespace BPrivate
373 #if __GNUC__ < 3
374 //! NetPositive binary compatibility support
376 _BWidthBuffer_::_BWidthBuffer_()
380 _BWidthBuffer_::~_BWidthBuffer_()
384 _BWidthBuffer_* gCompatibilityWidthBuffer = NULL;
386 extern "C"
387 float
388 StringWidth__14_BWidthBuffer_PCcllPC5BFont(_BWidthBuffer_* widthBuffer,
389 const char* inText, int32 fromOffset, int32 length, const BFont* inStyle)
391 return BPrivate::gWidthBuffer->StringWidth(inText, fromOffset, length,
392 inStyle);
395 #endif // __GNUC__ < 3