Lines Matching full:dict
2 * dict.c: dictionary of reusable strings, just used to avoid allocation
36 * Note2: the fast function used for a small dict won't protect very
56 #include <libxml/dict.h>
70 #define xmlDictComputeKey(dict, name, len) \ argument
71 (((dict)->size == MIN_DICT_SIZE) ? \
72 xmlDictComputeFastKey(name, len, (dict)->seed) : \
73 xmlDictComputeBigKey(name, len, (dict)->seed))
75 #define xmlDictComputeQKey(dict, prefix, plen, name, len) \ argument
77 (xmlDictComputeKey(dict, name, len)) : \
78 (((dict)->size == MIN_DICT_SIZE) ? \
79 xmlDictComputeFastQKey(prefix, plen, name, len, (dict)->seed) : \
80 xmlDictComputeBigQKey(prefix, plen, name, len, (dict)->seed)))
83 #define xmlDictComputeKey(dict, name, len) \ argument
84 xmlDictComputeFastKey(name, len, (dict)->seed)
85 #define xmlDictComputeQKey(dict, prefix, plen, name, len) \ argument
86 xmlDictComputeFastQKey(prefix, plen, name, len, (dict)->seed)
118 struct _xmlDictEntry *dict; member
232 * @dict: the dictionary
241 xmlDictAddString(xmlDictPtr dict, const xmlChar *name, unsigned int namelen) { in xmlDictAddString() argument
250 pool = dict->strings; in xmlDictAddString()
262 if ((dict->limit > 0) && (limit > dict->limit)) { in xmlDictAddString()
277 pool->next = dict->strings; in xmlDictAddString()
278 dict->strings = pool; in xmlDictAddString()
294 * @dict: the dictionary
305 xmlDictAddQString(xmlDictPtr dict, const xmlChar *prefix, unsigned int plen, in xmlDictAddQString() argument
313 if (prefix == NULL) return(xmlDictAddString(dict, name, namelen)); in xmlDictAddQString()
318 pool = dict->strings; in xmlDictAddQString()
330 if ((dict->limit > 0) && (limit > dict->limit)) { in xmlDictAddQString()
345 pool->next = dict->strings; in xmlDictAddQString()
346 dict->strings = pool; in xmlDictAddQString()
569 xmlDictPtr dict; in xmlDictCreate() local
579 dict = xmlMalloc(sizeof(xmlDict)); in xmlDictCreate()
580 if (dict) { in xmlDictCreate()
581 dict->ref_counter = 1; in xmlDictCreate()
582 dict->limit = 0; in xmlDictCreate()
584 dict->size = MIN_DICT_SIZE; in xmlDictCreate()
585 dict->nbElems = 0; in xmlDictCreate()
586 dict->dict = xmlMalloc(MIN_DICT_SIZE * sizeof(xmlDictEntry)); in xmlDictCreate()
587 dict->strings = NULL; in xmlDictCreate()
588 dict->subdict = NULL; in xmlDictCreate()
589 if (dict->dict) { in xmlDictCreate()
590 memset(dict->dict, 0, MIN_DICT_SIZE * sizeof(xmlDictEntry)); in xmlDictCreate()
592 dict->seed = __xmlRandom(); in xmlDictCreate()
594 dict->seed = 0; in xmlDictCreate()
596 return(dict); in xmlDictCreate()
598 xmlFree(dict); in xmlDictCreate()
616 xmlDictPtr dict = xmlDictCreate(); in xmlDictCreateSub() local
618 if ((dict != NULL) && (sub != NULL)) { in xmlDictCreateSub()
622 dict->seed = sub->seed; in xmlDictCreateSub()
623 dict->subdict = sub; in xmlDictCreateSub()
624 xmlDictReference(dict->subdict); in xmlDictCreateSub()
626 return(dict); in xmlDictCreateSub()
631 * @dict: the dictionary
638 xmlDictReference(xmlDictPtr dict) { in xmlDictReference() argument
643 if (dict == NULL) return -1; in xmlDictReference()
645 dict->ref_counter++; in xmlDictReference()
652 * @dict: the dictionary
660 xmlDictGrow(xmlDictPtr dict, size_t size) { in xmlDictGrow() argument
671 if (dict == NULL) in xmlDictGrow()
682 oldsize = dict->size; in xmlDictGrow()
683 olddict = dict->dict; in xmlDictGrow()
689 dict->dict = xmlMalloc(size * sizeof(xmlDictEntry)); in xmlDictGrow()
690 if (dict->dict == NULL) { in xmlDictGrow()
691 dict->dict = olddict; in xmlDictGrow()
694 memset(dict->dict, 0, size * sizeof(xmlDictEntry)); in xmlDictGrow()
695 dict->size = size; in xmlDictGrow()
699 the main dict. It is nicer to run through the array twice, first in xmlDictGrow()
710 okey = xmlDictComputeKey(dict, olddict[i].name, olddict[i].len); in xmlDictGrow()
711 key = okey % dict->size; in xmlDictGrow()
713 if (dict->dict[key].valid == 0) { in xmlDictGrow()
714 memcpy(&(dict->dict[key]), &(olddict[i]), sizeof(xmlDictEntry)); in xmlDictGrow()
715 dict->dict[key].next = NULL; in xmlDictGrow()
716 dict->dict[key].okey = okey; in xmlDictGrow()
725 entry->next = dict->dict[key].next; in xmlDictGrow()
727 dict->dict[key].next = entry; in xmlDictGrow()
747 * put back the entry in the new dict in xmlDictGrow()
753 okey = xmlDictComputeKey(dict, iter->name, iter->len); in xmlDictGrow()
754 key = okey % dict->size; in xmlDictGrow()
755 if (dict->dict[key].valid == 0) { in xmlDictGrow()
756 memcpy(&(dict->dict[key]), iter, sizeof(xmlDictEntry)); in xmlDictGrow()
757 dict->dict[key].next = NULL; in xmlDictGrow()
758 dict->dict[key].valid = 1; in xmlDictGrow()
759 dict->dict[key].okey = okey; in xmlDictGrow()
762 iter->next = dict->dict[key].next; in xmlDictGrow()
764 dict->dict[key].next = iter; in xmlDictGrow()
787 * @dict: the dictionary
789 * Free the hash @dict and its contents. The userdata is
793 xmlDictFree(xmlDictPtr dict) { in xmlDictFree() argument
800 if (dict == NULL) in xmlDictFree()
809 dict->ref_counter--; in xmlDictFree()
810 if (dict->ref_counter > 0) { in xmlDictFree()
817 if (dict->subdict != NULL) { in xmlDictFree()
818 xmlDictFree(dict->subdict); in xmlDictFree()
821 if (dict->dict) { in xmlDictFree()
822 for(i = 0; ((i < dict->size) && (dict->nbElems > 0)); i++) { in xmlDictFree()
823 iter = &(dict->dict[i]); in xmlDictFree()
831 dict->nbElems--; in xmlDictFree()
836 xmlFree(dict->dict); in xmlDictFree()
838 pool = dict->strings; in xmlDictFree()
844 xmlFree(dict); in xmlDictFree()
849 * @dict: the dictionary
853 * Add the @name to the dictionary @dict if not present.
858 xmlDictLookup(xmlDictPtr dict, const xmlChar *name, int len) { in xmlDictLookup() argument
865 if ((dict == NULL) || (name == NULL)) in xmlDictLookup()
873 if (((dict->limit > 0) && (l >= dict->limit)) || in xmlDictLookup()
880 okey = xmlDictComputeKey(dict, name, l); in xmlDictLookup()
881 key = okey % dict->size; in xmlDictLookup()
882 if (dict->dict[key].valid == 0) { in xmlDictLookup()
885 for (insert = &(dict->dict[key]); insert->next != NULL; in xmlDictLookup()
911 if (dict->subdict) { in xmlDictLookup()
915 if (((dict->size == MIN_DICT_SIZE) && in xmlDictLookup()
916 (dict->subdict->size != MIN_DICT_SIZE)) || in xmlDictLookup()
917 ((dict->size != MIN_DICT_SIZE) && in xmlDictLookup()
918 (dict->subdict->size == MIN_DICT_SIZE))) in xmlDictLookup()
919 skey = xmlDictComputeKey(dict->subdict, name, l); in xmlDictLookup()
923 key = skey % dict->subdict->size; in xmlDictLookup()
924 if (dict->subdict->dict[key].valid != 0) { in xmlDictLookup()
927 for (tmp = &(dict->subdict->dict[key]); tmp->next != NULL; in xmlDictLookup()
952 key = okey % dict->size; in xmlDictLookup()
955 ret = xmlDictAddString(dict, name, l); in xmlDictLookup()
959 entry = &(dict->dict[key]); in xmlDictLookup()
975 dict->nbElems++; in xmlDictLookup()
978 (dict->size <= ((MAX_DICT_HASH / 2) / MAX_HASH_LEN))) { in xmlDictLookup()
979 if (xmlDictGrow(dict, MAX_HASH_LEN * 2 * dict->size) != 0) in xmlDictLookup()
989 * @dict: the dictionary
993 * Check if the @name exists in the dictionary @dict.
998 xmlDictExists(xmlDictPtr dict, const xmlChar *name, int len) { in xmlDictExists() argument
1003 if ((dict == NULL) || (name == NULL)) in xmlDictExists()
1010 if (((dict->limit > 0) && (l >= dict->limit)) || in xmlDictExists()
1017 okey = xmlDictComputeKey(dict, name, l); in xmlDictExists()
1018 key = okey % dict->size; in xmlDictExists()
1019 if (dict->dict[key].valid == 0) { in xmlDictExists()
1022 for (insert = &(dict->dict[key]); insert->next != NULL; in xmlDictExists()
1048 if (dict->subdict) { in xmlDictExists()
1052 if (((dict->size == MIN_DICT_SIZE) && in xmlDictExists()
1053 (dict->subdict->size != MIN_DICT_SIZE)) || in xmlDictExists()
1054 ((dict->size != MIN_DICT_SIZE) && in xmlDictExists()
1055 (dict->subdict->size == MIN_DICT_SIZE))) in xmlDictExists()
1056 skey = xmlDictComputeKey(dict->subdict, name, l); in xmlDictExists()
1060 key = skey % dict->subdict->size; in xmlDictExists()
1061 if (dict->subdict->dict[key].valid != 0) { in xmlDictExists()
1064 for (tmp = &(dict->subdict->dict[key]); tmp->next != NULL; in xmlDictExists()
1097 * @dict: the dictionary
1101 * Add the QName @prefix:@name to the hash @dict if not present.
1106 xmlDictQLookup(xmlDictPtr dict, const xmlChar *prefix, const xmlChar *name) { in xmlDictQLookup() argument
1113 if ((dict == NULL) || (name == NULL)) in xmlDictQLookup()
1116 return(xmlDictLookup(dict, name, -1)); in xmlDictQLookup()
1125 okey = xmlDictComputeQKey(dict, prefix, plen, name, l); in xmlDictQLookup()
1126 key = okey % dict->size; in xmlDictQLookup()
1127 if (dict->dict[key].valid == 0) { in xmlDictQLookup()
1130 for (insert = &(dict->dict[key]); insert->next != NULL; in xmlDictQLookup()
1142 if (dict->subdict) { in xmlDictQLookup()
1146 if (((dict->size == MIN_DICT_SIZE) && in xmlDictQLookup()
1147 (dict->subdict->size != MIN_DICT_SIZE)) || in xmlDictQLookup()
1148 ((dict->size != MIN_DICT_SIZE) && in xmlDictQLookup()
1149 (dict->subdict->size == MIN_DICT_SIZE))) in xmlDictQLookup()
1150 skey = xmlDictComputeQKey(dict->subdict, prefix, plen, name, l); in xmlDictQLookup()
1154 key = skey % dict->subdict->size; in xmlDictQLookup()
1155 if (dict->subdict->dict[key].valid != 0) { in xmlDictQLookup()
1157 for (tmp = &(dict->subdict->dict[key]); tmp->next != NULL; in xmlDictQLookup()
1168 key = okey % dict->size; in xmlDictQLookup()
1171 ret = xmlDictAddQString(dict, prefix, plen, name, l); in xmlDictQLookup()
1175 entry = &(dict->dict[key]); in xmlDictQLookup()
1190 dict->nbElems++; in xmlDictQLookup()
1193 (dict->size <= ((MAX_DICT_HASH / 2) / MAX_HASH_LEN))) in xmlDictQLookup()
1194 xmlDictGrow(dict, MAX_HASH_LEN * 2 * dict->size); in xmlDictQLookup()
1202 * @dict: the dictionary
1211 xmlDictOwns(xmlDictPtr dict, const xmlChar *str) { in xmlDictOwns() argument
1214 if ((dict == NULL) || (str == NULL)) in xmlDictOwns()
1216 pool = dict->strings; in xmlDictOwns()
1222 if (dict->subdict) in xmlDictOwns()
1223 return(xmlDictOwns(dict->subdict, str)); in xmlDictOwns()
1229 * @dict: the dictionary
1231 * Query the number of elements installed in the hash @dict.
1237 xmlDictSize(xmlDictPtr dict) { in xmlDictSize() argument
1238 if (dict == NULL) in xmlDictSize()
1240 if (dict->subdict) in xmlDictSize()
1241 return(dict->nbElems + dict->subdict->nbElems); in xmlDictSize()
1242 return(dict->nbElems); in xmlDictSize()
1247 * @dict: the dictionary
1256 xmlDictSetLimit(xmlDictPtr dict, size_t limit) { in xmlDictSetLimit() argument
1259 if (dict == NULL) in xmlDictSetLimit()
1261 ret = dict->limit; in xmlDictSetLimit()
1262 dict->limit = limit; in xmlDictSetLimit()
1268 * @dict: the dictionary
1276 xmlDictGetUsage(xmlDictPtr dict) { in xmlDictGetUsage() argument
1280 if (dict == NULL) in xmlDictGetUsage()
1282 pool = dict->strings; in xmlDictGetUsage()