idxset

#ifndef fooidxsethfoo
#define fooidxsethfoo

/* $Id: idxset.h 90 2004-07-17 14:12:30Z lennart $ */

/***
  This file is part of polypaudio.
 
  polypaudio is free software; you can redistribute it and/or modify
  it under the terms of the GNU General Public License as published
  by the Free Software Foundation; either version 2 of the License,
  or (at your option) any later version.
 
  polypaudio is distributed in the hope that it will be useful, but
  WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  General Public License for more details.
 
  You should have received a copy of the GNU General Public License
  along with polypaudio; if not, write to the Free Software
  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
  USA.
***/

#include <inttypes.h>

#define PA_IDXSET_INVALID ((uint32_t) -1)

unsigned pa_idxset_trivial_hash_func(const void *p);
int pa_idxset_trivial_compare_func(const void *a, const void *b);

unsigned pa_idxset_string_hash_func(const void *p);
int pa_idxset_string_compare_func(const void *a, const void *b);

struct pa_idxset;

struct pa_idxset* pa_idxset_new(unsigned (*hash_func) (const void *p), int (*compare_func) (const void*a, const void*b));
void pa_idxset_free(struct pa_idxset *s, void (*free_func) (void *p, void *userdata), void *userdata);

int pa_idxset_put(struct pa_idxset*s, void *p, uint32_t *index);

void* pa_idxset_get_by_index(struct pa_idxset*s, uint32_t index);
void* pa_idxset_get_by_data(struct pa_idxset*s, void *p, uint32_t *index);

void* pa_idxset_remove_by_index(struct pa_idxset*s, uint32_t index);
void* pa_idxset_remove_by_data(struct pa_idxset*s, void *p, uint32_t *index);

/* This may be used to iterate through all entries. When called with
   an invalid index value it returns the first entry, otherwise the
   next following. The function is best called with *index =
   PA_IDXSET_VALID first. */
void* pa_idxset_rrobin(struct pa_idxset *s, uint32_t *index);

/* Return the oldest entry in the idxset */
void* pa_idxset_first(struct pa_idxset *s, uint32_t *index);
void *pa_idxset_next(struct pa_idxset *s, uint32_t *index);

int pa_idxset_foreach(struct pa_idxset*s, int (*func)(void *p, uint32_t index, int *del, void*userdata), void *userdata);

unsigned pa_idxset_ncontents(struct pa_idxset*s);
int pa_idxset_isempty(struct pa_idxset *s);

#endif

/* $Id: idxset.c 90 2004-07-17 14:12:30Z lennart $ */

/***
  This file is part of polypaudio.
 
  polypaudio is free software; you can redistribute it and/or modify
  it under the terms of the GNU General Public License as published
  by the Free Software Foundation; either version 2 of the License,
  or (at your option) any later version.
 
  polypaudio is distributed in the hope that it will be useful, but
  WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  General Public License for more details.
 
  You should have received a copy of the GNU General Public License
  along with polypaudio; if not, write to the Free Software
  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
  USA.
***/

#ifdef HAVE_CONFIG_H
#include <config.h>
#endif

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <string.h>

#include "idxset.h"

struct idxset_entry {
    void *data;//key
    uint32_t index;//index - start_index是array的索引
    unsigned hash_value;//hash

    struct idxset_entry *hash_prev, *hash_next; //hash_table[hash_value]指向的链表的next和previous
    struct idxset_entry* iterate_prev, *iterate_next; //iterate_list_head指向的链表next和previous
};

struct pa_idxset {
    unsigned (*hash_func) (const void *p);//key的hash函数
    int (*compare_func)(const void *a, const void *b);//key的比较函数
    
    unsigned hash_table_size, n_entries; //hash_table_size的大小，固定1023；n_entries元素个数
    struct idxset_entry **hash_table, **array, *iterate_list_head, *iterate_list_tail;//hash_table数组；array数组；*iterate_list_head, *iterate_list_tail链表
    uint32_t index, start_index, array_size;//index值，每次增加一个数据就会加1；start_index表示数组的起始index；array_size是array数组的大小；元素的索引是index - start_index
};

//
unsigned pa_idxset_string_hash_func(const void *p) {
    unsigned hash = 0;
    const char *c;
    
    for (c = p; *c; c++)
        hash = 31 * hash + *c;
    
    return hash;
}

int pa_idxset_string_compare_func(const void *a, const void *b) {
    return strcmp(a, b);
}

unsigned pa_idxset_trivial_hash_func(const void *p) {
    return (unsigned) p;
}

int pa_idxset_trivial_compare_func(const void *a, const void *b) {
    return a != b;
}

//初始化pa_idxset*
struct pa_idxset* pa_idxset_new(unsigned (*hash_func) (const void *p), int (*compare_func) (const void*a, const void*b)) {
    struct pa_idxset *s;

    s = malloc(sizeof(struct pa_idxset));
    assert(s);
    s->hash_func = hash_func ? hash_func : pa_idxset_trivial_hash_func;
    s->compare_func = compare_func ? compare_func : pa_idxset_trivial_compare_func;
    s->hash_table_size = 1023;
    s->hash_table = malloc(sizeof(struct idxset_entry*)*s->hash_table_size);
    assert(s->hash_table);
    memset(s->hash_table, 0, sizeof(struct idxset_entry*)*s->hash_table_size);
    s->array = NULL;
    s->array_size = 0;
    s->index = 0;
    s->start_index = 0;
    s->n_entries = 0;

    s->iterate_list_head = s->iterate_list_tail = NULL;

    return s;
}

//pa_idxset*
void pa_idxset_free(struct pa_idxset *s, void (*free_func) (void *p, void *userdata), void *userdata) {
    assert(s);

    if (free_func) {
        while (s->iterate_list_head) {
            struct idxset_entry *e = s->iterate_list_head;
            s->iterate_list_head = s->iterate_list_head->iterate_next;

            if (free_func)
                free_func(e->data, userdata);
            free(e);
        }
    }

    free(s->hash_table);
    free(s->array);
    free(s);
}

//由key值(p)在list中遍历查找p对应的idxset_entry*
static struct idxset_entry* hash_scan(struct pa_idxset *s, struct idxset_entry* e, void *p) {
    assert(p);
    //
    assert(s->compare_func);
    for (; e; e = e->hash_next)
        if (s->compare_func(e->data, p) == 0)
            return e;

    return NULL;
}

//0 1 2 3 ... start_index ...start_index + array_size
//index是从0开始的；
//s->array有效范围是start_index到start_index + array_size
//数组的每个元素idxset_entry*
static void extend_array(struct pa_idxset *s, uint32_t index) {
    uint32_t i, j, l;
    struct idxset_entry** n;
    assert(index >= s->start_index);

    if (index < s->start_index + s->array_size)
        return;

    for (i = 0; i < s->array_size; i++)
        if (s->array[i])
            break;

    l = index - s->start_index - i + 100;
    n = malloc(sizeof(struct hash_table_entry*)*l);
    assert(n);
    memset(n, 0, sizeof(struct hash_table_entry*)*l);
    
    for (j = 0; j < s->array_size-i; j++)
        n[j] = s->array[i+j];

    free(s->array);
    
    s->array = n;
    s->array_size = l;
    s->start_index += i;
}

//由index取得元素的指针idxset_entry**
//注意数组索引是index-s->start_index
static struct idxset_entry** array_index(struct pa_idxset*s, uint32_t index) {
    if (index >= s->start_index + s->array_size)
        return NULL;
    
    if (index < s->start_index)
        return NULL;
    
    return s->array + (index - s->start_index);
}

//插入key值为p到s中；返回array的index
int pa_idxset_put(struct pa_idxset*s, void *p, uint32_t *index) {
    unsigned h;
    struct idxset_entry *e, **a;
    assert(s && p);

    assert(s->hash_func);
    //计算hash值
    h = s->hash_func(p) % s->hash_table_size;

    assert(s->hash_table);
    //从s->hash_table[h]链表中，遍历查找p
    if ((e = hash_scan(s, s->hash_table[h], p))) {
        if (index)
            *index = e->index;
        
        return -1;
    }

    e = malloc(sizeof(struct idxset_entry));
    assert(e);

    e->data = p;
    e->index = s->index++;
    e->hash_value = h;

    //插入到s->hash_table[h]指向的双向链表的开头
    /* Insert into hash table */
    e->hash_next = s->hash_table[h];
    e->hash_prev = NULL;
    if (s->hash_table[h])
        s->hash_table[h]->hash_prev = e;
    s->hash_table[h] = e;

    //赋值到s->array指向的数组
    /* Insert into array */
    extend_array(s, e->index);
    a = array_index(s, e->index);
    assert(a && !*a);
    *a = e;

    //赋值到s->iterate_list_head指向的数组的结尾
    /* Insert into linked list */
    e->iterate_next = NULL;
    e->iterate_prev = s->iterate_list_tail;
    if (s->iterate_list_tail) {
        assert(s->iterate_list_head);
        s->iterate_list_tail->iterate_next = e;
    } else {
        assert(!s->iterate_list_head);
        s->iterate_list_head = e;
    }
    s->iterate_list_tail = e;
    
    //元素的个数加1
    s->n_entries++;
    assert(s->n_entries >= 1);
    
    if (index)
        *index = e->index;

    return 0;
}

//数组array中查找idxset_entry *，返回对应的data值
void* pa_idxset_get_by_index(struct pa_idxset*s, uint32_t index) {
    struct idxset_entry **a;
    assert(s);
    
    if (!(a = array_index(s, index)))
        return NULL;

    if (!*a)
        return NULL;

    return (*a)->data;
}

//由p在s->hash_table[h]中查找idxset_entry *，返回index和data值
void* pa_idxset_get_by_data(struct pa_idxset*s, void *p, uint32_t *index) {
    unsigned h;
    struct idxset_entry *e;
    assert(s && p);
    
    assert(s->hash_func);
    h = s->hash_func(p) % s->hash_table_size;

    assert(s->hash_table);
    if (!(e = hash_scan(s, s->hash_table[h], p)))
        return NULL;

    if (index)
        *index = e->index;

    return e->data;
}

//在s中删除idxset_entry *
//在数组array中删除；在链表s->iterate_list_head删除；在s->hash_table[e->hash_value]中删除；个数减1
static void remove_entry(struct pa_idxset *s, struct idxset_entry *e) {
    struct idxset_entry **a;
    assert(s && e);

    /* Remove from array */
    a = array_index(s, e->index);
    assert(a && *a && *a == e);
    *a = NULL;
    
    /* Remove from linked list */
    if (e->iterate_next)
        e->iterate_next->iterate_prev = e->iterate_prev;
    else
        s->iterate_list_tail = e->iterate_prev;
    
    if (e->iterate_prev)
        e->iterate_prev->iterate_next = e->iterate_next;
    else
        s->iterate_list_head = e->iterate_next;

    /* Remove from hash table */
    if (e->hash_next)
        e->hash_next->hash_prev = e->hash_prev;

    if (e->hash_prev)
        e->hash_prev->hash_next = e->hash_next;
    else
        s->hash_table[e->hash_value] = e->hash_next;

    free(e);

    assert(s->n_entries >= 1);
    s->n_entries--;
}

//由index查找到idxset_entry *,然后在s中删除idxset_entry *
void* pa_idxset_remove_by_index(struct pa_idxset*s, uint32_t index) {
    struct idxset_entry **a;
    void *data;
    
    assert(s);

    if (!(a = array_index(s, index)))
        return NULL;

    data = (*a)->data;
    remove_entry(s, *a);
    
    return data; 
}

//由data查找到idxset_entry *,然后在s中删除idxset_entry *
void* pa_idxset_remove_by_data(struct pa_idxset*s, void *data, uint32_t *index) {
    struct idxset_entry *e;
    unsigned h;
    
    assert(s->hash_func);
    h = s->hash_func(data) % s->hash_table_size;

    assert(s->hash_table);
    if (!(e = hash_scan(s, s->hash_table[h], data)))
        return NULL;

    data = e->data;
    if (index)
        *index = e->index;

    remove_entry(s, e);

    return data;
}

//返回index索引的下一个元素（链表）。注意下一个会循环的
void* pa_idxset_rrobin(struct pa_idxset *s, uint32_t *index) {
    struct idxset_entry **a, *e = NULL;
    assert(s && index);

    if ((a = array_index(s, *index)) && *a)
        e = (*a)->iterate_next;

    if (!e)
        e = s->iterate_list_head;

    if (!e)
        return NULL;
    
    *index = e->index;
    return e->data;
}
//获取第一个元素的index,元素的data （或者key）
void* pa_idxset_first(struct pa_idxset *s, uint32_t *index) {
    assert(s);

    if (!s->iterate_list_head)
        return NULL;

    if (index)
        *index = s->iterate_list_head->index;
    return s->iterate_list_head->data;
}

//查找index的下一个元素
void *pa_idxset_next(struct pa_idxset *s, uint32_t *index) {
    struct idxset_entry **a, *e = NULL;
    assert(s && index);

    if ((a = array_index(s, *index)) && *a)
        e = (*a)->iterate_next;
    
    if (e) {
        *index = e->index;
        return e->data;
    } else {
        *index = PA_IDXSET_INVALID;
        return NULL;
    }
}

//遍历iterate_list_head中的每个idxset_entry，遍历过程中会回调func（包含删除元素的功能）
int pa_idxset_foreach(struct pa_idxset*s, int (*func)(void *p, uint32_t index, int *del, void*userdata), void *userdata) {
    struct idxset_entry *e;
    assert(s && func);

    e = s->iterate_list_head;
    while (e) {
        int del = 0, r;
        struct idxset_entry *n = e->iterate_next;

        r = func(e->data, e->index, &del, userdata);

        if (del)
            remove_entry(s, e);

        if (r < 0)
            return r;

        e = n;
    }
    
    return 0;
}

//idxset_entry元素的个数
unsigned pa_idxset_ncontents(struct pa_idxset*s) {
    assert(s);
    return s->n_entries;
}

//s是空的（没有idxset_entry）
int pa_idxset_isempty(struct pa_idxset *s) {
    assert(s);
    return s->n_entries == 0;
}