1 /* 2 * Copyright (C) 1996-2012, International Business Machines Corporation and Others. 3 * All rights reserved. 4 */ 5 6 /** 7 * \file 8 * \brief C API: Boyer-Moore StringSearch prototype. 9 * \internal 10 */ 11 12 #ifndef _BMS_H 13 #define _BMS_H 14 15 #include "unicode/utypes.h" 16 17 #if !UCONFIG_NO_COLLATION && !UCONFIG_NO_BREAK_ITERATION 18 19 #include "unicode/ucol.h" 20 21 #ifndef U_HIDE_INTERNAL_API 22 23 /** 24 * A <code>UCD</code> object holds the Collator-specific data needed to 25 * compute the length of the shortest string that can 26 * generate a partcular list of CEs. 27 * 28 * <code>UCD</code> objects are quite expensive to compute. Because 29 * of this, they are cached. When you call <code>ucd_open</code> it 30 * returns a reference counted cached object. When you call <code>ucd_close</code> 31 * the reference count on the object is decremented but the object is not deleted. 32 * 33 * If you do not need to reuse any unreferenced objects in the cache, you can call 34 * <code>ucd_flushCCache</code>. If you no longer need any <code>UCD</code> 35 * objects, you can call <code>ucd_freeCache</code> 36 * 37 * @internal ICU 4.0.1 technology preview 38 */ 39 typedef void UCD; 40 41 /** 42 * Open a <code>UCD</code> object. 43 * 44 * @param coll - the collator 45 * @param status - will be set if any errors occur. 46 * 47 * @return the <code>UCD</code> object. You must call 48 * <code>ucd_close</code> when you are done using the object. 49 * 50 * Note: if on return status is set to an error, the only safe 51 * thing to do with the returned object is to call <code>ucd_close</code>. 52 * 53 * @internal ICU 4.0.1 technology preview 54 */ 55 U_INTERNAL UCD * U_EXPORT2 56 ucd_open(UCollator *coll, UErrorCode *status); 57 58 /** 59 * Release a <code>UCD</code> object. 60 * 61 * @param ucd - the object 62 * 63 * @internal ICU 4.0.1 technology preview 64 */ 65 U_INTERNAL void U_EXPORT2 66 ucd_close(UCD *ucd); 67 68 /** 69 * Get the <code>UCollator</code> object used to create a <code>UCD</code> object. 70 * The <code>UCollator</code> object returned may not be the exact 71 * object that was used to create this object, but it will have the 72 * same behavior. 73 * 74 * @param ucd - the <code>UCD</code> object 75 * 76 * @return the <code>UCollator</code> used to create the given 77 * <code>UCD</code> object. 78 * 79 * @internal ICU 4.0.1 technology preview 80 */ 81 U_INTERNAL UCollator * U_EXPORT2 82 ucd_getCollator(UCD *ucd); 83 84 /** 85 * <code>UCD</code> objects are expensive to compute, and so 86 * may be cached. This routine will free the cached objects and delete 87 * the cache. 88 * 89 * WARNING: Don't call this until you are have called <code>close</code> 90 * for each <code>UCD</code> object that you have used. also, 91 * DO NOT call this if another thread may be calling <code>ucd_flushCache</code> 92 * at the same time. 93 * 94 * @internal ICU 4.0.1 technology preview 95 */ 96 U_INTERNAL void U_EXPORT2 97 ucd_freeCache(); 98 99 /** 100 * <code>UCD</code> objects are expensive to compute, and so 101 * may be cached. This routine will remove any unused <code>UCD</code> 102 * objects from the cache. 103 * 104 * @internal 4.0.1 technology preview 105 */ 106 U_INTERNAL void U_EXPORT2 107 ucd_flushCache(); 108 109 /** 110 * BMS 111 * 112 * This object holds the information needed to do a Collation sensitive Boyer-Moore search. It encapulates 113 * the pattern, the "bad character" and "good suffix" tables, the Collator-based data needed to compute them, 114 * and a reference to the text being searched. 115 * 116 * To do a search, you first need to get a <code>UCD</code> object by calling <code>ucd_open</code>. 117 * Then you construct a <code>BMS</code> object from the <code>UCD</code> object, the pattern 118 * string and the target string. Then you call the <code>search</code> method. Here's a code sample: 119 * 120 * <pre> 121 * void boyerMooreExample(UCollator *collator, UChar *pattern, int32_t patternLen, UChar *target, int32_t targetLength) 122 * { 123 * UErrorCode status = U_ZERO_ERROR; 124 * int32_t offset = 0, start = -1, end = -1; 125 * UCD *ucd = NULL); 126 * BMS *bms = NULL; 127 * 128 * ucd = ucd_open(collator, &status); 129 * if (U_FAILURE(status)) { 130 * // could not create a UCD object 131 * return; 132 * } 133 * 134 * BMS *bms = bms_open(ucd, pattern, patternLength, target, targetlength, &status); 135 * if (U_FAILURE(status)) { 136 * // could not create a BMS object 137 * ucd_close(ucd); 138 * return; 139 * } 140 * 141 * 142 * // Find all matches 143 * while (bms_search(bms, offset, &start, &end)) { 144 * // process the match between start and end 145 * ... 146 * 147 * // advance past the match 148 * offset = end; 149 * } 150 * 151 * // at this point, if offset == 0, there were no matches 152 * if (offset == 0) { 153 * // handle the case of no matches 154 * } 155 * 156 * bms_close(bms); 157 * ucd_close(ucd); 158 * 159 * // UCD objects are cached, so the call to 160 * // ucd_close doesn't delete the object. 161 * // Call this if you don't need the object any more. 162 * ucd_flushCache(); 163 * } 164 * </pre> 165 * 166 * NOTE: This is a technology preview. The final version of this API may not bear any resenblence to this API. 167 * 168 * Knows linitations: 169 * 1) Backwards searching has not been implemented. 170 * 171 * 2) For Han and Hangul characters, this code ignores any Collation tailorings. In general, 172 * this isn't a problem, but in Korean locals, at strength 1, Hangul characters are tailored 173 * to be equal to Han characters with the same pronounciation. Because this code ignroes 174 * tailorings, searching for a Hangul character will not find a Han character and visa-versa. 175 * 176 * 3) In some cases, searching for a pattern that needs to be normalized and ends 177 * in a discontiguous contraction may fail. The only known cases of this are with 178 * the Tibetan script. For example searching for the pattern 179 * "\u0F7F\u0F80\u0F81\u0F82\u0F83\u0F84\u0F85" will fail. (This case is artificial. We've 180 * been unable to find a pratical, real-world example of this failure.) 181 * 182 * NOTE: This is a technology preview. The final version of this API may not bear any resenblence to this API. 183 * 184 * @internal ICU 4.0.1 technology preview 185 */ 186 struct BMS; 187 typedef struct BMS BMS; /**< @see BMS */ 188 189 /** 190 * Construct a <code>MBS</code> object. 191 * 192 * @param ucd - A <code>UCD</code> object holding the Collator-sensitive data 193 * @param pattern - the string for which to search 194 * @param patternLength - the length of the string for which to search 195 * @param target - the string in which to search 196 * @param targetLength - the length of the string in which to search 197 * @param status - will be set if any errors occur. 198 * 199 * @return the <code>BMS</code> object. 200 * 201 * Note: if on return status is set to an error, the only safe 202 * thing to do with the returned object is to call 203 * <code>bms_close</code>. 204 * 205 * @internal ICU 4.0.1 technology preview 206 */ 207 U_INTERNAL BMS * U_EXPORT2 208 bms_open(UCD *ucd, 209 const UChar *pattern, int32_t patternLength, 210 const UChar *target, int32_t targetLength, 211 UErrorCode *status); 212 213 /** 214 * Close a <code>BMS</code> object and release all the 215 * storage associated with it. 216 * 217 * @param bms - the <code>BMS</code> object to close. 218 * @internal ICU 4.0.1 technology preview 219 */ 220 U_INTERNAL void U_EXPORT2 221 bms_close(BMS *bms); 222 223 /** 224 * Test the pattern to see if it generates any CEs. 225 * 226 * @param bms - the <code>BMS</code> object 227 * @return <code>TRUE</code> if the pattern string did not generate any CEs 228 * 229 * @internal ICU 4.0.1 technology preview 230 */ 231 U_INTERNAL UBool U_EXPORT2 232 bms_empty(BMS *bms); 233 234 /** 235 * Get the <code>UCD</code> object used to create 236 * a given <code>BMS</code> object. 237 * 238 * @param bms - the <code>BMS</code> object 239 * 240 * @return - the <code>UCD</code> object used to create 241 * the given <code>BMS</code> object. 242 * 243 * @internal ICU 4.0.1 technology preview 244 */ 245 U_INTERNAL UCD * U_EXPORT2 246 bms_getData(BMS *bms); 247 248 /** 249 * Search for the pattern string in the target string. 250 * 251 * @param bms - the <code>BMS</code> object 252 * @param offset - the offset in the target string at which to begin the search 253 * @param start - will be set to the starting offset of the match, or -1 if there's no match 254 * @param end - will be set to the ending offset of the match, or -1 if there's no match 255 * 256 * @return <code>TRUE</code> if the match succeeds, <code>FALSE</code> otherwise. 257 * 258 * @internal ICU 4.0.1 technology preview 259 */ 260 U_INTERNAL UBool U_EXPORT2 261 bms_search(BMS *bms, int32_t offset, int32_t *start, int32_t *end); 262 263 /** 264 * Set the target string for the match. 265 * 266 * @param bms - the <code>BMS</code> object 267 * @param target - the new target string 268 * @param targetLength - the length of the new target string 269 * @param status - will be set if any errors occur. 270 * 271 * @internal ICU 4.0.1 technology preview 272 */ 273 U_INTERNAL void U_EXPORT2 274 bms_setTargetString(BMS *bms, const UChar *target, int32_t targetLength, UErrorCode *status); 275 276 #endif /* U_HIDE_INTERNAL_API */ 277 278 #endif 279 280 #endif /* _BMS_H */ 281