2  * dict.c: dictionary of reusable strings, just used to avoid allocation
33 #include <libxml/dict.h>
47 #define xmlDictComputeKey(dict, name, len)			\
48     (((dict)->size == MIN_DICT_SIZE) ?				\
52 #define xmlDictComputeQKey(dict, prefix, plen, name, len)	\
54       (xmlDictComputeKey(dict, name, len)) :			\
55       (((dict)->size == MIN_DICT_SIZE) ?			\
60 #define xmlDictComputeKey(dict, name, len)			\
62 #define xmlDictComputeQKey(dict, prefix, plen, name, len)	\
95     struct _xmlDictEntry *dict;
149  * @dict: the dictionnary
158 xmlDictAddString(xmlDictPtr dict, const xmlChar *name, int namelen) {
166     pool = dict->strings;
188 	pool->next = dict->strings;
189 	dict->strings = pool;
205  * @dict: the dictionnary
216 xmlDictAddQString(xmlDictPtr dict, const xmlChar *prefix, int plen,
223     if (prefix == NULL) return(xmlDictAddString(dict, name, namelen));
228     pool = dict->strings;
250 	pool->next = dict->strings;
251 	dict->strings = pool;
442     xmlDictPtr dict;
452     dict = xmlMalloc(sizeof(xmlDict));
453     if (dict) {
454         dict->ref_counter = 1;
456         dict->size = MIN_DICT_SIZE;
457 	dict->nbElems = 0;
458         dict->dict = xmlMalloc(MIN_DICT_SIZE * sizeof(xmlDictEntry));
459 	dict->strings = NULL;
460 	dict->subdict = NULL;
461         if (dict->dict) {
462 	    memset(dict->dict, 0, MIN_DICT_SIZE * sizeof(xmlDictEntry));
463 	    return(dict);
465         xmlFree(dict);
483     xmlDictPtr dict = xmlDictCreate();
485     if ((dict != NULL) && (sub != NULL)) {
489         dict->subdict = sub;
490 	xmlDictReference(dict->subdict);
492     return(dict);
497  * @dict: the dictionnary
504 xmlDictReference(xmlDictPtr dict) {
509     if (dict == NULL) return -1;
511     dict->ref_counter++;
518  * @dict: the dictionnary
526 xmlDictGrow(xmlDictPtr dict, int size) {
537     if (dict == NULL)
548     oldsize = dict->size;
549     olddict = dict->dict;
555     dict->dict = xmlMalloc(size * sizeof(xmlDictEntry));
556     if (dict->dict == NULL) {
557 	dict->dict = olddict;
560     memset(dict->dict, 0, size * sizeof(xmlDictEntry));
561     dict->size = size;
565 	the main dict. It is nicer to run through the array twice, first
576 	    okey = xmlDictComputeKey(dict, olddict[i].name, olddict[i].len);
577 	key = okey % dict->size;
579 	if (dict->dict[key].valid == 0) {
580 	    memcpy(&(dict->dict[key]), &(olddict[i]), sizeof(xmlDictEntry));
581 	    dict->dict[key].next = NULL;
582 	    dict->dict[key].okey = okey;
591 		entry->next = dict->dict[key].next;
593 		dict->dict[key].next = entry;
613 	     * put back the entry in the new dict
619 		okey = xmlDictComputeKey(dict, iter->name, iter->len);
620 	    key = okey % dict->size;
621 	    if (dict->dict[key].valid == 0) {
622 		memcpy(&(dict->dict[key]), iter, sizeof(xmlDictEntry));
623 		dict->dict[key].next = NULL;
624 		dict->dict[key].valid = 1;
625 		dict->dict[key].okey = okey;
628 		iter->next = dict->dict[key].next;
630 		dict->dict[key].next = iter;
653  * @dict: the dictionnary
655  * Free the hash @dict and its contents. The userdata is
659 xmlDictFree(xmlDictPtr dict) {
666     if (dict == NULL)
675     dict->ref_counter--;
676     if (dict->ref_counter > 0) {
683     if (dict->subdict != NULL) {
684         xmlDictFree(dict->subdict);
687     if (dict->dict) {
688 	for(i = 0; ((i < dict->size) && (dict->nbElems > 0)); i++) {
689 	    iter = &(dict->dict[i]);
697 		dict->nbElems--;
703 	xmlFree(dict->dict);
705     pool = dict->strings;
711     xmlFree(dict);
716  * @dict: the dictionnary
720  * Add the @name to the dictionnary @dict if not present.
725 xmlDictLookup(xmlDictPtr dict, const xmlChar *name, int len) {
731     if ((dict == NULL) || (name == NULL))
740     okey = xmlDictComputeKey(dict, name, len);
741     key = okey % dict->size;
742     if (dict->dict[key].valid == 0) {
745 	for (insert = &(dict->dict[key]); insert->next != NULL;
771     if (dict->subdict) {
775         if (((dict->size == MIN_DICT_SIZE) &&
776 	     (dict->subdict->size != MIN_DICT_SIZE)) ||
777             ((dict->size != MIN_DICT_SIZE) &&
778 	     (dict->subdict->size == MIN_DICT_SIZE)))
779 	    skey = xmlDictComputeKey(dict->subdict, name, len);
783 	key = skey % dict->subdict->size;
784 	if (dict->subdict->dict[key].valid != 0) {
787 	    for (tmp = &(dict->subdict->dict[key]); tmp->next != NULL;
812 	key = okey % dict->size;
815     ret = xmlDictAddString(dict, name, len);
819 	entry = &(dict->dict[key]);
835     dict->nbElems++;
838         (dict->size <= ((MAX_DICT_HASH / 2) / MAX_HASH_LEN))) {
839 	if (xmlDictGrow(dict, MAX_HASH_LEN * 2 * dict->size) != 0)
849  * @dict: the dictionnary
853  * Check if the @name exists in the dictionnary @dict.
858 xmlDictExists(xmlDictPtr dict, const xmlChar *name, int len) {
862     if ((dict == NULL) || (name == NULL))
871     okey = xmlDictComputeKey(dict, name, len);
872     key = okey % dict->size;
873     if (dict->dict[key].valid == 0) {
876 	for (insert = &(dict->dict[key]); insert->next != NULL;
902     if (dict->subdict) {
906         if (((dict->size == MIN_DICT_SIZE) &&
907 	     (dict->subdict->size != MIN_DICT_SIZE)) ||
908             ((dict->size != MIN_DICT_SIZE) &&
909 	     (dict->subdict->size == MIN_DICT_SIZE)))
910 	    skey = xmlDictComputeKey(dict->subdict, name, len);
914 	key = skey % dict->subdict->size;
915 	if (dict->subdict->dict[key].valid != 0) {
918 	    for (tmp = &(dict->subdict->dict[key]); tmp->next != NULL;
951  * @dict: the dictionnary
955  * Add the QName @prefix:@name to the hash @dict if not present.
960 xmlDictQLookup(xmlDictPtr dict, const xmlChar *prefix, const xmlChar *name) {
967     if ((dict == NULL) || (name == NULL))
970         return(xmlDictLookup(dict, name, -1));
979     okey = xmlDictComputeQKey(dict, prefix, plen, name, l);
980     key = okey % dict->size;
981     if (dict->dict[key].valid == 0) {
984 	for (insert = &(dict->dict[key]); insert->next != NULL;
996     if (dict->subdict) {
1000         if (((dict->size == MIN_DICT_SIZE) &&
1001 	     (dict->subdict->size != MIN_DICT_SIZE)) ||
1002             ((dict->size != MIN_DICT_SIZE) &&
1003 	     (dict->subdict->size == MIN_DICT_SIZE)))
1004 	    skey = xmlDictComputeQKey(dict->subdict, prefix, plen, name, l);
1008 	key = skey % dict->subdict->size;
1009 	if (dict->subdict->dict[key].valid != 0) {
1011 	    for (tmp = &(dict->subdict->dict[key]); tmp->next != NULL;
1022 	key = okey % dict->size;
1025     ret = xmlDictAddQString(dict, prefix, plen, name, l);
1029 	entry = &(dict->dict[key]);
1044     dict->nbElems++;
1047         (dict->size <= ((MAX_DICT_HASH / 2) / MAX_HASH_LEN)))
1048 	xmlDictGrow(dict, MAX_HASH_LEN * 2 * dict->size);
1056  * @dict: the dictionnary
1065 xmlDictOwns(xmlDictPtr dict, const xmlChar *str) {
1068     if ((dict == NULL) || (str == NULL))
1070     pool = dict->strings;
1076     if (dict->subdict)
1077         return(xmlDictOwns(dict->subdict, str));
1083  * @dict: the dictionnary
1085  * Query the number of elements installed in the hash @dict.
1091 xmlDictSize(xmlDictPtr dict) {
1092     if (dict == NULL)
1094     if (dict->subdict)
1095         return(dict->nbElems + dict->subdict->nbElems);
1096     return(dict->nbElems);

Indexes created Wed Jul 18 07:22:35 CEST 2012