view src/protocols/jabber/hashtable.c @ 6322:dd2be7cd66df

[gaim-migrate @ 6821] This is: -Alphabetize the translation things in ChangeLog -Spell Brian Tarricone's name correctly (I hope...) -A fix for a crash when renaming a group containing a chat, thanks to javabsp. Me gusta this change. -Make the rename group dialog use gaim_request_input(). The old dialog may be a bit prettier, but this one uses the request code, which means less work for UIs, which rocks. -Change the TRUE and FALSE defines in aim.h to be more compatible with c++. Thanks to Zack Rusin for this change. -Declare aim.h as a C file when it is used in a c++ program. This should let libfaim be used in C++ programs such as kopete. Thanks again to Zack Rusin. -Rename aimutil_itemidx() to aimutil_itemindex(). "idx" is not a standard abbreviation, and code is written once and read many times--it should be easily readable. -Not an automatic laundry folding machine. So I'm going to do that. (Fold my laundry) (Not automatically) (yet) committer: Tailor Script <[e-mail]>

/*
The contents of this file are subject to the Mozilla Public License
Version 1.1 (the "License"); you may not use this file except in
csompliance with the License. You may obtain a copy of the License at
http://www.mozilla.org/MPL/

Software distributed under the License is distributed on an "AS IS"
basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See the
License for the specific language governing rights and limitations
under the License.

The Original Code is expat.

The Initial Developer of the Original Code is James Clark.
Portions created by James Clark are Copyright (C) 1998, 1999
James Clark. All Rights Reserved.

Contributor(s):

*/

#include "xmldef.h"

#ifdef XML_UNICODE_WCHAR_T
#ifndef XML_UNICODE
#define XML_UNICODE
#endif
#endif

#include "hashtable.h"

#define INIT_SIZE 64

static
int keyeq(KEY s1, KEY s2)
{
    for (; *s1 == *s2; s1++, s2++)
        if (*s1 == 0)
            return 1;
    return 0;
}

static
unsigned long hash(KEY s)
{
    unsigned long h = 0;
    while (*s)
        h = (h << 5) + h + (unsigned char)*s++;
    return h;
}

NAMED *lookup(HASH_TABLE *table, KEY name, size_t createSize)
{
    size_t i;
    if (table->size == 0) {
        if (!createSize)
            return 0;
        table->v = calloc(INIT_SIZE, sizeof(NAMED *));
        if (!table->v)
            return 0;
        table->size = INIT_SIZE;
        table->usedLim = INIT_SIZE / 2;
        i = hash(name) & (table->size - 1);
    }
    else {
        unsigned long h = hash(name);
        for (i = h & (table->size - 1);
                table->v[i];
                i == 0 ? i = table->size - 1 : --i) {
            if (keyeq(name, table->v[i]->name))
                return table->v[i];
        }
        if (!createSize)
            return 0;
        if (table->used == table->usedLim) {
            /* check for overflow */
            size_t newSize = table->size * 2;
            NAMED **newV = calloc(newSize, sizeof(NAMED *));
            if (!newV)
                return 0;
            for (i = 0; i < table->size; i++)
                if (table->v[i]) {
                    size_t j;
                    for (j = hash(table->v[i]->name) & (newSize - 1);
                            newV[j];
                            j == 0 ? j = newSize - 1 : --j)
                        ;
                    newV[j] = table->v[i];
                }
            free(table->v);
            table->v = newV;
            table->size = newSize;
            table->usedLim = newSize/2;
            for (i = h & (table->size - 1);
                    table->v[i];
                    i == 0 ? i = table->size - 1 : --i)
                ;
        }
    }
    table->v[i] = calloc(1, createSize);
    if (!table->v[i])
        return 0;
    table->v[i]->name = name;
    (table->used)++;
    return table->v[i];
}

void hashTableDestroy(HASH_TABLE *table)
{
    size_t i;
    for (i = 0; i < table->size; i++) {
        NAMED *p = table->v[i];
        if (p)
            free(p);
    }
    free(table->v);
}

void hashTableInit(HASH_TABLE *p)
{
    p->size = 0;
    p->usedLim = 0;
    p->used = 0;
    p->v = 0;
}

void hashTableIterInit(HASH_TABLE_ITER *iter, const HASH_TABLE *table)
{
    iter->p = table->v;
    iter->end = iter->p + table->size;
}

NAMED *hashTableIterNext(HASH_TABLE_ITER *iter)
{
    while (iter->p != iter->end) {
        NAMED *tem = *(iter->p)++;
        if (tem)
            return tem;
    }
    return 0;
}