Hashed bucket linked lists of referenced objects

Store references in and retrive from linked lists based on a hash. More...

Files
file	refobj.c
	Referenced Lockable Objects.

Data Structures
struct	blist_obj
	Entry in a bucket list. More...
struct	bucket_list
	Bucket list, hold hashed objects in buckets. More...
struct	bucket_loop
	Bucket iterator. More...

Typedefs
typedef int32_t(*	blisthash )(const void *, int)
	Callback used to calculate the hash of a structure. More...
typedef void(*	blist_cb )(void *, void *)
	This callback is run on each entry in a list. More...

Functions
void *	create_bucketlist (int bitmask, blisthash hash_function)
int	addtobucket (struct bucket_list *blist, void *data)
	Add a reference to the bucketlist. More...
void	remove_bucket_item (struct bucket_list *blist, void *data)
	Remove and unreference a item from the list. More...
int	bucket_list_cnt (struct bucket_list *blist)
	Return number of items in the list. More...
void *	bucket_list_find_key (struct bucket_list *blist, const void *key)
	Find and return a reference to a item matching supplied key. More...
void	bucketlist_callback (struct bucket_list *blist, blist_cb callback, void *data2)
	Run a callback function on all items in the list. More...
struct bucket_loop *	init_bucket_loop (struct bucket_list *blist)
	Create a bucket list iterator to safely iterate the list. More...
void *	next_bucket_loop (struct bucket_loop *bloop)
	Return a reference to the next item in the list this could be the first item. More...
void	remove_bucket_loop (struct bucket_loop *bloop)
	Safely remove a item from a list while iterating in a loop. More...

Detailed Description

Store references in and retrive from linked lists based on a hash.

Create a hashed bucket list.

See Also

Hashed Bucket Lists

Burtle Bob hash algorythim.

A bucket list is a ref obj the "list" element is a array of "bucket" entries each has a hash the default is to hash the memory when there is no call back

Todo:

Dont hash the memory supply a key perhaps a key array type.

Warning

the hash must be calculated on immutable data.

Note

a bucket list should only contain objects of the same type.

Unreferencing the bucketlist will cause it to be emptied and freed when the count reaches 0.

See Also

blisthash

Parameters

bitmask	Number of buckets to create 2^bitmask.
hash_function	Callback that returns the unique hash for a item this value must not change.

Returns

Reference to a empty bucket list.

Typedef Documentation

typedef void(* blist_cb)(void *, void *)

This callback is run on each entry in a list.

See Also

bucketlist_callback()

Parameters

data	Reference held by the list.
data2	Reference to data supplied when calling bucketlist_callback.

Definition at line 278 of file dtsapp.h.

typedef int32_t(* blisthash)(const void *, int)

Callback used to calculate the hash of a structure.

Parameters

data	Data or key to calculate hash from.
key	Key if set to non zero data supplied is the key not data.

Returns

Hash for the Reference.

Definition at line 271 of file dtsapp.h.

Function Documentation

int addtobucket	(	struct bucket_list *	blist,
		void *	data
	)

Add a reference to the bucketlist.

Create a entry in the list for reference obtained from data.

Parameters

blist	Bucket list to add too.
data	to obtain a reference too and add to the list.

Returns

0 on failure 1 on success.

Definition at line 428 of file refobj.c.

References bucket_list::bucketbits, bucket_list::count, ref_obj::data, blist_obj::data, blist_obj::hash, bucket_list::list, bucket_list::locks, blist_obj::next, objlock(), objref(), objunlock(), objunref(), blist_obj::prev, refobj_offset, and bucket_list::version.

Referenced by add_radserver(), framework_mkthread(), process_config(), rfc6296_map_add(), and xslt_addparam().

                                                              {
    char *ptr = data;
    struct ref_obj *ref;
    struct blist_obj *lhead, *tmp;
    unsigned int hash, bucket;

    if (!objref(blist)) {
        return (0);
    }

    if (!objref(data)) {
        objunref(blist);
        return (0);
    }

    ptr = ptr - refobj_offset;
    ref = (struct ref_obj *)ptr;

    hash = gethash(blist, data, 0);
    bucket = ((hash >> (32 - blist->bucketbits)) & ((1 << blist->bucketbits) - 1));

    pthread_mutex_lock(&blist->locks[bucket]);
    lhead = blist->list[bucket];
    /*no head or non null head*/
    if (!lhead || lhead->prev) {
        if (!(tmp = malloc(sizeof(*tmp)))) {
            pthread_mutex_unlock(&blist->locks[bucket]);
            objunref(data);
            objunref(blist);
            return (0);
        }
        memset(tmp, 0, sizeof(*tmp));
        tmp->hash = hash;
        tmp->data = ref;

        /*there is no head*/
        if (!lhead) {
            blist->list[bucket] = tmp;
            tmp->prev = tmp;
            tmp->next = NULL;
        /*become new head*/
        } else if (hash < lhead->hash) {
            tmp->next = lhead;
            tmp->prev = lhead->prev;
            lhead->prev = tmp;
            blist->list[bucket] = tmp;
        /*new tail*/
        } else if (hash > lhead->prev->hash) {
            tmp->prev = lhead->prev;
            tmp->next = NULL;
            lhead->prev->next = tmp;
            lhead->prev = tmp;
        /*insert entry*/
        } else {
            lhead = blist_gotohash(lhead, hash, blist->bucketbits);
            tmp->next = lhead->next;
            tmp->prev = lhead;

            if (lhead->next) {
                lhead->next->prev = tmp;
            } else {
                blist->list[bucket]->prev = tmp;
            }
            lhead->next = tmp;
        }
    } else {
        /*set NULL head*/
        lhead->data = ref;
        lhead->prev = lhead;
        lhead->next = NULL;
        lhead->hash = hash;
    }

    blist->version[bucket]++;
    pthread_mutex_unlock(&blist->locks[bucket]);

    objlock(blist);
    blist->count++;
    objunlock(blist);
    objunref(blist);

    return (1);
}

int bucket_list_cnt

(

struct bucket_list *

blist

)

Return number of items in the list.

Parameters

blist

Bucket list to get count of.

Returns

Total number of items in all buckets.

Definition at line 552 of file refobj.c.

References bucket_list::count, objlock(), and objunlock().

Referenced by add_radserver(), ldap_doadd(), and ldap_domodify().

                                                      {
    int ret = -1;

    if (blist) {
        objlock(blist);
        ret = blist->count;
        objunlock(blist);
    }
    return (ret);
}

void* bucket_list_find_key	(	struct bucket_list *	blist,
		const void *	key
	)

Find and return a reference to a item matching supplied key.

The key is supplied to the hash callback ad the data value and the key flag set. The hash for the object will be returned by the hash callback to find the item in the lists.

Note

if the hash is not calculated equal to the original value it wont be found.

Parameters

blist	Bucket list to search.
key	Supplied to hash callback to find the item.

Returns

New reference to the found item that needs to be unreferenced or NULL.

Definition at line 572 of file refobj.c.

References bucket_list::bucketbits, ref_obj::data, blist_obj::data, blist_obj::hash, bucket_list::list, bucket_list::locks, objref(), and objunref().

Referenced by get_config_category(), get_config_entry(), get_config_file(), ldap_getattr(), ldap_getentry(), nfqueue_attach(), xml_getattr(), and xml_getnode().

                                                                              {
    struct blist_obj *entry;
    int hash, bucket;

    if (!blist) {
        return (NULL);
    }

    hash = gethash(blist, key, 1);
    bucket = ((hash >> (32 - blist->bucketbits)) & ((1 << blist->bucketbits) - 1));

    pthread_mutex_lock(&blist->locks[bucket]);
    entry = blist_gotohash(blist->list[bucket], hash + 1, blist->bucketbits);
    if (entry && entry->data) {
        objref(entry->data->data);
    } else
        if (!entry) {
            pthread_mutex_unlock(&blist->locks[bucket]);
            return NULL;
        }

    pthread_mutex_unlock(&blist->locks[bucket]);

    if (entry->data && (entry->hash == hash)) {
        return (entry->data->data);
    } else
        if (entry->data) {
            objunref(entry->data->data);
        }

    return NULL;
}

void bucketlist_callback	(	struct bucket_list *	blist,
		blist_cb	callback,
		void *	data2
	)

Run a callback function on all items in the list.

This will iterate safely through all items calling the callback with the item and the optional data supplied.

See Also

blist_cb

Parameters

blist	Bucket list to iterate through.
callback	Callback to call for each iteration.
data2	Data to be set as option to the callback.

Definition at line 613 of file refobj.c.

References init_bucket_loop(), next_bucket_loop(), and objunref().

Referenced by config_cat_callback(), config_entry_callback(), config_file_callback(), and rfc6296_test().

                                                                                           {
    struct bucket_loop *bloop;
    void *data;

    if (!blist || !callback) {
        return;
    }

    bloop = init_bucket_loop(blist);
    while(blist && bloop && (data = next_bucket_loop(bloop))) {
        callback(data, data2);
        objunref(data);
    }
    objunref(bloop);
}

void* create_bucketlist	(	int	bitmask,
		blisthash	hash_function
	)

Definition at line 356 of file refobj.c.

References bucket_list::bucketbits, and objalloc().

Referenced by add_radserver(), ldap_addinit(), ldap_modifyinit(), rfc6296_map_add(), socketserver(), startthreads(), xslt_clearparam(), and xslt_open().

                                                                     {
    struct bucket_list *new;
    short int buckets, cnt;

    buckets = (1 << bitmask);

    /* allocate session bucket list memory size of the struct plus a list lock and version for each bucket*/
    if (!(new = objalloc(sizeof(*new) + (sizeof(void *) + sizeof(pthread_mutex_t) + sizeof(size_t)) * buckets, empty_buckets))) {
        return NULL;
    }

    /*initialise each bucket*/
    new->bucketbits = bitmask;
    new->list = (void *)((char *)new + sizeof(*new));
    for (cnt = 0; cnt < buckets; cnt++) {
        if ((new->list[cnt] = malloc(sizeof(*new->list[cnt])))) {
            memset(new->list[cnt], 0, sizeof(*new->list[cnt]));
        }
    }

    /*next pointer is pointer to locks*/
    new->locks = (void *)&new->list[buckets];
    for (cnt = 0; cnt < buckets; cnt++) {
        pthread_mutex_init(&new->locks[cnt], NULL);
    }

    /*Next up version array*/
    new->version = (void *)&new->locks[buckets];

    new->hash_func = hash_function;

    return (new);
}

struct bucket_loop* init_bucket_loop

(

struct bucket_list *

blist

)

Create a bucket list iterator to safely iterate the list.

Parameters

blist

Bucket list to create iterator for.

Returns

Bucket list iterator that needs to be unreferenced when completed.

Definition at line 640 of file refobj.c.

References bucket_loop::blist, bucket_loop::bucket, blist_obj::hash, bucket_loop::head, bucket_loop::head_hash, bucket_list::list, bucket_list::locks, objalloc(), objref(), bucket_list::version, and bucket_loop::version.

Referenced by bucketlist_callback(), get_category_loop(), ldap_doadd(), and ldap_domodify().

                                                                       {
    struct bucket_loop *bloop = NULL;

    if (blist && (bloop = objalloc(sizeof(*bloop), free_bloop))) {
        objref(blist);
        bloop->blist = blist;
        bloop->bucket = 0;
        pthread_mutex_lock(&blist->locks[bloop->bucket]);
        bloop->head = blist->list[0];
        if (bloop->head) {
            bloop->head_hash = bloop->head->hash;
        };
        bloop->version = blist->version[0];
        pthread_mutex_unlock(&blist->locks[bloop->bucket]);
    }

    return (bloop);
}

void* next_bucket_loop

(

struct bucket_loop *

bloop

)

Return a reference to the next item in the list this could be the first item.

Parameters

bloop

Bucket iterator

Returns

Next available item or NULL when there no items left

Definition at line 662 of file refobj.c.

References bucket_loop::blist, bucket_loop::bucket, bucket_list::bucketbits, bucket_loop::cur, bucket_loop::cur_hash, ref_obj::data, blist_obj::data, blist_obj::hash, bucket_loop::head, bucket_loop::head_hash, bucket_list::list, bucket_list::locks, blist_obj::next, objref(), blist_obj::prev, bucket_list::version, and bucket_loop::version.

Referenced by bucketlist_callback(), get_category_next(), ldap_doadd(), and ldap_domodify().

                                                         {
    struct bucket_list *blist = bloop->blist;
    struct ref_obj *entry = NULL;
    void *data = NULL;

    pthread_mutex_lock(&blist->locks[bloop->bucket]);
    if (bloop->head_hash && (blist->version[bloop->bucket] != bloop->version)) {
        /* bucket has changed unexpectedly i need to ff/rew to hash*/
        bloop->head = blist_gotohash(blist->list[bloop->bucket], bloop->head_hash + 1, blist->bucketbits);
        /*if head has gone find next suitable ignore any added*/
        while (bloop->head && (bloop->head->hash < bloop->head_hash)) {
            bloop->head = bloop->head->next;
        }
    }

    while (!bloop->head || !bloop->head->prev) {
        pthread_mutex_unlock(&blist->locks[bloop->bucket]);
        bloop->bucket++;
        if (bloop->bucket < (1 << blist->bucketbits)) {
            pthread_mutex_lock(&blist->locks[bloop->bucket]);
            bloop->head = blist->list[bloop->bucket];
        } else {
            return NULL;
        }
    }

    if (bloop->head) {
        bloop->cur = bloop->head;
        entry = (bloop->head->data) ? bloop->head->data : NULL;
        data = (entry) ? entry->data : NULL;
        objref(data);
        bloop->head = bloop->head->next;
        bloop->head_hash = (bloop->head) ? bloop->head->hash : 0;
        bloop->cur_hash = (bloop->cur) ? bloop->cur->hash : 0;
    }
    pthread_mutex_unlock(&blist->locks[bloop->bucket]);

    return (data);
}

void remove_bucket_item	(	struct bucket_list *	blist,
		void *	data
	)

Remove and unreference a item from the list.

Note

Dont use this function directly during iteration as it imposes performance penalties.

Parameters

blist

Bucket list to remove item from.

See Also

remove_bucket_loop

Parameters

data	Reference to be removed and unreferenced.

Definition at line 517 of file refobj.c.

References bucket_list::bucketbits, bucket_list::count, ref_obj::data, blist_obj::data, blist_obj::hash, bucket_list::list, bucket_list::locks, blist_obj::next, objlock(), objunlock(), objunref(), blist_obj::prev, and bucket_list::version.

Referenced by ldap_unref_attr(), and ldap_unref_entry().

                                                                      {
    struct blist_obj *entry;
    int hash, bucket;

    hash = gethash(blist, data, 0);
    bucket = ((hash >> (32 - blist->bucketbits)) & ((1 << blist->bucketbits) - 1));

    pthread_mutex_lock(&blist->locks[bucket]);
    entry = blist_gotohash(blist->list[bucket], hash + 1, blist->bucketbits);
    if (entry && entry->hash == hash) {
        if (entry->next && (entry == blist->list[bucket])) {
            entry->next->prev = entry->prev;
            blist->list[bucket] = entry->next;
        } else if (entry->next) {
            entry->next->prev = entry->prev;
            entry->prev->next = entry->next;
        } else if (entry == blist->list[bucket]) {
            blist->list[bucket] = NULL;
        } else {
            entry->prev->next = NULL;
            blist->list[bucket]->prev = entry->prev;
        }
        objunref(entry->data->data);
        free(entry);
        objlock(blist);
        blist->count--;
        blist->version[bucket]++;
        objunlock(blist);
    }
    pthread_mutex_unlock(&blist->locks[bucket]);
}

void remove_bucket_loop

(

struct bucket_loop *

bloop

)

Safely remove a item from a list while iterating in a loop.

While traversing the bucket list its best to use this function to remove a reference and delete it from the list.

Note

Removeing a item from the list without using this function will cause the the version to change and the iterator to rewind and fast forward.

Parameters

bloop

Bucket iterator.

Definition at line 710 of file refobj.c.

References bucket_loop::blist, bucket_loop::bucket, bucket_list::bucketbits, bucket_list::count, bucket_loop::cur, bucket_loop::cur_hash, ref_obj::data, blist_obj::data, blist_obj::hash, bucket_list::list, bucket_list::locks, blist_obj::next, objlock(), objunlock(), objunref(), blist_obj::prev, bucket_list::version, and bucket_loop::version.

                                                          {
    struct bucket_list *blist = bloop->blist;
    int bucket = bloop->bucket;

    pthread_mutex_lock(&blist->locks[bloop->bucket]);
    /*if the bucket has altered need to verify i can remove*/
    if (bloop->cur_hash && (!bloop->cur || (blist->version[bloop->bucket] != bloop->version))) {
        bloop->cur = blist_gotohash(blist->list[bloop->bucket], bloop->cur_hash + 1, blist->bucketbits);
        if (!bloop->cur || (bloop->cur->hash != bloop->cur_hash)) {
            pthread_mutex_unlock(&blist->locks[bucket]);
            return;
        }
    }

    if (!bloop->cur) {
        pthread_mutex_unlock(&blist->locks[bucket]);
        return;
    }

    if (bloop->cur->next && (bloop->cur == blist->list[bucket])) {
        bloop->cur->next->prev = bloop->cur->prev;
        blist->list[bucket] = bloop->cur->next;
    } else if (bloop->cur->next) {
        bloop->cur->next->prev = bloop->cur->prev;
        bloop->cur->prev->next = bloop->cur->next;
    } else if (bloop->cur == blist->list[bucket]) {
        blist->list[bucket] = NULL;
    } else {
        bloop->cur->prev->next = NULL;
        blist->list[bucket]->prev = bloop->cur->prev;
    }

    objunref(bloop->cur->data->data);
    free(bloop->cur);
    bloop->cur_hash = 0;
    bloop->cur = NULL;
    blist->version[bucket]++;
    bloop->version++;
    pthread_mutex_unlock(&blist->locks[bucket]);

    objlock(blist);
    blist->count--;
    objunlock(blist);
}